Razbor_kriptov_-_chast_2

Обозначим через φq бq, πq подстановку при фиксированном значении q Q q Q’ .Тогда подстановкаEk определена следующим образом алгоритм зашифрования :

Ek x πq_ r 1 φq_r … φq_1 бq_0 x , где х– блок открытого текста.

Другими словами: на вход поступил блок не символ! х.. Сначала применяется функциябq_0 x – входноеотображение на ключе q0. Затем r раз применяется отображение φq_r, …,φq_1 –раундовая функция на ключах q1…qr. И в конце – выходная функция πq_ r 1 наключе qr 1.

Алгоритм расшифрования состоитв реализации подстановкиEk 1:

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r π 1q_ r 1 y ,где у– блокзашифрованного текста.

!!! РАЗОБРАТЬСЯ, ГДЕ МИНУС 1 СТЕПЕНЬ А ГДЕ НЕТ !!! НИЧЕГО НЕ ПОНЯТНО В СТЕПЕНЯХ !!!

Другими словами: на вход поступил блок шифротекста у. Применяем сначалаπ 1q_ r 1 на ключе qr 1, затем φ 1q_r и т.ддоφ 1q_1, в конце б 1q_0. Обратите внимание на порядок преобразований: мы как бы«распутываем» то, что сделали на этапе зашифрования.

Опр. Часть итеративного алгоритма шифрования, ограниченная применением подстановкиφq_i, называется i тым раундом шифрования. При этом i 1..r– число раундов шифрования СБШ

Опр. Часть итеративного алгоритма шифрования, ограниченная применением подстановки

φ 1q_i, называется r i 1 тым раундомрасшифрования. При этом i 1..r– число раундов расшифрования СБШ.

Обратитевнимание: на каждом раунде работаетодна и таже функция φ,но на разных раундовых ключах.

Теперь дадим названия введенным нами функциям.

Если φ x’,q y’ или тосамое в другой форме: φq_i x’ y’ – навход i го раунда поступил блок x’ то векторыx’ и y’ –входной и выходной блокиi го раунда шифрования, а qi – раундовый ключ.

Накартинке изображено: былблокх,что то к нему применили, получили x’,применили φq_i, получили y’ и послали дальше.

Продолжаем. Отображения φ x,q , б x,q π x,q называются раундовой,входной и выходной функциями СБШ.

Стойкость обеспечивается раундовой функцией.

Величины q0 и qr 1 – ключи входнойи выходнойфункции.

Опр. Системафункций θ0,…,θr 1 с использованием которой по ключу k вычисляются ключи q0, …, qr 1 , называется ключевым расписанием СБШ.

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

Опытным криптоаналитикам всегда хотелось инволютивности шифра это когда одну и ту же функциюEk применяют для шифрования и расшифрования . И это достижимо путем подбора функций φ, б,π. Рассмотрим теорему на эту тему.

Перед началом, если забыли посмотрите чуть выше, что такое Q иQ’.

Теорема.

Если длялюбого ключа q Q’ подстановки бq x и πq x взаимно обратные, и длялюбого ключа qQ’ подстановкаφq x – инволюция, то алгоритм шифрования итеративного СБШ обратим, и расшифрование отличается от зашифрования использованием ключейв обратном порядке.

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

Одно из самых простых доказательств. Достаточно записать все, что намизвестно, и получим то, что и требовалось доказать.

Во первых, нам известны функции зашифрования и расшифрования чуть выше :

Ek x πq_ r 1 φq_r … φq_1 бq_0 x ,

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r π 1q_ r 1 y

Во вторых, мы знаем изусловия, что для любого ключа q Q’подстановки бq x иπq x взаимно обратные. Это означает, что:

1.	бq0 π 1q0 иπq0 б 1q0
2.	бq_ r 1 π 1q_ r 1 и πq_ r 1 б 1q_ r 1

В третьих, мы знаем, что φq x – инволюция, то есть: φq_i φq_i 1 для любогоi 1..n

Почти все. Теперь еще раз взгляните нафункцию расшифрования пункт«во первых» :

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r π 1q_ r 1 y

Смотрим пункт «во вторых» и заменяем б 1q_0 наπq0

Смотрим пункт «в третьих», понимаем, что «фи» вминус первой это то же самое, что и просто

«фи», и заменяем φ1q_1 … φ 1q_r на φq_1 … φq_r

Еще раз смотрим напункт«во вторых» и заменяем π 1q_ r 1 на бq_ r 1 .

Видим, что получилось то, что требовалось доказать:

