Анализ процедур генерации ключей криптографических алгоритмов. Программная реализация критерия «хи-квадрат» Draft SP 800–90b

Критерий «хи-квадрат» (χ²-критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики [1]. Для нашего случая проверка по критерию «хи-квадрат» позволит узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ, то есть удовлетворяет ли он требованию равномерного распределения или нет.

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n_i чисел (в сумме n₁ + n₂ + … + n_k = N). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n_i и «эталонным» p_i · N. Сложим их, и в результате получим:

χ²_эксп. = (n₁ — p₁ · N)² + (n₂ — p₂ · N)² + … + (n_k — p_k · N)².                                     (5)

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ²_эксп.), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i-го слагаемого, поделив его на p_i · N:

                                      (6)

Наконец, запишем полученное выражение более компактно и упростим его:

                                                             (7)

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

Приемлемым считают p от 10 % до 90 %. Если χ²_эксп. много больше χ²_теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n_i слишком далеко уходят от теоретических p_i · N и не могут рассматриваться как случайные [1]. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Если χ²_эксп. много меньше χ²_теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n_i слишком близки к теоретическим p_i · N и не могут рассматриваться как случайные.

А вот если χ²_эксп. лежит в некотором диапазоне, между двумя значениями χ²_теор., которые соответствуют, например, p = 25 % и p = 50 %, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными [1].

Итак, процедура проверки имеет следующий вид:

а)                 Диапазон от 0 до 1 разбивается на k равных интервалов;

б)                 Запускается ГСЧ N раз (N должно быть велико, например, N/k > 5);

в)                 Определяется количество случайных чисел, попавших в каждый интервал: n_i, i = 1, …, k;

г)                 Вычисляется экспериментальное значение χ²_эксп. по следующей формуле:

                                                       (8)

где p_i = 1/k — теоретическая вероятность попадания чисел в k-ый интервал.

Путем сравнения экспериментально полученного значения χ²_эксп. с теоретическим χ²_теор. делается вывод о пригодности генератора для использования.

Программная реализация.

Литература:

1.                 http://csrc.nist.gov/publications/PubsSPs.html «DRAFT — SP800–90b».