Генераторы псевдослучайных чисел с применением Crypto++ - Тестирование последовательностей
ОГЛАВЛЕНИЕ
Тестирование последовательностей
Ниже читатель найдет различные тесты, применяемые при оценке эффективности генератора. Полное описание читателю следует искать в Руководстве по статистическим тестам NIST и в Искусстве компьютерного программирования Кнута.
Кроме того, следует посмотреть SP800-22 NIST, Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических применений. На сайте NIST есть программное обеспечение для тестирования генератора.
NIST требует, чтобы PRNG прошел 16 статистических тестов. Тесты перечислены ниже с кратким описанием.
• Частота – соотношение нулей и единиц для всей последовательности.
• Частота внутри блока – определяет, равна ли частота единиц в M-битовом блоке примерно M/2.
• Серии – общее число серий нулей и единиц во всей последовательности, где серия – непрерывная последовательность одинаковых битов.
• Длиннейшая серия единиц в блоке – определяет, соответствует ли длина длиннейшей серии единиц в тестируемой последовательности длине длиннейшей серии единиц, ожидаемой в случайной последовательности.
• Ранг случайной двоичной матрицы – проверяет на линейную зависимость между подстроками фиксированной длины из исходной последовательности.
• Дискретное преобразование Фурье (спектральное) – выявляет периодические свойства.
• Сравнение с неперекрывающимся (непериодическим) шаблоном – число вхождений предопределенных целевых подстрок.
• Сравнение с перекрывающимся (периодическим) шаблоном - число вхождений предопределенных целевых подстрок.
• Универсальный статистический тест Маурера – число битов между совпадающими комбинациями. Задача теста – выяснить, можно ли существенно сжать последовательность без потери информации.
• Сложность Лемпела-Зива – до какой степени можно сжать тестируемую последовательность. Последовательность считается неслучайной, если ее можно существенно сжать.
• Линейная сложность – длина генерации регистра с обратной связью.
• Серийность – частота всех без исключения перекрывающихся m-битовых комбинаций по всей последовательности.
• Приблизительная энтропия - частота всех без исключения перекрывающихся m-битовых комбинаций.
• Накопленная сумма – определяет, является ли накопленная сумма частичных последовательностей, входящих в тестируемую последовательность, слишком большой или слишком маленькой по сравнению с ожидаемым поведением накопленной суммы для случайных последовательностей.
• Случайные отклонения – определяет, не превышает ли число появлений состояния в течение случайного блуждания ожидаемое число для случайной последовательности.
• Разновидность случайных отклонений – обнаруживает отклонения от ожидаемого числа появлений разных состояний в течение случайного блуждания.
Кнут утверждает, что случайная последовательность должна пройти 13 статистических тестов. Тесты, не входящие в требования NIST, перечислены ниже.
• Хи-квадрат – классическое определение
• Колмогоров-Смирнов – расширяет критерий хи-квадрат до набора действительных чисел
• Интервал – обнаруживает интервалы между числами по диапазону чисел в последовательности
• Покер (разбиение) - n групп из пяти последовательных целых чисел из потока, соблюдающих итоговую схему. Одна пара - aabcd, три карты одного достоинства и две другого- aaabb, и т.д.
• Сборщик купонов – Проверяет длину последовательности, требуемую для наблюдения всех чисел в наборе от 0 до d-1.
• Перестановка – число порядков разбиения последовательности на части
• Столкновение – используется, если критерий хи-квадрат превышает определенное число столкновений
• Интервал между днями рождения – похож на парадокс дней рождения при выборе двух целых чисел в последовательности
Выбор начального числа
Криптографически стойкие RNG делят слабое место с другими генераторами псевдослучайных чисел – и те, и другие требуют начальное число на входе. Если секретное начальное число скомпрометировано, злоумышленник сможет мгновенно сгенерировать всю выходную последовательность, используя такой же алгоритм.
В 1995г. Дэвид Вагнер, тогда аспирант в Беркли, и его бывший однокурсник Ян Голдберг взломали генератор случайных чисел, используемый веб-браузером Netscape для защиты онлайновых транзакций. Они определили, что Netscape создавал свои начальные числа с помощью легко предсказываемых чисел, таких как время суток.
Функции выработки ключа
Функции выработки ключа используются (среди прочего) для выработки ключей на основе секретных паролей или парольных фраз. Для справки смотрите RFC 2898, Спецификация криптографии на базе паролей. Кроме того, платформа .NET предоставляет Rfc2898DeriveBytes, входящий в состав System.Security.Cryptography.
Функции выработки ключа часто используются вместе с несекретными параметрами для выработки ключей на основе общего секретного значения. Также может применяться KDF для обеспечения того, чтобы выработанные ключи обладали другими желательными свойствами, к примеру, исключение слабых ключей в некоторых специальных системах шифрования.
Функции выработки ключа применяются также в приложениях для выработки ключей на основе секретных паролей или парольных фраз, обычно не обладающих желательными свойствами для непосредственного использования в качестве криптографических ключей. В таких приложениях рекомендуется умышленно делать функцию выработки ключа медленной, чтобы сорвать атаку перебором или словарную атаку на входное значение пароля или парольной фразы.
Такое применение можно выразить через Dk = KDF(ключ, соль, повторения), где Dk – выработанный ключ, KDF - функция выработки ключа, ключ – исходный ключ или пароль, соль – случайное число, играющее роль криптографической соли, а повторения относятся к числу повторений подфункции. Выработанный ключ используется вместо исходного ключа или пароля в качестве ключа для системы. Значения соли и числа повторений (если оно не фиксированное) хранятся вместе с хешированным паролем или отправляются в виде простого текста с помощью зашифрованного сообщения.