Ek 1 y πq0 φq_1 … φq_r бq_ r 1 y

Теорема доказана.

ШифрФейстеля.

Предисловие.

Это один из подходов к построению раундовой функции.

Опр. Шифр Фейстеля – итеративный СБШ, раундовая функция которогопостроенаследующим образом:

1.Входнойблок разбивается на 2 половинки: х1 их2

2.На местопервогоблока перемещается блок х2

3.	Наместо второго записывается x1 ψ x2,q , гдеψ: Vn x Q Vn –функция усложнения
	шифраФейстеля
А раундовая функция выглядит так: φ x1,x2 ,q и действует вот так:
φ :V2n x Q		V2n
СхемашифраФейстеля.
φ	x1,x2 ,q	x2, x1 ψ x2,q

Даже добавить нечего – все очевидносоответствует трем шагам из последнего определения.

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

Обратитевнимание: это 1 раунд из шифра Фейстеля. Подробно нарисованный.

Замечание.

Варианты алгоритмашифраФейстеля могут отличаться:

1.Функцией усложнения ψ

2.Количеством раундов

3.Длиной блока

4.Ключевым расписанием

5.Входным и выходным отображениями

Вам тоже кажется, что это похожена регистр сдвига? Правильно. См.следующее замечание.

Замечание.

При раундовом ключе q преобразование φq есть преобразование регистра левого сдвига длины 2 т.к. в нем 2 ячейки: х1 их2 над множеством Vn с функцией обратной связи x1 ψ x2,q .

Другими словами: этот шифр можнореализовать как регистрлевого сдвига с указанной функцией обратной связи. Просто посмотрите еще раз на картинку и это станет очевидно.

Замечание.

Биективность преобразования φq равносильна биективности функции обратной связи по переменной х1,которая достигается независимо от конструкции функции усложнения ψ она можетбыть любой .

Сейчас Вы узнаете нечто новое из совсем базовой части. Обычно мырисовали плюс в кружочке и называли получившийся символоперацией XOR. Благодаря достижениям лучших криптографов, теперь плюс можно не только обвести вкружочек. Но и в квадратик! И это будет называться «сложение по модулю2n». Зачем это нужно? Смотрите.

Функция обратной связи записана как x1 ψ x2,q . Аможноли вместо XOR поставить сложение по модулю 2n?Можно: так как всего имеется 2n значений это количество мы определили в самом начале раздела , и функцияобратной связи биективна по «х», топри сложении его с различными числами будем гарантированно получать различные выходные значения. Вот и все. А теперь – в научном виде.

Замечание. Биективность раундовой функции сохраняется при использовании и других биективных по «х» операций, например, сложения по модулю 2n.

А теперь поговорим о преимуществах шифраФейстеля. Об этом написана одна лемма и целая теорема.

Лемма.

При любой функции усложнения выполнено φ 1q Tn φq Tn, где Тn – операция циклического сдвига вектора на n элементов влево.

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

Заметим, что Tn 1 Tn – инволюция почему???

Тогда перефразируем то, что нужно доказать. Покажем, что подстановки φq и φ 1q – сопряженные в группе циклических сдвигов T1 порождается сдвигом на 1 элемент . Вспомним, что такое сопряженность из прошлого семестра.

g,f – сопряженные отображения в группе H, если найдется такой h из H,что g h*f*h 1

Так как в нашем случае Tn 1 Tn, то это и докажетусловие леммы.

При любомq из Q и любых x1,x2из V2 умножимусловие φ 1q Tn φq Tn на φq: φq Tn φq Tn e

Это и будем доказывать. Что несложно:

Лемма доказана.

Теорема.

Если длялюбого q из Q’выполненоπq x бq 1 *Tn x ,то шифр Фейстеля обратим и расшифрование отличается от зашифрования лишь использованием раундовых ключей в обратном порядке.

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

Снова вспомним функции зашифрования и расшифрования:

Ek x πq_ r 1 φq_r … φq_1 бq_0 x ,

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r π 1q_ r 1 y

Из условия теоремы: πq x бq 1 * Tn x . Заменяем в функции зашифрования:

Ek x бq_ r 1 1 *Tn x φq_r … φq_1 бq_0 x ,

Тогда функция расшифрования примет вид:

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r Tn 1 x *бq_ r 1 1 y

Вспоминаем из начала доказательствапредыдущей леммы , что Tn 1 Tn. Тогда:

Ek 1 y б 1q_0 φ 1q_1 … φ 1q_r Tn x *бq_ r 1 1 y

