Razbor_kriptov_-_chast_2

Следствие. Проблема распознавания эквивалентности двух автоматов Мили алгоритмически разрешима.

Другими словами: за конечное число шагов можно проверить эквивалентностьна абсолютно всех словах по факту проверив только на словах длины n 1 .

Теорема о сокращенном автомате.

Длякаждого автомата Мили может быть построен единственный с точностью до изоморфизма обозначения элементов S эквивалентный ему сокращенный автомат.

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

Для начала напомним, что автомат не является сокращенным, если есть какой либо класс эквивалентных состояний. А вотесли любые 2 состояния не эквивалентны – автомат получает полное право называться сокращенным.

Пусть есть класс эквивалентных состояний автомата А. Поставим всоответствие всем этим состояниям одно единственное состояние автомата А’.

Тогда любые 2 состояния автомата А’ будут не эквивалентны. При этом автоматы А и А’ будут совпадать с точностью до обозначений элементов S.

Замечание. Построение сокращенного автомата может бытьвыполнено законечное число шагов.

То есть нашли эквивалентные состояния –объединили в одно, и т.д., пока не получим сокращенный автомат.

Опр. Входные последовательности v,w из X*не различимы автоматом А, если для любого состояния s из множества состояний S и для любого символаuиз Х выполнено:

f* vu, s

f* wu, s

Конечно же, v и w – словаодной длины принадлежат одному множеству слов Х* .

Пояснение неразличимых входных слов:

1.Были в состоянии s, подали v – получили выходное слово

2.Были в состоянии s, подали w – получили то же выходное слово.

То есть, зная s и выходное слово, определить, что былоподано на вход: vи w.

В противном случае говорят, что v и w различимы автоматом А.

Опр. Автомат А называется различающим входа, если любые2 входные последовательности различимы автоматом А.

Лемма. Входные слова v и w из Х* не различимы автоматом А тогдаи только тогда,когда:

1.Для любогосостояния s из S эквивалентны h* v,s иh* w,s

Напомним, h – состояние, в которое перейдетавтоматпри подаче символа v или w.

2. f* v,s f* w,s – совпадают выходные символы

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

Докажемв сторону « », в обратную – аналогично.

Пусть входные слова v и w не различимы автоматом А, s – некоторое произвольное состояние автомата А. Тогда, по определению неразличимых слов, для любых слов uиз Х выполняется:

f* vu, s f* wu, s – слева означает последовательную подачу на вход «v» и «u».

Перепишем в более подробном виде:

f* v,s f* u,h* v,s

f* w,s f* u,h w,s

Это можно записать в виде системы:

,,

f ,h v,s f u,h v,s

Первое уравнение системы: первые выходныеслова совпали

Второе уравнение системы: показывает, что состоянияh v,s и h ,s эквивалентны подали на входодинаковое слово–получили одинаковые выходные слова .

Доказано.

Предисловие. Определение автомата, различающего входы,казалось бы,не вызывает сложностей. Однако, как его определить в конкретном случае? Перебирать словавсех возможных длин бесконечный цикл? . Нет, всего лишь воспользоваться нужной теоремой.

ТеоремаЧена.

Пусть А – автомат Мили с n состояниями. Если любые двевходные последовательности длины n2n 1 различимы автоматом А, то автомат А – автомат, различающий выходы.

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

Следствие.

Задача распознавания различимости входовавтоматом алгоритмически разрешима.

Периодичностьвконечныхавтоматах.

Обозн. dS – число состояний автомата А X,S,Y,h,f , достижимых из состояния s.

Или по научному: ds | z S, z h* w,s , w X* |

Пояснение: количествосостояний z автомата А, в которые можно перейти из состояния s при подаче некоторой входнойпоследовательности w.

Замечание. Если автомат А сильно связен, то dS	nдлялюбого состояния s S, где |S| n.
Замечание. Для любого состояния sавтомата: dS	0 и не больше мощности компоненты
связности автоматного графа, содержащей s.

Пример не уверен в правильности . Напомним, что понятие компоненты связности относится к неориентированным графам:

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

