Псевдослучайное число


Псевдослучайное число

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник энтропии ГПСЧ Достоинства Недостатки
/dev/random в Linux Счётчик тактов процессора, однако собирается только во время аппаратных прерываний LFSR, с хешированием выхода через Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
Yarrow от Брюса Шнайера[3] Традиционные (устаревшие) методы AES-256 и Гибкий криптостойкий дизайн Долго «нагревается», очень маленькое внутреннее состояние, слишком сильно зависит от криптостойкости выбранных алгоритмов, медленный, применим исключительно для генерации ключей
Генератор Леонида Юрьева[4] Шум звуковой карты  ? Скорее всего, хороший и быстрый источник энтропии Нет независимого, заведомо криптостойкого ГПСЧ, доступен исключительно в виде Windows
Microsoft Встроен в Windows, не «застревает» Маленькое внутреннее состояние, легко предсказуем
Взаимодействие между потоками В Java другого выбора пока нет, большое внутреннее состояние Медленный сбор энтропии
Chaos от Ruptor[5] Счётчик тактов процессора, собирается непрерывно Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора Пока самый быстрый из всех, большое внутреннее состояние, не «застревает»
RRAND от Ruptor[6] Счётчик тактов процессора Зашифровывание внутреннего состояния поточным шифром Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает»

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

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

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

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

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

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

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

Примечания

  1. Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования. Указ. соч. — С. 129—130.
  2. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0-521-43108-5
  3. 1 2 http://www.schneier.com/yarrow.html
  4. http://leo.yuriev.ru/random
  5. http://cryptolib.com/crypto/chaos/
  6. http://cryptolib.com/crypto/rrand/

См. также

Ссылки

Литература

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

Wikimedia Foundation. 2010.

Смотреть что такое "Псевдослучайное число" в других словарях:

  • псевдослучайное число — Число, извлеченное из псевдослучайной последовательности. [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN pseudo random number …   Справочник технического переводчика

  • псевдослучайное число — pseudoatsitiktinis skaičius statusas T sritis automatika atitikmenys: angl. pseudorandom number vok. Pseudozufallszahl, f rus. псевдослучайное число, n pranc. nombre pseudo aléatoire, m …   Automatikos terminų žodynas

  • Число — У этого термина существуют и другие значения, см. Число (значения). Число  основное понятие математики[1], используемое для количественной характеристики, сравнения и нумерации объектов. Возникнув ещё в первобытном обществе из потребностей… …   Википедия

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

  • HDCP — Не следует путать с DHCP. У этого термина существуют и другие значения, см. HD. Работа с оптическими дисками Оптический диск Образ оптического диска, ISO образ Эмулятор оптических дисководов Программное обеспечение для работы с файловыми… …   Википедия

  • Атака на основе подобранного шифротекста — (англ. Chosen ciphertext attack)  криптографическая атака, при которой криптоаналитик собирает информацию о шифре путем подбора зашифрованного текста и получения его расшифровки при неизвестном ключе. Как правило, криптоаналитик может… …   Википедия

  • Теорема Вольстенхольма — (англ. Wolstenholme s theorem) утверждает, что для любого простого числа выполняется сравнение где   средний биномиальный коэффициент. Эквивалентное сравнение Неизвестны составные числа, удовлетворяющие теореме Вольстенхол …   Википедия

  • IPv6 — Название: Internet Protocol version 6 Уровень (по модели OSI): Сетевой Семейство: TCP/IP Назначение протокола: Адресация Спецификация: RFC 2460 Основные реализации (клиенты) …   Википедия

  • Оказия — Оказия  случай (заимств. в XVII в. из польск. яз., где okazja «случай» (от лат. occasio суф. производного от occidere «падать»)). 1. Удобный, благоприятный случай. Послать письмо с оказией. Хоть раненько задумал ты жениться, да… …   Википедия

  • Псевдослучайная последовательность — (ПСП) последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи. Хотя псевдослучайная последовательность в этом смысле… …   Википедия