Вспомним, очем была лемма φ 1q Tn φq Tn . Перепишем все «фи» в таком виде:

Из последнего выражения получаем:

Ek 1 y бq_0 1 *Tn x φq_1 … φq_r бq_ r 1 y

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

Теорема доказана.

Построениераундовойфункции.

СпособыусложненияшифраФейстеля.

Пусть раундовые ключиблочного шифра являются двоичными векторами, при этом Q Vn, а раундовая функция СБШ есть отображение V2n m V2n.

//Другими словами: то же, что V2n x Vm V2n.Навходе блок длины 2n и раундовыйключ длины m, на выходе – блок длины 2n.

Кроме того, функция усложнения шифраФейстеляестьотображение: Vn m Vn.

Замечание.

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

Конструктивные слои раундовых функций имеют следующее функциональное назначение:

1.Перемешивание входных блоков

2.Подмешивание раундового ключа

3.Реализация сложной нелинейной зависимости между знаками ключа входного и выходного блоков.

Дополнительно. Как реализуется нелинейность? Есть блок, он разбивается на куски, например, по 6 бит. Затем каждыйпроходит через S блок перестановок переменных . И полученные биты зависят с высокойстепенью нелинейности от входных.Потом результат перемешивается, и уже на следующем раунде будет зависеть не толькоот 1 , нои от 2 .А если не перемешивать – то будет зависеть всегда только от входных данных так как в таком случае эти данные просто пройдутчерез несколько S блоков .

Лекция последняя.

Наней рассмотрим правила построения раундовой функции, узнаем подробнее про S – блоки, увидим несколько новыхсхем поточных шифров.

Построениераундовойфункции.

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

Требования к раундовойфункции:

1.Подмешивание раундового ключа

2.Перемешивание.

3.Нелинейная зависимость иначе можно былобырешить систему линейных уравнений и по шифротексту найти открытый текст

Перемешивание действительно важно. Как оно происходит? Вспомним, что в идеальном случае каждый выходной бит должен зависеть откаждого входногос высокойстепенью нелинейности. Тогда, если размер блока равен 64, то нужно реализовать 64 булевы функции, которые зависят от всех 64 переменных с высокой степенью нелинейности. Это крайне сложная задача даже для самого опытного криптографа. Поэтому поступают иначе: блок разбивают на несколько небольшихблоков например, по 4бит , реализуют4 б.ф., свысокой степенью нелинейности зависящие от всех 4 переменных, иприменяютко всему блоку. Как именно – узнаем чуть позже.

Условия, которым должна удовлетворять раундовая функция.

1. Для любого раундового ключа q подфункция φq раундовой функции φq x,q – биективна дляобратимости шифра . Как правило, используется операция XOR илисложение по модулю с ключом.

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

Замечание.		преобразование s x1, …,x 2n реализуют с помощью
При больших n нелинейную замену
набора нелинейных преобразований.
S x 1 , ..,x 2n	s1 x 1 , …,x u ,…, sd	x 2n u 1 ,x 2n ,n 2n/d

где s1 … sd – s боксы раундовой функции нелинейного преобразования множества V2n/d.

Но ведь еслиодин и тотже наборпоследовательно пропустить через несколько таких блоков, то получим то же самое, какбудто пропустили через 1 блок? Переставили одним образом, затем результатпереставили другим и еще раз переставили – ничем не отличается от того, что сразу бы изменили порядок за1 раз. И результат зависит от входногоблока.

Для решения этой проблемы используетсяперемешивание.

Алгоритм такой: исходная последовательность делится на блоки длинойd и они проходят через s блоки. Затем получаем выходную последовательность и перемешиваем ее. Результатсноваделим на блоки длины d, пропускаем через s блоки. Итак далее. Таким образом, результатs блоков будет зависеть не толькоот 8 входных бит, нои от чего то еще.

Замечание. Число d, используемой внелинейном слое s боксов,выбирается как компромисс между сложностью реализации s блока и криптографическими качествами s боксов.

Замечание об СЛК . Необходимо,чтобы при изменении одного битавходного блока изменилось не менее половины битвыходного блока. Это правило называется СЛК – строгийлавинный критерий.

Другими словами: при изменении 1 бита во входном блоке на выходебудет совершенно другой блок.

Пункт 3 условий для раундовой функции . Перемешивающиеслои раундовой функции должны реализовыватьтакие связи между входными и выходными битами s боксов, чтобы выполнялись условия:

1.Каждый s бокс удовлетворяет СЛК

