для чего нужен генератор случайных чисел и как им пользоваться
Что такое ГСЧ – как работает генератор случайных чисел
Алгоритм генератора случайных чисел часто используется в видеоиграх, где он устанавливает разные результаты каждый раз, когда его запускают. Возможно, вы заметили, что даже если вы играете на одном уровне в игре, каждый раз, когда вы пытаетесь выполнить миссию, он не будет одинаковым. Различия не будут наблюдаться в локации или требованиях к миссии, но они будут наблюдаться в количестве приближающихся врагов и областях их появления, изменениях климата и различных препятствиях, которые встречаются между ними. Это делает игру более захватывающей и интересной.
В противном случае, после нескольких попыток игра покажется скучной, так как вы сможете предсказать события, которые произойдут дальше. Это может показаться простым, но для компьютера – генерировать случайные числа – это сложная задача, требующая следовать точным инструкциям, закодированным в нём.
Истинный ГСЧ против псевдо ГСЧ
Есть два типа генераторов случайных чисел: истинные и псевдо.
Какие приложения используют ГСЧ
Не во всех играх используется генератор случайных чисел, что делает их менее конкурентоспособными и часто утомительными, однако, новые игры почти всегда идут с генератором случайных чисел. Многие приложения и игры выигрывают от случайности, поскольку они могут приносить интерес и прибыль только в том случае, если они случайны:
Помимо игровых приложений, есть код случайных чисел в JavaScript, используемый разработчиками и кодировщиками во всём мире для включения генератора случайных чисел в их программы. У Google есть свой очень интересный инструмент, который также основан на теории случайных чисел JavaScript и может генерировать случайные числа. Этот инструмент может пригодиться, когда вы играете в игры с друзьями и семьей. Чтобы посмотреть ГСЧ Google, нажмите здесь.
Манипуляции с ГСЧ
Я уже обсуждал различия между истинным ГСЧ и псевдо ГСЧ и тот факт, что в играх используется псевдо ГСЧ, основанный на алгоритме. Некоторые увлеченные геймеры используют утилиты эмуляции для анализа игр и выявления лазеек, которые можно использовать для управления результатами, даже если используется алгоритм генератора случайных чисел.
ГСЧ на основе алгоритма использует начальное число, которое представляет собой комбинацию определенных факторов и генерирует результат в игре. Это применяемые законы математики, и поскольку 1+1 всегда равно 2, аналогично, если известны факторы в игре, которые приносят желаемый результат, то вы всегда можете достичь того же результата.
Например, если игра требует от игрока выбрать определенного персонажа с определенными усилениями, и результатом будет легкая битва с боссом, то этот шаблон будет постоянным, и все, кто выберет одни и те же варианты, будут иметь одинаковые результаты. Но, для обычного игрока это было бы невозможно, и псевдо-ГСЧ всегда казался бы истинным ГСЧ.
Почему геймеры ненавидят ГСЧ
Геймеров можно разделить на соревнующихся игроков, спидраннеров и средних игроков. Любой конкурентоспособный игрок, овладевший техникой игры и движениями, захочет бросить вызов другим игрокам и побеждать на основе навыков и, несомненно, возненавидит игру, если на результат повлияет генератор случайных чисел. Точно так же спидраннер хотел бы завершить игру как можно скорее, но алгоритм генератора случайных чисел включает тормоза, создавая каждый раз неизвестные и неожиданные сценарии в игре.
В идеале геймеры хотели бы уменьшить количество случаев, когда они сталкиваются со средством генерации случайных чисел в игре, чтобы держать весь игровой процесс и результат под своим контролем. Но, это возможно лишь до определенной степени. И когда геймер часами осваивает игрового персонажа и его движения, он больше всего расстраивается, когда случается что-то случайное, и вся стратегия нарушается. Иногда это тоже действует как благословение, но обычно это проклятие.
Кто такой RNGesus?
Обычные игроки, которые играют только для того, чтобы развлечься или скоротать время, не заботятся о результате игры. Но, опытные профессиональные игроки ненавидят проигрывать только потому, что удача была не в их пользу.
Игроки, которые проигрывают, часто винят в своих поражениях злой ГСЧ, который выгоден их противникам. Там где зло, должен быть Бог – RNGesus.
Среди геймеров во всем мире появился новый термин, RNGesus, который больше соответствует игре слов с «Иисусом». Поскольку Иисус Христос считается нашим спасителем в реальном мире, RNGesus – это вообразимая сущность, созданная для спасения игроков от пагубных последствий ГСЧ. Это нигде не доказывается, но началось как миф, а теперь распространилось по игровому сообществу, как лесной пожар.
Окончательный вердикт по ГСЧ – хорошо или плохо?
На этот вопрос сложно ответить, и определенно не может быть одного и того же ответа для всех. В то время как среднестатистические геймеры утверждают, что это хорошо, другим нравится соревновательный дух.
Алгоритм генератора случайных чисел действительно сохраняет непредсказуемость и интересность каждый раз, когда вы играете на одном уровне. Он стал важной частью многих игр, предлагая разнообразие, например, головоломки, карточные игры, ролевые игры и многие другие. Но, для геймеров, которые верят в навыки как в единственный способ пройти игру, ГСЧ подрывает их потенциал, когда вытаскивает что-то случайное из коробки.
Игры предназначены для развлечения и удовольствия. Если у вас хороший ГСЧ, вы сможете получить лучшие варианты, несмотря на низкие шансы. В случае плохого ГСЧ, вы получите худший результат, даже если вы играли в игру именно так, как должно. Правда в том, что это не то, что можно воспринимать так серьёзно, особенно если оно основано на алгоритме генератора случайных чисел.
Алгоритмы рандома
В этой статье вы увидите самые разнообразные велосипеды алгоритмы для генерации случайных чисел.
Про что статья
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’ах.
Избавляем игрока от раздражения: правильное использование случайных чисел
Если вам доведётся пообщаться с фанатом RPG, то вскоре вы услышите жалобы на рандомизированные результаты и лут, а также о том, насколько раздражающими они могут быть. Многие геймеры высказывают свою досаду, и пока некоторые разработчики придумывают инновационные решения, большинство по-прежнему заставляет нас проходить приводящие в ярость проверки на усидчивость.
Но есть способ и получше. Используя случайных чисел и их генерирование иным образом, мы можем создавать захватывающий игровой процесс, создающий «идеальный» уровень сложности, не выбешивая при этом игроков. Но прежде чем мы перейдём к этому, давайте рассмотрим основы генераторов случайных чисел (или RNG).
Генератор случайных чисел и его применение
Случайные числа встречаются нам повсюду и используются для добавления вариативности в ПО. В общем случае RNG обычно применяются для моделирования хаотических событий, демонстрации непостоянства или являются искусственным ограничителем.
Скорее всего, вы ежедневно взаимодействуете со случайными числами или результатами их действий. Они используются в научных опытах, видеоиграх, анимациях, искусстве и практически в каждом приложении компьютера. Например, RNG скорее всего реализован в простых анимациях в вашем телефоне.
Теперь, когда мы поговорили немного о RNG, давайте взглянем на их реализацию и узнаем, как применять их для улучшения игр.
Стандартный генератор случайных чисел
Почти в каждом языке программирования среди прочих функций есть стандартный RNG. Его работа заключается в возврате случайного значения в интервале двух чисел. В разных системах стандартные RNG можно реализовать десятками разных способов, но в общем случае они имеют одинаковый эффект: возвращают случайное число из интервала, каждое значение в котором может быть выбрано с одинаковой вероятностью.
В играх генераторы часто используются для симуляции бросков костей. В идеале они должны использоваться только в ситуациях, когда каждый из результатов должен возникать равное количество раз.
Если вы хотите поэкспериментировать с редкостью или разными степенями рандомизации, то вам больше подойдёт следующий способ.
Взвешенные случайные числа и слоты редкости
Этот тип RNG является основой для любой RPG с системой редкости предметов. В частности, он применяется, когда вам нужен рандомизированный результат, но некоторые значения должны выпадать с меньшей частотой, чем остальные. При изучении вероятностей в пример часто приводят мешок с шариками. При взвешенном RNG в мешке может быть три синих шарика и один красный. Так как нам нужен всего один шарик, мы получим или красный, или синий, но с большей вероятностью он будет синим.
Почему может быть важна взвешенная рандомизация? Давайте в качестве примера возьмём внутриигровые события SimCity. Если бы каждое событие выбиралось невзвешенными способами, то вероятность совершения каждого события статистически было бы одинаковым. То есть с одинаковой вероятностью вам бы предлагали открыть новое казино или происходило бы землетрясение. Добавив веса, мы можем сделать так, чтобы эти события происходили в пропорциональной вероятности, обеспечивающей хороший геймплей.
Виды и применения
Группировка одинаковых предметов
Во многих книгах по информатике такой способ называется «мешком». Имя говорит само за себя — классы или объекты используются для создания визуального представления мешка в буквальном смысле.
По сути, это работает так: есть контейнер, в который можно поместить объекты, функция для помещения объекта в «мешок» и функция для случайного выбора предмета из «мешка». Возвращаясь к нашему примеру с шариками, можно сказать, что наш мешок будет содержать синий, синий, синий и красный шарики.
С помощью этого способа рандомизации мы можем приблизительно задавать частоту возникновения результатов, чтобы усреднить игровой процесс для каждого игрока. Если мы упростим результаты до шкалы от «Очень плохо» до «Очень хорошо», то получим гораздо более приятную систему по сравнению с той, когда игрок может получить ненужную последовательность нежелательных результатов (например, результатов «Очень плохо» 20 раз подряд).
Однако статистически получить серию плохих результатов всё равно возможно, просто вероятность этого снизилась. Мы рассмотрим способ, который для снижения количества нежелательных результатов заходит немного дальше.
Вот краткий пример того, как может выглядеть псевдокод класса мешка:
Реализация слотов редкости
Слоты редкости — это способ стандартизации для задания частоты выпадания объекта (обычно используемый для упрощения процесса создания дизайна игры и вознаграждений игрока).
Вместо задания частоты каждого отдельного предмета в игре мы создаём соответствующую ему редкость — например, редкость «Обычный» может представлять вероятность определённого результата 20 к X, а уровень редкости «Редкий» — вероятность 1 к X.
Этот способ не сильно изменяет функцию самого мешка, зато может использоваться для увеличения эффективности на стороне разработчика, позволяя быстро назначить статистическую вероятность экспоненциально большому количеству предметов.
Кроме того, разделение редкости на слоты полезно для изменения восприятия игрока. Оно позволяет быстро и без необходимости возиться с числами понять, как часто должно происходить событие, чтобы игрок не терял интереса.
Вот простой пример того, как мы можем добавить в наш мешок слоты редкости:
Случайные числа с переменной частотой
Мы рассказали о некоторых из самых распространённых способов работы со случайностями в играх, поэтому давайте перейдём к более сложному. Концепция использования переменных частот начинается аналогично мешку из приведённых выше примеров: у нас есть заданное количество результатов, и мы знаем, насколько часто хотим их возникновения. Разница в реализации в том, что мы хотим изменять вероятность результатов при их возникновении.
Зачем нам это может понадобиться? Возьмём, например, игры с собиранием. Если у нас есть десять возможных результатов для получаемого предмета, когда девять являются «обычными», а один — «редким», то тогда вероятности очень просты: 90% времени игрок будет получать обычный предмет, а 10% времени — редкий. Проблема возникает тогда, когда мы учитываем несколько вытягиваний из мешка.
Давайте посмотрим на наши шансы получения серии обычных результатов:
Как эту проблему решают переменные частоты
Решение заключается в реализации в наших объектах интервала случайности. Для этого мы задаём максимальную и минимальную редкость каждого объекта (или слоты редкости, если вы хотите соединить этот способ с предыдущим примером). Например, давайте дадим нашему обычному предмету минимальное значение редкости 1, а максимальное — 9. Редкий предмет будет иметь минимальное и максимальное значение 1.
Теперь по показанному выше сценарию у нас будет десять предметов, девять из которых являются экземплярами обычного, а один — редким. При первом вытягивании есть вероятность 90% получения обычного предмета. При переменных частотах после вытягивания обычного предмета мы снижаем его значение редкости на 1.
При этом в следующем вытягивании у нас будет в целом девять предметов, восемь из которых обычные, что даёт вероятность 89% вытягивания обычного. После каждого результата с обычным предметом случайность этого предмета падает, что увеличивает вероятность вытягивания редкого, пока мы не останемся с двумя предметами в мешке, одним обычным и одним редким.
Таким образом, вместо вероятности 35% вытягивания 10 обычных предметов подряд у нас останется вероятность всего в 5%. Вероятность граничных результатов, таких как вытаскивание 20 обычных предметов подряд, снижается до 0,5%, а дальше становится и того меньше. Это создаёт постоянные результаты для игроков, и защищает нас от граничных случаев, в которых игрок постоянно вытягивает плохой результат.
Создание класса переменных частот
Самой простой реализацией переменной частоты будет извлечение предмета из мешка, а не просто его возвращение:
Хотя в такой простой версии проявляются некоторые проблемы (например, мешок постепенно переходит в состояние нормального распределения), она отображает незначительные изменения, позволяющие стабилизировать результаты рандомизации.
Развитие идеи
Мы описали основную идею переменных частот, но в собственных реализациях нам нужно рассмотреть ещё довольно много аспектов:
Менее скучные случайные числа
Во многих играх по-прежнему для создания сложности используется стандартное генерирование случайных чисел. При этом создаётся система, в которой половина игроков отклоняется в одну или другую сторону от ожидаемых результатов. Если оставить это без внимания, возникнет возможность граничных случаев со слишком большим количеством повторяющихся неудачных результатов.
Ограничивая интервалы разброса результатов, мы можем обеспечить более целостный игровой процесс и позволить получать от неё удовольствие большему количеству игроков.
Как работает новый генератор случайных чисел Intel
Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.
К сожалению, ваша первая покупка в интернете была скомпрометирована с самого начала: вскоре обнаружится, что якобы безопасный протокол, по которому браузер установил соединение, на самом деле не очень защищён.
Проблема в том, что секретные ключи, которые использовал Netscape, были недостаточно случайными. Их длина составляла всего 40 бит, что означает около триллиона возможных комбинаций. Это кажется большим числом, но хакерам удалось взломать эти коды, даже на компьютерах 1990-х годов, примерно за 30 часов. Якобы случайное число, которое Netscape использовал для генерации секретного ключа, базировалось всего на трёх значениях: времени суток, идентификационном номере процесса и идентификационном номере материнского процесса — все они являются предсказуемыми. Из-за этого злоумышленник имел возможность сократить количество вариантов для перебора и найти нужный ключ гораздо раньше, чем предполагали в Netscape.
Программисты Netscape с радостью бы использовали полностью случайные числа для генерации ключа, но не знали, как их получить. Причина в том, что цифровые компьютеры всегда находятся в точно определённом состоянии, которое меняется только при поступлении определённой команды от программы. Самое лучшее, что вы можете сделать — эмулировать случайность, генерируя так называемые псевдослучайные числа с помощью специальной математической функции. Набор таких чисел на первый взгляд выглядит полностью случайным, но кто-нибудь другой с помощью такой же процедуры может легко сгенерировать в точности такие же числа, так что обычно они плохо подходят для шифрования.
Исследователям удалось изобрести генераторы псевдослучайных чисел, которые признаны криптографически надёжными. Но их нужно запускать с качественного случайного начального значения (random seed), иначе они всегда сгенерируют один и тот же набор чисел. И для этого начального значения вам нужно нечто такое, что действительно невозможно подобрать или предсказать.
К счастью, несложно получить действительно непредсказумые значения, используя хаотическую вселенную, которая со всех сторон окружает строго детерминированный мир компьютерных битов. Но как именно это сделать?
В течение последних лет в онлайне работает источник случайных чисел под названием Lavarand. Он был создан в 1996 году для автоматической генерации случайных значений путём обработки фотографий декоративного светильника — лавовой лампы, которая непредсказуемым образом меняет облик каждую секунду. С тех пор случайными значениями из этого источника воспользовались более миллиона раз.
Есть и более изощрённые аппаратные генераторы случайных чисел, которые регистрируют квантовые эффекты, например, удары фотонов в зеркало. Вы можете на самом обычном компьютере получить случайные числа путём регистрации непредсказуемых событий, таких как точное время нажатия на кнопки клавиатуры. Но чтобы получить большое количество таких случайных значений, придётся нажать немало кнопок.
Мы с коллегами в компании Intel решили, что нужно сделать более простой способ. Вот почему уже более десяти лет многие из чипсетов нашего производства содержат аналоговый аппаратный генератор случайных чисел. Проблема в том, что его аналоговый контур впустую расходует энергию. Вдобавок, трудно сохранить работоспособность этой аналоговой схемы по мере совершенствования техпроцесса по производству микросхем и их миниатюризации. Поэтому сейчас мы разработали новую и полностью цифровую систему, которая позволяет микропроцессору генерировать обильный поток случайных значений без этих проблем. Скоро этот новый цифровой генератор случайных чисел придёт к вам вместе с новым процессором.
Первая попытка Intel сделать лучший генератор случайных чисел на обычных ПК датируется 1999-м годом, когда компания Intel представила компонент Firmware Hub для чипсетов. Генератор случайных чисел в этом чипе (PDF) представляет собой аналоговый дизайн на базе кольцевого осциллятора, который регистрирует тепловой шум с резисторов, усиливает его и использует результирующий сигнал для изменения периода относительно медленного генератора тактовых импульсов. На каждый непредсказуемый «тик» этого медленного генератора микросхема накладывала частоту колебаний второго, быстрого генератора, который регулярно меняет своё значение между двумя бинарными состояниями: 0 и 1. В результате получается непредсказуемая последовательность нулей и единиц.
Проблема в том, что кольцевой осциллятор, который занимается усилением теплового сигнала, потребляет слишком много энергии — и он работает постоянно, независимо от того, нужны или нет компьютеру случайные числа в данный момент. Эти аналоговые компоненты также доставляют неудобства каждый раз, когда компания меняет техпроцесс производства микросхем. Каждые несколько лет компания модернизирует производственные линии, чтобы делать микросхемы в более миниатюрном масштабе. И каждый раз этот аналоговый фрагмент нужно по-новому калибровать и тестировать — эта сложная и кропотливая работа стала настоящей головной болью.
Вот почему в 2008 году Intel принялась за разработку генератора случайных чисел, который работает исключительно на цифровой основе. Исследователи компании в Хиллсборо (Орегон, США), совместно с инженерами Design Lab в Бангалоре (Индия) начали изучать ключевую проблему — как получить случайный поток битов без использования аналоговых схем.
Забавно, но предложенное ими решение нарушает основное правило цифрового дизайна, что схема должна всегда быть в определённом положении и возвращать либо логический 0, либо 1. Конечно, цифровой элемент может проводить краткосрочные промежутки времени в неопределённом положении, переключаясь между этими двумя значениями. Однако, он должен работать предельно чётко и никогда не должен колебаться между ними, иначе это вызовет задержки или даже сбой в системе. В нашем же генераторе случайных битов колебания являются фичей, а не багом.
НЕОПРЕДЕЛЁННЫЕ СХЕМЫ: Когда транзистор 1 и транзистор 2 включаются, пара инвертеров поворачивают узлы Node A и Node B в одинаковое положение [налево]. Если возрастает тактовая частота [жёлтый график справа], эти транзисторы отключаются. Первоначально оба инвертера обращаются в неопределённое положение, но случайный тепловой шум в инвертерах скоро поворачивает один узел в логическое положение 1, а другой узел — в логическое положение 0.
Дизайн состоит из пары инвертеров — элементов цепи, у которых значение на выходе является обратным значению на входе. Мы соединили выход одного инвертера со входом другого инвертера. Если на выходе у первого инвертера 0, то второй инвертер получает это на входе и, соответственно, выдаёт 1. Или если первый инвертер выдаёт 1, то второй инвертер будет выдавать 0.
Дополнительно в цепь к двум инверторам добавлены два транзистора с довольно странным местоположеием. Включение этих транзисторов даёт на входе и на выходе обоих инвертеров логическую 1. Конечно, инвертеры пришлось слегка модифицировать, чтобы такой фокус стал возможным, но это довольно просто сделать.
Самое интересное начинается, когда транзисторы отключают. Двум инвертерам не нравится, что у них на выходах одинаковое состояние, и они стремятся принять противоположное положение, то есть одно из двух устойчивых состояний. Но какой инвертер поменяется на 0? Это неизвестно.
Есть две вероятности, и цепь выбирает между ними. В идеальном мире статус-кво может сохраняться вечно, но в реальности даже минимальное воздействие теплового шума — случайных атомных вибраций — сталкивает цепь в одно из двух возможных устойчивых состояний.
В данном случае, наша простая цифровая схема с лёгкостью получает частичку вездесущной случайности природы. Всё что нам остаётся — подключить генератор тактовых импульсов, который будет регулярно включать и выключать транзисторы. На каждый такт генерируется один случайный бит.
Этот цифровой подход к генерации случайных битов работал бы хорошо, если бы инвертеры были абсолютно одинаковыми. Но из-за несовершенства физического мира так никогда не бывает. В реальности, два инвертера никогда не бывают абсолютно одинаковыми. Отличия в их характеристиках могут казаться чрезвычайно маленькими, но в данном применении эти отличия способны легко скомпрометировать случайный поток битов, который мы пытаемся извлечь из цепи.
Чтобы соблюсти сбалансированность инвертеров, мы встроили механизм обратной связи, чтобы схема соответствовала одному из правил статистической случайности, в соответствии с которым в длинной последовательности должно быть одинаковое количество всех возможных чисел. Таким образом, мы можем бороться с предсказуемостью, которая внушает такой ужас любому криптологу.
Одновременно с разработкой надёжного цифрового источника случайных чисел, другие инженеры Intel начали разработку дополнительных логических элементов, чтобы эффективно обрабатывать и использовать эти биты. Вы могли бы подумать, что процессор способен просто принимать сырой поток битов из генерирующего контура и вставлять их в программу. Но на самом деле эти биты не настолько случайны, как хотелось бы. Сырой поток из контура, независимо от качества оборудования, в любом случае может иметь какие-то перекосы в ту или иную сторону.
Нашей целью было создать систему, которая выдаёт поток случайных чисел, соответствующий признанным криптографическим критериям, таким как стандарты Национального института стандартов и технологий США. Чтобы гарантировать качество наших случайных чисел, мы разработали трёхступенчатый процесс, в котором задействованы первоначальная цифровая схема, «нормализатор» (conditioner) и генератор псевдослучайных чисел — теперь известный под кодовым названием Bull Mountain.
Наш предыдущий аналоговый генератор был способен выдавать только пару сотен килобит случайных чисел в секунду, в то время как новый генерирует их потоком около 3 Гб/с. Он начинает работу, собирая практически случайные значения двух инвертеров блоками по 512 бит. В дальнейшем эти блоки разбиваются на пары 256-битных чисел. Конечно, если оригинальные 512 бит не полностью случайны, эти 256-битные числа тоже не будут полностью случайными. Но их можно математически скомбинировать таким образом, чтобы получить 256-битное число, близкое к идеальному.
ТРИ УРОВНЯ ЧИСЕЛ: Генератор случайных чисел Intel Bull Mountain предотвращает любые варианты предсказуемости с помощью трёхступенчатого процесса. Сначала цифровой контур генерирует поток случайных битов. Потом «нормализатор» (conditioner) генерирует на основе этого потока хорошие случайные начальные значения (random seeds). На третьем этапе генератор псевдослучайных чисел выдаёт поток цифр для использования в программном обеспечении.
Всё это лучше показано на простой иллюстрации. Предположите на секунду, что генератор случайных битов выдаёт 8-битные комбинации, то есть как бы числа в диапазоне от 0 до 255. Предположите также, что эти 8-битные числа не полностью случайны. Теперь представьте, что, к примеру, какой-то неуловимый изъян в цепи смещает выдаваемые значения в нижнюю часть диапазона. На первый взгляд, поток случайных чисел кажется хорошим, но если вы обработаете миллионы значений, то заметите, что числа из верхней части диапазона встречаются немножко реже, чем числа из нижней части.
Одно из возможных решений этой проблемы простое: всегда берите пару 8-битных чисел, перемножайте их, а потом отбрасывайте верхние восемь бит из получившегося 16-битного числа. Такая процедура устранит перекос практически целиком.
Bull Mountain не работает с 8-битными числами: он работает, как уже было сказано, с 256-битными числами. И он их не перемножает, а производит более сложные криптографические операции. Но основная идея та же самая. Вы можете представить этот этап как «нормализацию» по устранению тех отклонений от случайного распределения чисел, которое может возникнуть в схеме с двумя инвертерами.
Нам действительно хочется хорошо спать по ночам, так что спроектировали дополнительную схему, которая проводит тестирование потоков 256-битных чисел, которые поступают в «нормализатор», чтобы они не были слишком смещёнными в какую-то сторону. Если такое обнаруживается, мы помечаем его как бракованный и не соответствующий стандартам. Таким образом, операции производятся только с качественными парами чисел.
Гарантированной случайности недостаточно, если случайные значения не выдаются достаточно быстро, чтобы соответствовать стандартам. Хотя аппаратный контур генерирует поток значительно быстрее, чем его предшественники, этого всё ещё недостаточно для некоторых современных задач. Чтобы Bull Mountain мог выдавать случайные числа так же быстро, как выдают поток программные генераторы псевдослучайных чисел, но при этом сохранять высокое качество случайных чисел, мы добавили ещё один уровень в схему. Здесь 256-битные случайные числа используются как криптографически надёжные начальные значения (random seeds) для генерации большого количества псевдослучайных 128-битных чисел. Поскольку 256-битные числа поступают с частотой 3 ГГц, то гарантируется достаточное количество материала для быстрой генерации криптографических ключей.
Новая инструкция под названием RdRand даёт возможность программе, которой нужны случайные числа, обратиться с запросом к аппаратному обеспечению, которое их производит. Созданная для 64-битных процессоров Intel, инструкция RdRand — это ключ к генератору Bull Mountain. Она извлекает 16-, 32- или 64-битные случайные значения и помещает их в регистр, доступный для программы. Инструкция RdRand была открыта для публики около года назад, и первым процессором Intel, который будет поддерживать её, станет Ivy Bridge. Новый чипсет работает на 37% быстрее, чем его предшественник, а размер его минимальных элементов уменьшен с 32 до 22 нанометров. Общее увеличение производительности хорошо сочетается с потребностями нашего генератора случайных чисел.
Хотя лавовые лампы выглядят круто, они впишутся не в каждый интерьер. Мы думаем, что наш подход к генерации случайных чисел, напротив, найдёт самое универсальное применение.
Как уже было упомянуто, регистрация точного времени нажатия на клавиши использовалась как удобный источник случайных стартовых значений для генераторов в прошлом. Для тех же целей использовали передвижения мыши и даже скорость поиска секторов на жёстком диске. Но такие события не всегда дают вам достаточное количество случайных битов, и при определённом времени измерений эти биты становятся предсказуемыми. Хуже того, поскольку мы теперь живём в мире серверов с SSD и виртуализацией, эти физические источники случайностей просто недоступны на многих компьютерах. На этих машинах требуется получать случайные числа каким-то другим способом, а не событиями на периферийных устройствах. Bull Mountain предлагает решение.
Так что если вы программист, будьте готовы к появлению обильного источника случайности прямо под рукой. И даже если вы не хотите отказываться от любимого генератора псевдослучайных чисел, который привыкли использовать для криптографии, научных вычислений или даже в играх — у вас теперь есть Bull Mountain для получения начальных значений к нему. Мы ожидаем, что такое применение Bull Mountain будет весьма популярным, в результате чего вырастут и расцветут разные виды замечательного софта.