Самодельный генератор псевдослучайных чисел (ГПСЧ) стал побочным продуктом работы над любительским шифром, а шифры для меня всего лишь хобби и поле для творчества и экспериментов. Поскольку в своём шифре я делал упор на заранее непредсказуемые динамические связи, которые зависят от промежуточных состояний шифра, сама собой напросилась идея о применении этой непредсказуемости для генерации псевдослучайных чисел. Нужно было лишь оценить степень случайности полученного генератора. Как выполнялась оценка, что показали тесты NIST и сравнение с известными «эталонами» — далее в статье.
Первые тесты и их результаты
Первичные проверки случайности своего генератора я выполнял с помощью нескольких простых тестов, но они не давали полной картины и нужно было что-то более основательное. Выбор пал на комплекс из 15 тестов случайности NIST SP 800-22, а на GitHub нашлась подходящая реализация на Python без лишних зависимостей и необходимости установки: скачал, запустил и получил результат. Данные для анализа принимаются в виде файла, потому для проверки необходимо генерировать числа проверяемым ГПСЧ, сохранять их в файл и передавать этот файл тестирующей программе.
Сколько данных нужно для корректного анализа? Поиск выдал рекомендацию: минимум 1 млн бит. В описании к реализации тестов приводится пример анализа файлов с размером 1 Mibibit (= 131072 байта). Исходя из этого я решил взять близкий размер 1280000 бит (= 160 тыс байт), что составляет 20 тыс сгенерированных 64-битных чисел. Больше брать не стал, поскольку реализация тестов на Python довольно медленная и ждать тестирования слишком больших файлов пришлось бы довольно долго.
Итак, первый запуск: создаю массив на 20 тыс чисел, заполняю его с помощью своего генератора, сохраняю в файл и отправляю на тестирование. Немного жду, получаю результат и — о, чудо! — все тесты пройдены. Даже не верилось пройти тесты NIST с первого раза. Но ладно, для проверки генерирую ещё несколько файлов, запускаю тестирование и… для некоторых файлов обнаруживаю провалы в каком-то из 15 тестов (каждый раз в разном).
Из поиска: «вероятность того, что истинно случайная последовательность не пройдет конкретный тест (ложный провал), составляет 1% » и «поскольку пакет включает 15 различных тестов, общая вероятность того, что хотя бы один из них даст ложный провал для хорошего ГПСЧ теоретически может достигать ~14-15%». Значит, допустимо получить не более одного провала в тестах 6 независимых файлов, но я получал 2-3 провала на каждые 6 файлов. Это недостаток самого ГПСЧ или реализации тестов?
Тестирование шифра
Если ГПСЧ основан на шифре, то казалось логичным проверить «случайность» самого шифра: взять произвольный ключ, зашифровать заполненный нулями байтовый массив (160 тыс байт), сохранить в файл и выполнить тесты. И так несколько файлов с разными ключами. А результаты получились такие же: 2-3 провала на 6 файлов. Уже можно было признать, что проблема в самом шифре (и основанном на нём генераторе), но смущал факт, что чаще всего проваливался не какой-то один тест из 15, а каждый раз разный. Стали появляться сомнения в тестах, но вначале нужно было более тщательно проверить сам шифр.
Я взял несколько ключей, с которыми были провалы при шифровании нулей, и зашифровал этими ключами массивы, заполненные значениями 0x01, 0x02, 0xfe и 0xff. Получил много файлов: несколько для зашифрованных взятыми ключами единиц, несколько для зашифрованных двоек и т. д. Для всех файлов выполнил тесты и результаты опять не выявили какой-то закономерности: если зашифрованные конкретным ключом нули проваливают какой-то тест, то зашифрованные другие значения могли или пройти все 15 тестов NIST, или провалить какой-то другой из 15 (не тот, который проваливался на зашифрованных нулях).
Ещё раз взял те же «провальные» ключи и зашифровал ими нули, но в 10 раз больше — 1,6 млн байт вместо 160 тыс. Запустил тесты (это было долго) и снова часть файлов тесты полностью прошла, а в другой части провал по какому-то из тестов и опять не по тому, по которому проваливалась более короткая версия файла. Те же результаты, если поменять количество циклов шифрования (оно нефиксированное и легко меняется). По крайней мере, теперь можно осторожно допустить, что отдельные провалы появляются хаотично, а не выявляют какой-то явный недостаток шифра (или недостаток у шифра имеется, но проявляется локально на небольшом объёме данных).
Сравнение с «эталонами»
Пусть и хаотично, но собственные ГПСЧ и шифр проваливают тесты случайности NIST чаще приемлемого. А как пройдут те же тесты «эталоны» — проверенные генераторы и шифры? В качестве эталонного генератора был взят знаменитый Mersenne Twister (std::mt19937_64), а шифры под рукой оказались только в составе gpg (взял AES256, TWOFISH и GRASSHOPPER). Сгенерировал несколько файлов с помощью mt19937_64, а для шифров создавал заполненные нулями файлы и зашифровал их без сжатия с помощью gpg:
gpg -c --cipher-algo AES256 --compress-algo none File00.bin
gpg -c --cipher-algo TWOFISH --compress-algo none File10.bin
gpg -c --cipher-algo GRASSHOPPER --compress-algo none File20.bin
Техническую информацию (заголовки GPG) из файлов я удалять не стал, посчитав её влияние несущественным на фоне 160 тыс зашифрованных байтов. То есть, выполнял тесты зашифрованных файлов без какой-либо их модификации. На удивление сгенерированные с помощью mt19937_64 и (отдельно) зашифрованные с помощью gpg файлы показали приблизительно такие же результаты тестов: 2-3 провала на 6 файлов. Радует хотя бы то, что мои алгоритмы в этом смысле выглядят не хуже.
Завершающие тесты
Но всё же почему так много провалов при тестировании даже проверенных алгоритмов? Может, я выбрал не те алгоритмы? Тогда я решил выполнить более тщательное тестирование ещё одного эталона — данных из /dev/urandom. В этот раз я стал тщательно отмечать количество провалов по 15 тестам NIST для каждого из файлов и помещать их в таблицу, вычисляя также общий процент провалов. Заодно выполнил тесты для QrandomGenerator::global() и ещё раз для mt19937_64. Полученная таблица приведена ниже:
Алгоритм | Файлы 1-6 | Файлы 7-12 | Файлы 13-18 | Провалы, % |
/dev/urandom | 0 0 0 0 0 0 | 0 0 0 1 0 2 | 1 0 1 0 0 1 | 2,22% |
QRandomGenerator | 0 0 0 0 1 3 | 0 0 1 0 0 0 | 0 0 0 0 2 0 | 2,59% |
mt19937_64 | 0 0 0 0 0 0 | 0 0 0 0 0 0 | 0 1 0 0 0 0 | 0,37% |
Магия? В этот раз mt19937_64 прошёл все тесты практически без единого провала, хотя в прежние запуски провалов было много (они точно были!), а «главный эталон» /dev/urandom провалил непозволительно много тестов. Возможно, для подобных тестов нужно намного больше файлов (50-100) или это должны были быть более длинные файлы (сотни миллионов байт вместо одного миллиона бит). Но главный для себя вывод я сделал: мои ГПСЧ и шифр проходят NIST SP 800-22 не хуже проверенных аналогов. В качестве подтверждения (и для сравнения с предыдущей таблицей) ниже приводится таблица провалов завершающих тестов своего ГПСЧ:
Алгоритм | Файлы 1-6 | Файлы 7-12 | Провалы, % |
ГПСЧ | 2 0 0 0 1 1 | 0 0 0 0 1 0 | 2,78% |
ГПСЧ (дубль 2) | 1 0 0 0 0 0 | 1 0 1 0 0 0 | 1,67% |
ГПСЧ (дубль 3) | 0 0 0 0 0 0 | 3 0 0 1 0 0 | 2,22% |
ГПСЧ (быстрый) | 0 0 0 0 0 0 | 1 1 0 0 0 1 | 1,67% |
Сравнение скорости генерации
Упомянув в таблице «ГПСЧ (быстрый)» я имел в виду отдельный режим своего генератора, адаптированный для более быстрого вычисления, возможно, в ущерб качеству генерации. Однако, судя по результатам тестов, генерируемые в этом режиме числа не выглядят менее случайными. Но раз уж речь зашла о скорости, то было интересно сравнить оба режима между собой, а также с другими распространёнными генераторами.
Для сравнения скорости на C++ была написана программа, замеряющая время заполнения выбранными генераторами массива из 10 млн 64-битных чисел. Компиляция программы с оптимизациями (-O2). Чтение из /dev/urandom всего массива целиком, замер времени без учёта открытия и закрытия файла. Вызов getrandom() также для всего массива целиком (с флагом GRND_NONBLOCK). Типичные результаты приведены в таблице ниже (по возрастанию времени):
Алгоритм | Время, мс |
Собственный ГПСЧ (быстрый) | 106 |
std::mt19937_64 | 125 |
Собственный ГПСЧ (обычный) | 194 |
getrandom() | 360 |
/dev/urandom | 362 |
QRandomGenerator::global() | 428 |
QRandomGenerator::system() | 8205 |
Заключение
Был соблазн сделать также подробное описание тестируемого генератора, но статья и так уже получилась достаточно длинной. Тем не менее, исходный код генератора на C++ доступен на GitFlic, а шифр, на котором генератор основан, описан в отдельной статье. А по результатам описанных тестов можно сделать следующие выводы:
тесты случайности NIST SP 800-22 могут давать ложные провалы даже для заведомо качественных ГПСЧ;
собственный ГПСЧ проходит данные тесты не хуже некоторых «эталонов»;
при этом, оба режима ГПСЧ имеют вполне неплохую скорость, которая для быстрого режима превосходит даже Mersenne Twister (mt19937_64).