Генератор псевдослучайных чисел большой разрядности

Генератор псевдослучайных чисел большой разрядности

Недавно появилась статья с описанием скоростного генератора случайных чисел (утверждается что самого быстрого в мире).

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

Далее в статье будет описан генератор сверхдлинных псевдослучайных чисел. Он базируется на криптографическом преобразовании “Русская Рулетка”. Генератор формирует числа длиной 2000h байт (восемь килобайт) со скоростью 12 ГигаБайт в секунду в один поток (на одном процессорном ядре).

Генератор собран на базе криптографического преобразования «РусскаяРулетка», которое было специально «заточено» под скоростную генерацию случайных чисел. Для этого из него исключена схема ввода ключей шифрования и соответственно удалена обратимость преобразования для формирования криптостойкой последовательности псевдослучайных чисел.

Тестовая последовательность (100 МегаБайт) получаемая в результате работы генератора полностью проходит статистические тесты NIST, DieHard.

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

Исходные числа содержат нулевые байты, кроме счетчика, который размещен в младших 8 байт.

Схема базового криптографического преобразования

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

Обьединение накопителей в 256 байтное число реализовано с использованием операции битового суммирования (XOR) в двух вариантах.

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

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

Вот как он реализован, регистры ymm0-ymm7 содержат 16 накопителей:

vperm2i128 ymm10,ymm0,ymm0,001h; поменять местами 1 и 16 накопители

vpxor ymm0,ymm0,ymm1;

vpxor ymm1,ymm1,ymm2;

vpxor ymm2,ymm2,ymm3;

vpxor ymm3,ymm3,ymm4;

vpxor ymm4,ymm4,ymm5;

vpxor ymm5,ymm5,ymm6;

vpxor ymm6,ymm6,ymm7;

vpxor ymm7,ymm7,ymm10; замкнуть кольцо модификаций

Изменений состояния единственного бита приводит к гарантированному 50% изменению всех битов во всех накопителях за 32 раунда работы кольцевой схемы, поэтому минимальный размер блока получается равен 32*256=8КилоБайт.

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

Вот код этого преобразования:

vpxor ymm1,ymm1,ymm0;

vpxor ymm2,ymm2,ymm1;

vpxor ymm3,ymm3,ymm2;

vpxor ymm4,ymm4,ymm3;

vpxor ymm5,ymm5,ymm4;

vpxor ymm6,ymm6,ymm5;

vpxor ymm7,ymm7,ymm6;

vperm2i128 ymm8,ymm7,ymm7,001h; поменять местами 1 и 16 накопители

vpxor ymm0,ymm0,ymm8; замкнуть кольцо модификаций

Изменений состояния единственного бита в этой схеме приводит к гарантированному 50% изменению всех битов во всех накопителях за 16 раундов работы кольцевой схемы,

Далее будут описаны криптографическое преобразование и процедура генерации псевдослучайного числа размером 8КилоБайт.

12 3 4 Следующая ⇒