Razbor_kriptov_-_chast_2

Опр. Автомат А’ называется подавтоматом автомата А, если:

X’ – подмножество множества Х обозн. X’ X

Атакже S’ S; Y’ Y

Аf’ иh’есть ограничение функций fи h на множество X’ x S’

Обозначается:

hi :X x S	S
fi : Xx S	Y

Не спрашивайте, что такое «ограничение функции на множество» не понял. Но если кому то после почти 30 страниц чтения материал кажется простым, то предлагаю Вам разобраться с этим определением. К тому же, после обращения к гуглу, приходит

понимание, что оно совсем простое  Если дана функция , и ,

то мы можем получить новую функцию, рассматривая значения функции только на элементах . Эта функция определена равенством при . Функция называется ограничением

функции на подмножество её области определения .

Замечание. Подавтоматом автомата А, в частности, является автомат, задаваемый компонентой сильной связности автомата А.

Определение из прошлого семестра: Опр. Компонента сильной связности ориентированного г рафа – это максимальное количество вершин, где любая вершина достижима из любой другой. Или же просто: циклы без подходов к ним.

Заметили слово «в частности» в определении? Оно означает, что не каждому автомату соответствует компонента сильной связности.

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

А вот такой – не соответствует почему???

Опр. Гомоморфизмом автоматов А иА’ называется тройка функций:

Φ1	: X	X’
Ф2	: S	S’
Ф3 : Y		Y’

Для которых при всех х из Х и s из S выполнено равенство:

h’ Ф1 x ,Ф2 s	Ф2	h x,s
f’ Ф1 x ,Ф2 s	Ф3	h x,s

Что тут написано? А вот что: можно сначала применить функции к аргументам Ф1 x , Ф2 s ,а затем вычислить значение h’ и f’. Аможно сначалавычислить, а затем применить Ф: Ф2 h x,s и Ф3 h x,s – результат будет одинаковый.

Опр. Если Ф1, Ф2, Ф3 – биективные отображения, то автоматы А и А’ называются изоморфными.

Замечание 1.

Изоморфизм автоматов можно трактовать следующим образом: входы,выходыи состояния автомата А переобозначаются так, что таблица автомата А превращается в таблицу автомата А’.

Замечание 2.

Изоморфизм совпадение с точностью до вершин графов автоматов – необходимое, но не достаточное условие изоморфизма самих автоматов.

Казалось бы, почему? Смотрите: изоморфные автоматы – это один и тотже автомат, только входы, выходыи состояния обозначены по разному. Поэтомупонятно, что у изоморфных автоматов будут изоморфные графы.

А вотв другую сторону – невсегда. Графы могут совпадать с точностью до меток дуг, но при этом задавать разные автоматы.

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

Опр. Последовательным соединением автоматов Мили:

А1 X,S1,Y,h1,f1 и А2	Y,S2, Z,h2,f2
Называется автомат А	Y, S1 x S2, Z,h, f , где:

Для любого х из Х иs из S выполняется:

h x,s	h x,	s1s2	h1 x,s1 ,h2 f x, s1 ,s2 и
f x,s	f x,	s1s2	f2 f1 x,s1 ,s2

Обозн. A1 A2 – последовательное соединение автоматов

Пояснение: на вход подаем некоторый символ x.Автомат А1 находится в состоянии s1. Он переходитв состояние h x, s1s2 ивыдаетвыходнойсимвол f x, s1 . Этот символ поступаетна вход второму автомату, который находился всостоянии s2. Он переходит в состояние h2 f x,s1 ,s2 . А что свыходным символом? Тоже все просто! Начальное состояние второго автомата – s2, входной символ f1 x,s1 .Тогда выходным символом,прямо по определению, будет f2 f1 x,s1 , s2 .

Опр.

Прямой суммой автоматов А1 X,S1, Y, h1,f1 и А2 Y,S2, Z,h2, f2

Называется автоматА X, S,Y,h,f ,где:

X	X1x X2
S	S1 x S2
Y	Y1 x Y2		h1 x1s1 , h2 x2s2
И длялюбого х изХ и sиз S функцияh x,s h x1,x2 s1s2
А также f x,s f x1,x2 s1s2		f1 x1s1 , f2 x2s2

Различимостьавтоматамисостоянийивходов.

Опр. Реакцией состояния s автомата А называется порожденное им отображение:

fS : X*	Y*
fS w	f* w,s

