Случайные и псевдослучайные числа

Краткая историческая справка

К середине 40-ых годов ХХ века Американский аналитический центр RAND создал машину, которая была способна генерировать случайные числа с помощью генератора импульсов. Через некоторое время они опубликовали книгу с последовательностью длинной в миллион случайных чисел.

Рис. 1 – Книга — “A Million Random Digits with 100,000 Normal Deviates”

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

         В 1951 году появился первый компьютер, который, поставлялся со встроенным генератором случайных данных на основе дробовых шумов – Ferranti Mark 1.

         В 1997 году программисты из компании Silicon Graphics создали LavaRand. Эта установка состояла из вебкамеры, направленной на лава-лампы, стоявшие рядом на столе. Картинка с этой камеры являла собой источник энтропии – Скорость генерации равна 165 Кб случайных чисел в секунду.

Рис. 2 – LavaRand

         В 1999 году Intel внедрил аппаратный генератор случайных чисел в собственный чипсет i810. Это решение давало по-настоящему случайные числа на основе температурных шумов процессора, но работало медленнее, чем программные ГПСЧ (генераторы псевдослучайных чисел).

Введение

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

         Также не должно быть возможности определить начальное значение на основе каких-либо сгенерированных значений. Не должно быть очевидной корреляции между начальным значением и каким-либо числом последовательности, полученной из этого начального значения. Каждый элемент последовательности должен выглядеть как результат независимого случайного события, вероятность которого равна 1/2.

Сферы применения

Перечислим несколько сфер, где активно используются случайные числа:

1. Моделирование.
   Компьютерное моделирование физических явлений.
2. Криптография и информационная безопасность. Случайные числа часто используются в тестировании корректности или эффективности алгоритмов и программ, также они могут выступать входным потоком информации. Многие алгоритмы используют генерацию псевдослучайных чисел для решения прикладных задач (например, криптографические алгоритмы шифрования, генерация уникальных идентификаторов, «соль» для хэш-функций и др.).
3. Компьютерные игры. Случайность в играх имеет значительную роль. В компьютерных или настольных играх случайность помогает разбавить игровой процесс и уравнять шансы между игроками разного уровня подготовки.

Разница между случайными и псевдослучайными числами

Случайные числа делятся на две категории:

1. Физически случайное число (истинно случайное) – последовательность чисел, построенная на основе непредсказуемого физического явления.
2. Псевдослучайное число – последовательность чисел, подчиняемая заданному распределению.

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

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

1. Дробовой шум – шум в электрических цепях.
2. Тепловой шум – «прослушка» резисторов.
3. Атмосферный шум – радиоприемник, который ловит наводки и шумы в эфире.
4. Фотоэлектрический эффект.
5. Квантовые явления – радиоактивный распад атомов.

Недостатки:

1. Дороговизна применения.
2. Сложность конструкции.
3. Медленная генерация последовательностей.

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

1. Линейный конгруэнтный метод.
2. Вихрь Мерсенна.

Недостатки:

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

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

Заключение

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

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

Список литературы

1. Pierre L’Ecuyer and Richard Simard. 2007. TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Softw. 33, 4, Article 22 (August 2007). DOI=10.1145/1268776.1268777 iro.umontreal.ca/testu01/tu01.html

2. Intel Corporation. Intel 810 Chipset Design Guide, June 1999. downlintel.com/design/chipsets/designex/29065701.pdf

3. Intel Digital Random Number Generator (DRNG) Software Implementation Guide — intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

4. Дональд Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. Третье издание — 2011 — Вильямс. ISBN 978-5-8459-0081-4, 

5. Cryptography Research, Inc. Evaluation summary: VIA C3 Nehemiah random number generator — 2003 — cryptography.com/public/pdf/VIA_rngsum.pdf