Razbor_kriptov_-_chast_2

Свойства.

1.Обе последовательности содержат конечное число различных элементов. Пояснение: сами последовательности бесконечны, но число различных элементов конечно ввиду конечности множеств Х и П(Х).

2.Обе последовательности являются периодическими.

Пояснение: так как в них конечное число различных элементов, рано или поздно начнутся совпадения (g5 = g12, например). В таком случае:

{g, g2, g3, g4} – предпериод {g5, …, g11} – период

Ну и дальше: g5 = g12, g6 = g13, g7 = g14 и т.д.

Опр. Периодом элемента х относительно преобразования g называется период последовательности g_(x).

Опр. Предпериодом элемента х относительно преобразования g называется предпериод последовательности g_(x).

Обозначается tx,g и vx,g.

Утв. Для любого преобразования g из П(Х) и для любого х из множества Х сумма длин периода и предпериода не превышает мощности Х.

tx,g + vx,g ≤ |X|

При этом равенство будет (tx,g + vx,g = |X| ) в случаях:

1.Если преобразование является полноцикловым (граф является единым циклом без подходов)

2.При наличии подхода, но только если он начинается с элемента х. Это вот так:

Графы были подробно разобраны в предыдущей части разбора, поэтому не будем на них останавливаться. Продолжаем утверждение.

1.Если х – циклическая вершина в графе преобразования g (Г(g)), то длина предпериода элемента х относительно преобразования g равна 0, а длина периода равна длине цикла в графе Г(g), на котором находится вершина х.

В виде значков это выглядит так:

Vx,g = 0; tx,g = длине цикла, содержащего х, в Г(g).

2.Если х – ациклическая вершина (находится на подходе в графе Г(g)), то длина предпериода vx,g равна длине подхода от x к циклу в Г(g), а длина периода tx,g равна длине этого цикла.

На всякий случай – картинка:

Покажем справедливость утверждения на примере.

Пусть g – преобразование множества V3 регистра правого сдвига с функцией обратной связи f = x1 x2x3.

*Регистры тоже взяты из прошлого семестра, тут снова без остановок. Функция обратной связи не биективна, так как x1 x2x3 не биективна по выталкиваемой переменной – x3.

А раз функция обратной связи не биективна, в графе Г(g) такого регистра будут подходы. Построим его.

Определим длину предпериода и период для вершины 110. V110, g = 0 – так как находится на цикле

T110, g = 4 – длина цикла, на котором он находится Действительно, последовательность будет выглядеть так: g_(110) = {(110), (111), (011), (101), …}

Аналогично можно посмотреть для любого элемента. Например, 010: V010, g = 2 – длина подхода, на котором он находится

T010, g = 1 – так как не находится на цикле (в таком случае период = 1)

Опр. Периодом преобразования g называется период последовательности g_ = {g, g2, g3, …}.

Опр. Предпериодом преобразования g называется предпериод последовательности g_ = {g, g2, g3, …}.

Обозначается vg и tg.

Утв. Для любого g из П(Х) (преобразований множества Х): Tg = НОК(l1, …, lm) – НОК длин циклов

Vg = max(c1, …, xm) = максимальная из длин подходов

Ну действительно, если нужно, чтобы на всех элементах совпали 2 преобразования:

gs = gp, где s≤p

Нужно взять НОК длин циклов. Ведь если длина периода первой равна 3, а второй

– 5, то совпадения в обоих начнутся с 15.

Замечание. Для любого g из П(Х), где x принадлежит множеству Х, выполняется: 1 ≤ tx,g ≤ n, где |X| = n (мощность Х равна n)

1 ≤ tg ≤ n!

Рассмотрим, когда наступают граничные случаи.

tx,g = 1 – когда элемент х находится на петле или подходе к петле tx,g = n – в случае полноциклового преобразования

tg = 1 – (не понял) когда граф состоит из несколькиз циклов с подходами? tg = n! – невозможно определить

Полноцикловые преобразования

Опр. Преобразование g множества Х мощности n называется полноцикловым, если граф Г(g) представляет собой цикл длины n.

Замечание. Всякое многоцикловое преобразование биективно. Tg = tx,g = n

Vg = vx,g = 0

Для любых х из множества Х.

Теорема. Число различных полноцикловых преобразований множества Х мощности n равно (n 1)!

Действительно, сколькими способами можно расставить n элементов на цикле? Правильный ответ – n!

