как работает рандом в компьютере

Содержание
  1. Алгоритмы рандома
  2. Про что статья
  3. C++ rand
  4. С++11 STL random
  5. PRNG — Pseudo-random Numbers Generator
  6. XorShift
  7. 8-bit рандом в эмуляторе z26
  8. Компактный рандом для Z80 от Joe Wingbermuehle
  9. Генератор рандома в DOOM
  10. RDRAND
  11. Концовка
  12. «Случайности не случайны, всё это большой обман.» или как работают элементы рандома в играх.
  13. Как компьютер генерирует случайные числа
  14. Создание случайных чисел из семени
  15. Числовой круг
  16. Выбор семени
  17. Конечный результат
  18. Заключительные замечания
  19. Подробно о генераторах случайных и псевдослучайных чисел
  20. Введение
  21. Как отличить случайную последовательность чисел от неслучайной?
  22. Чуть более сложный пример или число Пи
  23. Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
  24. Уязвимости ГПСЧ
  25. Линейный конгруэнтный ГПСЧ (LCPRNG)
  26. Предсказание результатов линейно-конгруэнтного метода
  27. Взлом встроенного генератора случайных чисел в Java
  28. Взлом ГПСЧ Mersenne twister в PHP
  29. Область для взлома
  30. Задание распределения для генератора псевдослучайных чисел
  31. Экспоненциальное распределение
  32. Тесты ГПСЧ

Алгоритмы рандома

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

Про что статья

C++ rand

Первое что узнаёт начинающий программист С++ по теме получения рандома — функция rand, которая генерирует случайное число в пределах от 0 и RAND_MAX. Константа RAND_MAX описана в файле stdlib.h и равна 32’767, но этом может быть не так, например в Linux (см. коммент). Если же rand() в вашем компиляторе генерирует числа в пределах 32’767 (0x7FFF) и вы хотите получить случайное число большого размера, то код ниже можно рассматривать как вариант решения этой проблемы:

Реализация функции rand в старом C была проста и имела следующий вид:

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

С++11 STL random

Данный сорт рандома появился в C++11 и представляет из себя следующий набор классов: minstd_rand, mt19937, ranlux, knuth_b и разные их вариации.

Чтобы последовательность случайных чисел не повторялась при каждом запуске программы, задают «зерно» псевдослучайного генератора в виде текущего времени или, в случае с некоторыми ретро (и не только) играми — интервалы между нажатиями клавиш с клавиатуры/джойстика. Библиотека random же предлагает использовать std::random_device для получения зерна лучше чем от time(NULL), однако в случае с компилятором MinGW в Windows функция практически не работает так как надо. До сих пор…

Некоторые из алгоритмов в STL random могут работать быстрее чем rand(), но давать менее качественную последовательность случайных чисел.

PRNG — Pseudo-random Numbers Generator

Можете считать это название — синонимом линейного конгруэнтного метода. PRNG алгоритмы похожи на реализацию rand в C и отличаются лишь константами.

PRNG алгоритмы быстро работают и легки в реализации на многих языках, но не обладают большим периодом.

XorShift

Алгоритм имеющий множество вариаций отличающихся друг от друга периодом и используемыми регистрами. Подробности и разновидности XorShift’а можете посмотреть на Википедии или Хабре. Приведу один из вариантов с последовательностью 2 в 128-й степени.

Данный генератор очень хорош тем, что в нём вообще нет операций деления и умножения — это может быть полезно на процессорах и микроконтроллерах в которых нету ассемблерных инструкций деления/умножения (PIC16, Z80, 6502).

8-bit рандом в эмуляторе z26

Z26 это эмулятор старенькой приставки Atari2600, в коде которого можно обнаружить рандом ориентированный на работу с 1-байтовыми регистрами.

Однажды мне пришлось сделать реализацию этого алгоритма для z80:

Компактный рандом для Z80 от Joe Wingbermuehle

Если вам интересно написание программ под машины с зилогом, то представляю вашему вниманию алгоритм от Joe Wingbermuehle (работает только на зилоге):

Генератор рандома в DOOM

В исходниках игры Дум есть такой интересный файл под названием m_random.c (см. код), в котором описана функция «табличного» рандома, то есть там вообще нет никаких формул и магии с битовыми сдвигами.

Приведу более компактный код наглядно показывающий работу этой функции.

