Самодельный генератор псевдослучайных чисел (ГПСЧ) стал побочным продуктом работы над любительским шифром, а шифры для меня всего лишь хобби и поле для творчества и экспериментов. Поскольку в своём шифре я делал упор на заранее непредсказуемые динамические связи, которые зависят от промежуточных состояний шифра, сама собой напросилась идея о применении этой непредсказуемости для генерации псевдослучайных чисел. Нужно было лишь оценить степень случайности полученного генератора. Как выполнялась оценка, что показали тесты NIST и сравнение с известными «эталонами» — далее в статье.
Первые тесты и их результаты
Первичные проверки случайности своего генератора я выполнял с помощью нескольких простых тестов, но они не давали полной картины и нужно было что‑то более основательное. Выбор пал на комплекс из 15 тестов случайности NIST SP 800–22, а на GitHub нашлась подходящая реализация на Python без лишних зависимостей и необходимости установки: скачал, запустил и получил результат. Данные для анализа принимаются в виде файла, потому для проверки необходимо генерировать числа проверяемым ГПСЧ, сохранять их в файл и передавать этот файл тестирующей программе.
Сколько данных нужно для корректного анализа? Поиск выдал рекомендацию: минимум 1 млн бит. В описании к реализации тестов приводится пример анализа файлов с размером 1 Mibibit (= 131 072 байта). Исходя из этого я решил взять близкий размер 1 280 000 бит (= 160 тыс байт), что составляет 20 тыс сгенерированных 64-битных чисел. Больше брать не стал, поскольку реализация тестов на Python довольно медленная и ждать тестирования слишком больших файлов пришлось бы довольно долго.
Итак, первый запуск: создаю массив на 20 тыс чисел, заполняю его с помощью своего генератора, сохраняю в файл и отправляю на тестирование. Немного жду, получаю результат и — о, чудо! — все тесты пройдены. Даже не верилось пройти тесты NIST с первого раза. Но ладно, для проверки генерирую ещё несколько файлов, запускаю тестирование и… для некоторых файлов обнаруживаю провалы в каком‑то из 15 тестов (каждый раз в разном).
Из поиска: «вероятность того, что истинно случайная последовательность не пройдет конкретный тест (ложный провал), составляет 1% » и «поскольку пакет включает 15 различных тестов, общая вероятность того, что хотя бы один из них даст ложный провал для хорошего ГПСЧ теоретически может достигать ~14-15%». Значит, допустимо получить не более одного провала в тестах 6 независимых файлов, но я получал 2–3 провала на каждые 6 файлов. Это недостаток самого ГПСЧ или реализации тестов?
Тестирование шифра
Если ГПСЧ основан на шифре, то казалось логичным проверить «случайность» самого шифра: взять произвольный ключ, зашифровать заполненный нулями байтовый массив (160 тыс байт), сохранить в файл и выполнить тесты. И так несколько файлов с разными ключами. А результаты получились такие же: 2–3 провала на 6 файлов. Уже можно было признать, что проблема в самом шифре (и основанном на нём генераторе), но смущал факт, что чаще всего проваливался не какой‑то один тест из 15, а каждый раз разный. Стали появляться сомнения в тестах, но вначале нужно было более тщательно проверить сам шифр.
Я взял несколько ключей, с которыми были провалы при шифровании нулей, и зашифровал этими ключами массивы, заполненные значениями 0×01, 0×02, 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).
Дополнение от 04.07.2026
Только после запуска тестов SmokeRand уважаемого @alvoskov я в полной мере понял, насколько важно было выбрать правильный инструмент тестирования случайности. С помощью скрипта make_pkg.sh (входит в комплект) я собрал deb‑пакет для smokerand и установил на своём дистрибутиве Linux. Далее тесты запускались с помощью «конвейера» (pipe):
/MyGenerator | smokerand brief stdin64
Батарея brief, например (25 тестов, ~68 ГБ данных), на моей машине выполнялась даже быстрее, чем 15 тестов NIST на Python для 160 тыс байт. И больше никаких плясок с ложными провалами.
