Razbor_kriptov_-_chast_2

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

Замечание: лучше всего, когда функция φ – инволютивна φγt φγt 1 , так как φγt обеспечивает зашифрование, а φγt 1 – расшифрование.

Расширенная схема СПШ.

1.Есть внутреннее состояние

2.В каждом такте оно изменяется под воздействием функции переходов

3.В каждом такте от него берется функция выходов, которая дает бит гаммы

Фильтр – генератор* * для самых умных** ** не пытайтесь понять .

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

Давайте теперь подумаем, какую функцию можно выбрать в качестве шифрующей. Вот можно ли взять дизънкцию: V ?

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

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

Тогда давайте узнаем требования к функции шифрования Итак, она должна быть:

1.Биективной по xt

2.Существенно зависеть от γt

3.Желательно быть инволютивной отметили ранее .

Всем этим требваниям идеально удовлетворяет функция XOR. Именноона чаще всего и используется в качестве шифрующей. Нарисуем же теперь полную сему, где XOR займет свое законное место:

Обратите внимание: генераторы гаммы должны работать синхронно! То есть наодин

итот же символ как шифротекста, так и открытого, должен быть сгенерирован один

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

Замечание. Ограничимся рассмотрением подстановочныхпоточных шифров, для которых алфавиты Х и У открытых текстов и шифротекстов равномощны. Замечание. Однозначность расшифрования обеспечивается тогда и толькотогда, когда fш биективна по х. Это мы уже чуть выше разобрали.

СПШ по способу подмешивания ключа	Генераторы типа счетчик
Генераторы с внутренней обратной
связью.
Замечание: в качестве ключа может	Замечание: в генераторах типа счетчик (как
быть использовано начальное
заполнение генератораю	следует из названия) в качестве функции
	переходов используется (как правило)
	увеличение значения внутреннего состояния
	на 1
	Все, что здесь делает функция переходов –
	обеспечивает каждый раз новое внутреннее
	состояние. Никакого секрета она не несет.

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

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

СвойстваСПШ.

Свойство 1. Возможность рассинхронизации. Причины возникновения:

1.Потеря бита шифротекста при передаче

2.Зацикливание генератора пропуск бита гаммы

Способы восстановления синхронизма:

1.Повторное шифрование с реинициализацией ключа

2.Разбиение открытого текста на блоки, начало и окончание которыхснабжается маркерами последовательностями специального вида .

То есть ошибки будут только до маркера. После него – снова синхронизируется.

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

Свойство 2 положительное .

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

Свойство 3 положительное .

Защита от несанционированных вставок и удалений отрезков шифротекста.

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

Свойство 4 отрицательное Отсутствие защиты от подмены отрезка шифротекста на отрезок той жедлины.

Свойство 5 отрицательное Уязвимость к атаке вставкой. Шаг 1.

Задан открытый текст: x1 x2 x3 x4 Задана гамма: γ1, γ2, γ3,γ4

И шифротекст: y1 y2 y3 y4

На 1 шаге шифротекст перехватывает злоумышленник

Шаг 2.

Злоумышленник заставляет отправителя на той же гамме зашифровать сообщение x1 α x2 x3, отличающееся от предыдущего вставкой одного бита α, известного злоумышленнику.

В таком случае имеем: Открытый текст: x1 α x2 x3

Гамма: γ1, γ2, γ3, γ4

И шифротекст: y1’ y2’y3’y4’

Как вы уже догадались, y1 и y1’ будут совпадать: да вообщевсе у без штриха и с ним будут совпадать, за исключениемодного бита, куда был вставлен α. В нашем случае

окажется y2		y2’. То есть:
y1	x1 XOR γ1	y1’	α XOR y2’
y2	x2 XOR γ2	y2’

И снова злоумышленник перехватывает шифротекст.

Шаг 3.

Злоумышленнику известны α и y2’. По этим данным он восстанавливает γ2:

γ2 y2’XOR α

Теперь злоумышленнику известно γ2 и y2 из первого перехваченного шифротекста . Восстанавливаем х2:

