[recovery mode] Генератор псевдослучайных чисел большой разрядности
Недавно появилась статья с описанием скоростного генератора случайных чисел (утверждается, что самого быстрого в мире).
Понятно, её автор не читает русскоязычных статей по теме, но если бы читал, то не стал бы утверждать о мировом первенстве своего генератора в скорости работы. Скорость генерации псевдослучайных чисел в 12 ГигаБайт/сек. была достигнута достаточно давно.Этот генератор применяется для выработки ключей шифрования.
Далее в статье будет описан генератор сверхдлинных псевдослучайных чисел. Он базируется на криптографическом преобразовании «Русская Рулетка».
Генератор формирует числа длиной 8192 байта со скоростью 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 для фиксированных. Поэтому такое криптопреобразование получило название «Русская Рулетка».
Формирование 4 КилоБайтного числа из 256 Байтного
Имея генератор с разрядностью 256 Байт, получить 8 КилоБайтное число — непростая задача. Сформировать 32 числа размером 256 Байт и сказать, что это 8 КилоБайтное число не получится.
Поясню на простом примере.
Пускай у нас есть несколько генераторов псевдослучайных чисел с разрядностью 32 бита (всего 4 миллиарда комбинаций). Как бы мы их не комбинировали в большое число, все равно через 4 миллиарда раундов это большое число повторится полностью…
Но это не все.
Есть еще одна искусственность при формировании чисел большой разрядности из более коротких. Значения выдаваемые любым генератором псевдослучайных чисел связаны между собой конкретной и одозначной зависимостью, когда последующие значения всегда функционально зависят от предыдущих.
Нам же нужно связать все псевдослучайные компоненты большого числа зависимостями так, чтобы значение любого компонента влияло на все остальные, а не только на последующие.
Проще говоря, у такого числа не должно быть начального и конечного компонента, все они должны быть в неразрывном кольце.
Поэтому нужно делать генератор на полную разрядность в 8 КилоБайт, используя более короткое криптопреобразование как базовый компонент. Для этого:
- исходный 8 КилоБайтный буфер шифруется блоками 256 Байт
- шифрование выполнено по схеме гаммирования с обратной связью
- такое шифрование производится в два прохода (по кольцу)
- в первом проходе используются модули с переменными кольцевыми сдвигами и закрепленными за нелинейными модулями накопителями
- во втором проходе используются фиксированные кольцевые сдвиги и кольцевой сдвиг накопителей относительно нелинейных преобразователей.
В такой схеме состояние любого бита зависит от всех остальных битов в выходном числе.
Разные криптопреобразования в проходах шифрования нужны для более равномерного распределения статистических параметров такого большого числа.
Такая схема формирования псевдослучайных чисел выдает последовательность со статистическими параметрами, полностью удовлетворяющими критериям случайности по версии NIST (отсутствуют выпадения из заданных диапазонов пропорций и значение Р не опускается ниже 0,002ххх)…
Тесты NIST разработаны для 64 битных генераторов и они при дефолтных настройках осуществляют усреднение параметров для 1 500 000 чисел в тестовой последовательности. В нашем же случае, генерируются числа длиной 8К, и усреднение статистических параметров осуществляется всего для 1500 чисел. И тем не менее, уже на такой небольшой выборке значений удается успешно пройти статистические тесты…
При этом обеспечивается скорость генерации случайных чисел на уровне 12 ГигаБайт/сек.
Реализация в тестовой программе
Эта достаточно громоздкая двухпроходная конструкция используется для формирования псевдослучайных чисел размером 8 КилоБайт со скоростью не менее 12 ГигаБайт/сек.
Исходные тексты и скомпилированная программа генерации псевдослучайных чисел доступны по ссылкам.
Феноменальная скорость достигается за счет большой разрядности регистров (32 байта) и конвейерной (параллельной) обработки команд.
Тестовый генератор использует команды AVX2, поэтому скорость работы зависит от конкретной модели процессора, а на «старых» процессорах может не работать, на «новых» процессорах скорость будет гораздо выше заявленных 12 ГигаБайт/сек.
На процессорах Intel шестой генерации (тестирование проводилось именно на них) скорость генератора определялась в первую очередь пропускной способностью памяти, а не частотой процессора.
На настоящий момент это самый быстрый генератор псевдослучайных чисел с самой большой разрядностью генерируемых чисел и самыми качественными статистическими параметрами по версии NIST.
Вот такой получился тройной рекордсмен…
Ну и по традиции, всем генераторам псевдослучайных чисел авторы присваивают имена, не будем отступать от этой традиции и окрестим его именем » RU-lette», от имени прародителя, а по-русски получается, что его имя «ру-лет»…
