Случайности не случайны, или как компьютеры генерируют случайные числа

Регистр сдвига

Регистр сдвига получается тогда, когда мы соединяем вместе n D-триггеров. Входы тактирования соединяются вместе и являются входом тактирования регистра сдвига. Выход каждого триггера является выходом сдвигового регистра и, одновременно, подключается к входу следующего триггера. Вход нулевого триггера является входом регистра сдвига.

Что же получилось в итоге? Представим, что на тактовый вход постоянно подается сигнал, и триггеры периодически срабатывают, т. е. «переносят» сигнал со своего входа на выход. Допустим, во время первого такта мы подали единичку на вход регистра, а в остальное время там ноль. Как будут меняться сигналы на нашем регистре с течением времени? С первым тактом единица с входа нулевого триггера попадет на его выход (он также является и входом первого). По второму такту единичка попадает на выход первого и т. д. Таким образом, по мере поступления тактовых импульсов, наша единица будет смещаться вправо каждый такт, т. е. сдвигаться. Дойдя до последнего триггера, единица из него выйдет, но никуда уже не попадет. И так происходит со всеми данными, поступающими на вход регистра сдвига: с каждым тактом они сдвигаются вправо.

Такт№

Вход

Выход 0

Выход 1

Выход 2

Выход 3

1

1

1

2

1

3

1

4

1

5

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG)?—?это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа?—?т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ?—?это проблема. Если говорить про другие задачи, то эти свойства?—?могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство?—?воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Проблемы с rand()

// init seed
int seed = ...;
srand(seed);

uint64 bad_rand() {
	return rand();
}
uint64 unix_rand(uint64 *state) {
	srand(*state);
	uint32 r1 = rand();
	srand(r1);
	uint32 r2 = rand();
	*state = r2;
	uint64 result = ((uint64)r2 << 32) | r1;
	return result;
}
  1. Зависимость старшей половины бит от младшей. В качестве seed для старших 32 бит выступают младшие, т.е. части числа связаны функциональной зависимостью, которую можно обнаружить, т.е. показать неслучайность.
  2. RAND_MAX на моей системе был равен 231-1. Т.е. на самом деле rand() выдаёт только 31 бит! А в конечном числе меняются только 62 бита, 31-й и 63-й же всегда нули.
  3. Самый серьёзный недостаток — неопределённость функции rand(). Вообще нельзя сказать, будет ли RAND_MAX одинаковым на всех системах. Нельзя даже утверждать, что реализация rand() будет одинаковой на Windows и Linux, не будет зависеть от разрядности ОС, версии Libc, компилятора или чего-то ещё. Одна и та же симуляция, запущенная на разных хозяйских системах, будет выдавать разные результаты. Кошмар для отладки!

Прочие соображения

Изменение распределения

Равномерные распределения

Большинство генераторов случайных чисел изначально работают с целыми числами или отдельными битами, поэтому требуется дополнительный шаг для достижения «канонического» равномерного распределения между 0 и 1. Реализация не так тривиальна, как деление целого числа на его максимально возможное значение. Конкретно:

  1. Целое число, используемое в преобразовании, должно обеспечивать достаточное количество бит для намеченной точности.
  2. Сама природа математики с плавающей запятой означает, что чем ближе число к нулю, тем выше точность. Эта дополнительная точность обычно не используется из-за большого количества требуемых битов.
  3. Ошибка округления при делении может исказить результат. В худшем случае предположительно исключенная граница может быть проведена с учетом ожиданий, основанных на математике с действительными числами.

Основной алгоритм, используемый OpenJDK, Rust и Numpy, описан в предложении для C ++ STL. Он не использует дополнительную точность и страдает смещением только в последнем бите из-за округления до четности. При переносе этого «канонического» равномерного распределения в другой диапазон возникают другие числовые проблемы. Предлагаемый метод для языка программирования Swift утверждает, что везде используется полная точность.

Равномерно распределенные целые числа обычно используются в таких алгоритмах, как тасование Фишера-Йейтса . Опять же, простая реализация может вызвать смещение результата по модулю, поэтому необходимо использовать более сложные алгоритмы. Метод, который почти никогда не выполняет деление, был описан в 2018 году Дэниелом Лемиром, при этом текущее состояние дел — вдохновленный арифметическим кодированием «оптимальный алгоритм» 2021 года Стивеном Кэноном из Apple Inc.

