Генератор псевдослучайных чисел

Материал из Википедии — свободной энциклопедии

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

Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

Содержание 1 Детерминированные ГПСЧ 2 ГПСЧ с источником энтропии или ГСЧ 2.1 Примеры ГСЧ и источников энтропии 3 ГПСЧ в криптографии 4 Аппаратные ГПСЧ 5 См. также 5.1 Ссылки 5.2 Литература

[править] Детерминированные ГПСЧ

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

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

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

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

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

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, linear feedback shift registers, generalized feedback shift registers.

Из современных ГПСЧ широкое распространение получил Вихрь Мерсенна, предложенный в 1997 году Мацумото и Нишимурой. Его достоинствами являются колоссальный период (2¹⁹⁹³⁷-1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение от силы в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако существуют сложные алгоритмы, распознающие последовательность, порождаемую с помощью Вихря Мерсенна как неслучайную. Это делает Вихрь Мерсенна неподходящим для криптографии.

[править] ГПСЧ с источником энтропии или ГСЧ

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

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

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

[править] Примеры ГСЧ и источников энтропии

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

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

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

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

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

[править] Аппаратные ГПСЧ

Основная статья: Аппаратный генератор случайных чисел

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

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

[править] См. также

• Пакет статистического тестирования NIST STS
• Пакет статистического тестирования CryptX
• Тесты DIEHARD
• Метод Монте-Карло
• Случайное простое число

[править] Ссылки

• Андрей Зубинский «В поисках случайности». Компьютерное Обозрение, 29 (2003)
• Юрий Лифшиц. Курс «Современные задачи криптографии» (Лекция 9: «Псевдослучайные генераторы»)
• Л. Бараш «Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел».
• noonv «Старый взгляд на новые вещи»
• random.org(англ.) - онлайновый сервис для генерации случайных чисел
• Cryptographic Random Numbers(англ.)
• Theory and Practice of Random Number Generation(англ.)
• Zvi Gutterman, Benny Pinkas, and Tzachy Reinman «Analysis of the Linux Random Number Generator»(англ.)
• NIST SP 800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications [1](англ.)

[править] Литература

• Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2, глава 3 «Случайные числа»