Случайные числа

Термины

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

Случайное число (или истинно случайное число) – это разновидность случайной величины, с заданным законом распределения, получающий энтропию от текущего состояния некоторого атрибута физической среды. Например, атмосферный шум радиоволн, дробовой шум, радиоактивное излучение и т.д.

Криптографически стойкие псевдослучайные числа – это псевдослучайные числа, разработанные специалистами по криптографии, которые берут начальное значение (SEED) для алгоритма, как истинно случайное число.

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

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

• Отсутствие зацикливаний последовательности псевдослучайных чисел в пределах рассматриваемой задачи.
• Скорость исполнения логики и экономия памяти.
• Повторяемость полученной последовательности n-е количество раз.
• Возможность разделения последовательности на множество потоков.

Перечень наиболее заметных генераторов псевдослучайных чисел: Mid-Square, Lehmer, Rule 30, Вихрь Мерсенна, Xorshift, Fortuna, Xoroshiro128+, 64-bit MELG, Squares RNG, Itamaraca (Ita).

Генератор истинно случайных чисел (ГИСЧ) – это некоторое физическое устройство, которое генерирует последовательность случайных чисел, в зависимости от значений процессов, протекающих в некоторой физической среде.

Генератор криптографически стойких псевдослучайных чисел (ГКСПСЧ Анг. Cryptographically secure pseudorandom number generator, CSPRNG) – это определенный алгоритм генерирующий псевдослучайные числа, разработанный специалистами по криптографии, который берет начальное значение (SEED), как истинно случайное число из некоторой физической среды.

Число - это ключевое понятие в математике, которое применяется для количественного описания различных объектов, сравнения различных объектов, нумерации различных объектов и входящих в них элементов. Цифры – это письменные знаки, применяемые с целью обозначения чисел. В большинстве случаев используются арабские цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Существуют также и другие знаки для обозначения цифр, например, римские цифры, славянская кириллическая нумерация (сохранялась до XVIII века), Еврейская система, Египетская система и прочие.

История возникновения и методы получения случайных чисел

Случайность нередко встречается в живой природе, но получить её искусственным путем, задача, требующая значительных усилий. Одиннадцать столетий назад до нашей эры, в Китае был распространен опыт разбиения сильным ударом черепашьего панциря, с дальнейшим истолкованием размеров полученных случайных частей. В 5 веке до нашей эры афинская демократия подразумевала “равенство политических партий”, это равенство достигалась именно случайным выбором. Греческая демократия подразумевала власть народа, поэтому афинские греки считали любые выборы не демократичными. В результате выборы проводились по жребию. Фрэнсис Гальтон писал в своей книге, что не смог найти лучшего способа сгенерировать случайное число, кроме как бросать игральные кости. Даже при самом легком броске предугадать исход не представляется возможным.

Для получения большого объема случайных чисел, Авиационный научно-исследовательский институт RAND в сороковых годах прошлого столетия, разработал устройство, добывающее случайные числа при помощи применения генератора случайных импульсов. Результаты работы RAND были опубликованы в научной работе "Один миллион случайных чисел и сто тысяч нормальных отклонений". В 46 году, Джон Фон Нейман создал генератор псевдослучайных чисел. Принцип работы которого базируется на том, чтобы задать произвольное число, возвести данное число в степень, исключить цифры из средней части результата, и повторять этот процесс n-е количество раз. Но сгенерированная по такому правилу последовательность, вне зависимости от начального значения, будет иметь некоторый период, после которого последовательность повторяется. Когда мы имеем дело с детерминированной функцией, полностью избежать повторений невозможно. Но на практике, это не будет иметь значения, так как период цикла можно сделать очень большим.

Интернет сообщество нуждалось в защите информации, поэтому в 95 году создали Secure Sockets Layer или SSL, для реализации которого требовался качественный генератор псевдослучайных чисел. Вследствие, того что в 90-х годах прошлого века большинство процессоров не предоставляли специальной инструкции для получения случайных чисел, то выбор качественного начального значения для генератора псевдослучайных чисел имел приоритетное значение. Специалисты SGI спроектировали в 1997 году LavaRand, состоящий из веб-камеры, которая смотрит на две лава лампы, расположенные рядом друг с другом на столе. Полученное изображение было качественным источником энтропии. По принципу обработки температурных шумов Intel в 2012 году дополнили в свои чипы инструкциями RDRAND и RDSEED, которые позволяли получать истинно случайные числа на высокой скорости. Но отмечается что в среде специалистов к этим инструкциям нет доверия, так как есть опасения, что это закладки для NASA.

