d_n_trunov18 мая в 14:40

Тестирование случайности самодельного ГПСЧ и сравнение с эталонами

6 мин

11K

Комментарии 12

Просто запустите dieharder ($ ./simd | pv | dieharder -a -g 200), не страдайте фигнёй (но нужно будет ускорить алгоритм, тесты более требовательные к объёму данных, нужно где-то 250GiB на один запуск).

d_n_trunov 19 мая в 13:08

К dieharder ещё нужно созреть (хотя интерес имеется, конечно). Только меня как раз смущает "250GiB на один запуск". А то получится как в анекдоте:

Доктор: А для улучшения сна я Вам рекомендую на ночь бокал шампанского и тёплую ванну.
Пациент: Бокал шампанского - ещё куда ни шло. Но боюсь, что тёплую ванну я не выпью.

alvoskov 22 мая в 14:56

250 GiB для тестирования даже некриптографического ГПСЧ - это достаточно небольшая выборка. Тесты dieharder и NIST полезны, но не очень чувствительные и порой пропускают "игрушечные" генераторы, непригодные ни для каких количественных оценок. Современный стандарт испытаний некриптографических ГПСЧ - это PractRand на выборке хотя бы 1 ТиБ (а лучше 16-128 ТиБ) в сочетании с TestU01 (SmallCrush, Crush, BigCrush, там порядка сотен гигабайт надо)

Об интерпретации p-value статистических тестов: провал - это скорее значение вне интервала [1e-10, 1-1e-10], если видите просто подозрительные (вне интервала [0.01, 0.99] или даже скорее [0.001, 0.999]) - то просто перезапустите тест на большей выборке.

d_n_trunov 23 мая в 13:50

Спасибо за пояснения!

На Ваш другой комментарий я постараюсь ответить немного позже.

alvoskov 22 мая в 15:33

Пропробовал проверить Ваш генератор DeepRandFast с помощью своей батареи тестов SmokeRand (режим full, выборка около 2 ТиБ). Что удивительно - генератор прошёл тесты, а это значит, что дальше тестировать с помощью PractRand и TestU01 - затея вполне осмысленная. Вот результаты, там также есть портированный на C99 DeepRandFast. Правильно ли я его портировал? Процедуру инициализации максимально упростил, т.к. в get_seed64() у меня всё равно криптографический генератор реализован.

https://gist.github.com/alvoskov/09de2a0ddaa3d5c9b8698e50ae64c093

Разумеется, эти тесты - скорее базовые проверки на равномерность распределения, и не заменяют криптоанализа.

О самой конструкции ГПСЧ: он чем-то напоминает ISAAC. Период не меньше 2^64, т.к. в нелинейную часть "подмешивается" 64-битный счётчик. Но, насколько я понимаю, из-за возможной одинаковости индексов у Вас не гарантируется обратимость преобразования внутреннего состояния ГПСЧ (Вы его называете "ключом"), что может снижать его период.

d_n_trunov 23 мая в 19:48

Спасибо Вам за проявленный интерес к алгоритму и за тесты на 2 ТиБ! Честно сказать, результаты и меня удивили.

Правильно ли я его портировал?

Да, вполне. Я скомпилировал Ваш портированный DeepRandFast со своей версией в одной программе и несколько раз сгенерировал по 1 млн чисел с одинаковыми ключами. Разницы в генерациях не обнаружил.

Но, насколько я понимаю, из-за возможной одинаковости индексов у Вас не гарантируется обратимость преобразования внутреннего состояния ГПСЧ (Вы его называете "ключом"), что может снижать его период.

Да, реальный период может быть меньше максимально возможного. Максимальный я оцениваю в 2^(16384+64) чисел за счёт 2^16384 возможных варианта ключа и 2^64 возможных значений счётчика. Поскольку значений счётчика всегда 2^64, а снижаться может только количество вариантов ключей, то реальный период может находиться между 2^64 и максимальным.

alvoskov 25 мая в 08:27

Чтобы период был максимальным, нужно чтобы (а) состояние генератора могло бы быть получено только из одного состояния-предшественника (во многих случаях это легко доказать) (б) все состояния должны ложиться на один цикл (это хорошо доказывается или опровергается для LCG или LFSR, но не для нелинейных генераторов вроде Вашего). Для нелинейных генераторов существуют вероятностные оценки среднего периода, но они зависят от обратимости/необратимости функции перехода (обновления состояния генератора): https://www.pcg-random.org/posts/random-invertible-mapping-statistics.html -

d_n_trunov 25 мая в 19:36