Построим 2 такие компоненты то есть без стрелочек :

На картинке слева имеем, что dS равно мощности компоненты связностии равно 2.

А что на картинке справа? Мощность компоненты равна 3, аdS равна 2. Именно поэтому в замечании написано «не больше», а не «равно».

Теорема.

Под воздействием входной периодической последовательности Х_ с длиной предпериодаv и длиной периодаt неавтономный автомат Мили А X,S,Y,h,f при начальном состоянии s проходит периодическую последовательность состояний S_ s с длинойпредпериода v’ s и длиной периода t’ s ,выдавая периодическую выходную последовательность Y_ s сдлиной предпериода v’’ s идлиной периода t’’ s , где:

1.	v’ s	и v’’ s	v	dS– 1 t
	Пояснение: на вход подали последовательность v,t –с длиной предпериодаv и длиной
	периода t. При этом проходим последовательность внутренних состояний v’ s ,t’ s и
2.	получаем на выходе последовательность v’’ s ,t’’ s .
	t’ s	и t’’ s	D t	D 2t … D ds*t , где D–множество делителей
3.	t’ s	v’ s	v	dst

4.Если А– автоматМура т.е. внешне автономный, или функция выходов f не зависит от Х ,

то t’’ | t’ s .

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

Следствие 1.

Если функция переходов h x,s инъективна по входной переменной х, то t’ s tay*t, где tay D 2 D 3 … D dS .

Напомним, инъективность – это когда при изменении х меняется и значение функции.

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

Пусть t не делитt’ s . Тогда xi xi t’ s при некотором i v.Таккак h x,s инъективна по х, тодля любого состояния s из S:

h xi, s h xi t’ s , s .

Пояснение. Были в состоянии s и подали i й символ последовательности. То есть на следующем

шаге	i	1 шаге будемнаходиться в состоянии h xi, s . Аналогично h xi t’ s ,s – состояние, в
которое перейдем после i t’ s 1тактов. Это можно записать через обычные s:
si 1	si	t’ s 1.

Но это противоречит тому, что t’ s – длина периода S_ s .Это говорит о неверности предположения «Пусть t не делит t’ s ». То есть t’ s имеет вид t’ s tay*t.

Отсюдапо предыдущей теореме из делителя вынесли t : tay D 2 D 3 … D dS .

Доказано.

Другими словами: требовалось показать, что если подать на входпериодическую последовательность с длиной периода t и функцией перехода, инъективной по х, то пройдем последовательность состояний с длиной периода tay*t. Предположили, что равенство не выполняется, то есть t не делит t’ s ,где t –длинапериодавходной последовательности, а t’ s – длина периода последовательности состояний. Так как периоды не совпадают, значит, на расстоянии t’ s в последовательности Х есть разные элементы. Если естьразные элементы – то и внутренние состояния будут разными не забывайте об инъективности по х . Противоречие – последовательность внутренних состояний имеет период t’ s , а значит, на данном расстоянии в ней должны стоять одинаковые элементы.

Следствие 2.

Пусть А – регулярный автомат. Введем функции:

g’ hxv * … *hx1

ghxv t *… * hxv 1

где g и g’ : S S.

Тогда:

1.v’ s и v’’ s v –длиныпредпериодов последовательности внутренних состояний и выходной последоватльности меньше v

2.t’ s и t’’ s –делитель числа lSt, где lS – длинацикла подстановки g, на котором находится элемент g’ s .

Вчастности, если х – чисто периодическая последовательность, то lS – длина цикла подстановки g hxt *… * hx1 , на котором находится состояние s.

Теорема из двух пунктов .

1.Если А S,Y,h,f –автономный автомат, то при начальном состоянии s S, имеющим длину предпериода v s и длину периода t s относительно преобразования h, автомат А генерируетвыходную последовательность с длиной предпериода vs и длиной периода ts,

где vs v s и ts | t s .

2. Пусть задано множествоY y0,…,ym 1 , обозн. kj – частота элемента yj в отрезке выходной последовательности v s 1, v s t s . Тогда:

ts , d’ НОД k0,…,kn 1 .