Но при этом будет получено n одинаковых циклов, отличающихся только сдвигом (см. картинку). Поэтому делим на n и получаем: n!/n = (n 1)!

Немного обозначений. Пусть Ek – множество вычетов по модулю k (множество целых чисел от 0 до k 1). Пусть g: Ek > Ek (на входе элемент из Ek и на выходе тоже) Теперь мы готовы к следующему определению.

Опр. Линейный конгруэнтный генератор (ЛКГ) – это преобразование вида g(x) = (ax + b)mod(k)

где a,b,k – множитель, сдвиг и модуль ЛКГ.

Замечание. ЛКГ имеет период длиной не более k.

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

Замечание. Если tg = k, то g называется ЛКГ полного периода.

Теорема. Длина периода ЛКГ равна k тогда и только тогда, когда выполнены условия:

1.(b,k) – взаимно просты

2.(a 1) – кратно любому простому делителю k

3.(a 1) кратно 4, если k делится на 4 (обозн. 4|k).

Другими словами: если нужно проверить, что длина периода ЛКГ равна k, нужно проверить эти 3 пункта.

Идем дальше. В частности, если модуль ЛКГ k=2r, то ЛКГ имеет полный период тогда и только тогда, когда:

1.B – нечетное

2.A сравнимо с 1 по модулю 4 (проще говоря, остаток от деления k на 4 равен 1).

Утв. Пусть n > 1, g,ϕ – преобразования Vn и Vn 1 соответственно, где: g(x1…xn) = {f1(x1…xn 1), … , fn 1(x1 … xn*1), fn(x1…xn)}

ϕ(x1…xn) = {f1(x1…xn 1), … , fn 1(x1 … xn*1)}

Тогда g – полноцикловое тогда и только тогда, когда ϕ – подстановка (биективное преобразование) Vn 1 и fn(x1..xn) = h(x1…xn 1) xn, где вес функции h нечетен (напомним, вес функции – это количество единиц в ее таблице истинности).

Сначала кажется, что выше написано что то сложное, но уже после повторного прочтения оказывается, что это не так. Вот смотрите: есть ϕ и g, формулы для которых написаны выше. Тогда g – полноцикловая, если ϕ – биекция и выполняется одно условие для fn.

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

Утв. Пусть gn – треугольная подстановка множества Vn, задаваемая системой координатных функций:

1	1
2	1 2
	1..

g – это биекция (иначе о полноцикловости дальше можно не говорить), причем:

fi(x1…xi) = xi h xi … xi 1 , где i 1..n – то есть функция линейна попеременной с наименьшим номером.

Тогда подстановка g –полноцикловая тогда и только тогда, когда функция h1 1 и вес hi нечетен, где i 2..n начинается с двойки, так как первый обязательно должен быть равен 1 .

Принципсклеивания/расклеивания.

На самом деле, сейчас мы будем говорить не об этом. К принципу перейдем чуть позже, а пока – вступление.

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

f x1…xn	x1 ϕ x2 … xn
и	x2a2 … xnan, где:
f x1..xn		1
	,
	,	0

Тогда граф преобразования g – Г(g) – отличается от графа Г(h) тем, что либо 1 цикл в графе Г(g) распадается на 2 цикла в Г(h), либо 2 цикла в Г(g) объединяются в 1 в

Г(h).

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

Итак:

f x1…xn x1 ϕ x2 … xn первая функция обратной связи x1 ϕ x2 … xn x2a2 … xnan – вторая функция обратной связи

Так как регистры по условию биективны, то f будет биективной по выталкиваемой переменнойx1.

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

g x1…xn x2, …, xn, x1 ϕ x2 … xn

h x1…xn x2, …, xn, x1 ϕ x2 … xn x2a2 … xnan

Вопрос – на каких векторах g и h принимают разные значения? Они ведь различаются только подчеркнутой частью!

Очевидно, они будут разными, если x2a2 … xnan 1. А это происходит, когда все х равны а и равны 1. Вспомните:

,1 (not x записывается как х с верхним подчеркиванием)

,0

Собственно, это то, что нужно было заметить. Ставим галочку. Теперь рассмотрим утверждение.

Утв. Значения регистров сдвига g и h будут различаться лишь на следующих векторах:

(0, a2, …, an) и (1, a2, …, an)

Покажем это:

g(0, a2, …, an) = (a2, .., an, ϕ(a2, …, an))

g(1, a2, …, an) = (a2, .., an, 1

ϕ(a2, …, an))