То есть автомат находится в состоянии s, подаем на вход слово, получаем выходное слово. Так вот, отображение множества входных слов в множество выходных слов называется реакцией.

Замечание.

Реакцией состояния s автономного автомата называется порожденная им выходная последовательность вводить f не нужно .

Другими словами: Если автомат автономен, то выход определяется только текущим состоянием.

Опр. Реакцией автоматаА обозн. A называется множествореакций всех его состояний: A fs, s S

Опр. Состояния s и zавтомата А назовем эквивалентными, если они имеют одинаковую реакцию.

Другими словами: автомат может находиться как в состоянии s, так и z. Если в любом из этих состояний подать на вход одинаковую входную последовательность, на выходеполучим однои то же.

Опр. Автоматы называютэквивалентными, если одинаковы их реакции.

Напомним, реакцией автомата называется множество реакцией всех его состояний.

Замечание. Эквивалентные автоматы являются однородными.

Другими словами: совпали реакции	совпаливходныеи выходные функции –
значит, совпали и их области определения авфавиты		автоматы однородны.

Напомним: Автоматы А и А’ называются однородными, если совпадают их входные алфавиты и выходныеалфавиты.

Опр. АвтоматА называется сокращенным, еслине эквивалентны любые 2 его состояния.

Но все хорошее когда нибудь заканчивается. Заканчивается и раздел без доказательств. Приготовьтесь, сейчас начнется много теорем с неочевидными доказательствами. Откроет же его особая теорема Хармана Мили. Помните, в прошлом разборе была лемма Анселя, которую мы не доказывали, так как это очень сложно? Таквот, теорема Хармана Мили в несколько раз сложнее, а разборее доказательстваможно сравнить с изучением квантового криптоанализатора. Говорят, полностью понять ее способен только истинный криптограф. Проверим, удастся ли это нам.

Рассуждение перед теоремой .

Пусть есть автоматА и унего 2 состояния: s и z.Эквивалентны ли эти состояния? Чтобы ответить на этот вопрос, нужно сравнить их реакции аесли совсем правильно

– реакции состояния s и реакции состояния z .Если они совпали – состояния эквивалентны.

Но fS переводит множество всех слов алфавита Х во множество всех слов алфавита У. Но длины слов бесконечны! Ихможет быть бесконечно много. И мы можем проверить реакции на словах длины1000 иони там совпадут, а на словах длины1001 – уже нет. Получается, нужно проверить все слова, которых бесконечное количество т.к. длина слова не ограничена . Что делать? Криптоаналитик без дипломабудет ждать окончания бесконечного цикла, втовремя как жесткий криптограф применит теорему Хафмана Мили.

Теорема Хафмана Мили.

Для эквивалентности двух состояний автомата А с nразличными состояниями

|S| n необходимо идостаточно, чтобы совпалиреакции этих состояний на входные слова длиныне больше n 1.

Физический смысл теоремы Хафмана Мили : если совпали реакции двух состояний навсех словах длиныn 1, то и для словбольшей длины совпадут. Таким образом, проверить нужно вполнеконкретные слова: всех слова длины n 1, где |S| n – количество состояний автомата. Вот так выглядитсовпадение реакций на картинке:

Предупреждение. Доказательство теоремы Хафмана Мили включаетнесколько определений, замечаний, утверждений, обозначений и доказательств.

Доказательство.

Доказательство начнем с определения.

Опр. Состояния s и zавтомата А назовем k эквивалентными, если совпадают их реакции на всех входных словах длины k. Обозначается f* w,s f* w,z для любых w их Хk.

Заметьте: здесь написано «k эквивалентными», а не просто «эквивалентными». Почему? Все просто: на словах длины 3 они могут совпасть, а на словах длины 4 уже нет. В такомслучае название будет«3 эквивалентные».

Замечание: отношение k эквивалентности является отношением эквивалентности, так как оно:

1. Рефлексивно: f* w,s f* w,s

2.Симметрично:

3.Транзитивно:

Из прошлого семестра вспоминаем:если отношение является отношением эквивалентности, то это означает, что множество в нашем случае – множество состояний автомата разбивается на классы эквивалентности.

Итак, закрепим: множество S разбивается на классы k эквивалентных состояний.

Обозн. Обозначим Rk –разбиение множестваS на классы k эквивалентных состояний, и ξk –

количество блоков разбиения Rk.

Замечание. Если совпали реакции 2 х состояний автомата на входныеслова длиныk 1, то совпадутихреакции и навходныесловадлиныk.

