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

Автор:

Рубрика: Технические науки

Опубликовано в Молодой учёный №7 (54) июль 2013 г.

Статья просмотрена: 160 раз

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

Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов. Программная реализация критерия «хи-квадрат» Draft SP 800–90b // Молодой ученый. — 2013. — №7. — С. 72-76. — URL https://moluch.ru/archive/54/7370/ (дата обращения: 22.08.2018).

Критерий «хи-квадрат» (χ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».

Основные термины (генерируются автоматически): число, интервал, критерий, равномерное распределение.


Похожие статьи

Подробный аналитический разбор физического датчика calif.bit...

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет

Критерий хи-квадрат: Ценность кси квадрата для распределения 80000000 образцов 11.417116. и вероятность взвешенной ценности кси...

Проверка статистических гипотез в психолого-педагогических...

Существуют следующие виды распределения: Равномерное распределение (все значения встречаются одинаково часто), симметричное

Проверим возможности применения критерия Стьюдента: Нормальность распределения признака для первой группы с помощью...

О некоторых свойствах вероятностных характеристик

Учтем, что любое множество, кардинальное число которого больше, чем конечное, уже в своем определении содержит недостаточность

Согласно нему, если r и — независимые случайные величины, равномерно распределённые на интервале (0, 1], то z0 и z1 независимы и...

О случайности псевдослучайных последовательностей

Рассмотрим графический тест «Гистограмма распределения элементов». Этот тест позволяет оценить равномерное распределение символов в исследуемой

Полученный результат анализируется при помощи критерия с числом степеней свободы равным.

Об опыте использования табличного процессора Excel при...

Найти закон распределения числа студентов, успешно пересдавших экзамен

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

На листе «Генератор «выборка 100» можно получить 100 значений равномерно, нормально или

На листе «Перерасчет «выборка 10 000» можно скорректировать длину интервала группирования...

Оценка параметров распределения амплитуд в управляющих...

Как видим, распределение зависит от числа степеней свободы .

зависит от выбора интервала усреднения . Выбор значения осуществлялся с учетом значения доминирующей в частоты ; (принималось ).

Вариационный ряд антропометрических признаков студенток...

Определив число классов для заданной численности выборки, находят классовый интервал.

Вправо и влево от класса с максимальной численностью на кривой распределения (или вверх и вниз от этого класса в табл. 4) число значений признака в...

Кластеризация стран Европы по демографическим признакам

С помощью кластерного анализа страны Европы были поделены на кластеры по разному числу признаков.

диапазон дисперсий возмущений: [0.01; 0.20]; − случайное распределение шума: равномерное распределение.

О задаче восстановления нестационарной стохастической...

Таким образом, оптимизация квадратичного критерия (7) производится по и

Входное воздействие принадлежит интервалу от 0 до 1. Отсчеты по равномерны (

С уменьшением скорости изменения параметра сокращается число интервалов разбиения, а также...

Обсуждение

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

Похожие статьи

Подробный аналитический разбор физического датчика calif.bit...

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет

Критерий хи-квадрат: Ценность кси квадрата для распределения 80000000 образцов 11.417116. и вероятность взвешенной ценности кси...

Проверка статистических гипотез в психолого-педагогических...

Существуют следующие виды распределения: Равномерное распределение (все значения встречаются одинаково часто), симметричное

Проверим возможности применения критерия Стьюдента: Нормальность распределения признака для первой группы с помощью...

О некоторых свойствах вероятностных характеристик

Учтем, что любое множество, кардинальное число которого больше, чем конечное, уже в своем определении содержит недостаточность

Согласно нему, если r и — независимые случайные величины, равномерно распределённые на интервале (0, 1], то z0 и z1 независимы и...

О случайности псевдослучайных последовательностей

Рассмотрим графический тест «Гистограмма распределения элементов». Этот тест позволяет оценить равномерное распределение символов в исследуемой

Полученный результат анализируется при помощи критерия с числом степеней свободы равным.

Об опыте использования табличного процессора Excel при...

Найти закон распределения числа студентов, успешно пересдавших экзамен

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

На листе «Генератор «выборка 100» можно получить 100 значений равномерно, нормально или

На листе «Перерасчет «выборка 10 000» можно скорректировать длину интервала группирования...

Оценка параметров распределения амплитуд в управляющих...

Как видим, распределение зависит от числа степеней свободы .

зависит от выбора интервала усреднения . Выбор значения осуществлялся с учетом значения доминирующей в частоты ; (принималось ).

Вариационный ряд антропометрических признаков студенток...

Определив число классов для заданной численности выборки, находят классовый интервал.

Вправо и влево от класса с максимальной численностью на кривой распределения (или вверх и вниз от этого класса в табл. 4) число значений признака в...

Кластеризация стран Европы по демографическим признакам

С помощью кластерного анализа страны Европы были поделены на кластеры по разному числу признаков.

диапазон дисперсий возмущений: [0.01; 0.20]; − случайное распределение шума: равномерное распределение.

О задаче восстановления нестационарной стохастической...

Таким образом, оптимизация квадратичного критерия (7) производится по и

Входное воздействие принадлежит интервалу от 0 до 1. Отсчеты по равномерны (

С уменьшением скорости изменения параметра сокращается число интервалов разбиения, а также...

Задать вопрос