Большинство ГСЧ от 0 до 1 включают 0, но исключают 1, в то время как другие включают или исключают оба.

Другие дистрибутивы

Учитывая источник однородных случайных чисел, существует несколько методов для создания нового случайного источника, который соответствует функции плотности вероятности . Один метод, называемый методом инверсии , включает интегрирование до области, большей или равной случайному числу (которое должно быть сгенерировано между 0 и 1 для правильного распределения). Второй метод, называемый методом принятия-отклонения , включает выбор значений x и y и проверку того, больше ли функция x значения y. Если это так, значение x принимается. В противном случае значение x отклоняется, и алгоритм пытается снова.

В качестве примера для отбраковочной выборки, чтобы сгенерировать пару статистически независимых стандартных нормально распределенных случайных чисел ( x , y ), можно сначала сгенерировать полярные координаты ( r , θ ), где r 2 ~ χ 2 2 и θ ~ UNIFORM ( 0,2π) (см. Преобразование Бокса – Маллера ).

Отбеливание

Выходы нескольких независимых ГСЧ могут быть объединены (например, с помощью операции побитового исключающего ИЛИ ), чтобы обеспечить объединенный ГСЧ, по крайней мере, такой же хороший, как и лучший используемый ГСЧ. Это называется .

Вычислительные и аппаратные генераторы случайных чисел иногда объединяют, чтобы отразить преимущества обоих типов. Вычислительные генераторы случайных чисел обычно могут генерировать псевдослучайные числа намного быстрее, чем физические генераторы, в то время как физические генераторы могут генерировать «истинную случайность».

ГПСЧ в криптографии[]

Шаблон:Main
Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (Шаблон:Lang-en), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Циклическое шифрование

В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.

ANSI X9.17

ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:

  1. Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
  2. Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
  3. Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
  • DTi — значение даты и времени на начало i-ой стадии генерации.
  • Vi — начальное значение для i-ой стадии генерации.
  • Ri — псевдослучайное число, созданное на i-ой стадии генерации.
  • K1, K2 — ключи, используемые на каждой стадии.

Тогда:

Ri = EDEK1,K2  Vi ]
Vi+1 = EDEK1,K2  Ri]

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Алгоритмы консенсуса

PVRB для организации сетевого консенсуса играет огромное значение. Транзакции в блокчейнах защищены электронной подписью, поэтому “атака на транзакцию” это всегда включение/исключение транзакции в блок (или в несколько блоков). А главной задачей алгоритма консенсуса является договориться о порядке этих транзакций и о порядке блоков, которые включают в себя эти транзакции. Также, необходимым свойством для реальных блокчейнов является финальность — возможность сети договориться о том, что цепочка до финализированного блока является окончательной, и никогда не будет исключена из за появления нового форка. Обычно, чтобы договориться о том, что блок является валидным и, главное, финальным, требуется собрать подписи с большинства производителей блоков (далее BP — block-producers), что требует как минимум доставить цепочку блоков на все BP, а подписи распространить между всеми BP. При росте числа BP, количество необходимых сообщений в сети экспоненциально растет, поэтому, алгоритмы консенсуса, требующие финальность, используемые например в pBFT-консенсусе Hyperledger, не работают с нужной скоростью, начиная уже с нескольких десятков BP, требуя огромного числа соединений.

Если в сети имеется неоспоримый и честный PVRB, то, даже в самом простом приближении, можно на основании него выбирать одного из block producers и назначать его “лидером” в течение одного раунда протокола. Если у нас есть block producer-ов, из которых являются честными, не цензурируют транзакции и не строят форки цепочки с целью проведения атаки “double spend”, то использование равномерно распределенного неоспоримого PVRB позволит выбирать честного лидера с вероятностью . Если каждому лидеру назначить собственный временной интервал, в течение которого он может произвести блок и провалидировать цепочку, и эти интервалы равны по времени, то цепочка блоков честных BP будет длиннее, чем цепочка, сформированная зловредными BP, и алгоритм консенсуса, полагающийся на длину цепочки, попросту отбросит “плохую”. Этот принцип выделения равных квантов времени каждому BP впервые был применен в Graphene (предшественнике EOS), и позволяет большинство блоков закрывать одной подписью, что очень сильно снижает сетевую нагрузку и позволяет этому консенсусу работать крайне быстро и устойчиво. Тем не менее, сети EOS сейчас приходится использовать специальные блоки (Last Irreversible Block), которые подтверждаются подписями 2/3 BP. Эти блоки служат для обеспечения финальности (невозможности появления форка цепочки, начинающегося раньше последнего Last Irreversible Block).

Также, в реальных имплементациях, схема протокола сложнее — голосования за предлагаемые блоки проводятся в несколько этапов, чтобы поддерживать работу сети в случае пропуска блоков и проблем с сетью, но даже с учетом этого, алгоритмы консенсуса с использованием PVRB требуют существенно меньше сообщений между BP, что позволяет сделать их быстрее, чем традиционный PВFT, или различные его модификации.

Наиболее яркий представитель таких алгоритмов: Ouroboros от команды Cardano, который, как объявлено, обладает математически доказуемой стойкостью к наличию сговора среди BP.

В Ouroboros PVRB используется для определения так называемого “BP schedule” — расписания, согласно которому каждому BP назначается свой временной слот для публикации блока. Большим преимуществом использования PVRB является полное “равноправие” BP (согласно размерам их балансов). Честность PVRB гарантирует, что зловредные BP не могут контролировать расписание временных слотов, и, поэтому не могут манипулировать цепочкой, заранее подготавливая и анализируя форки цепочки, а для выбора форка достаточно полагаться просто на длину цепочки, не оперируя хитрыми способами вычисления “полезности” BP и “веса” его блоков.

Вообще во всех случаях, когда в децентрализованной сети нужно выбрать случайного участника, почти всегда лучшим выбором будет PVRB, а не детерминистический вариант на основе, к примеру, хеша блока. Без PVRB возможность повлиять на выбор участника ведет к появлению атак, в которых атакующий может, выбирая из нескольких вариантов будущего, выбирать следующего коррумпированного участника или сразу нескольких, чтобы обеспечить более весомую долю в принятии решения. Использование PVRB дискредитирует эти типы атак.

Криптографические ГПСЧ

PRNG, подходящий для криптографических приложений, называется криптографически безопасным PRNG (CSPRNG). Требование для CSPRNG состоит в том, чтобы злоумышленник, не знающий начального числа, имел лишь незначительное преимущество в различении выходной последовательности генератора от случайной последовательности. Другими словами, в то время как PRNG требуется только для прохождения определенных статистических тестов, CSPRNG должен пройти все статистические тесты, которые ограничены полиномиальным временем в размере начального числа. Хотя доказательство этого свойства выходит за рамки текущего состояния теории вычислительной сложности , убедительные доказательства могут быть предоставлены путем сведения CSPRNG к проблеме, которая считается сложной , такой как целочисленная факторизация . Как правило, могут потребоваться годы проверки, прежде чем алгоритм может быть сертифицирован как CSPRNG.

Некоторые классы CSPRNG включают следующее:

  • потоковые шифры
  • блочные шифры , работающие в счетчике или выход обратной связи режиме
  • PRNGs , которые были разработаны специально , чтобы быть криптографически обеспечения, такие как Microsoft «s Cryptographic Application Programming Interface функции CryptGenRandom , то алгоритм тысячелистника (встроенный в Mac OS X и FreeBSD ), и Фортуна
  • комбинированные PRNG, которые пытаются объединить несколько примитивных алгоритмов PRNG с целью удаления любой обнаруживаемой неслучайности
  • специальные конструкции, основанные на предположениях математической жесткости: примеры включают генератор Микали-Шнорра , псевдослучайную функцию Наора-Рейнгольда и алгоритм Блюма Блюма Шуба , которые обеспечивают надежное доказательство безопасности (такие алгоритмы довольно медленны по сравнению с традиционными конструкциями и непрактичны для многих приложений )
  • общие ГПСЧ: хотя было показано, что (криптографически) безопасный ГПСЧ может быть построен в общем случае из любой односторонней функции , эта общая конструкция на практике очень медленная, поэтому представляет в основном теоретический интерес.

Было показано, что АНБ вставило асимметричный бэкдор в сертифицированный NIST генератор псевдослучайных чисел Dual_EC_DRBG .

