Алгоритм генератора псевдослучайных чисел. Генератор псевдослучайных чисел – random

Детерминированные ГПСЧ

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

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

Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 2 (n/2) где n это размер внутреннего состояния в битах, хотя линейные-конгруэнтные генераторы и РЛСО (LFSR) генераторы обладают максимальными циклами порядка 2 n . Если ГПСЧ может сходиться к слишком коротким циклам, такой ГПСЧ становится предсказуемым и является непригодным.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

• Слишком короткий период/периоды
• Последовательные значения не являются независимыми
• Некоторые биты «менее случайны», чем другие
• Неравномерное одномерное распределение
• Обратимость

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

ГПСЧ с источником энтропии или ГСЧ

Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются «генераторами случайных чисел» («random number generator» ) или сокращённо ГСЧ (RNG). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника . Таким образом, под ГСЧ теперь принято подразумевать именно криптостойкие ГПСЧ с внешним источником энтропии.

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие как шум звуковой карты или значения (processor clock counter) которые легко считываются, например, при помощи инструкции в процессорах Intel. До появления в процессорах возможности считывать значение самого чувствительного к малейшим изменениям окружающей среды счётчика тактов процессора, сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например smart-карты), которые таким образом остаются уязвимыми. Многие ГСЧ до сих пор используют традиционные (устаревшие) методы сбора энтропии такие как действия пользователя (движения мыши и т. п.), как например в и Yarrow , или взаимодействие между нитями (threads), как например в Java secure random.

Вот несколько примеров ГСЧ с их источниками энтропии и генераторами:

• /dev/random в / - источник энтропии: , однако собирается только во время аппаратных прерываний; ГПСЧ: LFSR, с хэшированием выхода через ; достоинства: есть во всех Unix-ах, надёжный источник энтропии; недостатки: очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom );
• Yarrow от - источник энтропии: традиционные (устаревшие) методы; ГПСЧ: AES-256 и маленького внутреннего состояния; достоинства: гибкий криптостойкий дизайн; недостатки - долго «нагревается», очень маленькое внутреннее состояние, слишком сильно зависит от криптостойкости выбранных алгоритмов, медленный, применим исключительно для генерации ключей;
• генератор от Леонида Юрьева (Leo Yuriev) - источник энтропии: шум звуковой карты; ГПСЧ: пока не известен; достоинства: скорее всего хороший и быстрый источник энтропии; недостатки - нет независимого, заведомо криптостойкого ГПСЧ, доступен исключительно в виде DLL под Windows;
• Microsoft CryptoAPI - источник энтропии: текущее время, размер hard drive, размер свободной памяти, id процесса и NETBIOS имя компьютера; ГПСЧ: хэш внутреннего состояния размером в 128 бит (хэш присутствует только в 128-битовых версиях Windows); достоинства - встроен в Windows, не «застревает»; недостатки - маленькое внутреннее состояние, легко предсказуем;
• Java SecureRandom - источник энтропии: взаимодействие между нитями (threads); ГПСЧ: хэш внутреннего состояния (1024 бит); достоинства - в Java другого выбора пока нет, большое внутреннее состояние; недостатки: медленный сбор энтропии, хотя в Java другого выбора пока всё равно нет;
• Chaos от Ruptor - источник энтропии: , собирается непрерывно; ГПСЧ: хэширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia генератора; достоинства: пока самый быстрый из всех, большое внутреннее состояние, не «застревает».

Аппаратные ГПСЧ

Кроме устаревших хорошо известных LFSR генераторов широко применявшихся в качестве аппаратных ГПСЧ в прошлом веке к сожалению очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и так же держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA или ASIC ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, по этому до сих пор все известные аппаратные ГПСЧ были сломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR генераторами и оба были сломаны с помощью алгебраических атак.

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

В компьютерных программах нередко требуется эмуляция случайности. Например, при разработке игр. Если в программе имеется некий генератор, т. е. производитель, случайного числа, то, используя полученное таким образом число, можно выбирать ту или иную ветку выполнения программы, или произвольный объект из коллекции. Другими словами, главное – сгенерировать число. Эмуляция случайности иного рода основывается на нем.

Мы наверняка не знаем, есть ли в природе случайность, или она нам только кажется из-за ограниченности наших знаний. Мы только знаем, что в программировании настоящей случайности нет. Неоткуда взяться произвольному числу, нельзя запрограммировать его появление из ниоткуда. Можно лишь создать программу, которая в результате применения сложной формулы к "зерну" будет выдавать число, и нам будет казаться, что это число случайно.

"Зерно" – это исходные данные для формулы. Им может быть, например, системное время в миллисекундах, которое постоянно меняется. Следовательно, "зерно" будет постоянно разным. Или программист может задавать его самостоятельно.

Подобную программу (в реальности модуль или функцию) называют генератором псевдослучайных чисел. В состав стандартной библиотеки языка Python входит модуль random. Он содержит множество функций, связанных с эмуляцией случайности (например, "перемешивание" элементов последовательности), а не только функции генерации псевдослучайных чисел.

В этом уроке будут рассмотрены функции random(), randrange() и randint() из модуля random. Обратите внимание, что модуль random содержит одноименную функцию random(). Так бывает.

Чтобы обращаться к функциям, надо импортировать модуль random:

>>> import random

Или импортировать отдельные функции из него:

>>> from random import random , randrange, randint

Функции для получения целых "случайных" чисел – randint() и randrange()

Функции randint() и randrange() генерируют псевдослучайные целые числа. Первая из них наиболее простая и всегда принимает только два аргумента – пределы целочисленного диапазона, из которого выбирается любое число:

>>> random .randint (0 , 10 ) 6

или (если импортировались отдельные функции):

>>> randint(100 , 200 ) 110

В случае randint() обе границы включаются в диапазон, т. е. на языке математики отрезок описывается как .

Числа могут быть отрицательными:

>>> random .randint (-100 , 10 ) -83 >>> random .randint (-100 , -10 ) -38

Но первое число всегда должно быть меньше или, по-крайней мере, равно второму. То есть a <= b.

Функция randrange() сложнее. Она может принимать один аргумент, два или даже три. Если указан только один, то она возвращает случайное число от 0 до указанного аргумента. Причем сам аргумент в диапазон не входит. На языке математики – это }