МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
Кафедра математического моделирования и анализа данных
ЦЕПЬ МАРКОВА С ЧАСТИЧНЫМИ СВЯЗЯМИ И ПЕРЕМЕННЫМ ШАБЛОНОМ
Курсовая работа
Батуры Олега Владимировича
студента 3 курса,
специальность
«Компьютерная безопасность»
Научный руководитель:
доктор физ.-мат. наук,
заведующий кафедрой ММАД
Ю. С. Харин
Минск,
2015
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ПРИКЛАДНОЙ математики и информатики
Кафедра математического моделирования и анализа данных
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
Студент Батура Олег Владимирович, 3 курс, 9 группа
1. Тема работы Цепь Маркова с частичными связями и переменным шаблоном
2. Срок сдачи студентом законченной работы ________ 2015 г.
3. Перечень вопросов, подлежащих разработке
· Исследовать вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном. Найти -мерное распределение вероятностей .
· Построить компьютерную модель ЦМ с переменным шаблоном.
· Построить статистические оценки параметров модели при известной функции шаблона , исследовать свойства оценок.
· Построить оценки параметров модели при периодически изменяющемся, но неизвестном шаблоне.
Руководитель курсовой работы______________ / Ю. С. Харин/ ______ 2015 г.
Задание принял к исполнению_______________ 2015 г.
ОГЛАВЛЕНИЕ
Введение. 4
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 5
1.1. Цепь Маркова порядка . 5
1.2. Цепь Маркова с частичными связями ЦМ. 7
1.3. Цепь Маркова с частичными связями и переменным шаблоном ЦМ 9
1.4. Статистическое оценивание параметров ЦМ, состоятельность оценок 11
1.5. Статистическое оценивание параметров ЦМ. 15
2. ПРАКТИЧЕСКАЯ ЧАСТЬ. 16
2.1. Описание программы.. 16
2.2. Моделирование временного ряда длительности . 17
2.3. Построение оценок максимального правдоподобия и . 18
2.4. Результаты экспериментов. 21
2.5. Вывод. 23
Заключение. 24
Список использованной литературы.. 25
Введение
При математическом моделировании сложных систем и процессов в различных научных сферах часто возникает необходимость построения вероятностно-статистических моделей дискретных временных рядов , где пространство состояний — конечное множество мощности с длинной памятью [1]. Известной моделью таких дискретных временных рядов является цепь Маркова достаточно высокого порядка , определяющего длину памяти; если , то цепь Маркова называется простой, если — сложной. Однако для такой модели число параметров растет экспоненциально при увеличении порядка : , и для статистического оценивания параметров требуется иметь реализацию не всегда доступной на практике длительности . В связи с этим актуальна проблема построения малопараметрических моделей цепей Маркова высокого порядка. В данной работе исследуется малопараметрическая модель цепи Маркова порядка с частичными связями ЦМ, рассмотренная в [2], для которой шаблон связей зависит от времени, исследуются ее вероятностные характеристики, строятся статистические оценки параметров при известной функции шаблона, а также при периодически изменяющемся, но неизвестном шаблоне.
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 1.1. Цепь Маркова порядкаВ криптологии для моделирования дискретных временных рядов с глубиной памяти используется цепь Маркова порядка (ЦМ), обобщающая модель простой цепи Маркова [3].
Определение. Цепь Маркова , порядка с пространством состояний , определенная на вероятностном пространстве () и временной области , характеризуется обобщенным марковским свойством:
Это означает, что условное распределение вероятностей будущих состояний при фиксированной предыстории зависит не от всей этой предыстории, а от ближайшей на глубину предыстории
Цепь Маркова ЦМ() характеризуется -мерным начальным распределением вероятностей
и -мерной матрицей вероятностей одношаговых переходов в момент времени :
=
Матрица при этом удовлетворяет условиям нормировки (если она не зависит от времени, то есть , ЦМ() в таком случае называется однородной):
В таком случае -мерное распределение вероятностей имеет вид:
Число независимых параметров, определяющих матрицу вероятностей одношаговых переходов для однородной ЦМ(), равно .
При увеличении глубины памяти число параметров экспоненциально возрастает, и для идентификации такой модели требуется наблюдать реализацию не всегда доступной на практике длительности .
Возникает задача поиска малопараметрической модели цепи Маркова высокого порядка, для которой число параметров в матрице задается числом параметров . Одной из таких моделей является цепь Маркова порядка с частичными связями (ЦМ) [2].
1.2. Цепь Маркова с частичными связями ЦМПусть – однородная ЦМ(), заданная на вероятностном пространстве () с некоторой ()-мерной матрицей вероятностных переходов
Рассмотрим – параметр, который называется числом связей; – произвольный целочисленный -вектор с упорядоченными компонентами:
Этот вектор называется шаблоном связей, – множество всевозможных таких векторов с компонентами, мощность – некоторая -мерная стохастическая матрица.
Определение. Цепь Маркова называется цепью Маркова -го порядка с -частичными связями и обозначается ЦМ(), если ее вероятности одношаговых переходов имеют вид:
Это означает, что вероятность перехода процесса в состояние в момент времени зависит не от всех значений предыдущих состояний процесса, а лишь от некоторых избранных состояний.
В данном случае, вместо параметров ЦМ() данная модель полностью определяется параметрами , что играет существенную роль на практике.
Замечание. Если , , то и ЦМ() представляет из себя цепь Маркова порядка , то есть ЦМ( ЦМ.
В дальнейшем будем рассматривать однородную цепь Маркова с частичными связями.
Следует отметить, что -мерное распределение вероятностей для данной модели имеет следующий вид:
Возникает проблема исследования свойств такой модели цепи Маркова, в которой шаблон зависел бы от какой-либо функции. Данное свойство помогло бы сделать распознавание шаблона для злоумышленника более проблематичным, что сыграло бы важную роль в криптостойкости модели.
1.3. Цепь Маркова с частичными связями и переменным шаблоном ЦМПусть – однородная ЦМ(), заданная на вероятностном пространстве (), определенная ранее. Рассмотрим обобщение данной модели, когда шаблон зависит от времени :
причем:
В общем случае шаблон зависит от некоторой функции, определяющей его изменение. Простейшая модель такой зависимости – периодическая функция с некоторым периодом :
.
В частности, при имеются два различных шаблона и которые циклично повторяются:
Для данного частного случая -мерное распределение вероятностей имеет вид:
При произвольной модели зависимости шаблона от времени имеем общую формулу:
Использование такой модели цепи Маркова позволяет сделать выборку для злоумышленника как можно более случайной, что сильно влияет на криптостойкость модели, так как появляются сложности с распознаванием зависимости и поиском используемого шаблона. Полезно исследование такой модели ЦМ, в которой шаблон периодически изменяется, но неизвестен.
Далее рассмотрим задачу статистической оценки параметров модели ЦМ при известном шаблоне и поиска свойств оценок.
1.4. Статистическое оценивание параметров ЦМ, состоятельность оценокДля статистического оценивания параметров ЦМ() будем пользоваться методом максимального правдоподобия.
Рассмотрим задачу построения оценок максимального правдоподобия (ОМП) для параметров шаблона и стохастической матрицы по наблюдаемой реализации длительности .
Введем обозначения, пусть – мультииндекс -го порядка; – функция, которую назовем селектором -го порядка с параметрами и – индикатор события ; – начальное -мерное распределение вероятностей ЦМ;
– частота -граммы для шаблона , удовлетворяющая условию нормировки:
Для модели ЦМ логарифмическая функция правдоподобия имеет вид:
Для того, чтобы найти ОМП для матрицы , необходимо решить задачу на условный экстремум:
В результате получаем условную ОМП для матрицы ():
Далее рассматривается задачу поиска ОМП для шаблона .
Пусть – стационарное распределение вероятностей ЦМ. Пусть ЦМ – стационарна (), тогда распределение вероятностей -граммы для шаблона будет иметь следующий вид:
Соответствующая частотная оценка вероятностей:
.
Энтропия -мерного распределения вероятностей запишется в виде:
Количество информации по Шеннону, содержащейся в -грамме о будущем символе :
Логарифмическая функция правдоподобия для оценки имеет следующий вид:
где – подстановочная оценка энтропии, получающаяся при подстановке вместо истинных значений их оценок {}.
Учитывая, что не зависит от , добавляя также не зависящее от слагаемое , а также используя тот факт, что:
приходим к следующей ОМП шаблона :
где – подстановочная оценка количества информации по Шеннону, получающаяся при подстановке вместо истинных значений их оценок {}.
Теорема 1. Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:
Теорема 2. Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:
1.5. Статистическое оценивание параметров ЦМДля ЦМ оценки параметров генератора с переменной обратной связью строятся аналогично модели с постоянной обратной связью с учетом периодически изменяющегося шаблона .
Логарифмическая функция правдоподобия имеет следующий вид:
Задача на условный экстремум
решается в общем виде, и это позволяет решить частную задачу оценки параметров генератора с переменной обратной связью.
Теорема 3. Если ЦМ является стационарной, то при истинном шаблоне и оценка состоятельна:
Теорема 4. Если ЦМ является стационарной и шаблон идентифицируемый, то при оценка состоятельна:
2. ПРАКТИЧЕСКАЯ ЧАСТЬ 2.1. Описание программыПостроена компьютерная модель цепи Маркова с частичными связями и переменным шаблоном со следующими входными параметрами:
· глубина предыстории однородной цепи Маркова ЦМ.
· длина временного ряда с пространством состояний .
· Шаблоны и , которые повторяются с периодом
· Стохастическая матрица вероятностей одношаговых переходов для шаблонов:
В частном случае, при данная матрица имеет следующий вид:
Реализовано моделирование цепи Маркова с частичными связями и переменным шаблоном, нахождение оценок максимального правдоподобия матрицы вероятностей одношаговых переходов и переменного шаблона смоделированного временного ряда. Далее более подробно рассматривается алгоритм работы программы.
2.2. Моделирование временного ряда длительностиСлучайным образом выбираются первые элементов последовательности. Для моделирования элементов с нечетными номерами выбирается шаблон . Рассматривается -предыстория элемента. Распределениями вероятностей исхода для данных элементов являются строки матрицы , соответствующие состояниям предыдущих элементов
В частности, если предыстория элемента имеет вид
,
то при
Элементы с четными номерами моделируются аналогичным образом с использованием шаблона
На каждом шаге моделирование происходит с помощью генератора псевдослучайных чисел, работающего по следующему алгоритму:
1. Генерируется число в диапазоне .
2.
В результате имеется временной ряд , где пространство состояний – конечное множество мощности .
2.3. Построение оценок максимального правдоподобия иЛогарифмическая функция правдоподобия имеет вид:
Задача на условный экстремум:
Поиск условной оценки максимального правдоподобия матрицы одношаговых переходов ищется путем приравнивания к нулю компонент градиента логарифмической функции правдоподобия:
Используя тот факт, что матрица стохастическая,
, условная оценка полностью определяется шаблоном
Для вычисления оценки шаблона при известном истинном значении числа связей можно воспользоваться алгоритмом полного перебора значений логарифмической функции правдоподобия.
В частности, при имеется следующая система уравнений:
где частота выпадения при предыстории .
Условной оценкой максимального правдоподобия является решение данной системы:
.
Логарифмическая функция правдоподобия перепишется в следующей форме:
Оценка максимального правдоподобия ищется путем перебора вариантов шаблонов. Производится подсчет частот при всевозможных вариантах пар шаблонов и выбирается та пара, которая максимизирует логарифмическую функцию правдоподобия. Таким образом:
Оценка максимального правдоподобия матрицы имеет вид:
2.4. Результаты экспериментовЭкспериментальные оценки параметров построены при следующих входных данных:
Рис. 1. Зависимость числа ошибок распознавания истинного шаблона при 100 экспериментах от
При :
При :
При :
При :
2.5. ВыводРезультаты показывают состоятельность оценки при истинном шаблоне и . Также очевидна состоятельность оценки шаблона при .
Таким образом, для более точного распознавания матрицы одношаговых переходов и шаблона требуется наблюдать реализацию как можно большей длительности .
ЗаключениеВ данной работе исследованы вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном, реализована компьютерная модель ЦМ с переменным шаблоном. Построены статистические оценки параметров модели при известной функции шаблона , периодически изменяющемся, но неизвестном шаблоне. Исследована состоятельность данных оценок.
Результаты экспериментов показали, что для более точного распознавания матрицы одношаговых переходов и шаблона требуется наблюдать реализацию как можно большей длительности .
Список использованной литературы1. Алферов А. П. и др. Основы криптографии / Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. – 2-е изд., испр. и доп. – М.: Гелиос АРВ, 2002. – 480 с.
2. Харин Ю. С., Петлицкий А. И. Цепь Маркова -го порядка с частичными связями и их статистическое оценивание – Дискретная математика, 2007. – Т. 12, вып. 2. С. 109-130.
3. Харин Ю. С. и др. Криптология / Харин Ю. С., Агиевич С. В., Васильев Д. В., Матвеев Г. В. – Мн.: БГУ, 2013. – 511 с.