Случайность компьютеру не дана: числа выдаёт алгоритм от стартового семени (seed), поэтому ряд называют псевдослучайным. Линейный конгруэнтный метод, вихрь Мерсенна, ББШ, Ярроу и Fortuna покрывают путь от компилятора до криптографии – период вихря доходит до 219937 – 1 значений. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов разбирают пять алгоритмов, созданных с 1949 по 1999 год, и цену подмены.
В основе электронно-вычислительных машин лежат числовая логика, математика и информатика. Мыслить произвольно, как человек, компьютер не умеет. А расчёты в разных сферах то и дело требуют непредсказуемой последовательности.
Учёные обошли препятствие несколькими методами: каждый выдаёт ряд значений, где соседи выглядят несвязанными. Генератор псевдослучайных чисел – алгоритм, который строит такой ряд по строгой формуле и всё же имитирует случай.
Работа любого генератора начинается с семени (seed) – числа, от которого разворачивается вся последовательность. Простейшее семя – текущее время в секундах. Продвинутый вариант снимает показание физического датчика и стартует с полученной величины.
Линейный конгруэнтный метод
Линейный конгруэнтный метод предложил математик Деррик Лемер в 1949–1951 годах. Алгоритм подходит для простых случаев и встроен в стандартные компиляторы, но криптографической стойкости не даёт.
Суть метода – формула:
,
где a – множитель из диапазона 0 ≤ a < m, c – приращение при 0 ≤ c < m, x0 – стартовое число, тоже меньшее m. Запись mod m означает остаток от деления: результат скобок делят на m, а хвост становится очередным членом последовательности.
Период последовательности – число элементов, после которого значения повторяются в том же порядке, – не превышает m, а значит ряд предсказуем. Зато алгоритм работает быстро, требует мало памяти и легко ложится на любой язык программирования.
Вихрь Мерсенна
Вихрь Мерсенна создали японские учёные Макото Мацумото и Такудзи Нисимура в 1997 году. Период последовательности равен числу Мерсенна (Mn = 2n – 1). Популярная версия MT19937 повторяется через 219937 – 1 значений, то есть примерно через 4,3 · 106001.
Числа вихря Мерсенна проходят статистические тесты DIEHARD на качество генерации. Для криптографии ряд приходится дополнительно прогонять через алгоритм хеширования.
Равномерное распределение алгоритм держит сразу в 623 измерениях. «Внутрянка» – матрицы, биты и сдвиги: результат складывается в векторы, которые читаются как псевдослучайные целые числа заданного периода.
Криптографические генераторы
Криптографические генераторы защищают саму последовательность. Даже зная несколько элементов ряда, злоумышленник не предскажет ни предыдущие, ни следующие значения.
Источником энтропии часто служат физические датчики: снятое показание становится основой расчёта. Второй способ – табличный генератор с ячейками, заполненными заранее из случайного диапазона, вот только запаса хватает на один раз.
Алгоритм Блюм – Блюма – Шуба
Алгоритм придумали в 1986 году супруги Блюм – Ленора и Мануэль – вместе с Майклом Шубом. Расчёт опирается на бит чётности, который контролирует правильность двоичного числа, либо на младший бит – крайний правый разряд с наименьшим весом.
,
где p и q – простые числа, желательно крупные: тысячи, десятки тысяч и выше. M – произведение p и q, а mod M – остаток от деления квадрата xn на M.
Метод ББШ (в английском написании BBS) ценят в криптографии за стойкость, которую обеспечивает высокая вычислительная сложность. Расплата – низкая скорость работы.
Простое число делится без остатка только на единицу и на себя. Именно простые числа берут за основу операций в алгоритмах генерации псевдослучайных значений.
Алгоритм Ярроу (Yarrow)
Ярроу создали в 1999 году Брюс Шнайер, Джон Келси и Нильс Фергюсон. Название пришло от тысячелистника обыкновенного (achillea): стебли растения служили для гаданий. Стойкость пускает алгоритм в чувствительные сферы – электронные подписи, шифрование, проверку целостности.
Алгоритм состоит из четырёх элементов:
- Накопитель энтропии
- Механизм усложнения
- Механизм генерации
- Механизм управления усложнением.
Сначала накопитель собирает случайные состояния – энтропию. Данные ложатся в два пула памяти: быстрый и медленный. Быстрый питает частые усложнения ключа, медленный – редкие, но существенные правки.
Затем механизм усложнения передаёт энтропию генератору и создаёт ключ шифрования. Узел сам решает, когда ключ пора обновить, и берёт свежие данные из быстрого или медленного пула.
Механизм генерации выдаёт ряд псевдослучайных чисел, который расшифровывает ключ предыдущего этапа. Без ключа программы видят обычный набор случайных битов.
В заключение механизм управления оценивает энтропию каждого источника. Как только счётчик доходит до предельной отметки, содержимое усложняется данными из соответствующего пула.
Алгоритм Fortuna
Fortuna – доработка Ярроу, сделанная Брюсом Шнайером и Нильсом Фергюсоном. Механизм собран из трёх частей: генератор чисел, аккумулятор энтропии от физических источников и система управления файлом начального числа, которая выручает после перезагрузки устройства.
Сигналы внешнего и внутреннего мира алгоритм раскладывает по 32 пулам подряд. Дальше содержимое перемешивается по расписанию: чаще всего в первом пуле, реже в паре, ещё реже в нескольких. Последние пулы приходят в движение крайне редко.
Готовая порция уходит в генератор на шифрование и возвращается псевдослучайной последовательностью чисел. Ключом служит значение предыдущей итерации программы.
Выбор упирается в задачу: простым расчётам хватит линейного конгруэнтного метода, статистике нужен вихрь Мерсенна, а шифрам и подписям – только криптостойкие ББШ, Ярроу и Fortuna. Подмена одного другим обходится дорого: предсказуемый ряд обесценивает любую защиту.