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

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

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

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

Генерация случайных чисел используется для создания чисел или текста для captcha, шифрования, генерации "соли" для хранения паролей, генератора паролей, порядка карт в онлайн-казино, принятия решений, создания выборок и моделирования.

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

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

У нас имеется последовательность чисел: 1 , 2 , 3 , 4 , 5. Является ли она случайной?

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

Последовательность будет случайной только в том случае, если между символами нет никакой зависимости.

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

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

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

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

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

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

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

Генераторы истинно случайных чисел используют такие физические явления, как:

• радиоактивность,
• тепловой шум,
• электромагнитный шум,
• квантовая механика и другие.

Генераторы истинно случайных чисел широко используются в системах безопасности по всему миру и в некоторых формах шифрования.

Источники энтропии используются для накопления энтропии и последующего получения начального значения (seed), необходимого генераторам случайных чисел.

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

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

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

Любители скоростных видеоигр часто используют эту уязвимость - они называют это манипуляцией ГПСЧ. Они заставляют игру работать предсказуемо, чтобы пройти ее как можно быстрее. К счастью, это не влечет критических проблем.

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

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

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

Генератор Google

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

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

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

Чтобы реализовать генерацию чисел этим методом, нам нужно выбрать четыре числа:

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

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

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

0 ≤ X₀ ≤ m, начальное число

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

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...

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

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

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

QRBG121

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

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

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

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

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

HotBits

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

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

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

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

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

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

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

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

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

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

Вы бросаете пять игральных костей за один раз и записываете получившиеся числа. Кубики располагаются слева направо следующим образом: 63131. Далее вы открываете длинный список слов на сайте EFF, чтобы найти соответствующее слово рядом с 63131. Это слово - "turbofan".

Вы можете повторить эту процедуру несколько раз. Например, пять раз. В итоге у вас может получиться фраза из пяти слов. Например, "turbofan purge unfitting try pruning". Если вы знаете, как использовать правила мнемоники, вы можете запомнить фразы, подобные этим.

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

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

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