x2 γ2 XOR y2

Известны x2 и y3’ – восстанавливаем γ3:

γ3 x2 XOR y3’

Известны γ3 и y3 – восстанавливаем x3: x3 γ3 XOR y3

И так далее.

Вывод: нельзя использовать одинаковую гамму для шифрования разных сообщений.

Замечание: злоумышленник может и не знать положение вставленного бита α, а определить его, сравнив 2 перехваченных шифротекста они будут будут отличаться только этим битом .

Самосинхронизирующиесяпоточныешифры. Сходство СПШ и ССПШ:

1.Наличие управляющего и шифрующего блоков

2.Уравнения расшифрования и зашифрования одинаковы.

Различия: внутреннее состояниеССПШ – n предшествующихбит шифротекста.

Общая схема ССПШ.

Свойства ССПШ.

Свойство 1 положительное

Самосинхронизация за n тактов в случае отсутствия потерь битов шифротекста . Это настолько важное свойство, что самое время рассмотреть пример. Представьте, что на каком то шаге вместо «0» во внутреннее состояние попала единица:

Тогда этот бит шифротекста будет расшифрован неверно. И следующий тоже:

Таким образом, за n тактов произошла самосинхронизация.

Свойство 2 отрицательное .

При искажении символа шифротекста до n последовательных бит расшифруются неверно.

Другими словами: вместо «0» пришел «1». Он попадет во внутреннее состояние и n штук расшифруются неверно. Чуть выше мы это увидели.

Свойство 3. Уязвимость к атаке повторной передачи.

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

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

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

Способы защиты:

1.Использование меток времени

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

Подумаем теперь над тем, какое начальное состояние у ССПШ? Можно сделать по хитрому. Пусть первые n символов открытого теста будут любыми. Вообще любыми, даже разными у отправителя и получателя надо же генератор чем то заполнить . А после них уже будет идти передаваемый текст. Тогда через n тактов они синхронизируются, и расшифровка всего текста произойдет корректно. То есть не нужно согласовывать начальноесостояние: оно может быть любым длины n .

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

Шифрыгаммирования.

Опр. Шифр гаммирования – подстановочный поточный шифр, в котором совпадают алфавиты открытого текста и шифротекста: Х У, и двумерное табличное заданиешифра образует латинский квадрат то есть fш xt, γt биективнаи пох, и поγ .

Давайте разбираться, что такое латинский квадрат.

Латинский квадрат – это матрица размера |X| x |X|, где каждая строка и каждый столбецесть перестановка элементов множества Х.

Пусть для примера Х Г У				Z5 – все по модулю 5.
Тогда латинский квадрат:
	xt \ γt		0		1			2		3		4
	0
	1				fш xt,γt
	2					–бит
	3				шифротекста
	4

Обратите внимание на слово «перестановка» в определении латинского квадрата. Это означает, что ни в строках, ни в столбиках значения не повторяются. Как в судоку.

Например, вот тут четверка повторяется – это уже не латинский квадрат

	xt \ γt		0	1		2	3	4
	0		0	4		2	1	4
	Это и означает,		что fш xt, γt	биективна и по х, и		по γ.

Почему? Смотрите пример: вот такая, как на картинке, ситуация,знаем мы γt иуt 4. Чему равен соответствующий бит xt? Нельзя определить: может быть как 3, так и 4. Отсюда биективность.

Опр. Если множество Ф φγ, γ принадлежит Г алфавитугаммы шифрующих подстановок шифра гаммирования образует группу, то шифр гаммирования называется групповым.

Опр. Шифр модульного гаммирования – это шифр, в котором алфавиты: Х У Г Zm и fш

определен следующим образом: fш γ,х	±х ± γ)mod(m)

Замечание. Шифр модельного гаммирования инволютивен, если fш имеет вид:

fш γ,х

±х - γ)mod(m)

Пример: y= γ-x => x= γ-y

Критерии оценки криптографических свойств поточных шифров.

