Генератор псевдослучайных чисел большой разрядности
Недавно появилась статья с описанием скоростного генератора случайных чисел (утверждается что самого быстрого в мире).
Понятно, её автор не читает русскоязычных статей по теме, но если бы читал, то не стал бы утверждать о мировом первенстве своего генератора в скорости работы. Скорость генерации псевдослучайных чисел в 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КилоБайт.
Нелинейный модуль преобразования
Нелинейный модуль преобразования во многом аналогичен используемому в Российском шифраторе «Магма» (бывший ГОСТ 28147-89) но имеет размер 16байт. Нелинейный модуль выполняет операции перестановки и кольцевого сдвига.
Сначала выполняется перестановка, индексы 16байтовой перестановки задаются в алгоритме, для каждого модуля используется собственная перестановка.
Затем выполняется кольцевой сдвиг фрагментов накопителя, сдвиги используются двух типов.
Первый тип использует фиксированные коэффициенты сдвига, для каждого накопителя, они задаются в алгоритме. Кольцевые сдвиги выполняются над 2байтными фрагментами накопителя. Внутри каждого накопителя все сдвиги одинаковые.
Второй тип кольцевого сдвига использует в качестве коэффициента сдвига переменное значение из накопителя сдвинутого в кольце нелинейных преобразователей на 8 позиций. Кольцевые сдвиги выполняются над 4байтными фрагментами 16байтного накопителя. Коэффициенты сдвига берутся из первого байта каждого 4байтного слова.
Соответственно в таком модуле используется 4 сдвига с не предсказуемыми и различными коэффициентами сдвига.
Сами циклические сдвигатели реализуют функцию частичной инверсии. Если в старшем разряде сдвигателя находится единичный бит, то старшие разряды инвертируются, число инвертируемых разрядов равняется числу коэффициента сдвига.
Вот реализация модуля с переменным кольцевым сдвигом:
vperm2i128 ymm8,ymm0,ymm0,001h; запомнить с обменом местами накопители
vpshufb ymm0,ymm0,[r14+0100h]; две перестановки по 16 байт каждая
vpand ymm8,ymm8,[r14]; обнуление в двойных словах разрядов 5-31
vpsubb ymm12,ymm15,ymm8; обратное значение для кольцевого сдвига
vpsravd ymm8,ymm0,ymm8; сдвиг с размножением знакового разряда
vpsllvd ymm0,ymm0,ymm12; сдвиг на освобожденные места
vpxor ymm0,ymm0,ymm8; суммирование с частичным инвертированием
В регистре ymm15 содержится значение 020h в каждом двойном слове
По адресу [r14+0100h] содержатся индексы перестановки
По адресу [r14] содержится восемь масок сдвига со значением 01fh
Вот реализация модуля с фиксированным кольцевым сдвигом:
vpshufb ymm1,ymm1,[r14+0100h]; две перестановки по 16 байт каждая
vpsraw ymm14,ymm1,5; сдвиг с размножением знакового разряда
vpsllw ymm1,ymm1,16-5; сдвиг на освобожденные места
vpxor ymm1,ymm1,ymm14; суммирование с частичным инвертированием
vpxor ymm1,ymm1,ymm2; суммирование накопителя с предшествующим
Если подсчитать общее количество кольцевых сдвигов в одном раунде преобразования, то их будет 4*16=64 для переменных сдвигов и 8*16=96 для фиксированных. Поэтому такое криптопреобразование получило название «Русская Рулетка».