Доказательство пункта 1.

Задан автономный автоматА S,Y,h,f .Вкаждом такте выдается выходной символ f s и осуществляется переход в новоевнутреннее состояние h s .

s – f s ; h s

Затем h s f h s ; h2 s

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

fi s f hi 1 s –в состоянии hi 1 s применили функцию f.

Обозн. f h s – выходная последовательность автомата А.

При этом t hi s	t s – длинапериодапоследовательности состояний равнапериоду
исходной последовательности недавно было .Аналогично v hi s		v s

А теперь ключевой момент. Вспоминаем определение усложненной последовательности, которое совсем недавноказалось непонятным:

Опр. Последовательность Y_={f(xi1,…,xin)} (пояснение: берем 1 элемент из Х1_, 1 элемент из Х2_ и т.д. и к этому набору применяем f), полученная из последовательности X_ = {(xi1, …, xin)} над декартовым произведением множеств Х1..Хn (т.е. каждый элемент – вектор из n координат) с помощью функции f: X1 x X2 x … x Xn -> Y, называется усложненной по отношению к исходным

последовательностям X1 … Xn, а f – функция усложнения

последовательностей X1…Xn.

И замечаем, что выходная последовательность	f h s является усложненной по отношению к
последовательности внутренних состояний hi	s , где f– функция усложнения. Даже пояснять

не нужно, просто посмотрите еще раз на определение. Потом на f h s .Потом снова на определение… Заметили? 

А из этого непосредственно следует, что длина периода выходной последовательностиделит длину периода последовательности внутренних состояний. И длина еепредпериода не превышает длину предпериода последовательности внутренних состояний.

Не нашел самих свойств усложненных функций, из которых это следует. Но тем не менее, это так.

Доказательство пункта 2.

Перед нами – все тотжеавтономные автоматА S,Y,h,f .

Из пункта 1 следует, что длинапериодавыходной последовательности делит длину периода последовательности внутренних состояний. Это можно записать в виде:

t s d’t s ,где d’ N.

То есть в периоде внутренних состояний «помещается» d’ периодов выходной последовательности. Воспользуемся этим.

Рассмотрим отрезок выходной последовательности v s 1, v s t s .

Так как t s – период последовательности внутренних состояний, то в таком отрезке находится d’ штук периодов выходной последовательности. Подождите читать дальше, пока не поймете это. Можно перечитать последние несколько абзацев.

Теперь вспомним обозначение,введенное прямо в теореме: «kj –частотаэлемента yj».

Попробуем определить d’ через k. Это не сложно. Так как ищемдлину периода выходной последовательности при заданной входной Y y0, …, ym 1 , а kj – частота элемента yj, то достаточно взять их НОД: d’ НОД k0, …, km 1 . Это проще понять, чем объяснить, поэтому перечитайте еще раз.Можетедаже на последовательности какой нибудь попробовать.

Отсюда d’ | kj. Чуть раньше также записали: t s d’t s .

Доказано.

Другими словами: доказали, что еслиА – автономный автомат, то последовательность внутренних состояний является периодической так как s–конечно . Атакже два соотношения для выходной последовательности: vs v s и ts | t s . Затем взяли отрезок последовательности выходных состояний, точно находясь на ее периоде. И целое количествораз встретили на ней период выходной последовательности. Откудасделали вывод: d’ | kj.

Следствие 1.

Пусть при начальном состоянии s длина периода последовательности S_ s есть простое число t s , тогда если ограничение функции f на период последовательности внутренних состояний S_ s есть константа, то длина периодавыходной последовательности равна 1, иначе – длина

периода входной последовательности равна ts		t s .
Доказательство.		h s	h2 s …
Переходы внутренних состояний обозначим: s
t hi s	t s – простое число поусловию .

Из пункта 1 недавней теоремы: ts | t s , следовательно:

s	1 если все элементы одинаковые напериоде посл.	s принимает одинак.значения
t	в остальных случаях

Это все потому, что t s – простое и не может ни на что делиться! И ts | t s фактически означает ts t s .

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

Следствие 2.