h(0, a2, …, an) = (a2, .., an, 1

ϕ(a2, …, an))

2

n

2

n

,

ϕ(a2, …, an))

h(1, a , …, a

) = (a , .., a

a2

an

1,

Почему так? Вспомните, что мы заметили чуть раньше. А именно:

2

n

) справа

окажется 1

когда все хравны а иравны 1. Поэтому для h(0, a , …, a

x2

… xn

1 0.

А теперь плавно переходим к демонстрации корректности теоремы, которая была чуть выше. Оно вытекает прямо из утверждения. А утверждение из того, что заметили чуть раньше. Чувствуете? Это и есть понимание криптографии.

Пусть вершины (0, a2, …, an) и (1, a2, …, an) лежат на 1 цикле в графе Г(g). Построим граф Г(g).

Поправим направление стрелочек и получим граф Г(h):

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

Проверим все те же 2 точки, подкорректируем и получим граф Г(h):

Итак, как вы помните, h отличается от g только наличием дополнительного элемента коньюнкции. В примере показано, что при переходе от g к h либо 1 цикл распадется на 2, либо 2 объединятся в 1. Определить это легко: по тому, на одном или разных циклах лежат указанные 2 точки (они указаны в утверждении выше).

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

А мы его изменили: теперь 1 переходит в 6, в 5 – в 2. Цикл распадается на два.

А пока пойдем дальше, непосредственно к склеиванию.

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

1.Определить пары векторов (0, a2, …, an) и (1, a2, …, an), которые принадлежат разным циклам

2.Добавить (операцией к функции обратной связирегистра сдвига элементарную конъюнкцию x2a2 … xnan

Это прямо следует из предыдущейтеоремы – за каждый раз можно склеивать по 2 цикла в 1. Пример уже только что рассмотрели. Склеив все циклы в 1, получим полноцикловый регистр сдвига (подходов нет, так как по условию все биективно).

Замечание. Если в графе регистра сдвига r циклов, то для построения полноциклового регистра сдвига необходимо выполнить (r 1) раз шаги 1 2, указанные выше.

Пример.

Пусть g – преобразование множества V3 регистра левого сдвига с функцией обратной связи f=x3 x1x2 1. Построить полноцикловый регистр.

Обратите внимание, если Вам это удастся, то Ваш диплом будет сразу отправлен в корзину. Потому что это невозможно, так как x3 x1x2 1 не линейна по x1 – выталкиваемой переменной.

Поэтому функцию обратной связи заменим на линейную по x1. Вот такую: f x1 x2x3 1. И начнем построение с графа Г g :

С чего начать склеивание? Правильно, с пункта 1, а именно поиска вершин 0a2a3 и 1a2a3. То есть различающихся только первой координатой. Они подчеркнуты на рисунке красным.

Вспоминаем:	1
,
Поэтому 10 в нашем случае – это x2not(x3). ,	0	x2not(x3).
Добавляем к функции обратной связи:f x1 x2x3 1

Смотрим, что произойдет с графом. Помним, что смотреть нужно только на выбранные ранее 2 вершины – 010 и 110.

«Переводим» 11 в x2x3 и снова добавляем ее к функции обратной связи: f x1 x2x3 1 x2not(x3) x2x3

Получаем:

На выходе получили полноцикловый регистр сдвига. Причем действовали строго по инструкции из 2 пунктов, что и показывает ее правильность.

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

Линейный регистр сдвига

Может ли линейное преобразование быть полноцикловым? Запомните – никогда! Сейчас напишу, почему. Дело в том, что линейное преобразование– это преобразование, где каждая координатная функция линейна. Что будет в нуле? Петля! Всегда. Потому что если на вход линейной функции подать 0, она будет равна 0. А здесь все функции линейны. Это на понятном языке. А теперь – то же самое на научном.

Замечание.

Линейное преобразование пространства Рn над полем Р не является полноцикловым, так как нулевой вектор является неподвижным элементом любого линейного преобразования.

Опр. Линейное преобразование пространства Pn (причем |P| = k) с длиной периода kn 1 называется линейным преобразованием максимального периода.

Пояснение: всего в множестве kn элементов (n векторов, каждый из k координат). Степень (n 1) потому, что нуль в период не входит – как уже ранее заметили, на нем будет петля.

Пусть g – преобразование линейного регистра сдвига с функцией обратной связи f = an 1xn + … + a1x2 + a0x1, где a0…an 1 принадлежат P.

Тогда справедливо определение.