Большинство алгоритмов ГПСЧ создают последовательности, которые равномерно распределяются по любому из нескольких тестов. Это открытый вопрос, который занимает центральное место в теории и практике криптографии , есть ли способ отличить вывод высококачественного ГПСЧ от действительно случайной последовательности. В этой настройке отличитель знает, что использовался либо известный алгоритм ГПСЧ (но не состояние, с которым он был инициализирован), либо был использован действительно случайный алгоритм, и должен различать два. Безопасность большинства криптографических алгоритмов и протоколов, использующих ГПСЧ, основана на предположении, что невозможно отличить использование подходящего ГПСЧ от использования действительно случайной последовательности. Простейшими примерами этой зависимости являются потоковые шифры , которые (чаще всего) работают, исключая или объединяя открытый текст сообщения с выходом PRNG, создавая зашифрованный текст . Создание криптографически адекватных ГПСЧ чрезвычайно сложно, потому что они должны соответствовать дополнительным критериям. Размер его периода является важным фактором криптографической пригодности ГПСЧ, но не единственным.

Не спеша, эффективно и правильно – путь разработки. Часть 1. Парадигма

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

Алгоритм Лемера

Самый простой приемлемый метод генерации случайных чисел — алгоритм Лемера. (Для простоты я использую термин «генерация случайных чисел» вместо более точного термина «генерация псевдослучайных чисел».) Выраженный в символьном виде, алгоритм Лемера представляет собой следующее:

На словах это звучит так: «новое случайное число является старым случайным числом, умножаемым на константу a, после чего над результатом выполняется операция по модулю константы m». Например, предположим, что в некий момент текущее случайное число равно 104, a = 3 и m = 100. Тогда новое случайное число будет равно 3 * 104 mod 100 = 312 mod 100 = 12. Вроде бы просто, но в реализации этого алгоритма много хитроумных деталей.

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект RandomNumbers. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный RandomNumbersProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылки на пространства имен верхнего уровня System и Collections.Generic.

Затем я добавил класс с именем LehmerRng для реализации RNG-алгоритма Лемера. Код показан на рис. 2. Версия алгоритма Лемера за 1988 год использует a = 16807 и m = 2147483647 (которое является int.MaxValue). Позднее, в 1993 году Лемер предложил другую версию, где a = 48271 как чуть более качественную альтернативу. Эти значения берутся из математической теории. Демонстрационный код основан на знаменитой статье С. К. Парка (S. K. Park) и К. У. Миллера (K. W. Miller) «Random Number Generators: Good Ones Are Hard to Find».

Рис. 2. Реализация алгоритма Лемера

Проблема реализации в том, чтобы предотвращать арифметическое переполнение. Алгоритм Лемера использует ловкий алгебраический трюк. Значение q является результатом m / a (целочисленное деление), а значение r равно m % a (m по модулю a).

При инициализации RNG Лемера начальным (зародышевым) значением можно использовать любое целое число в диапазоне . Многие RNG имеют конструктор без параметров, который получает системные дату и время, преобразует их в целое число и использует в качестве начального значения.

RNG Лемера вызывается в методе Main демонстрационной программы:

Каждый вызов метода Next возвращает значение в диапазоне .

Алгоритм Лемера весьма эффективен, и в простых сценариях я обычно выбираю именно его. Но заметьте, что ни один алгоритм из представленных в этой статье не обладает надежностью криптографического уровня и что их следует применять только в ситуациях, где не требуется статической строгости (statistical rigor).

Последовательности ГПСЧ и заполнение

Если вы запустите приведенный выше пример программы с несколько раз, вы заметите, что она каждый раз выводит один и тот же результат! Это означает, что хотя каждое число в последовательности кажется случайным по сравнению с предыдущими, вся последовательность вовсе не случайна! А это означает, что наша программа оказывается полностью предсказуемой (одни и те же входные данные всегда приводят к одним и тем же выходным данным). Бывают случаи, когда это может быть полезно или даже желательно (например, вы хотите, чтобы научное моделирование повторялось, или вы пытаетесь выяснить, почему ваш генератор случайных подземелий дает сбой).

Но часто это не то, что нужно. Если вы пишете игру «hi-lo» (высоко-низко) (где у пользователя есть 10 попыток угадать число, а компьютер сообщает ему, является ли его предположение слишком высоким или слишком низким), вы не хотите, чтобы программа каждый раз выбирала одни и те же числа. Итак, давайте подробнее посмотрим, почему это происходит, и как мы можем это исправить.

Помните, что каждое число в последовательности ГПСЧ определенным образом генерируется из предыдущего числа. Таким образом, при любом одном и том же начальном числе ГПСЧ всегда будут генерировать одну и ту же последовательность чисел! Мы получаем ту же последовательность, потому что наше начальное число всегда 5323.

