Метод дифференциального криптоанализа

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СВЯЗИ,

ИНФОРМАТИЗАЦИИ И ТЕЛЕКОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

 

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ 

ИНФОРМАЦИОННЫХ  ТЕХНОЛОГИЙ

 

 

кафедра С и СПД            

 

 

САМОСТОЯТЕЛЬНАЯ РАБОТА

 

НА ТЕМУ:

 

“МЕТОД ДИФФЕРЕНЦИАЛЬНОГО  КРИПТОАНАЛИЗА”

 

 

 

 

 

Проверил: Джураев Р.Х.

 

Выполнил: Дуганов А.К.

 

Группа – 420 - 09

 

 

 

 

 

 

 

 

ТАШКЕНТ – 2013

 

СОДЕРЖАНИЕ:

 

Введение…………………………………………………..…………………….4

 

1.  Комбинированные  методы шифрования

Комбинирование простых  способов шифрования..………………………5

 

2.  Теория проектирования  блочных шифров…...……………………………8

2.1.  Сети Файстеля………………………………………………………..8

2.2.  Простые соотношения……………………………………………….9

2.3.  Групповая структура………………………………………………...9

2.4.  Слабые ключи………………………………………………………10

2.5.  Устойчивость алгоритма  к дифференциальному и

линейному криптоанализу…………………………………………10

2.6.  Проектирование S-блоков…………………………………………11

2.7.  Проектирование  блочного шифра………………………………...13

 

3.  Блочные шифры……………………………………………………………14

3.1.  Алгоритм Lucifer……………………………………………………14

3.2.  Алгоритм Madryga………………………………………………….15

3.2.1.  Описание алгоритма  Madryga………………………………16

3.2.1.  Криптоанализ  алгоритма Madryga………………………….17

3.3.  Алгоритм REDOC…………………………………………………..18

3.3.1.  Алгоритм REDOC III………………………………………..18

3.4.  Алгоритм LOKI……………………………………………………..19

3.4.1.  Алгоритм LOKI91…………………………………………...19

3.4.2.  Описание алгоритма  LOKI91……………………………… 21

3.4.3.  Криптоанализ  алгоритма LOKI91………………………….21

3.5.  Алгоритм Knufu и Knafre…………………………………………..22

3.5.1.  Алгоритм Knufu…………………………………………..…23

3.5.2.  Алгоритм Knafre………………………………………….....23

3.6.  Алгоритм ММВ…………………………………………………….24

3.6.1.  Стойкость алгоритма  ММВ………………………………...25

3.7.  Алгоритм Blowfish…………………………………………………26

3.7.1.  Описание алгоритма  Blowfish……………………………...26

3.7.2.  Стойкость алгоритма  Blowfish……………………………..29

3.8.  Алгоритм RC5………………………………………………………29

 

4. Объединение блочных  шифров…………………………………………....32

4.1.  Двойное шифрование………………………………………………32

4.2.  Тройное шифрование……………………………………………....33

4.2.1.  Тройное шифрование  с двумя ключами…………………..33

4.2.2.  Тройное шифрование  с тремя ключами…………………...35

4.2.3.  Тройное шифрование  с минимальным ключом…………..35

4.2.4.  Режимы тройного  шифрования……………………………35

4.2.5.  Варианты тройного  шифрования………………………….37

4.3.  Удвоение длины  блока…………………………………………… 38

4.4.  Другие схемы  многократного шифрования……………………...39

4.4.1.  Двойной режим  OFB/счетчика…………………………….39

4.4.2.  Режим ECB+OFB…………………………………………...39

4.4.3.  Схема xDESⁱ………………………………………………...40

4.4.4.  Пятикратное шифрование………………………………….41

4.5.  Уменьшение длины  ключа в CDMF……………………………...42

4.6.  Отбеливание………………………………………………………..42

4.7.  Каскадное применение  блочных алгоритмов……………………43

4.8.  Объединение нескольких  блочных алгоритмов…………………44

 

Заключение…...……………………………………………………………….45

Список литературы…………...………………………………………………46

 

 

ВВЕДЕНИЕ

Шифрсистемы классифицируются по различным признакам: по видам  защищаемой информации (текст, речь, видеоинформация), по криптографической стойкости, по принципам обеспечения защиты информации (симметричные, ассиметричные, гибридные), по конструктивным принципам (блочные и поточные) и др. При построении отображений шифра используются с математической точки зрения два вида отображений: перестановки элементов открытого текста и замены элементов открытого текста на элементы некоторого множества. В связи с этим множество шифров делится на 3 вида: шифры перестановки, шифры замены и композиционные шифры, использующие сочетание перестановок и замен. Рассмотрим последний класс шифров, то есть шифры композиции.

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

