Разработка программного комплекса статистического тестирования криптографических генераторов на основе Марковских моделей
Проблема защиты информации. Эффективные алгоритмы статистического анализа выходных последовательностей, основанного на оценивании таких Марковских моделей как, однородная цепь Маркова, однородная цепь Маркова s-ого порядка, скрытая марковская модель.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 03.05.2019 |
| Размер файла | 196,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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]:
где - порог критерия, определяемый по уровню значимости с степенями свободы, где - число независимых параметров.
Структура программного комплекса
Результаты на модельных данных
Используя модуль генерации модельных данных были сгенерированы следующие выходные последовательности:
|
№ |
Данные |
Длина последовательности |
Результаты тестирования |
||||
|
M1 |
M2 |
M3 |
M4 |
||||
|
1 |
S1 |
20 |
H1 |
H0 |
H0 |
H0 |
|
|
2 |
S2 |
100 |
H1 |
H1 |
H1 |
H1 |
|
|
3 |
S3 |
100000 |
H1 |
H1 |
H1 |
H1 |
|
|
4 |
S4 |
100 |
H1 |
H1 |
H1 |
H1 |
|
|
5 |
S5 |
1000 |
H0 |
H0 |
H0 |
H0 |
|
|
6 |
S6 |
20 |
H1 |
H1 |
H1 |
H1 |
|
|
7 |
S7 |
100 |
H0 |
H0 |
H0 |
H0 |
Список литературы
1. Харин Ю.С. и др. Криптология. -- 2013. -- Минск.
2. Харин Ю.С., Н.М. Зуев, Е.Е. Жук. -- 2011. -- Минск.
Размещено на Allbest.ru
...Подобные документы
Защита информации и средства для ее обеспечения. Обзор моделей информационной безопасности. Основные сведения о марковских случайных процессах. Алгебраический метод решения уравнения Колмогорова. Исследование среднего времени до отказа безопасности.
дипломная работа [1,1 M], добавлен 12.01.2022Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Алгоритмы и стандарты криптографических преобразований. Криптографические преобразования на основе специального программного обеспечения. Метод криптографических преобразований на основе жесткой логики. Аналоги модуля шифрования и дешифрования данных.
курсовая работа [971,6 K], добавлен 30.01.2018Анализ возможностей утечки информации, неавторизованного и несанкционированного доступа к ресурсам ЛВС сельскохозяйственного комплекса. Ознакомление с антивирусными программы и брандмауэрами. Разработка программного комплекса для защиты информации.
дипломная работа [3,6 M], добавлен 17.04.2010Проект экспериментального программного комплекса индексирования и поиска неструктурированной текстовой информации в многоязычной среде, состоящего из математических моделей, алгоритмов и программных средств. Исследование характеристик его эффективности.
автореферат [296,5 K], добавлен 31.01.2012Порядок и основные этапы построения двоичных неравномерных эффективных кодов с помощью методики Хаффмена. Сравнительная характеристика полученных кодов. Кодирование текста построенными кодами. Разработка марковских процедур для кодирования слов.
лабораторная работа [520,7 K], добавлен 29.09.2011Исследование больших объемов данных, выявление зависимостей, статистические и маркетинговые исследования и построение моделей. Создание проекта разработки статистического пакета. Структура пакета, план его реализации. Выбор инструментов разработки.
курсовая работа [1,3 M], добавлен 20.10.2012Рассмотрение основных понятий криптографии: конфиденциальности, целостности, аутентификации и цифровой подписи. Описание криптографических средств защиты (криптосистемы, принципы работы криптосистемы, распространение ключей, алгоритмы шифрования).
дипломная работа [802,2 K], добавлен 08.06.2013Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности.
методичка [57,0 K], добавлен 06.07.2009Анализ способов построения генераторов случайных чисел для криптографических задач. Анализ генератора случайных чисел на основе магнитометров. Анализ статистических свойств двоичных последовательностей, полученных путем квантования данных магнитометра.
дипломная работа [2,5 M], добавлен 06.05.2018Анализ существующих алгоритмов обработки информации человеком и современных моделей памяти. Разработка алгоритмов и математической модели ассоциативного мышления. Имитационная модель обработки информации. Компьютерный эксперимент по тестированию модели.
курсовая работа [2,3 M], добавлен 19.11.2014Понятие модели данных как отображения непрерывных последовательностей реального мира в набор дискретных объектов. Типы моделей: растровая, векторная, преимущества и недостатки. Увеличение потребностей в генерализации в зависимости от уменьшения масштаба.
презентация [310,4 K], добавлен 26.11.2013Разработка алгоритма автоматического создания отзывов на русском языке с использованием лексико-синтаксических шаблонов. Процесс создания текста при помощи цепей Маркова. Принцип работы Томита-парсера. Применение автоматических генераторов текстов.
курсовая работа [150,6 K], добавлен 27.09.2016Принципы разработки в системе программного обеспечения САПР. Выбор среды для формирования моделей и функций. Процесс создания моделей деталей. Разработка API-приложения для среды разработки. Тестирование разработанного функционала портала-хранилища.
курсовая работа [704,0 K], добавлен 18.01.2017Анализ единичных и комплексных показателей качества аппаратного комплекса системы защиты информации. Расчет стоимости для каждой фазы жизненного цикла системы защиты информации программного комплекса, а также расчет общей стоимости владения комплексом.
курсовая работа [65,9 K], добавлен 20.02.2012Этапы статистического анализа данных, приемы и методы его проведения. Ключевые положения закона больших чисел в теории вероятностей, его общий смысл. Теорема Бернулли - простейшая форма закона больших чисел. Количество данных, способы его измерения.
реферат [112,3 K], добавлен 03.03.2014Концептуальная модель задачи на основе триады "Задача–Данные–Решатель" и работа генератора вспомогательных концептуальных моделей. Разработка программы на языке Python, позволяющая решать любые задачи по заданным действительным математическим формулам.
курсовая работа [1,9 M], добавлен 27.11.2011Анализ проблемных аспектов построения и функционирования системы физической защиты информации предприятия. Модель угроз информационной безопасности. Разработка и обоснование модели и процедур выбора средств СФЗИ на основе метода анализа иерархий.
дипломная работа [2,6 M], добавлен 01.07.2011Анализ моделей и методов реализации интеллектуальных игр в системе человек-робот. Среда разработки Choreographe. Алгоритмы модуля распознавания, обработки данных, функций модуля игры. Тестирование программного комплекса, исправление и редакция ошибок.
дипломная работа [1,7 M], добавлен 12.08.2017Точные и приближенные методы анализа структурной надежности. Критерии оценки структурной надежности методом статистического моделирования. Разработка алгоритма и программы расчета структурной надежности. Методические указания по работе с программой.
дипломная работа [857,8 K], добавлен 17.11.2010
