Генератор чисел

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

Использование генераторов случайных чисел

Генерация случайных чисел — неотъемлемая часть множества повседневных и сложных IT-задач, от видеоигр до масштабных веб-приложений. Например, сайты используют рандомайзеры для показа случайных баннеров или ротации рекламных блоков. В криптографии ГСЧ критически важны для создания уникальных шифров и безопасных ключей доступа.

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

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

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

Представьте последовательность чисел: 1 , 2 , 3 , 4 , 5. Можно ли назвать ее случайной?

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

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

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

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

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

Для проверки надежности алгоритмов Национальный институт стандартов и технологий США (NIST) разработал специальный «Пакет статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений». Он включает 15 строгих тестов, оценивающих степень хаотичности битов, создаваемых аппаратными и программными рандомайзерами.

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

Глобально выделяют два типа систем: генераторы истинно случайных чисел (ГИСЧ, или TRNG) и генераторы псевдослучайных чисел (ГПСЧ, или PRNG). Первые используют для получения данных непредсказуемые физические явления, вторые — математические алгоритмы.

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

В качестве источников энтропии для ГИСЧ выступают:

• радиоактивный распад;
• тепловой шум;
• электромагнитный шум;
• квантово-механические флуктуации и другие физические явления.

Генераторы истинно случайных чисел — это золотой стандарт для систем кибербезопасности и криптографического шифрования во всем мире. Данные от физических источников накапливаются для формирования стартового значения (seed), на основе которого алгоритм выдает абсолютно непредсказуемый результат.

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

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

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

Эту уязвимость активно используют спидраннеры (игроки, проходящие видеоигры на скорость) — они называют этот процесс «манипуляцией ГСЧ» (RNG manipulation). Заставляя игру вести себя предсказуемо, они экономят время на прохождение. В гейминге это не вызывает критических проблем.

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

Если хакер узнает seed-значение, использованное для создания RSA-ключей в TLS-сертификатах, он сможет расшифровать весь проходящий сетевой трафик. Это означает, что пароли, данные банковских карт и личная переписка окажутся в руках злоумышленников.

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

Генератор Google

У поисковой системы Google есть собственный удобный генератор случайных чисел, написанный на JavaScript. Этот встроенный инструмент отлично подойдет для настольных игр в кругу семьи или для проведения быстрых розыгрышей. Чтобы его найти, достаточно ввести в строке поиска Google запрос «генератор случайных чисел».

Линейно-конгруэнтный метод

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

Для настройки генерации этим методом необходимо задать четыре целочисленных параметра:

m > 0, модуль (остаток от деления)

0 ≤ a ≤ m, множитель

0 ≤ c ≤ m, приращение

0 ≤ X₀ ≤ m, начальное значение (seed)

Сама последовательность псевдослучайных чисел вычисляется по следующей формуле:

Xₙ₊₁ = (aXₙ + c) mod m

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

Например, если взять следующий набор:

X₀ = 3, a = 4, c = 5, m = 6

Мы получим короткую, зацикленную последовательность:

3, 5, 1, 3, 5, 1

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

X₀ = 2, a = 85, c = 507, m = 1356

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

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Хотя линейно-конгруэнтный генератор (LCG) способен выдавать статистически качественную последовательность чисел, он уязвим. Алгоритмы на его основе предсказуемы, поэтому их категорически запрещено применять в криптографии.

Уязвимость линейных конгруэнтных генераторов впервые доказал Джим Ридс в 1977 году, а в 1982 году криптограф Джоан Бояр усовершенствовала взлом, успешно атаковав не только линейные, но также квадратичные и кубические генераторы. Тем самым они доказали полную непригодность конгруэнтных методов для защиты данных. Тем не менее, этот алгоритм остается крайне востребованным в некриптографических сферах, например, в статистическом моделировании или играх. Он работает исключительно быстро и успешно проходит большинство базовых эмпирических тестов на случайность.

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

QRBG121

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

Лавовые лампы

В штаб-квартире IT-компании Cloudflare в Сан-Франциско установлена эффектная стена из аппаратных генераторов случайных чисел, известных как «лавовые лампы». Внутри таких ламп находится прозрачное масло и подкрашенный полупрозрачный парафин. Лампа накаливания на дне колбы нагревает содержимое, заставляя парафин хаотично всплывать и опускаться, создавая постоянное, непредсказуемое движение фигур.

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

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

HotBits

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

Квантовые флуктуации в вакууме

Вопреки своему названию (от лат. vacuus — пустой), вакуум нельзя считать абсолютной пустотой. Согласно принципу неопределенности Гейзенберга, в нем непрерывно рождаются и мгновенно исчезают виртуальные частицы.

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

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

Генератор из углеродных нанотрубок

Данный инновационный метод объединяет микроскопические размеры с использованием теплового шума в качестве источника энтропии. Исследователи разработали аппаратный ГСЧ на базе ячейки статической памяти с произвольным доступом (SRAM). Ячейка печатается специальными чернилами с добавлением полупроводниковых углеродных нанотрубок и улавливает естественные колебания теплового шума, трансформируя их в случайные биты данных.

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

Кубики и Electronic Frontier Foundation (EFF)

Правозащитная организация Electronic Frontier Foundation (EFF) предложила гениально простой метод создания сверхнадежных паролей с помощью самого доступного физического рандомайзера — игральных костей.

Суть метода: вы бросаете сразу пять игральных кубиков и записываете выпавшую комбинацию. Если кубики слева направо показали 6, 3, 1, 3, 1, вы получаете число 63131. Затем вы открываете специальный длинный список слов (Diceware) на сайте EFF и находите слово, закрепленное за номером 63131. Допустим, это слово «turbofan».

Повторив процедуру пять раз, вы сгенерируете криптографически стойкую парольную фразу из пяти случайных слов. Например: «turbofan purge unfitting try pruning». Используя базовые правила мнемоники, подобные фразы на удивление легко запомнить, при этом их практически невозможно взломать.

Квантовый генератор случайных чисел из смартфона Nokia

В 2014 году исследователи из Женевского университета создали портативное устройство QRNG, использовав для этого камеру обычного смартфона Nokia N9.

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