Библиографическое описание:

Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов. Программная реализация критерия «хи-квадрат» Draft SP 800–90b // Молодой ученый. — 2013. — №7. — С. 72-76.

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

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

χ2эксп. = (n1 — p1 · N)2 + (n2 — p2 · N)2 + … + (nk — pk · N)2.                                     (5)

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

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

Описание: [ Формула 06 ]                                      (6)

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

Описание: [ Формула 07 ]                                                             (7)

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

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

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

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

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

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

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

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

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

Описание: [ Формула 08 ]                                                       (8)

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

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

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

 

Литература:

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

Обсуждение

Социальные комментарии Cackle