Чтобы сделать всю нашу последовательность случайной, нам нужен способ выбрать начальное число, которое не является фиксированным значением. Первый ответ, который, вероятно, приходит в голову, – нам нужно случайное число! Это хорошая мысль, но если нам нужно случайное число для генерации случайных чисел, тогда мы попадаем в уловку-22. Оказывается, нам на самом деле не нужно, чтобы наше начальное число было случайным – нам просто нужно выбирать что-то, что меняется при каждом запуске программы. Затем мы можем использовать наш ГПСЧ для генерации уникальной последовательности псевдослучайных чисел из этого начального числа.

Общепринятым методом для этого является использование системных часов. Каждый раз, когда пользователь запускает программу, время будет другим. Если мы используем это значение времени в качестве начального числа, тогда наша программа при каждом запуске будет генерировать другую последовательность чисел!

C поставляется с функцией , которая возвращает количество секунд с полуночи 1 января 1970 года. Чтобы использовать ее, нам просто нужно включить заголовок ctime, а затем инициализировать с помощью вызов . Мы еще не рассмотрели , но в данном контексте это эквивалент 0.

Вот та же программа, что и выше, но с вызовом в качестве начального числа:

Теперь наша программа будет каждый раз генерировать новую последовательность случайных чисел! Запустите ее пару раз и убедитесь сами.

std::rand() – посредственный ГПСЧ

Алгоритм, используемый для реализации , может варьироваться от компилятора к компилятору, что приводит к результатам, которые могут не совпадать между компиляторами. В большинстве реализаций используется метод, называемый линейным конгруэнтным генератором (LCG, Linear Congruential Generator). Если вы посмотрите на первый пример в этом уроке, вы заметите, что на самом деле это LCG, хотя и с намеренно выбранными плохими константами. LCG, как правило, имеют недостатки, из-за которых они не подходят для решения большинства проблем.

Одним из основных недостатков является то, что обычно устанавливается равным 32767 (по сути, 15 бит). Это означает, что если вы хотите генерировать числа в большем диапазоне (например, 32-битные целые числа), не подходит. Кроме того, не подходит, если вы хотите генерировать случайные числа с плавающей запятой (например, от 0,0 до 1,0), что часто бывает полезно при статистическом моделировании. Наконец, имеет относительно короткий период по сравнению с другими алгоритмами.

Тем не менее, идеально подходит для обучения программированию и для программ, в которых высококачественный ГПСЧ не является необходимостью.

Для приложений, где полезен высококачественный ГПСЧ, я бы порекомендовал вихрь Мерсенна (Mersenne Twister) (или один из его вариантов), который дает отличные результаты и относительно прост в использовании. Вихрь Мерсенна был введен в C++11, и мы покажем, как его использовать позже в этом уроке.

Seed: основа псевдослучайных алгоритмов

Первые алгоритмы формирования случайных чисел выполняли ряд основных арифметических действий: умножить, разделить, добавить, вычесть, взять средние числа и т.д. Сегодня такие мощные алгоритмы, как Fortuna и Yarrow (используется в FreeBSD, AIX, Mac OS X, NetBSD) выглядят как генераторы случайных чисел для параноиков. Fortuna, например, это криптографический генератор, в котором для защиты от дискредитации после выполнения каждого запроса на случайные данные в размере 220 байт генерируются еще 256 бит псевдослучайных данных и используются в качестве нового ключа шифрования — старый ключ при этом каждый раз уничтожается.

Прошли годы, прежде чем простейшие алгоритмы эволюционировали до криптографически стойких генераторов псевдослучайных чисел. Частично этот процесс можно проследить на примере работы одной математической функции в языке С.

Функция rand () является простейшей из функций генерации случайных чисел в C.

В этом примере рандома используется вложенный цикл для отображения 100 случайных значений. Функция rand () хороша при создании множества случайных значений, но они являются предсказуемыми. Чтобы сделать вывод менее предсказуемым, вам нужно добавить seed в генератор случайных чисел — это делается с помощью функции srand ().

Seed — это стартовое число, точка, с которой начинается последовательность псевдослучайных чисел. Генератор псевдослучайных чисел использует единственное начальное значение, откуда и следует его псевдослучайность. Генератор истинных случайных чисел всегда имеет в начале высококачественную случайную величину, предоставленную различными источниками энтропии.