Развеем миф, откуда берется гамма. Она берется из ключа. Есть ключ – он небольшой, удобный и легко запоминающийся (хотя не факт). К нему применяется криптографическая функция, и выдает гамму – большую последовательность с хорошими криптографическими свойствами.

Хорошо, если она будет псевдослучайной. В идеальном случае она окажется РРСП. {γt} – псевдослучайная

{γt} – в идеальном случае является РРСП

Чем больше здесь случайности, тем лучше. В идеальном случае, в зависимости от бита гаммы, вероятности указанного на рисунке будут равными:

Замечание. Наилучшая имитация идеального шифра получается тогда, когда последовательность шифрующих отображений {φγt} имитирует последовательность независимых случайных отображений X -> Y.

Поэтому необходимое условие криптографической стойкости СПШ – при случайном равновероятном выборе ключа управляющая гамма {γt} имитирует РРСП на алфавите Г.

Другими словами: чем ближе гамма к РРСП, тем непредсказуемое последовательность шифрующих отображений {φγt} и тем лучше будет шифр.

Замечание. В таких условиях шифротекст будет также имитировать РРСП (на алфавите У).

Пояснение: по свойству РРСП: РРСП плюс не РРСП дает РРСП (проверить!)

Следующая тема – предпоследняя. Если верить расположению звезд, то осталось всего 3 лекции (включая эту). Давайте начнем.

Блочные шифры. Итеративные блочные шифры.

Введение.

Введем новое обозначение – шифр ЕСВ. На понятном языке он называется шифром простой замены. Он шифрует блоки независимо друг от друга. А если подробнее – разбивает исходный текст на блоки, которые шифруются/расшифровываются независимо друг от друга. В виде упрощенной картинке это выглядит так:

Теперь можно начинать.

Пусть Х У V2n напомним, V2n – это множество двоичных 2n мерных векторов, то есть входной и выходной блоки имеют размерность 2n .

Тогда уравнение шифрования блочного шифра в режиме ЕСВ простой замены при ключе k из множества ключей К имеет вид: yt Ek xt , где t 1,2…, Ек – подстановка биекция на множестве V2n при любом k.

Таким образом, блочный шифр в режиме ЕСВ реализует простую замену алфавитаV2n, где

|Vn| 22n откуда??? .

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

ПринципыпостроенияподстановкиEk итеративногоСБШ симметричногоблочногошифра .

Говорят, что те, кому попадается этот билет, часто отправляются на пересдачу уже на первом вопросе. Нет, это не вопрос о физическом смысле 17 й производной. Он звучит так: «расшифруйте все 4 слова из названия темы».

1.Шифр – некоторое обратимое биективное преобразование множества открытых текстов. Биективность нужна длявозможности однозначной расшифровки зашифрованного текста.

2.Блочный – исходный тест разбивается на блоки и эти блоки шифруются. При этом равным входным блокам соответствуют одинаковые выходные.

3.Симметричный – шифрование и расшифрование происходят на одинаковых или очень близких ключах. «Очень близкий ключ» это ключ, который элементарно получается из исходного. Например, берутся биты исходного ключа в обратном порядке.

4.Итеративный – процесс зашифрования – это не одна сложная функция, а последовательность применения несколькихпростых функций.

Пусть φ x,q , б x,q , π x,q – биективные по переменной х отображения, которые принимают на вход блок длины 2n и выдают на выходеблок той жедлины. Если подробнее, то:

V2n x Q V2n

Где x V2n, q Q q Q’ чуть ниже поймете, откуда . При этом q– элемент множества производных ключей, генерируемых из основного ключа k.

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

Для реализации подстановки Ek используются производные ключи: q0 иqr 1 Q’

q1,…,qr Q

где qi θi k , при этом i 0..r 1

// Поясним: qi θi	k	означает, что qi получен из ключа путем применения к немуфункции θi.
При этом θ0, …, θr	1	– семейство функций, отображающих ключевое множество К во

множество Q’QrQ’ при генерации производных ключей из основного ключаК.