Ну действительно, если реакции совпали надлинных словах, то на болеекоротких совпадут точно: ведь символы поступают последовательно!

А раз так, идем дальше. Было разбиение множестваS и называлось это разбиение Rk. В разбиении было k эквивалентных состояний. Что это значит? Смотритекартинку.

А что из себя будет представлять разбиение Rk 1? Это продолжение разбиения Rk.

Вот смотрите:

Утв. 1 вспомогательное

Если Rk 1 Rk, то Rj Rk для любого j k

То есть k эквивалентные состояния являются просто эквивалентными.

Другими словами: проверили все входные словадлины k– получилинекоторое количество классов эквивалентности например, 3шт . И теперь если проверим словадлины k 1–снова получим 3шт классов эквивалентности.

Мощное утверждение. Докажем его.

Доказательство.

Достаточно показать, что длялюбого i kиз равенства Ri Ri 1 следуетравенство Ri 1 Ri 2.

То есть если реакции навходныесловадлиныi иi 1 совпали, то совпадут и реакции на слова длин i 1иi 1.

Пусть s и z– i 1 эквивалентные состояния совпадают реакции навходные словадлины i 1 .

Тогда длялюбого х изХи w из Xi:

f* xw,s f* xw,z

Слева написано здесь вотчто: автомат находился в состоянии s и на входбылподан символx, при этом автомат перешел в состояние h x,s . Затем на вход подали w, автомат к этому времени находился в состоянии h x,s .Записывается это так: f x,s f* w,h x,s .

Аналогично для правой стороны: f x,z f* w,h x,z .

Получим: f x,s f* w,h x,s f x,z f* w,h x,z

Из этого равенстваделаем вывод:

,,

f w,h x,s f w,h x,z

То есть состояния h x,s и h x,z являются i эквивалентными на любом слове длиныi совпадают их реакции – напомним, w принадлежит Xi .

Но по условию реакции Ri иRi 1 совпадают Ri Ri 1 . Атакже h x,s иh x,z являются i 1 эквивалентными. Отсюдаполучаем, что длялюбого символаа из алфавитаХ совпадут реакции этих состояний навходное словоwa:

f* wa, h x,s f* wa,h x,z

По аналогии с тем, что делали чуть выше:

,	,
f w ,h x,s	f wa,h x,z

Во второй строчке написано: находясь в состоянии s, подали на вход х – перешли в состояние

hx,s . Затемподали на вход символwa, уже находясь в состоянии h x,s , и получили выход: f* wa,

hx,s .

Это же можно записать в виде: f* xwa,s f* xwa,z . Получили совпадения для слов длины i 2 , то есть s и z– i 2 эквивалентные.

Почему? Напомним: w принадлежит Xi,в товремя как«а» это один символ из Х.

Отсюданепосредственно следует, что Ri 1 Ri 2.И правда, достаточно вспомнить определение: Состояния s и z автомата А назовем эквивалентными, если они имеют одинаковую реакцию.

Утверждение 1 вспомогательное доказано.

	ξi (количество блоков в разбиении Ri) больше i.
Утв. 2 вспомогательное .
Если Ri Ri 1, то

Обозначается ξi > i, i=1,2…

Пример: построим разбиение R4 проверим все слова длины 4 . И получим, например, 3 блока. Затем построим R5и получим 4 блока. Это утверждение показывает, что такое невозможно: если R4 R5,то количество блоков в разбиении R4 будетбольше4 минимум5 .

Доказательство по индукции .

1.Пусть i 1 R1 R2

Докажем, что ξ1 > 1 (количество разбиений в блоке R1 больше 1).

Пусть это не так, и ξ1 = 1 (то есть множество никак не разбилось). Тогда любые s и z из S являются 1-эквивалентными. В частности, для любого х из Х: h(x,s) и h(x,z) также являются 1-эквивалентными.

Тогда f(y, h(x,s)) = f(y, h(x,z)) для любого y из У.

Ну действительно, чуть выше написано, что любые два состояния из S являются 1- эквивалетными. s и z – тоже.

Приходим к вот такой системе:

,	,	все уже получали и видели.
f ,h x,s	f y,h x,z

Опишем словами первое уравнение: находились в состоянии s, подали навходx;находились в состоянии z, подали навходх–выходные символы совпали.При этом в первом случае перешли в состояние h x,s , вовтором – h x,z .