В условияхпункта 2 теоремы из двухпунктов равенство длинпериодов выходной последовательности и последовательности внутренних состояний ts t s возможно,если НОД k0,…,km 1 1.

На этом длинная и сложная лекция закончилась.

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

Тема«Рекуррентныезависимостиистатистическиесвойствавпсевдослучайных последовательностях».

Опр. Случайная идеальная последовательность является реализацией последовательности равномерно распределенных на некотором алфавите – прим.ред. случайных величин. Обозначается РРСП: равномерно распределенная случайная последовательность.

Пример: бросаем монету, выпадает «орел» 0 или «решка» 1 . В результате серии бросков получим последовательность РРСП. Почему? Потому что, бросив монету 1000 раз и зная полученные результаты, нельзя предсказать результат 1001 броска. Совсем. Здесь дажесамые жесткие криптографы бессильны. Обычно, получая случайную последовательность, хотят получить последовательность, близкую к РРСП.

А теперь то же, но научным языком:РРСП намножестве Х мощности k – это последовательность случайных величин, принимающих значения на множестве Х. Обозн. ξ1, ξ2, …

ТребованиякРРСП

1. Независимость. Для любого n идлялюбых индексовξt1,…tn, упорядоченных по
возрастанию 1 t1 … tn случайные величины	t1	…, ξtn независимы в

совокупности.

Другими словами: любые броски монеты независимы.

2.Равномерность. Для любого t случайная величина ξt равномерно распределена на множестве Х. То есть вероятность того, что она принимает некоторое значение х:

P(ξt == x) = 1/k для любого х их Х.

Другими словами: все элементы равновероятны

Важно: если пункты 1 и 2 выполнены, то последовательность является РРСП.

Свойства РРСП

1. Для любого n и		t1…tn, упорядоченных повозрастанию 1 t1 …
для любых индексовξ ,
tn n мерная случайная величина	t1	…, ξtn	равномерно распределена на множестве Xn.

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

2.Воспроизводимость при прореживании: любая подпоследовательность РРСП также является РРСП.

Другими словами: берем не все битыРРСП, атолько ихчасть –полученная последовательность также являетсяРРСП. Например, выберем только четные броски монеты –все равно получим РРСП. Важно: выбирать можно только поиндексам. По значениям нельзя – то есть чит«выберем все единицы» не работает 

3.Воспроизводимость при суммировании: если Х – аддитивная группа (относительно

операции сложения), то {Фt} – произвольная неслучайная (или случайная) последовательность, не зависящая от РРСП { ξt }, то последовательность {Yt} : yt=Фt + ξt также является РРСП.

Другими словами: есть 2 последовательности: одна РРСП, а вторая – любая (главное – они независимы). Так овт, если их поэлементно сложим – получим РРСП.

4.При любом натуральном t вероятность того, что ξt=х (t-й знак последовательности равен х, при условии, что известны первые t-1 знаков последовательности: ξ1 = x1, ξt-1=xt-1), равна: P(ξt == х | ξ1 = x1, ξt-1=xt-1) = 1/k.

Другими словами: знание предыдущих t-1 элементов последовательности никак не поможет в получении t-го элемента. Бросили монету 1000 раз – результат знаем. Но результат следующего, 1001-го броска, непредсказуем.

Атеперь ненадолго представьте, что Вы – криптограф, который построил поточный шифр, использующий РРСП в качестве шифрующей последовательности (гаммы). Представили? Достаточно. Не зря в начале было написано «ненадолго» - за подобное решение Вас сразу же уволят. Разберемся, почему.

Недостатки РРСП (о невозможности использования РРСП в качестве гаммы).

Пусть задан поточный шифр. На вход он принимает бит исходного текста xi, складывает с битом гаммы gammat и выдает зашифрованный символ yi.

Представьте, что есть отправитель и получатель. Отправитель шифрует текст с использованием гаммы и отправляет. Получатель, чтобы расшифровать его, должен пропустить его через ту же гамму! А откуда он ее возьмет, если нет возможности воссоздать ее? Даже если он бросит монету 1000 раз, как это сделал отправитель, он получит другую гамму и ничего расшифровать не получится.

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

