Что такое генератор случайных чисел?

  Для генерации действительно случайных чисел используют аппаратные генераторы случайных чисел (англ. Hardware random number generator — HRNG), или их еще называют генераторы истинно случайных чисел (англ. True random number generator — TRNG) — устройства, которые создают случайные значения, основываясь на хаотически изменяющихся свойствах физических процессов. Такие системы могут быть построены на использовании макроскопических случайных процессов, то есть в масштабе, позволяющем проводить измерения и наблюдения невооруженным глазом, например подбрасывание монетки, игральных костей или лототрона. Несмотря на то, что согласно ньютоновским законам механики, микроскопический процесс может быть полностью определен, хорошо сконструированный механизм, такой как колесо американской рулетки, будет выдавать непредсказуемый результат, который можно объяснить теорией хаоса и неустойчивостью динамических систем из-за разницы в начальных условиях каждой новой попытки. Основным недостатком генераторов с использованием макроскопических процессов всегда была их медленная скорость работы, и как результат — неспособности генерировать большое количество значений за определенный промежуток времени.   Сегодня аппаратные генераторы случайных чисел, как правило, используют устройства на основе микроскопических явлений, которые генерируют случайные низкоуровневые сигналы, такие как разного рода шумы (дробовой, тепловой, атмосферный), фотоэлектрический эффект и другие квантовые явления. Подобные процессы являются хорошими источниками энтропии, так как в теории их результат абсолютно невозможно спрогнозировать, но из-за сложности реализации и относительной медлительности работы, сфера использования таких генераторов ограничивается предметными областями с определенными требованиями к генерируемым значениям.
  В основном аппаратные генераторы случайных чисел применяются в криптографии для создания случайных криптографических ключей, чтобы обеспечить безопасную передачу данных, например в интернет-протоколах шифрования, таких как протокол защиты транспортного уровня (англ. Transport layer security — TLS).

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

  Альтернативой аппаратным (физическим) генераторам выступают генераторы на основе алгоритмов — генераторы псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator — PRNG), которые создают последовательность чисел со свойствами похожими на случайную последовательность. Числа сгенерированные ГПСЧ нельзя считать истинно случайными, так как они зависят от начального значения, которое не является случайным, но ряд преимуществ перед физическими генераторами, среди которых быстродействие, простота и относительная дешевизна реализации, делают такие генераторы широко применяемым во многих сферах. Существует много методов создания псевдослучайной последовательности числе, среди них можно выделить вихрь Мерсенна (англ. Mersenne Twister), линейный конгруэнтный метод (англ. linear congruential generator — LCG), Xorshift или генераторы регистров сдвига (англ. shift-register generator), WELL (англ. Well Equidistributed Long-period Linear) и другие.

Вихрь Мерсенна

  Самым распространенным универсальным ГПСЧ на сегодняшний день считается вихрь Мерсенна, который был разработан в 1997 году японскими учёными Макото Мацумото и Такудзи Нисимура. Название метода произошло от того, что длина его периода выбрана как простое число Мерсенна (Mersenne prime) — число вида . Данный генератор был разработан специально, чтобы решить основные недостатки тогдашних ГПСЧ, поэтому имеет ряд весомых преимуществ:

• Долгий период 2¹⁹⁹³⁷ — 1
• Успешно проходит множество тестов на статистическую случайность, включая тесты Diehard
• Разрешительная лицензия свободного ПО (англ. Permissive free software licence) и не содержит патентов для всех вариантов, кроме CryptMT
• k-распределение с 32-битной точностью для каждого 1 ≤ k ≤ 623
• Реализации обычно генерируют случайные числа быстрее, чем истинные случайные методы

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

ГПСЧ с источником энтропии

  Для задач криптографического шифрования, игровой индустрии и других, где важна как скорость генерации, так и истинная случайность начального значения, используются комбинированные устройств, которые сочетают в себе быстродействующий генератор псевдослучайных чисел и медленный, но совершенно непредсказуемый аппаратный генератор. Работает такой механизм следующим образом: физическое устройство, используя надежный источник энтропии (например, тепловой шум), генерирует начальное значение (англ. initial value, seed) для «псевдогенератора», который в свою очередь генерирует последующие числа, имея в начале высококачественное случайное значение. Именно такие комбинации криптостойкого ГПСЧ и внешнего источника энтропии на сегодняшний день являются распространенным решением для генерации случайных чисел.