Распространенные генераторы случайных чисел, какой из них следует использовать?
В информатике для генерации случайных чисел используется несколько методов. Вот несколько популярных:
- Линейный конгруэнтный генератор (LCG)
- Твистер Мерсенна
- Хоршифт
- ХОРОШО (хорошо, равнораспределенное, линейное, длиннопериодное)
- PCG (перестановочный конгруэнтный генератор)
(Когда требуется высокий уровень безопасности, например, для криптографии, эти методы не следует использовать. Вместо этого следует использовать криптографический генератор случайных чисел, например, предоставляемый Web Crypto API.)
Здесь я расскажу об их сильных и слабых сторонах и о том, где их использовать в вашем проекте.
1. Линейный конгруэнтный генератор (LCG)
LCG — один из старейших и самых известных алгоритмов генератора псевдослучайных чисел. Теория, стоящая за ними, относительно проста для понимания, и они легко и быстро реализуются.
Где использовать: они хороши для простых приложений, которым нужны случайные числа, но не предъявляют высоких требований к качеству случайности, например, для базовых компьютерных симуляций или игр. Их преимущество в том, что они быстрые и требуют очень мало памяти.
Преимущества: простота реализации, быстрота и мало памяти.
Слабые стороны: подходит не для всех приложений из-за низкой случайности. Младшие биты чисел, генерируемых LCG, заметно менее случайны, чем старшие биты.
Загрузка ЦП/памяти и скорость: Очень низкая загрузка ЦП и памяти, очень быстро.
function LCG(seed) {
const a = 1664525;
const c = 1013904223;
const m = Math.pow(2, 32);
let state = seed;
return function() {
state = (a * state + c) % m;
return state / m;
};
}
const lcg = LCG(123);
console.log(lcg());
2. Мерсенн Твистер
Вихрь Мерсенна имеет период 2¹⁹⁹³⁷-1 итерации и является одним из наиболее тщательно протестированных существующих генераторов случайных чисел. Однако он не подходит для криптографии.
Где использовать. Это полезно для приложений, которым требуется много случайных чисел с высококачественной случайностью, таких как моделирование методом Монте-Карло или процедурная генерация в видеоиграх.
Сильные стороны: отличные статистические свойства, длительный период.
Слабые стороны: относительно медленный, не подходит для криптографии.
Загрузка ЦП/памяти и скорость: умеренная загрузка ЦП и памяти, относительно низкая.
// Mersenne Twister
let MersenneTwister = require('mersenne-twister'); //npm package
let generator = new MersenneTwister();
console.log(generator.random());
3. Хоршифт
Xorshift RNG — это класс генераторов псевдослучайных чисел, открытых Джорджем Марсалья. Они генерируют следующее число в своей последовательности, многократно беря исключающее или числа со сдвинутой битовой версией самого себя.
Где использовать. Как правило, они очень быстры и используют очень мало памяти, что делает их подходящими для приложений, которым быстро требуется много случайных чисел и не предъявляются очень высокие требования к случайности, например в некоторых компьютерных графических приложениях. или приложений для моделирования.
Преимущества: просто, быстро.
Слабые стороны: Не подходит для криптографических целей, относительно короткий период по сравнению с другими генераторами.
Загрузка ЦП/памяти и скорость: Низкая загрузка ЦП и памяти, высокая скорость.
class XorShift {
constructor(seed = 1) {
this.state = seed;
}
next() {
this.state ^= this.state << 13;
this.state ^= this.state >> 17;
this.state ^= this.state << 5;
return this.state / Math.pow(2, 32);
}
}
let xorShift = new XorShift(123);
console.log(xorShift.next());
4. ХОРОШО
Генератор WELL совершенствует вихрь Мерсенна, решая некоторые из его проблем и обеспечивая более качественные статистические данные.
Где использовать. Подходит для приложений, которым требуется большое количество высококачественных случайных чисел и которые могут позволить себе более высокие вычислительные затраты, например, для научного моделирования или сложной процедурной генерации в играх.
Сильные стороны: улучшенные статистические качества по сравнению с Mersenne Twister.
Слабые стороны: более сложный и медленный, чем некоторые другие алгоритмы.
Загрузка ЦП/памяти и скорость: средняя или высокая загрузка ЦП и памяти, относительно низкая.
// WELL
let WELL = require('well-rng'); //npm package
let well = new WELL();
console.log(well.random());
5. PCG (перестановочный конгруэнтный генератор)
Семейство PCG представляет собой набор простых, быстрых, компактных и высококачественных генераторов случайных чисел. Это относительно недавнее дополнение к миру алгоритмов ГСЧ.
Где использовать. Они подходят для широкого спектра приложений, включая игры, симуляции и статистическую выборку, особенно там, где важен баланс между случайностью хорошего качества и скоростью.
Сильные стороны: высококачественные случайные числа, быстрота и компактность.
Слабые стороны: немного сложнее, чем самые простые алгоритмы (например, LCG или Xorshift).
Загрузка ЦП/памяти и скорость: загрузка ЦП и памяти от низкой до умеренной, высокая.
// PCG
let PCG = require('pcg-random');//npm package
let pcg = new PCG();
console.log(pcg.random());
Криптографические приложения требуют случайных чисел, которые являются непредсказуемыми и равномерно распределенными. Некриптографические генераторы случайных чисел, подобные упомянутым выше, предназначены для скорости и статистической случайности. Они не предназначены для того, чтобы противостоять тому, кто активно пытается предсказать следующее число, имея полное знание алгоритма и некоторые выходные данные, что является требованием для криптографических целей.
Уязвимости
Статистические генераторы случайных чисел (также известные как генераторы псевдослучайных чисел, PRNG) не являются действительно случайными; они детерминированы и работают по заданному алгоритму. При достаточном выходе этих генераторов или знании их состояния в определенный момент теоретически возможно предсказать их будущую продукцию. Вот некоторые известные методы предсказания:
- Расширение компрометации состояния: если злоумышленник знает внутреннее состояние PRNG, он может предсказать все будущие результаты. Это может произойти, если они могут прочитать память вашего программного обеспечения или заставить его вывести свое внутреннее состояние.
- Анализ выходных данных. Выходные данные PRNG часто содержат шаблоны или предубеждения, которые можно использовать для прогнозирования их будущих результатов. Если злоумышленник имеет доступ к достаточно длинной последовательности выходных данных ГПСЧ, он часто может предсказать будущие выходные данные. Для некоторых ГПСЧ это проще, чем для других.
- Отслеживание с возвратом: некоторые PRNG подвержены атакам с откатом, когда прошлый вывод генератора может быть выведен из текущего вывода. Это особенно важно для PRNG, которые используются для генерации криптографических ключей.
Ключевые выводы
- Качество случайности, скорость и использование памяти связаны друг с другом и могут различаться в зависимости от реализации и использования.
- Криптографически безопасные генераторы случайных чисел обычно работают медленнее своих незащищенных аналогов из-за дополнительных шагов, предпринимаемых для обеспечения безопасности.
- Период PRNG — это длина последовательности до того, как она начнет повторяться. Более длительный период, как правило, лучше, но обычно достаточно любого периода, достаточно длинного, чтобы последовательность не повторялась в течение ожидаемого времени выполнения программы.
Помните, что достижение истинной случайности в компьютерной среде представляет собой серьезную проблему из-за присущей ей детерминированной природы. Следовательно, многие так называемые генераторы случайных чисел (ГСЧ) на самом деле являются генераторами псевдослучайных чисел (ГСЧ), производящими последовательности, которые лишь приблизительно соответствуют истинной случайности. Важно знать, что взгляды на эти алгоритмы, в том числе на те, которые считаются «безопасными», со временем могут измениться. Это изменение может быть вызвано развитием технологий, новыми методами атак или увеличением вычислительной мощности.
Кроме того, уязвимости могут возникать из-за ошибок программирования или ошибок в выбранном алгоритме или его конкретной реализации. Поэтому крайне важно быть в курсе и регулярно обновлять свои знания о выбранном алгоритме и его конкретном пакете или реализации. Тем самым вы гарантируете, что ваш генератор случайных чисел сохранит свою целостность и надежно выполнит свои функции.