srand() принимает число и ставит его в качестве отправной точки. Если seed не выставить, то при каждом запуске программы мы будем получать одинаковые случайные числа.

Вот пример простой формулы случайного числа из «классики» — книги «Язык программирования C» Кернигана и Ричи, первое издание которой вышло аж в 1978 году:

Эта формула предполагает существование переменной, называемой random_seed, изначально заданной некоторым числом. Переменная random_seed умножается на 1 103 535 245, а затем 12 345 добавляется к результату; random_seed затем заменяется этим новым значением. Это на самом деле довольно хороший генератор псевдослучайных чисел. Если вы используете его для создания случайных чисел от 0 до 9, то первые 20 значений, которые он вернет при seed = 10, будут такими:

Если у вас есть 10 000 значений от 0 до 9, то распределение будет следующим:

0 — 10151 — 10242 — 10483 — 9964 — 9885 — 10016 — 9967 — 10068 — 9659 — 961

Любая формула псевдослучайных чисел зависит от начального значения. Если вы предоставите функции rand() seed 10 на одном компьютере, и посмотрите на поток чисел, которые она производит, то результат будет идентичен «случайной последовательности», созданной на любом другом компьютере с seed 10.

К сожалению, у генератора случайных чисел есть и другая слабость: вы всегда можете предсказать, что будет дальше, основываясь на том, что было раньше. Чтобы получить следующее число в последовательности, мы должны всегда помнить последнее внутреннее состояние генератора — так называемый state. Без state мы будем снова делать одну и ту же математическую операцию с одинаковыми числами, чтобы получить тот же ответ.

Как сделать seed уникальным для каждого случая? Самое очевидное решение — добавить в вычисления текущее системное время. Сделать это можно с помощью функции time().

Функция time() возвращает информацию о текущем времени суток, значение, которое постоянно изменяется. При этом метод typecasting гарантирует, что значение, возвращаемое функцией time(), является целым числом.

Итак, в результате добавления «случайного» системного времени функция rand() генерирует значения, которые являются более случайными, чем мы получили в первом примере.

Однако в этом случае seed можно угадать, зная системное время или время запуска приложения. Как правило, для приложений, где случайные числа являются абсолютно критичными, лучше всего найти альтернативное решение.

В .net framework есть функция System.Security.Cryptography.RandomNumberGenerator, где в расчетах учитываются следующие факторы:

  • ID текущего процесса;
  • текущий ID потока;
  • количество отсчетов с момента загрузки;
  • текущее время;
  • различные высокоточные счетчики производительности процессора;
  • MD4-хэш среды пользователя (имя пользователя, имя компьютера и т.д.).

Но опять же, все эти числа не случайны.

Лучшее, что вы можете сделать с детерминированными генераторами псевдослучайных чисел — добавить энтропию физических явлений.

Табличные ГСЧ

Табличные ГСЧ в качестве источника случайных чисел используют специальным
образом составленные таблицы, содержащие проверенные некоррелированные, то есть
никак не зависящие друг от друга, цифры. В табл. 22.1 приведен небольшой
фрагмент такой таблицы. Обходя таблицу слева направо сверху вниз, можно
получать равномерно распределенные от 0 до 1 случайные числа с нужным числом
знаков после запятой (в нашем примере мы используем для каждого числа по три
знака). Так как цифры в таблице не зависят друг от друга, то таблицу можно
обходить разными способами, например, сверху вниз, или справа налево, или,
скажем, можно выбирать цифры, находящиеся на четных позициях.

Таблица 22.1.Случайные цифры. Равномернораспределенные от 0 до 1 случайные числа
Случайные цифры Равномерно распределенныеот 0 до 1 случайные числа
9 2 9 2 4 2 6 0.929
9 5 7 3 4 9 3 0.204
5 9 1 6 6 5 7 6 0.269

Достоинство данного метода в том, что он дает действительно случайные числа,
так как таблица содержит проверенные некоррелированные цифры. Недостатки
метода: для хранения большого количества цифр требуется много памяти; большие
трудности порождения и проверки такого рода таблиц, повторы при использовании
таблицы уже не гарантируют случайности числовой последовательности, а значит,
и надежности результата.

Здесь
находится таблица, содержащая 500 абсолютно случайных проверенных чисел
(взято из книги И. Г. Венецкого, В. И. Венецкой «Основные
математико-статистические понятия и формулы в экономическом анализе»).