Некоторым источником энтропии, может служить метод наблюдения перемещения указателя курсора мыши над некоторой определенной областью на экране. Программа отслеживает координаты X и Y указателя курсора мыши, а затем выполняет определенную программистом логику, которая генерирует число. Например, таким способом можно генерировать seed для начального значения псевдослучайной последовательности. Источником для генерации истинно случайных чисел может быть и звуковая карта, которая в интегрированном виде встроена в любую материнскую плату. Шум на её линейном входе является хорошим источником энтропии. Главной задачей для получения истинно случайных чисел является считывание шума и обработка его статистических характеристик.

Квантовый генератор истинно случайных чисел создали швейцарские ученые при помощи телефона Nokia N9, принцип работы которого состоит в подсчете эмиссии фотонов. Данный квантовый процесс непредсказуем, так как в определенный интервал времени от источника света получается непредсказуемое количество фотонов. Отдача подобной системы ровна 1 мегабит/с. Самый высокоскоростной квантовый генератор истинно случайных чисел разработали Ученые НИТУ "МИСИС", Российского квантового центра. 8,05 Гб/с, скорость с которой устройство генерирует случайные числа, затем доказывает их непредсказуемое поведение в режиме реального времени.

Случайные числа: широкий спектр применений в различных областях

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

Азартные игры

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

Видеоигры

Случайные числа в той или иной мере используются практически во всех видеоиграх. Чтобы сгенерировать мир, расставить объекты и предметы в нем не обойтись без случайных чисел. Вернее, в большинстве игр достаточно использование псевдослучайных чисел. Прорисовать красивый ландшафт, для этой задачи требуется генератор случайных чисел. Например, чтобы расставить деревья в некотором виртуальном пространстве, можно сгенерировать последовательность псевдослучайных чисел начальный SEED для которых берется как текущее системное время. Можно взять последние цифры каждого из псевдослучайных чисел и представить их как координаты для деревьев, а первые цифры псевдослучайных чисел использовать для обозначения высоты дерева. Другой пример, чтобы создать разброс урона пули 10 до 14 после выстрела, необходимо сгенерировать псевдослучайное число, берем остаток от его деления 6 и прибавляем к нему 10. Если игрок должен увернутся от некоторой опасности с шансом в 51 процент, генерируем некоторое случайное число, если число превышает определенное значение, то игрок успешно увернулся.

Еще одним примером использования случайных чисел в видеоиграх это так называемые случайные встречи – принцип, применяемый в ролевых играх на компьютере, когда встреча игрока с ботами происходит случайным образом. Применение случайности в данной ситуации приводит к тому что игрок не знает о количестве нападающих и их состава. Одной из первых игр в которой были применены случайные встречи стала игра 1981 года Wizardy. Когда игроки перемещаются по некоторой враждебной области, например, лес, пещера или подземный дворец, то всегда есть вероятность нападения монстров. А, так как речь идет о случайных встречах то битва состоится в любом случае. В некоторых играх добавили возможность регулировать вероятность возникновения случайных встреч. Например, игра Final Fantasy VIII. В игре Pokemon Gold и Silver определенные разновидности покемонов возможно обнаружить только в строго определённое время суток. На сегодняшний день видеоигры со случайными встречами считаются устаревшими и практически не используются.

Физика

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

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

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

Криптография

Истинно случайные числа представляют основу большинства алгоритмов криптографии, обеспечивающие безопасность информационных технологий. Конфиденциальность, аутентификация, электронная коммерция – области где широко используется криптография. Например, при использовании алгоритма шифрования пользователем, он должен использовать последовательность истинно случайных чисел в качестве ключа. Ключ на основе истинно случайных чисел, обладающий высокой энтропией, будет доставлять проблему любому атакующему. Если представить, что в качестве ключа используется обычный 32-разрядный линейный конгруэнтный генератор псевдослучайных чисел, то будет создано четыре миллиарда возможных значений, после чего последовательность начнет повториться. Достаточно целеустремленный злоумышленник может их обработать методом прямого перебора за приемлемое время.

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

Дата создания: 31.03.2022

Изменено: 27.08.2022