NIST SP 800-22

NIST SP 800-22 — это серия стандартов и рекомендаций Национального института стандартов и технологий США (NIST), описывающая набор статистических тестов для проверки качества генераторов случайных и псевдослучайных чисел (ГСЧ/ГПСЧ). Официальное название документа — «A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications». Стандарт является одним из наиболее авторитетных и широко используемых инструментов для оценки криптографической стойкости генераторов случайных чисел.

История создания

Разработка NIST SP 800-22 началась в конце 1990-х годов в ответ на растущие требования к криптографической безопасности. В 1999 году NIST опубликовал первую версию документа, которая включала 16 статистических тестов. Основной целью было создание единого, стандартизированного набора тестов, который мог бы использоваться как разработчиками, так и независимыми экспертами для оценки качества ГСЧ.

В 2010 году вышла вторая редакция (Revision 1a), которая уточнила методологию проведения тестов, исправила некоторые ошибки и добавила новые рекомендации. В 2015 году была опубликована третья редакция (Revision 2), которая, помимо прочего, включила тест «Non-overlapping Template Matching Test» в расширенном виде. Наиболее актуальная на 2024 год версия — Revision 2, хотя NIST периодически выпускает уточняющие документы и исправления.

Назначение и область применения

NIST SP 800-22 предназначен для проверки гипотезы о том, что последовательность битов, генерируемая устройством или программой, является случайной. Стандарт не даёт абсолютной гарантии случайности, но позволяет с высокой степенью уверенности выявить статистические аномалии, которые могут указывать на наличие закономерностей или предсказуемости.

Основные области применения включают:

• Криптография: проверка ГСЧ, используемых для генерации ключей, векторов инициализации, одноразовых номеров (nonce) и других криптографических материалов.
• Моделирование и симуляция: оценка качества случайных чисел в научных вычислениях, статистическом моделировании (метод Монте-Карло), машинном обучении.
• Тестирование оборудования: проверка аппаратных генераторов случайных чисел (TRNG), основанных на физических процессах (шум диодов, тепловой шум, квантовые эффекты).
• Стандартизация и сертификация: использование в рамках процедур сертификации криптографических модулей (например, FIPS 140-3).

Состав набора тестов

Набор NIST SP 800-22 включает 15 статистических тестов, каждый из которых проверяет определённое свойство случайной последовательности. Тесты делятся на две основные категории: тесты, проверяющие равномерность распределения, и тесты, проверяющие независимость битов.

Основные тесты

Дополнительные тесты

Помимо 15 основных, в NIST SP 800-22 также описаны вспомогательные процедуры, такие как тест на корреляцию между последовательностями (например, для проверки независимости битов, генерируемых разными источниками).

Методология проведения тестов

Процедура тестирования по NIST SP 800-22 включает несколько этапов:

1. Формирование выборки: создаётся одна или несколько длинных последовательностей битов (обычно от 10^6 до 10^9 бит). Рекомендуется использовать не менее 1000 последовательностей длиной 1 млн бит каждая.
2. Выбор параметров: для каждого теста задаются параметры (например, длина блока, размер шаблона). NIST рекомендует стандартные значения, но допускает их изменение при условии документирования.
3. Вычисление P-value: для каждой последовательности вычисляется значение P-value (вероятность получить наблюдаемый результат при условии, что последовательность случайна). P-value лежит в диапазоне [0,1].
4. Принятие решения: если P-value ≥ α (обычно α = 0,01), то последовательность считается прошедшей тест (гипотеза о случайности не отвергается). Если P-value < α, тест считается непройденным.
5. Анализ совокупности результатов: для набора последовательностей вычисляется доля прошедших тест (должна быть не менее 0,96 при α=0,01) и равномерность распределения P-value (проверяется критерием согласия, например, χ²-тестом).

Критика и ограничения

Несмотря на широкое распространение, NIST SP 800-22 имеет ряд ограничений, которые неоднократно отмечались в научной литературе:

• Неполнота набора: тесты не охватывают все возможные виды статистических аномалий. Например, они неэффективны против некоторых типов детерминированных атак, основанных на анализе структуры ГПСЧ.
• Зависимость от длины выборки: короткие последовательности (менее 10^5 бит) могут давать ложные результаты, а очень длинные (более 10^9 бит) — выявлять незначительные отклонения, не имеющие практического значения.
• Сложность интерпретации: P-value не является мерой «случайности» — он лишь указывает на согласие с моделью случайности. Низкий P-value может быть вызван как дефектом ГСЧ, так и случайной флуктуацией.
• Отсутствие учёта контекста: тесты не учитывают специфику применения ГСЧ. Например, для криптографии важна не только статистическая случайность, но и непредсказуемость, которую NIST SP 800-22 не проверяет.
• Устаревание некоторых тестов: с развитием криптоанализа некоторые тесты (например, тест на линейную сложность) могут быть обойдены современными методами.

Альтернативы и дополнения

Помимо NIST SP 800-22, существуют другие наборы тестов для оценки ГСЧ:

• Dieharder: расширенная версия набора тестов Diehard, разработанного Джорджем Марсальей. Включает более 30 тестов.
• TestU01: библиотека, разработанная в Университете Монреаля. Содержит несколько наборов тестов (SmallCrush, Crush, BigCrush) различной мощности.
• ENT: простой набор из четырёх тестов (энтропия, хи-квадрат, среднее арифметическое, корреляция).
• AIS 31: немецкий стандарт, специализирующийся на тестировании аппаратных ГСЧ.

На практике часто используется комбинация нескольких наборов тестов для повышения надёжности оценки.

Применение в России

В Российской Федерации стандарт NIST SP 800-22 не является официальным нормативным документом. Для оценки качества ГСЧ в криптографических системах, используемых в государственных информационных системах, применяются национальные стандарты, в частности ГОСТ Р 34.10-2012 (и его последующие версии) и Р 1323565.1.006-2017 (методы тестирования ГСЧ). Однако в коммерческих и научных целях NIST SP 800-22 широко используется как один из эталонных наборов тестов. Многие российские разработчики криптографического ПО и аппаратных ГСЧ проводят тестирование по этому стандарту для подтверждения качества своей продукции.

Источники

1. NIST Special Publication 800-22 Revision 2 (2015). «A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications».
2. Rukhin, A., Soto, J., Nechvatal, J., et al. (2001). «A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications». NIST.
3. Paar, C., Pelzl, J. (2010). «Understanding Cryptography: A Textbook for Students and Practitioners». Springer.
4. Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
5. L'Ecuyer, P., Simard, R. (2007). «TestU01: A C Library for Empirical Testing of Random Number Generators». ACM Transactions on Mathematical Software.