Комбинирование тестов. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

На практике принятие или отвержение нулевой гипотезы основывают на результатах применения нескольких независимых тестов. Когда независимые тесты приводят к различным выводам, используется комбинирование результатов тестов с помощью статистик, учитывающих совокупность результатов всех использованных тестов. При небольшом количестве комбинируемых тестов используется статистика Фишера — Пирсона, которая сравнивается с распределением хи-квадрат. Если количество комбинируемых тестов велико, то рекомендуется применение теста Колмогорова — Смирнова.

Статистические тесты могут быть сгруппированы по тестируемым характеристикам для повышения надежности тестирования. Например, можно сгруппировать тесты:

• 1) проверки равномерности (Uniformity Tests);
• 2) часто появляющихся шаблонов (Pattern Tests);
• 3) проверки периодичности последовательности (Period Tests);
• 4) проверки на сжимаемость последовательности (Compression Tests);
• 5) проверки зависимости элементов последовательности (Dependence Tests);
• 6) кумулятивных сумм (Cumulative Sums Test);
• 7) проверяющие поток битов как поток m-битовых чисел (Integer Tests);
• 8) остальные (Other Tests).

Например, можно сгруппировать известные частотные тесты: побитовый и блочный тесты NIST, тест частот CPYPT-X, тест веса Хэмминга из TESTU01 и критерий частот Кнута.

При тестировании качества генератора ПСП среди генерируемых им последовательностей оценивается доля тех, что прошли тесты. В NIST разработана следующая методика:

Шаг 1. Выбор примитива для генерации тестируемых последовательностей.

Шаг 2. Генерация т двоичных последовательностей длины п с помощью примитива.

Шаг 3. Применение пакета тестов NIST к сгенерированным последовательностям.

Шаг 4. Получение значений p-values.

Результат каждого теста — одно или несколько значений p-value, по которым в дальнейшем принимается решение о результате прохождения примитивом пакета тестов NIST.

Шаг 5. Принятие решения о результате прохождения примитивом пакета тестов NIST.

Для принятия решения о результате предлагается использовать следующие два метода:

1) Соотношение прошедших и не прошедших тест последовательностей.

При данном ос число прошедших тест последовательностей должно быть.

— 4.0 Ipd-P) * ,

в пределах р± 3J———, где р- 1-а, т — число тестируемых последова;

V гп

тельностей.

2) Оценка распределения полученных значений p-values.

Для качественного генератора отклонение распределения значений p-values от теоретического должно быть случайным. Проверка этого осу;

^ (F- — sp}²

ществляется с помощью критерия у} = ?—¹———, где F_t — число попав;

«=1 ^sPi

ших в /-Й интервал p-values_f s — число тестируемых последовательностей, Pi — вероятность попадания значения p-value в /-й интервал. Значение.

(kу²Л

p-value вычисляется, но формуле p-value = у -, —. Если p-value больше.

V 2 2 )

заданного порогового значения, то считается, что примитив проходит пакет статистических тестов NIST.

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

Задачи и упражнения

• 10.1. Перечислите свойства РРСП па множестве X мощности k.
• 10.2. Какие существуют подходы к определению случайности? В чем состоит их сущность?
• 10.3. Проверьте для двоичной ЛРПтах-w выполнимость трех постулатов Голомба.
• 10.4. Какие из постулатов Голомба выполнены для НРП (я, k)?
• 10.5. Приведите примеры автономных автоматов, для выходных последовательностей которых известны длины периодов, линейная сложность, частоты знаков и мульти грамм.
• 10.6. Посчитайте для ЛРПтах-я значение статистик:
  • а) частотного теста;
  • б) автокорреляционного теста с задержкой т;
  • в) последовательного теста с параметром s = 8 < п
  • г) теста серий с параметром s = 8 < п.
• 10.7. Перечислите основные пакеты статистических тестов, охарактеризуйте их содержание.
• 10.8. Перечислите основные тестируемые характеристики ПСП.
• 10.9. Какие используются подходы к оценке качества генераторов последовательностей?