2.Наследующем раунде совокупностьвходных биткаждого s блокадолжназависеть от выходов несколькихs блоков на предыдущих раундах.

СлабыеитеративныеСБШ.

Опр. Ключ k итеративного r раундового СБШ называется μ слабым, если набор раундовых ключей q1…qr содержит ровно μ различных элементов. Понятно, что 1 μ r μ r означает, что все ключи разные, и о слабости речи не идет .

Слабым ключом называется 1 н слабый ключ все раундовые ключи совпали

Из 16 раундовых ключей оказалось только 5 уникальных? Это 5 слабый ключ.

Теорема.

Пусть k – слабый ключ итеративного r раундового СБШ. Порядок постановкиφq равенd то есть ord φq d , а tay –остаток отделения r на d. Тогда СБШ при ключеk является tay раундовым.

Напомним, что ord φq d на самом деле означает: φq d e

Фактически этатеорема о том, что при указанных условиях СБШ является на самом деле не r раундовой, а всего лишь tay раундовой.

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

Так как k– слабый ключ,то все раундовыеключи совпадают: q1 q2 … qr q обозначили как просто q .

Вспоминаем функцию зашифрования и начинаем над ней извращаться.

Ek x	πq_ r	1	φq	r бq_0 x	dp tay
Вспоминаем из условия: r
Ek x	πq_ r	1	φq	dp tay бq_0	x

Вспоминаем из условия,что ord φq d то есть φq d e

Ek x πq_ r 1 φq dp φq tay бq_0 x

Получили:

Ek x πq_ r 1	φq tay бq_0 x
Теорема доказана.
Следствие.	то есть tay 0 в предыдущей теореме , а подстановки бq_0 и πq_ r 1 –
Если d делитr

взаимно обратные, то подстановка Ek является тождественной.

Теорема.

Пусть k – этослабый ключ итеративного 2r раундового шифраФестеля, входной и выходной ключи совпадают q0 q2r 1 , и πq_0 б 1q0 Tn. ТогдаEk –инволюция, имеющая 2n неподвижных элементов.

Напомним 2 термина. Инволюция: Ek Ek 1. Неподвижный относительно преобразования элемент: Ek x x

Доказательство.			б 1q0 Tn примечателен
Вспоминаем,что шифр Фейстеля при заданном условии πq_0
тем, что зашифрование отличается то расшифрования только использованием
раундовых ключей в обратном порядке:
	Теорема.
	Если длялюбого q из Q’выполненоπq x бq 1 *Tn x ,то шифр Фейстеля обратим
	ирасшифрование отличается отзашифрования лишь использованием раундовых
	ключей в обратном порядке.
Запишем это ввиде формул. А точнее – скопируем:
Ek x πq_ 2r 1 φq_2r … φq_1 бq_0 x ,
Ek 1 y πq0 φq_1 … φq_2r бq_ 2r 1 y			q2r 1. Тогда:
Так как ключ k– слабый,то q1 … q2r. Такжепо условию q0
πq_ 2r	1 πq0
φq_2r … φq_1		φq_1 … φq_r
бq_0	бq_ 2r	1
То есть: Ek		x E 1k x –инволютивность доказали.

Пусть на входе –блок открытого текста a1a2 , где a1 и a2 – векторадлины n.
Пусть после входного отображения этот блок перешел в блокx1x2,то есть:							a1,a2 , т.е:
бq0	a1,a2	x1,x2 . Тогда если			a1,a2 – неподвижный элемент, то Ek a1,a2
Ek	a1,a2	πq_ 2r 1	φd 2r бq_0 a1,a2			a1,a2
Чуть раньше мы поняли,что πq_ 2r 1						πq0. А из условия: πq_0 б 1q0 Tn. Подставляем:
Ek	a1,a2	б1q0 Tn	φd 2r бq_0 a1,a2			a1,a2 .
Домножим на бq_0:			2r бq_0	a1,a2	бq0	a1,a2
Ek	a1,a2	Tn φd
Вспомним, что бq0			a1,a2	x1,x2 :

Ek a1,a2	Tn φd 2r x1,x2		x1,x2
Домножим на φq r:			φq r x1,x2
Ek a1,a2	Tn φd r x1,x2				Tn φq Tn
Вспомним лемму шифра Фейстеля: φ 1q
Ek a1,a2	Tn φd r x1,x2		Tn	φq r Tn	x1,x2
x1,x2	Tn x1,x2	x1	x2	почему??? .

Теорема доказана.