Алгоритм Fortuna

В качестве генератора можно использовать любой безопасный блочный шифр (в книге «Практическая криптография» предлагаются такие шифры, как AES (Rijndael), Serpent и Twofish) в режиме счётчика. Иными словами, в ответ на каждый запрос пользователя/приложения генератор производит псевдослучайные данные посредством шифрования последовательных натуральных чисел (значений счётчика). При этом в качестве исходного ключа используется начальное число, а после каждого запроса происходит обновление ключа: алгоритм генерирует 256 бит псевдослучайных данных с помощью старого ключа и использует полученное значение в качестве нового ключа. Это делается для того, чтобы злоумышленник не смог узнать предыдущие состояния генератора, даже если ему стало известно текущее состояние после очередного запроса. Кроме того, блочный шифр в режиме счётчика производит неповторяющиеся 16-байтовые блоки с периодом 2¹²⁸ в то время, как в истинных случайных данных при таких длинах последовательности с большой вероятностью должны встречаться одинаковые значения блоков. Поэтому для улучшения статистических свойств псевдослучайной последовательности максимальный размер данных, которые могут быть выданы в ответ на один запрос, ограничивается 2²⁰ байт (при такой длине последовательности вероятность найти одинаковые блоки в истинно случайном потоке составляет порядка 2⁻⁹⁷).

Аккумулятор собирает истинно случайные данные из внешних источников энтропии и равномерно распределяет их по 32 пулам (англ. pool).

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

Каждый источник энтропии распределяет события равномерно и циклически по 32 пулам ${\displaystyle P_{0},P_{1},\ldots ,P_{31}}$. Добавление события в пул означает его конкатенацию с уже имеющейся в пуле строкой. Всякий раз, когда объём содержимого пула ${\displaystyle P_{0}}$ становится достаточно большим, происходит обновление начального числа (то есть ключа шифрования) генератора посредством хеширования содержимого одного или нескольких пулов, причём пул ${\displaystyle P_{0}}$ участвует в каждом обновлении, пул ${\displaystyle P_{1}}$ — в каждом втором обновлении, пул ${\displaystyle P_{2}}$ — в каждом четвёртом обновлении и так далее. Таким образом, каждый последующий пул используется реже предыдущего и успевает накопить большее число энтропии. Это позволяет автоматически отражать атаки, при которых злоумышленник обладает информацией о части источников энтропии — рано или поздно происходит обновление ключа, задействующее энтропии больше, чем способен предсказать криптоаналитик. При этом можно показать, что время автоматического восстановления системы после атаки превосходит минимально возможное не более, чем в 64 раза (последнее справедливо, вообще говоря, только в случае, когда в системе имеется достаточное число пулов; для выполнения этого условия Fortuna требует производить обновления не более 10 раз в секунду: если бы существовал 33-й пул, при данной частоте обновлений он был бы впервые использован не ранее, чем через 13 лет после начала работы алгоритма).

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