Примерно до конца 19 века все используемые шифры практически  представляли собой различные комбинации шифров замены и перестановки, причем часто весьма изощренных. Например, использовались шифры с несколькими таблицами простой замены, выбор которых осуществлялся в зависимости от шифрования предыдущего знака, в шифрах замены перестановки строились с использованием специальных правил и т.д. Особенно надежными шифрами отличался российский «Черный кабинет» - организация занимавшаяся разработкой собственных шифров и дешифрованием шифров зарубежных. При отсутствии современных методов, а главное вычислительной техники, данные шифры могли считаться вполне надежными. Некоторые из них просуществовали вплоть до второй мировой войны, например, широко известный шифр «Два квадрата» применялся немцами вплоть до 1945 года (метод дешифрования данного шифра был разработан советскими криптографами и активно использовался во время войны).

 

1. Комбинированные методы шифрования

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

 

Рассмотрим  несколько примеров:

Пример 1. Возьмем в качестве открытого текста сообщение: «Я пишу курсовую».

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

Полученное сообщение  зашифруем с помощью метода подстановки:

Пусть каждому символу  русского алфавита соответствует число от 0 до 32. То есть букве А будет соответствовать 0, букве Б - 1 и т.д. Возьмем также некое число, например, 2, которое будет ключом шифра. Прибавляя к числу, соответствующему определенному символу 2, мы получим новый символ, например, если А соответствует 0, то  при прибавлении 2 получаем В и так далее. Пользуясь этим, получаем новый шифртекст: ююркххбхуьтасмд.

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

 

Пример 2. В качестве примера также рассмотрим шифр, предложенный Д. Френдбергом, который комбинирует многоалфавитную подстановку с генератором псевдослучайных чисел. Особенность данного алгоритма состоит в том, что при большом объеме шифртекста частотные характеристики символов шифртекста близки к равномерному распределению независимо от содержания открытого текста.

1. Установление  начального состояния генератора  псевдослучайных чисел.

2. Установление  начального списка подстановки.

3. Все символы  открытого текста зашифрованы? 

4. Если да - конец  работы, если нет - продолжить.

5. Осуществление  замены.

6. Генерация  случайного числа. 

7. Перестановка  местами знаков в списке замены.

8. Переход на  шаг 4.

 

Пример 3. Открытый текст: "АБРАКАДАБРА".

Используем  одноалфавитную замену согласно таблице 1.

Таблица 1:

А	Б	Д	К	Р
X	V	N	R	S

 

 

 

Последовательность  чисел, вырабатываемая датчиком: 31412543125.

1. у₁=Х.

После перестановки символов исходного алфавита получаем таблицу 2 (h₁=3).

Таблица 2:

Д	Б	А	К	Р
X	V	N	R	S

 

 

 

2. у₂=V. Таблица 2 после перестановки (h₂=1) принимает вид, представленный в таблице 3.

Таблица 3:

Б	Д	А	К	Р
X	V	N	R	S

 

 

 

Осуществляя дальнейшие преобразования в соответствии с  алгоритмом Френдберга, получаем шифртекст: "XVSNSXXSSSN".

 

Одной из разновидностей метода гаммирования является наиболее часто  применяемый метод многократного  наложения гамм. Необходимо отметить, что если у_i=Г_k(Г₁(x_i)), то Г_k(Г₁(x_i))=Г₁(Г_k(x_i)). (1*)

Тождество (1*) называют основным свойством гаммы.

Пример 4. Открытый текст: "ШИФРЫ"(25 09 21 17 28");

Г₁ = "ГАММА" ("04 01 13 13 01");

Г₂ = "ТЕКСТ" ("19 06 11 18 19"), согласно таблице 1.

Используемая  операция: сложение по mod 2.

1. Y1_i=x_i Å h1_i

11001 01001 10101 10001 11100

Å

00100 00001 01101 01101 00001

=

11101 01000 11000 11100 11101.

 

2. У2_i=y1_i Å   h2_i

11101 01000 11000 11100 11101

Å

10011 00110 01011 10010 10011

=

01110 01110 10011 01110 01110.

 

Проведем операцию шифрования, поменяв порядок применения гамм.

1. У1_i =x_i Å   h2_i

11001 01001 10101 10001 11100

Å

10011 00110 01011 10010 10011

=

01010 01111 11110 00011 01111.

 

2. У2_i'=y1_i' Å h1_i

01010 01111 11110 00011 01111

Å

00100 00001 01101 01101 00001

=

01110 01110 10011 01110 01110.

 

Таким образом, y2_i=y2_i', что является подтверждением основного свойства гаммы.

 

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

Пример 5. Открытый текст: "ШИФРЫ"("25 09 21 17 28");

Г₁ = Г₂= "ГАММА" ("04 01 13 13 01"), согласно таблице 1.

Используемая  операция: сложение по mod 2:

11001 01001 10101 10001 11100

Å

00100 00001 01101 01101 00001

Å

00100 00001 01101 01101 00001

=

11001 01001 10101 10001 11100.

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

 

2. Теория  проектирования блочных шифров

К. Шеннон выдвинул понятия  рассеивания и перемешивания. Спустя пятьдесят лет после формулирования этих принципов, они остаются краеугольным камнем проектирования хороших блочных шифров.