Опишем словами второе уравнение: находились в состоянии h x,z ,подали на вход y; находились в состоянииh x,z ,подали на вход y–выходные символы совпали.

Это можно записать одной строкой, означающей последовательную подачу на вход символов х и у.

f* xy, s

f* xy, z

Надеюсь вы помните, что х иу – этонекоторые символы. Ачто такое ху? Это уже слово длины 2. Из последнего выражения следует, что реакции s и z налюбоеслово длины 2 т.к.x иу – любые совпали. А значит, s и z являются 2 эквивалентными.

Получаем противоречие: в условии теоремы точнее, второго вспомогательного утверждения написано, что Ri Ri 1, амы получили, что любыедвасостояния являются 2 эквивалентными, то есть R1 R2.

Полученное предположение доказываетпервый пункт. Вспомните «Докажем, что ξ1 > 1. Пусть это не так, и ξ1 = 1…».

Итак, отбросив лишнее, имеем: ξ1 > 1.

2.	Предположение индукции.				ξk > k
	Пусть для i k из Rk		Rk 1 выполняется
3.	Докажем, что если		Rk 1	Rk 2, то выполняется		ξk+1 > k+1.
	Напомним,
		количество разбиений в блоке Rk, а блок Rk показывает реакции на

слова длины k. Поехали.

Так как Rk+1 ≠ Rk+2, то из утверждения 1 следует, что Rj ≠ Rj+1, где j=1..k.

//Не самый очевидный факт, поясним его. Вспомним утверждение 1: если Ri = Ri+1,

//то и все последующие совпадут: Ri = Ri+1 = Ri+1… А если Rj ≠ Rj+1, то и дальше так

//пойдет: Rj ≠ Rj+1 ≠ Rj+2…

Предположим обратное пункту 3. Пусть теперь ξk+1 ≤ k+1. Тогда, так как Rk ≠ Rk+1, то из предположения индукции (пункт 2) следует, что ξk > k.

Количество блоков разбиения Rk+1 можем увеличиться по сравнению с Rk (помните, недавно было, что Rk+1 – это продолжение разбиения Rk?).

А теперь – полуфинал (нет, не теоремы, а второго утверждения ;)). Напишем в строчку столбик все то, что мы сейчас обсуждали.

1. ξk > k

2. ξk+1 ≥ ξk – количество блоков может остаться неизменным или увеличиться 3. ξk+1 ≤ k+1 – из строки «предположим обратное…»

А вот теперь запишем в строчку:

kξk ≤ ξk+1 ≤ k+1

Не нужно быть жестким криптографом, чтобы увидеть здесь следующее: ξk = ξk+1 = k+1

Подсказка - ξk (количество разбиений) – это целое число. Бывает и дробное, но только на новейших квантовых криптокомпьютерах с сетевой картой Асус, которые мы не рассматриваем.

Финал доказательства утв. 2 .Чуть выше получили ξk+1 = k+1, то есть количество разбиений блоков Rk и Rk+1 совпало. Но это означает, что сами разбиения Rk и Rk+1 совпали, что противоречит предположению индукции (Rk Rk 1).

Полученное противоречие доказывает п.3 (который начался со слов «Предположим обратное пункту 3»).

Утверждение 2 (вспомогательное) доказано.

Тем временем, мы все еще в процессе доказательства теорема Хафмана-Мили, но уже близки к концу. Осталось вспомнить все, что было раньше, объединить и сделать вывод, достойный лишь истинного криптографа.

Вспоминаем: был автомат А с n состояниями. Если	Rn Rn 1, то	ξn+1 > n+1 (второе
вспомогательное утверждение).

Однако заметим, что больше n блоков мы точно не получим: состояний всего n. То есть на некотором шаге n-1 мы получим разбиение на блоки по 1 элементу.

Так как дальше разбиваться нечему, то получимRn 1 Rn.

Вспоминаем 1 вспомогательное утверждение:

Если Rk 1 Rk, то Rj Rk для любого j k

И видим,что только что мы, самитого не подозревая, доказали теорему Хафмана Мили. Специально не буду копировать ее сюда, чтобы вы перелистнули назад и убедились, что последняя строчка доказывает именно то, что написано в ее условии. И оценили, насколько теорема большая.

Замечание.

Для распознавания двухсостояний автомата Мили с n различными внутрениими состояниями, значение длины слов n 1 не улучшаемо.

Другими словами: перебирать нужно слова именно длины n 1. Не меньше.

Без доказательства.