Конечно же это ни какой не рандом и последовательность случайных чисел легко предугадать даже на уровне интуиции в процессе игры, но работает всё это крайне быстро. Если вам не особо важна криптографическая стойкость и вы хотите что-то быстро генерирующее «типа-рандом», то эта функция для вас. Кстати в Quake3 рандом выглядит просто — rand()&0x7FFF.

RDRAND

Некоторые современные процессоры способны генерировать случайные числа с помощью одной ассемблерной команды — RDRAND. Для использования этой функции в C++ вы можете вручную прописать нужные инструкции ассемблерными вставками или же в GCC подключить файл immintrin.h и выбрать любую из вариаций функции _rdrandXX_step, где XX означает число бит в регистре и может быть равно 16, 32 или 64.

Концовка

Класс std::minstd_rand из библиотеки STL random работает быстрее обыкновенного rand() и может стать его альтернативной заменой, если вас не особо волнует длинна периода в minstd. Возможны различия в работе этих функций в Windows и Unix’ах.

Источник

«Случайности не случайны, всё это большой обман.» или как работают элементы рандома в играх.

ПРЕДИСЛОВИЕ

Доброго времени суток StopGame! Сегодня я расскажу вам, как работают элементы рандома (случайных событий) и как на самом деле разработчики создают те или иные ситуации, где эти элементы требуются. Сразу уточню для большего понимания: случайность — рандом. Постараюсь рассказать как можно более сжато и понятно для восприятия. Ну что же, поехали!

О ВИДАХ СЛУЧАЙНЫХ ЭЛЕМЕНТОВ

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

На самом деле существует несколько ситуаций, где требуется применение элементов рандома:

1.Процедурная генерация (создание ландшафта и миров).

2.«Честная» генерация предметов (Выпадение предметов из противников, сундуков и тд.).

3.«Не честная» генерация предметов (Кейсы в играх, покупаемые за реальные деньги).

4.Ситуации, где на элементах рандома завязана вся игра. (Игральные карты, игры с шестигранным кубиком)

5.Различные ситуации, которые должны возникать в рандомное время (Например смена погоды с солнечной на дождливую).

Остановимся на каждом выделенном элементе более подробно. (если что-то забыл добавить в список, милости прошу в комментарии. Если будет действительно интересный и конструктивный коммент, я дополню блог).

Процедурная генерация

Конечно под этим словом подразумевается не только создание ландшафта и окружения, сюда входит местонахождение предметов на локации, персонажей и много чего ещё, но всё же самым популярным методом использования всё равно остаётся генерация случайных миров. Ярким примером может являться создание мира в «Minecraft», где работает именно процедурная генерация, она создаёт абсолютно всё окружение вокруг игрока (все блоки, сундуки, враги, объекты, персонажи и др.) и давайте разберём, как же он создаётся. На самом деле алгоритм не раз менялся, но на сегодняшний день он работает так:

Знаете ли вы, что мир в «Minecraft» не бесконечен? Он составляет 30 на 30 миллионов блоков. При генерации (не только в «Minecraft», во многих играх также) используется так называемый «seed» — начальное значение.

00141.4hF2hiD

Чтобы создать уникальный мир, это начальное значение создать из случайных цифр и символов. Без него не работает практически никакой метод ГПСЧ (Генератор псевдослучайных чисел). Но так как, компьютер не может создать ничего случайного, игра берёт за случайные цифры дату и время на компьютере. Если вы попытаетесь создать два мира в игре с одной и той же датой и временем (например 20.10.2020, 18:34), то получите два абсолютно одинаковых мира. Но созданием «seed» всё не кончается, далее это начальное значение преобразуется в 32-х битное число путём нескольких формул. После получается число, которое применяется ещё к одному методу — Шуму Перлина.

Шум Перлина на самом деле к звуку никакого отношения не имеет, это по сути картинка (пример на изображении ниже) с множеством оттенков серых, белых и чёрных цветов. Если говорить совсем простым языком, чем темнее пиксель на изображении шума Перлина, тем выше (либо ниже) создаётся ландшафт.

Допустим такой пример (очень упрощённо, на деле всё сложнее, есть куча «фильтров» последующей «полировки» мира). На картинке шума есть пиксели только трёх цветов (без оттенков): белый, серый и чёрный, тогда мир «Minecraft» может сгенерироваться с ландшафтом высотой максимум в 3 блока. Белым будет блок воздуха (по сути отсутствие блока), серым толщина ландшафта в 1 блок, а чёрным толщина в 2 блока. Но такой шум Перлина принято называть двумерным.