Опр. Псевдослучайная последовательность на множестве Х определена как последовательность длины m, порожденная из случайной последовательности (РРСП) длины n с помощью детерминированной функции полиномиальной вычислительной сложности. Как правило, m >> n (m намного больше n).

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

А что такое «полиномиальная сложность»? Многие (как и я) слышали это на информатике, но боялись спросить. Так вот, сейчас это перестанет быть непонятными словами и разложится по полочкам. Момент настал. Поехали.

Опр. Полиномиальная вычислительная сложность означает, что число условных вычислительных операций (например, сложений и умножений) в определенном поле, которых достаточно для вычисления псевдослучайной последовательности длины m, ограничено сверху величиной f(n), где f(n) – положительный полином над кольцом целых чисел.

Другими словами: количество операций, необходимых, чтобы получить из короткой РРСП псевдослучайную последовательность, выражается как полином. Например, f(n) = n5+n3. Напомним: Полином (многочлен) от n переменных — это сумма одночленов.

Линейные рекурсивные последовательности (ЛРП)

Опр. Последовательность Х_={x0, x1, …} над множеством Х называется рекурентной последовательностью порядка n>0, если найдется функция f : Xn -> X, такая что для любого i≥0 выполняется xi+n = f(xi, …, xi+n-1).

Другими словами: каждый (i+n) член последовательности выражается некоторым способом через функцию f от n предыдущих. Если злоумышленник перехватит указанный участок последовательности, то сможет все восстановить.

Это равенство называется законом рекурсии. Функция f – генератор рекурсивной последовательности X_. Вектор (x0, …, xn-1) называется начальным вектором рекурсивной последовательности.

Обозн. При множестве Х мощности k рекурсивную последовательность порядка n над Х обозначим: РП(k,n).

Замечание. Длина периода РП(k,n) ≤ kn.

Пояснение: kn – мощность множества всех векторов длины n. Так как их всего kn, то потом обязательно начнутся повторения.

Замечание. Между множеством всех РП(k,n) и множеством регистров сдвига длины n над множеством Х мощности k имеется биекция. Если генератор РП(k,n) совпадает с функцией обратной связи регистра сдвига, то данная рекуррентная последовательность с начальным вектором (x0, …, xn-1) есть первая координатная подпоследовательность X1_ последовательности fg(x0, …, xn-1).

Напомним, fg – обозначение регистра левого сдвига с функцией обратной связи f.

Другими словами: есть регистр сдвига с начальным заполнением (x0, …, xn-1). В следующем такте он перейдет в (x1, …, xn-1, f(x0, …, xn)) и так далее. Если f совпадает с генератором РП(k,n) (т.е. для одних и тех же последовательностей выдает одинаковый выход), то если возьмем подпоследовательность Х1_, то получим РП(k,n).

Кажется сложно, но только на словах. Картинка проясняет неясность:

А именно, на ней мы видим исходную последовательность (x1, …, xn-1). Затем строится регистр левого сдвига (было в прошлом семестре). Получим набор последовательностей. И если взять только первые координаты этих последовательностей, получим РП(k,n). Все потому, что функция обратной связи совпадает с генераторм, то есть для одинаковых входных данных дает тот же результат.

Замечание.

j-я координатная подпоследовательность последовательности fg(x0…xn-1) (обозн. Xj_) отличается от Х1_ сдвигом на j-1 знак (так как вторая координатная последовательность начинается с x1, третья – с х2 и т.д.)

То есть j-я координатная подпоследовательность – это та же первая, только со сдвигом. Вспомним утверждение с девятой страницы:

Если X_ отличается от Х1_ лишь сдвигом на j 1 знак (например: 12345… и 23451…), то длина периода и длина предпериода:

t(X_) = t(X1_) ν(X_) = ν(X1_)

Вот по этому утверждению получаем: t(fg(x0…xn-1)) = t(X1_) = t(РП(k,n))

То есть длина периода РП(k,n) есть длина периода всей последовательности векторов, полученных с использованием регистра сдвига.