Ещё раз спасибо за объяснения! Получается, в моём случае обоих пунктов одновременно достичь крайне сложно. И чтобы при этом не сломать что-то, что (возможно) неплохо работало. Допустим, сделать обратимой функцию перехода можно. Но чтобы все состояния легли на один цикл… я не представляю, как это сделать. С другой стороны, так ли уж важно добиться максимального периода? (просто мысль «вслух»)

А вот про вероятностные оценки довольно интересно. Если я правильно понял, в указанном Вами материале «Expected cycle length» означает среднюю длину цикла и она оценивается как 2^(B-1). И если B — это битовая длина состояния (ключа), то средний цикл в моём случае можно ожидать длиной 2^(16384-1) «узлов» (nodes). Опять же, если я правильно понял значение «Number of nodes on cycles < 2^k», то чем меньше взятое k, тем меньше «узлов» в их общем количестве и тем меньше вероятность на него попасть и наоборот. Значит, когда вероятность попасть на узел в коротком цикле становится более-менее значимой, то этот «короткий» цикл будет уже не таким уж и коротким. И получается, что при большом B уже не так важен максимальный период с единственным циклом, поскольку даже самый короткий цикл будет достаточно длинным. Ну, это если я правильно всё понял (и я учитывал только состояния ключа без состояния счётчика).

alvoskov 26 мая в 02:35

> означает среднюю длину цикла и она оценивается как 2^(B-1).

Это только для случай обратимого преобразования. Для необратимых там будет ближе к 2^(B/2) (более точные оценки есть в самой статье).

> поскольку даже самый короткий цикл будет достаточно длинным

Из-за линейной части (счётчика) он не будет короче 2^64. А насчет длины без счетчика - попробуйте заполнить нелинейную часть одними нулями и посмотрите, что будет (отключив счётчик).

> Но чтобы все состояния легли на один цикл… я не представляю, как это сделать.

Для LCG и LFSR (например, вихрь Мерсенна) длина периода доказывается математически, и если период максимален - это можно доказать без перебора. Для нелинейных генераторов вроде Ваше такого матаппарата обычно нет, и остается разве что перебор, который в Вашем случае невозможен.

d_n_trunov 26 мая в 20:09

Для необратимых там будет ближе к 2^(B/2)

Ну, 2^(B/2) тоже приемлемо, как по мне.

попробуйте заполнить нелинейную часть одними нулями и посмотрите, что будет (отключив счётчик)

То есть, ключ? Это интересно. Если обнулить ключ и отключить "подмешивание" счётчика при генерации, то в GenerateFast() ключ полностью перестаёт меняться - так и остаётся заполненный нулями. К счастью, в Generate() ключ всё-таки полностью меняется после каждых 256 генераций, даже если изначально заполнен нулями.

alvoskov 29 мая в 15:46

Ну, 2^(B/2) тоже приемлемо, как по мне.

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

То есть, ключ?

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

Ещё посмотрел на Ваши шифры (сразу скажу - я не криптограф) и обратил внимание вот на что:

Шифр с названием Seal уже был выпущен около 30 лет назад.
Не везде терминология является общепринятой: циклы обычно называют rounds (раунды, итерации), а Ваш номер блока - это скорее tweak. Русские термины, наверное. надо поискать в выпускаемой ТК26 открытой документации.
Не ясно происхождение значений сдвигов, а также таблицы замены.
Не вполне понятно, насколько это быстрее, чем аппаратно ускоренные AES или ChaCha.

d_n_trunov 29 мая в 18:55

В Вашем случае для обратимости преобразования достаточно обеспечить неодинаковость соответствующих индексов.

Хорошо, спасибо!

Шифр с названием Seal уже был выпущен около 30 лет назад

Жаль. Мне понравилось это название (и как-то же надо было назвать алгоритм). Не планировал сначала его публиковать, а потом так и оставил.

Не везде терминология является общепринятой

Спасибо за замечание!

Не ясно происхождение значений сдвигов, а также таблицы замены

Значения сдвигов я просто подбирал так, чтобы они не повторялись сами по себе и чтобы последовательное их сложение (по модулю 64) не дало сумму, равную любому из отдельных значений. А таблицу замены T для Seal я генерировал с помощью своего ESCK-7 (я его потом немного изменил, но таблицу менять не стал):

ESCK7 Cipher;
Cipher.KeyGenA("Seal", 10000);
uint64_t* T = Cipher.Key_data();

Не вполне понятно, насколько это быстрее, чем аппаратно ускоренные AES или ChaCha

Таких сравнений я не делал, но и цели обогнать AES или ChaCha по скорости не было.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий