Реферат: Композиции шифров

МПС РФ

МосковскийГосударственный Университет

ПутейСообщения (МИИТ)

Кафедра«Электроника и защита информации»

Курсовая работа

по дисциплине: «Криптографические методы

защиты информации»

На тему: «Композиции шифров»

Выполнил: Ефалов П.А.

Студент гр. АКБ-311

ИСУТЭ

Проверил: Титов Е.В.

Москва-2003

<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">

СОДЕРЖАНИЕ:

Введение…………………………………………………..…………………….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.  Алгоритм REDOCIII………………………………………..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.  Схема xDESi………………………………………………...40

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

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

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

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

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

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

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

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

ВВЕДЕНИЕ

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

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

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

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

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

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

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Рассмотрим несколько примеров:

<span Times New Roman",«serif»">        Пример 1. Возьмем в качестве открытоготекста сообщение: «Я пишу курсовую».

<span Times New Roman",«serif»">        Защитимэтот текст методом простой перестановки, используя в качестве ключа слово«зачет» и обозначая пробел буквой «ь». Выписываем буквы открытоготекста под буквами ключа. Затем буквы ключа расставляем в алфавитном порядке.Выписываем буквы по столбцам и получаем шифртекст: ььоиууяусшрюпкв.

<span Times New Roman",«serif»">        Полученноесообщение зашифруем с помощью метода подстановки:

<span Times New Roman",«serif»">Пусть каждому символу русского алфавитасоответствует число от 0 до 32. То есть букве А будет соответствовать 0, буквеБ — 1 и т.д. Возьмем также некое число, например, 2, которое будет ключомшифра. Прибавляя к числу, соответствующему определенному символу 2, мы получимновый символ, например, если А соответствует 0, то  при прибавлении 2 получаем В и так далее. Пользуясьэтим, получаем новый шифртекст: ююркххбхуьтасмд.

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

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">       

<span Times New Roman",«serif»">        Пример 2. В качестве примера такжерассмотрим шифр, предложенный Д. Френдбергом, который комбинируетмногоалфавитную подстановку с генератором псевдослучайных чисел. Особенностьданного алгоритма состоит в том, что при большом объеме шифртекста частотныехарактеристики символов шифртекста близки к равномерному распределению независимоот содержания открытого текста.

<span Times New Roman",«serif»">1. Установление начального состояниягенератора псевдослучайных чисел.

<span Times New Roman",«serif»">2. Установление начального спискаподстановки.

<span Times New Roman",«serif»">3. Все символы открытого текстазашифрованы?

<span Times New Roman",«serif»">4. Если да — конец работы, если нет — продолжить.

<span Times New Roman",«serif»">5. Осуществление замены.

<span Times New Roman",«serif»">6. Генерация случайного числа.

<span Times New Roman",«serif»">7. Перестановка местами знаков в спискезамены.

<span Times New Roman",«serif»">8. Переход на шаг 4.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Пример3.

<span Times New Roman",«serif»">Открытый текст: «АБРАКАДАБРА».

<span Times New Roman",«serif»">Используем одноалфавитную заменусогласно таблице 1.

<span Times New Roman",«serif»">Таблица 1:

<span Times New Roman",«serif»">А

<span Times New Roman",«serif»">Б

<span Times New Roman",«serif»">Д

<span Times New Roman",«serif»">К

<span Times New Roman",«serif»">Р

<span Times New Roman",«serif»">X

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">V

<span Times New Roman",«serif»;mso-ansi-language: EN-US">N

<span Times New Roman",«serif»;mso-ansi-language: EN-US">R

<span Times New Roman",«serif»;mso-ansi-language: EN-US">S

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»">Последовательность чисел, вырабатываемаядатчиком: 31412543125.

<span Times New Roman",«serif»">1. у1=Х.

<span Times New Roman",«serif»">После перестановки символов исходногоалфавита получаем таблицу 2 (h1=3).

<span Times New Roman",«serif»">Таблица 2:

<span Times New Roman",«serif»">Д

<span Times New Roman",«serif»">Б

<span Times New Roman",«serif»">А

<span Times New Roman",«serif»">К

<span Times New Roman",«serif»">Р

<span Times New Roman",«serif»">X

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»;mso-ansi-language:EN-US">V

<span Times New Roman",«serif»;mso-ansi-language:EN-US">N

<span Times New Roman",«serif»;mso-ansi-language:EN-US">R

<span Times New Roman",«serif»;mso-ansi-language:EN-US">S

<span Times New Roman",«serif»"> 

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">2. у2=V. Таблица 2 послеперестановки (h2=1) принимает вид, представленный в таблице 3.

<span Times New Roman",«serif»">Таблица 3:

<span Times New Roman",«serif»; mso-ansi-language:EN-US">Б

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Д

<span Times New Roman",«serif»">А

<span Times New Roman",«serif»">К

<span Times New Roman",«serif»">Р

<span Times New Roman",«serif»">X

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»; mso-ansi-language:EN-US">V

<span Times New Roman",«serif»; mso-ansi-language:EN-US">N

<span Times New Roman",«serif»; mso-ansi-language:EN-US">R

<span Times New Roman",«serif»; mso-ansi-language:EN-US">S

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Осуществляя дальнейшие преобразования всоответствии с алгоритмом Френдберга, получаем шифртекст:«XVSNSXXSSSN».

<span Times New Roman",«serif»">       

<span Times New Roman",«serif»">        Однойиз разновидностей метода гаммирования является наиболее часто применяемый методмногократного наложения гамм. Необходимо отметить, что если уi=Г

<span Times New Roman",«serif»; mso-ansi-language:EN-US">k<span Times New Roman",«serif»">(Г1(x<span Times New Roman",«serif»; mso-ansi-language:EN-US">i<span Times New Roman",«serif»">)), то Г<span Times New Roman",«serif»;mso-ansi-language: EN-US">k<span Times New Roman",«serif»">(Г1(x<span Times New Roman",«serif»; mso-ansi-language:EN-US">i<span Times New Roman",«serif»">))=Г1(Г<span Times New Roman",«serif»; mso-ansi-language:EN-US">k<span Times New Roman",«serif»">(x<span Times New Roman",«serif»;mso-ansi-language: EN-US">i<span Times New Roman",«serif»">)).(1*)

<span Times New Roman",«serif»">Тождество (1*) называют основнымсвойством гаммы.

<span Times New Roman",«serif»">Пример4.

<span Times New Roman",«serif»">Открытый текст: «ШИФРЫ»(25 09 21 17 28");

<span Times New Roman",«serif»">Г1

<span Times New Roman",«serif»;mso-ansi-language: EN-US"> <span Times New Roman",«serif»">=«ГАММА» («04 01 13 13 01»);

<span Times New Roman",«serif»">Г2 = «ТЕКСТ»(«19 06 11 18 19»), согласно таблице 1.

<span Times New Roman",«serif»">Используемая операция: сложение по mod2.

<span Times New Roman",«serif»;mso-ansi-language: EN-US">1. Y1i=xi

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å<span Times New Roman",«serif»; mso-ansi-language:EN-US"> h1i

<span Times New Roman",«serif»;mso-ansi-language: EN-US">11001 01001 10101 10001 11100

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">00100 00001 01101 01101 00001

<span Times New Roman",«serif»;mso-ansi-language: EN-US">=

<span Times New Roman",«serif»;mso-ansi-language: EN-US">11101 01000 11000 11100 11101.

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">2.

<span Times New Roman",«serif»">У<span Times New Roman",«serif»; mso-ansi-language:EN-US">2i=y1i <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å<span Times New Roman",«serif»"> <span Times New Roman",«serif»; mso-ansi-language:EN-US">  h2i

<span Times New Roman",«serif»">11101 01000 11000 11100 11101

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-bidi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">10011 00110 01011 10010 10011

<span Times New Roman",«serif»">=

<span Times New Roman",«serif»">01110 01110 10011 01110 01110.

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»">Проведем операцию шифрования, поменявпорядок применения гамм.

<span Times New Roman",«serif»">1. У1

<span Times New Roman",«serif»;mso-ansi-language: EN-US">i<span Times New Roman",«serif»">=<span Times New Roman",«serif»; mso-ansi-language:EN-US">xi<span Times New Roman",«serif»"> <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">Å<span Times New Roman",«serif»">   <span Times New Roman",«serif»;mso-ansi-language:EN-US">h<span Times New Roman",«serif»">2<span Times New Roman",«serif»; mso-ansi-language:EN-US">i<span Times New Roman",«serif»">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">11001 01001 10101 10001 11100

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">10011 00110 01011 10010 10011

<span Times New Roman",«serif»;mso-ansi-language: EN-US">=

<span Times New Roman",«serif»;mso-ansi-language: EN-US">01010 01111 11110 00011 01111.

<span Times New Roman",«serif»;mso-ansi-language: EN-US">

<span Times New Roman",«serif»;mso-ansi-language: EN-US">2.

<span Times New Roman",«serif»">У<span Times New Roman",«serif»; mso-ansi-language:EN-US">2i'=y1i' <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">Å<span Times New Roman",«serif»"> <span Times New Roman",«serif»; mso-ansi-language:EN-US"> h1i

<span Times New Roman",«serif»">01010 01111 11110 00011 01111

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»">00100 00001 01101 01101 00001

<span Times New Roman",«serif»">=

<span Times New Roman",«serif»">01110 01110 10011 01110 01110.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Таким образом, y2i=y2i',что является подтверждением основного свойства гаммы.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">        Присоставлении комбинированных шифров необходимо проявлять осторожность, так какнеправильный выбор составлявших шифров может привести к исходному открытомутексту. Простейшим примером служит наложение одной гаммы дважды.

<span Times New Roman",«serif»">Пример5.

<span Times New Roman",«serif»">Открытый текст: «ШИФРЫ»(«25 09 21 17 28»);

<span Times New Roman",«serif»">Г1= Г2= «ГАММА» («04 01 13 13 01»), согласнотаблице 1.

<span Times New Roman",«serif»">Используемая операция: сложение по mod2:

<span Times New Roman",«serif»">11001 01001 10101 10001 11100

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»">00100 00001 01101 01101 00001

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

<span Times New Roman",«serif»; mso-ansi-language:EN-US">

<span Times New Roman",«serif»"> 00100 00001 01101 01101 00001

<span Times New Roman",«serif»">=

<span Times New Roman",«serif»">11001 01001 10101 10001 11100.

<span Times New Roman",«serif»">Таким образом, результат шифрованияпредставляет собой открытый текст.

<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">

<span Times New Roman",«serif»">2. Теория проектирования блочных шифров

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

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

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

        Дляобеспечения надежности достаточно только перемешивания. Алгоритм, состоящий изединственной, зависимой от ключа таблицы подстановок 64 бит открытого текста в64 бит шифртекста был бы достаточно надежным. Недостаток в том, что дляхранения такой таблицы потребовалось бы слишком много памяти: 1020байт. Смысл создания блочного шифра и состоит в создании чего-то подобноготакой таблице, но предъявляющего к памяти более умеренные требования.

        Тонкость,состоит в том, что в одном шифре следует периодически перемежать в различныхкомбинациях перемешивание (с гораздо меньшими таблицами) и рассеивание. Такойшифр называют составным шифром (productcipher). Иногда блочный шифр, который использует последовательныеперестановки и подстановки, называют сетью перестановок-подстановок, или SP-сетью.

        Рассмотримфункцию fалгоритма DES. Перестановка срасширением и Р-блок реализуют рассеивание, а S-блоки — перемешивание. Перестановка с расширением и Р-блоклинейны, S-блоки — нелинейны. Каждая операциясама по себе очень проста, но вместе они работают превосходно.

        Кроме того, напримере DESможно продемонстрировать еще несколькопринципов проектирования блочных шифров. Первый принцип реализует идею итеративногоблочного шифра. При этом предполагается, что простая функция раундапоследовательно используется несколько раз. Двухраундовый алгоритм DESслишком ненадежен, чтобы все биты результата зависели отвсех битов ключа и всех битов исходных данных. Для этого необходимо 5 раундов.Весьма надежен 16-раундовый алгоритм DES, а 32-раундовыйDESеще более стоек.

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

        Большинствоблочных алгоритмов относятся к так называемым сетям Файстеля. Идея этих сетейдатируется началом семидесятых годов. Возьмем блок длиной п и разделимего на две половины длиной n/2: Lи R. Разумеется, число п должнобыть четным. Можно определить итеративный блочный шифр, в котором результат j-го раунда определяетсярезультатом предыдущего раунда:

        Li = Ri-1

        Ri = Li-1 <span Times New Roman";mso-hansi-font-family:«Times New Roman»; color:black;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">Å

  f(Ri-1, Ki)

Ki — подключ j-го раунда, а f — произвольная функция раунда.

        Применениеэтой концепции можно встретить в алгоритмах DES, Lucifer, FEAL, Khufu, Khafre, LOKI, ГОСТ, CAST, Blowfishи других. Этимгарантируется обратимость функции. Так как для объединения левой половины срезультатом функции раунда используется операция XOR, всегда истинно следующее выражение:

        Li-1 <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;color:black;mso-ansi-language:EN-US; mso-char-type:symbol;mso-symbol-font-family:Symbol">Å

  f(Ri-1, Ki ) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;color:black;mso-char-type:symbol; mso-symbol-font-family:Symbol">Å  Li-1 <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;color:black;mso-ansi-language:EN-US; mso-char-type:symbol;mso-symbol-font-family:Symbol">Å  f(Ri-1, Ki) = Li-1    

Шифр, использующий такую конструкцию, гарантированнообратим, если можно восстановить исходные данные fна каждом раунде. Сама функция fне важна, она не обязательно обратима.Мы можем спроектировать сколь угодно сложную функцию f,  но нам непонадобится реализовывать два разных алгоритма — один для зашифрования, адругой для расшифрования. Об этом автоматически позаботится структура сетиФайстеля.

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

        Алгоритм DESхарактеризуется следующим свойством: если ЕК(Р) = С, то ЕK' (Р') = С', где Р', С' и K' — побитовые дополнения Р, С иK. Это свойствовдвое уменьшает сложность лобового вскрытия. Свойства комплементарности в 256раз упрощают лобовое вскрытие алгоритма LOKI.