В игре используется в основном трёхмерный шум(3D) (но и двумерный тоже работает для «полировки»), так как при использовании только двумерного (2D) невозможно было бы создать например пещеры и различные постройки. Ниже вы можете увидеть 2D шум. На первой картинке вы видите слева сам шум, а справа результат создания (неудачный я нашёл пример, справа создаётся какая-то 2D игра). На второй картинке вы сразу видите результат работы шума Перлина уже в игровом движке. На третей и четвёртой картинке показано всё более понятно.

00143.HCN5rby00144.UAX2vOp00145.C34Zc72 00146.9OnWn9t

Вот примерно так и создаются все процедурно-генерируемые миры, шум Перлина совместно с алгоритмами псевдослучаных чисел остаются пожалуй самыми популярными и простыми. Я старался описать как можно более понятно, но допускаю, что всё равно слишком сложно для восприятия. Напишите в комментариях, если не понятно, буду дорабатывать блог. Ну а мы перейдём к следующему элементу случайности. Более подробно и в разы более интересно про процедурную генерацию можно узнать из видео ниже:

«Честная» и «нечестная» генерация предметов.

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

Давайте приведу условный пример: у вас есть игра в которой имеется 4 вида редкости какой-либо вещи: Обычный, редкий, эпический и легендарный. Вы подходите например к сундуку, откуда эти вещи вам выпадут и честной будет та система, где алгоритм случайности не изменяется разработчиками после релиза по желанию. То есть если вам выпал например легендарный предмет, то вам «повезло», так как в алгоритме выпало нужное число, если же нет, то вероятность на выпадение этого предмета не изменится исходя из прошлого полученного предмета.

Упрощённо эта система работает так: пусть вероятность выпадения предметов такая — обычный (70%), редкий (20%), эпический (9%), легендарный (1%). Всё это суммарно даёт 100% вероятность, и тогда алгоритм будет выглядеть так условно так: если случайно введённое число находится в промежутке от 0 до 70, выпадет обычный предмет, если от 71 до 90, выпадет редкий предмет, если от 91 до 99 то выпадет эпический предмет, а если введённое число 100 выпадет легендарный. Элементом рандома здесь и является это самое ввёденное число. Где же взять это рандомное число? Способов на самом деле масса: от ранее упомянутого seeda (просто брать последние два его числа), до прослушивания атмосферного шума и шума микрофона для его последующего преобразования в цифровой вид (так работает популярный сайт: Random.org).

00147.jpg5 IQ

Однако же StopGame — это игровой портал, поэтому давайте узнаем, как генерируются такие числа в двух, самых популярных игровых движках: Unity и Unreal Engine.

-В этих движках одним из методов используется «XorShift», который берёт за seed дату и время на ПК, потом преобразует полученное число в двоичную систему счисления, потом суммирует это число несколько раз со сдвигом вправо и влево, после полученное число обрезается по длине исходного и получается псевдослучайное число. Более понятно и подробно об этом способе рассказано в видео ниже.

Давайте теперь поговорим о «нечестной» генерации предметов.

Самое широкое распространение такой способ имеет в онлайн играх по типу: «Warface», «Overwatch» и «CS:GO». В них тоже используется принцип, основанный на вероятностях, как и в «честном» способе, только в отличие от него нечестный способ изменяет свою вероятность в зависимости от ранее полученных данных. Теперь языком попроще: если вам выпала «легендарная» вещь с шансом в 1%, то следующая «легендарная» вещь уже будет иметь шанс выпадения например 0.5% или менее, а вещи «обычной» с шансом в 70% наоборот поднимут свой шанс выпадения например до 80%, так после нескольких попыток открытия условных «кейсов в CS:GO» шанс будет повышаться, пока опять не достигнет своего максимума в 1%, а вероятность на выпадение «обычной» вещи не опустится до 70%.

00148.o65fo2vЕстественно нечестный способ, как правило, нужен для того, чтобы получить прибыль с игроков, ведь азарт и призрачная надежда на то, что «скоро уже выпадет легендарка, я чувствую» и заставляет игроков тратить деньги на подобного рода кейсы, рулетки, ставки и казино. Весь процесс контролируется разработчиками и они могут изменить параметры вероятностей в любой момент, так как все алгоритмы находятся на удалённом сервере. Давайте теперь поговорим о следующем элементе рандома.

Ситуации, где на элементах рандома завязана вся игра:

Я говорю про те игры, где ваша победа напрямую зависит от изначально (или в процессе) полученной случайной комбинации элементов. Самый яркий пример тому в реальной жизни — это игральные карты. Человек перемешивает карты руками, после раздаёт их на всех игроков. Но как карты может перемешать компьютер? На самом деле можно воспользоваться весьма странным, но рабочим методом: отслеживания перемещений стрелки мыши. (Не знаю, используется ли конкретно в конкретно карточных играх такой способ, но во многих проектах он присутствует). Компьютер отслеживает координаты X и Y, на которых сейчас находится мышь и берёт только по последней цифре от каждой координаты. Допустим стрелка мыши находится на координатах X=54 и Y=27. Алгоритм возьмёт для создания случайного числа только 4 (из числа 54) и 7 (из числа 27), далее функций может быть много, числа можно сложить, вычесть, умножить, разделить и получить любое другое новое псевдослучайное число. Далее карты нумеруются допустим от 0 до 36, сложим ранее полученные 4 и 7, получим 11, значит игроку достанется карта под номером 11 из колоды и так, пока игроки не получат нужное количество карт. Естественно отслеживаются все перемещения мыши допустим за минуту времени, так как если каждый раз смотреть на текущую координату мыши, псевдослучайное число всегда будет одним и тем же если мышь не двигается.

00149.wUQNKB6

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

Давайте перейдём к последнему элементу рандома, который я смог сформулировать.

Различные ситуации, которые должны возникать в рандомное время.

В пример можно привести дождь и грозу из того же «Minecraft». На самом деле там нет никакой случайности, периодичность дождей зависит от всё того же «злополучного» seedа, который создан при генерации мира. При определённых seedах период дождей изменяется, благодаря вычислениям по определённым формулам (которые «Mojang» не показывает). Грубо говоря в одном мире, с одним seed дожди происходят раз в игровых 5 дней, в другом же мире, с другим seed периодичность уже будет например раз в игровых 7 дней. Тут вообще нет никаких элементов рандома, всё происходит закономерно и по формулам.

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

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

Источник

Как компьютер генерирует случайные числа

Что такое случайность в компьютере? Как происходит генерация случайных чисел? В этой статье мы постарались дать простые ответы на эти вопросы.

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

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

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

Создание случайных чисел из семени

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

Давайте поэкспериментируем с этой идеей и посмотрим, куда она нас приведёт.

Функция искажения будет принимать одно значение, а возвращать другое. Назовём её R.

Числовой круг

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

1 4g7Sl3v 4NtPkbduzKoRrw

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

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

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали «прыжки» за счёт добавления, но что если использовать умножение? Умножим х на константу a.

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

Эти свойства вместе с правилом, что m и с должны быть взаимно простыми составляют теорему Халла-Добелла. Мы не будем рассматривать её доказательство, но если бы вы взяли кучу разных значений для разных констант, то могли бы прийти к тому же выводу.

Выбор семени

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

Конечный результат

Когда мы применяем функцию к её результату несколько раз, мы получаем рекуррентное соотношение. Давайте запишем нашу формулу с использованием рекурсии:

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

В разных языках программирования реализация линейного конгруэнтного метода отличается, то есть меняются значения констант. Например, функция случайных чисел в libc (стандартная библиотека С для Linux) использует m = 2 ^ 32, a = 1664525 и c = 1013904223. Такие компиляторы, как gcc, обычно используют эти значения.

Заключительные замечания

Существуют и другие алгоритмы генерации случайных чисел, но линейный конгруэнтный метод считается классическим и лёгким для понимания. Если вы хотите глубже изучить данную тему, то обратите внимание на книгу Random Numbers Generators, в которой приведены элегантные доказательства линейного конгруэнтного метода.

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

Источник

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

Введение

Как отличить случайную последовательность чисел от неслучайной?

Чуть более сложный пример или число Пи

0965ee61c195b3ecccc315b32b5c9847
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.

Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)

Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.

Уязвимости ГПСЧ

Линейный конгруэнтный ГПСЧ (LCPRNG)

Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

image loader

где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.

Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].

Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений

image loader

Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.

Предсказание результатов линейно-конгруэнтного метода

Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.

Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.

Взлом встроенного генератора случайных чисел в Java

Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы

Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)

Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).

Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:

до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так

Вывод данной программы будет примерно таким:

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

И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));

И всё, мы успешно взломали ГПСЧ в Java.

Взлом ГПСЧ Mersenne twister в PHP

Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.

Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:

10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor

Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так

Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.

Область для взлома

Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed’а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.

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

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

Треугольное распределение

Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.

image loader

Экспоненциальное распределение

Тесты ГПСЧ

Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.

Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.

В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.

Источник

Поделиться с друзьями
DOMA35.RU