Разработка программного комплекса статистического тестирования криптографических генераторов на основе Марковских моделей

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Разработка программного комплекса статистического тестирования криптографических генераторов на основе Марковских моделей

Ю.С. Харин, М.Ю. Деркач

Белорусский государственный университет

г. Минск, 220030, Республика Беларусь

Введение

цепь марков алгоритм однородный

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

В данной статье представлены эффективные алгоритмы статистического анализа выходных последовательностей, основанного на оценивании таких Марковских моделей как, однородная цепь Маркова, однородная цепь Маркова s-ого порядка, скрытая марковская модель, двойная марковская модель.

Математические модели

Пусть на вероятностном пространстве наблюдается выходная последовательность , длины .

Кратко представим используемые математические модели выходных последовательностей:

M1: Однородная цепь Маркова:

ДВР, определенный на вероятностном пространстве, называется цепью Маркова с пространством состояний, если для любого выполняется марковское свойство:

Однородная Цепь Маркова (ОЦМ) характеризуется начальным распределением вероятностей и матрицей вероятностей одношаговых переходов.

M2: Однородная цепь Маркова s-ого порядка:

Цепь Маркова , порядка s с пространством состояний, определенная на вероятностном пространстве и временной области, характеризуется обобщенным марковским свойством:

Однородная Цепь Маркова порядка s ОЦМ(s) характеризуется s-мерным начальным распределением вероятностей и ()-мерной матрицей вероятностей одношаговых переходов ??.

M3: Скрытая марковская модель:

Цепь Маркова, с пространством состояний, и ДВР с пространством состояний, определенные на вероятностном пространстве, называются скрытой марковской моделью, если для любого выполняется следующее свойство:

Скрытая марковская модель полностью определяется следующими параметрами [2]:

· - множество скрытых состояний.

· - множество обозреваемых состояний.

· начальное распределение вероятностей скрытых состояний

· матрица вероятностей одношаговых переходов скрытых состояний

· матрица вероятностей переходов из скрытого состояния в обозреваемое такая что

M4: Двойная марковская модель:

Цепь Маркова с пространством состояний, и цепь Маркова с пространством состояний , определенные на вероятностном пространстве, называются двойной цепной марковской моделью, если для любого выполняется следующее свойство:

Двойная марковская модель полностью определяется следующими параметрами [2]:

· - множество скрытых состояний.

· - множество обозреваемых состояний.

· начальное распределение вероятностей скрытых состояний

· матрица вероятностей одношаговых переходов скрытых состояний

· множество матриц вероятностей переходов из скрытого и произошедшего обозреваемого состояний в обозреваемое

Методы статистического оценивания параметров и проверки гипотез

Для статистического оценивания параметров этих моделей использовались следующие алгоритмы:

1. Метод оценки максимального правдоподобия для моделей M1, M2.

2. Метод статистического бутстрэпа для моделей M1, M2.

3. Метод сглаживания оценки максимального правдоподобия для моделей M1, M2.

4. Обобщенный EM-алгоритм (алгоритм Баума-Велша) для моделей M3, M4.

5. Метод оценивания оптимальной последовательности скрытых состояний для M3, M4.

Введем гипотезы = {гипотеза о том, что выходная последовательность - «чисто случайная} = {гипотеза о том, что выходная последовательность - РРСП} и .

В параметрическом виде гипотеза представима следующим образом:

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

1. Критерий согласия Пирсона для моделей M1, M2.

Этот критерий имеет вид [3]:

где - количество раз, когда состояние обозревается в последовательности , -порог критерия, определяемый по уровню значимости через квантиль - распределения с степенями свободы, где - число ненулевых вероятностей одношаговых переходов в -матрице

2. Критерий отношения правдоподобия для моделей M3, M4.

Этот критерий имеет вид [3]:

где - порог критерия, определяемый по уровню значимости с степенями свободы, где - число независимых параметров.

Структура программного комплекса

Результаты на модельных данных

Используя модуль генерации модельных данных были сгенерированы следующие выходные последовательности:

Список литературы

1. Харин Ю.С. и др. Криптология. -- 2013. -- Минск.

2. Харин Ю.С., Н.М. Зуев, Е.Е. Жук. -- 2011. -- Минск.

Размещено на Allbest.ru