Простое соотношение можно определить так:

        Если ЕK(Р)= С, то Ef(K)(g(P,K)) = h(C,K)

где f,gи h — простые функции. Под «простыми функциями» подразумеваютфункции, вычисление которых несложно, намного проще итерации блочного шифра. Валгоритме DESфункция f  представляет собой побитовое дополнение K, g — побитовое дополнение Р, ah — побитовоедополнение C. Это — следствие сложения ключа и текста операцией XOR.Для хорошего блочного шифра простых соотношений нет.

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

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

        Важен, однако,вопрос не о том, действительно ли алгоритм — группа, а о том, насколько онблизок к таковому. Если не хватает только одного элемента, алгоритм не образуетгруппу, но двойное шифрование было бы, с точки зрения статистики, просто потерейвремени. Работа над DESпоказала, что этот алгоритмвесьма далек от группы. Существует также ряд интересных вопросов о полугруппе,получаемой при шифровании DES. Содержит лиона тождество, то есть, не образует ли она группу? Иными словами, не генерируетли, в конце концов, некоторая комбинация операций зашифрования (не расшифрования)тождественную функцию? Если так, какова длина самой короткой из такихкомбинаций?

        Цельисследования состоит в оценке пространства ключей для теоретического лобовоговскрытия, а результат представляет собой наибольшую нижнюю границу энтропиипространства ключей.

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

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

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

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

        Исследованиядифференциального и линейного криптоанализа значительно прояснили теориюпроектирования надежных блочных шифров. Авторы алгоритма IDEAввели понятие дифференциалов, обобщение основной идеихарактеристик. Они утверждали, что можно создавать блочные шифры, устойчивые катакам такого типа. В результате подобного проектирования появился алгоритм IDEA. Позднее это понятие было формализовано в работах КайсаНиберг (KaisaNyberg) и Ларе Кнудсен, которые описали метод создания блочныхшифров, доказуемо устойчивых к дифференциальному криптоанализу. Эта теория быларасширена на дифференциалы высших порядков и частные дифференциалы. Какпредставляется, дифференциалы высших порядков применимы только к шифрам с малымчислом раундов, но частные дифференциалы прекрасно объединяются с дифференциалами.

        Линейныйкриптоанализ появился сравнительно недавно, и продолжает совершенствоваться.Были определены понятия ранжирования ключей и многократных аппроксимаций.Кем-то была предпринята попытка объединения в одной атаке дифференциального илинейного методов криптоанализа. Пока неясно, какая методика проектированиясможет противостоять подобным атакам.

        Кнудсендобился известного успеха, рассматривая некоторые необходимые (но, возможно,недостаточные) критерии того, что он назвал практически стойкими сетямиФайстеля — шифров, устойчивых как к дифференциальному, так и к линейному криптоанализу.Ниберг ввел для линейного криптоанализа аналог понятия дифференциалов в дифференциальномкриптоанализе.

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

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

        Мощьбольшинства сетей Файстеля, а особенно их устойчивость к дифференциальному илинейному криптоанализу, напрямую связана с их S-блоками. Поэтому вопрос о том, что же образует хороший S-блок, стал объектом многочисленных исследований.

        S-блок — это просто подстановка: отображение m-битовых входовна n-битовые выходы. Применяется большая таблица подстановок64-битовых входов на 64-битовые выходы. Такая таблица представляет собой S-блок размером 64*64 бит. S-блок с m-битовым входом и n-битовым выходом называется m*n-битовым S-блоком. Какправило, обработка в S-блоках — единственная нелинейная операция в алгоритме. Именно S-блоки обеспечивают стойкость блочного шифра. В общем случае, чембольше S-блоки, тем лучше.

        В алгоритме DESиспользуются восемь различных6*4-битовых S-блоков. В алгоритмах Khufuи Khafreпредусмотренединственный 8*32-битовый S-блок, в LOKI– 12*8-битовый S-блок, а в Blowfishи CAST– 8*32-битовые S-блоки. В IDEAS-блоком, по сути, служит умножение по модулю, это 16+16-битовый S-блок. Чем больше S-блок, тем труднееобнаружить статистические данные, нужные для вскрытия методами дифференциальногоили линейного криптоанализа. Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости кдифференциальному и линейному криптоанализу, стойкие S-блоки легче найти среди S-блоков большегоразмера. Большинство случайных S-блоков нелинейны,невырождены и характеризуются высокой устойчивостью к линейному криптоанализу,причем с уменьшением числа входных битов устойчивость снижается достаточно медленно.

        Размер т важнееразмера п. Увеличение размера п снижает эффективность дифференциальногокриптоанализа, но значительно повышает эффективность линейного криптоанализа.Действительно, если п ≥ 2m — т, наверняка существуетлинейная зависимость между входными и выходными битами S-блока. А если п ≥ 2m, линейная зависимость существуетдаже только между выходными битами.Заметная доля  работпо проектированию  S-блоков  состоитв  изучении булевыхфункций. Для  обеспечения безопасности,  булевы функцииS-блоков должны отвечать определенным требованиям. Они не должныбыть ни линейными, ни аффинными, ни даже близкими к линейным или аффиннымфункциям. Число нулей и единиц должно быть сбалансированным, и между различнымикомбинациями битов не должно быть никаких корреляций. При изменении значениялюбого входного бита на противоположное выходные биты должны вести себя независимо.Эти критерии проектирования так же связаны с изучением бент-функций (bentfunctions): функций, которые, как можно показать, оптимально нелинейны.Хотя они определены просто и естественно, их изучение очень трудно.

        По-видимому,очень важное свойство S-блоков — лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества входныхбитов. Нетрудно задать для булевых функций условия, выполнение которыхобеспечивает определенный лавинный эффект, но проектирование таких функцийзадача сложная. Строгий лавинный критерий (StrictAvalancheCriteria — SAC) гарантирует изменение ровно половины выходных битов приизменении единственного входного бита. В одной из работ эти критерии рассматриваютсяс точки зрения утечки информации.

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

еще рефераты
Еще работы по компьютерам. программированию