Быстрый поиск

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

1. у1=Х.

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

Таблица 2:

Д	Б	А	К	Р
X	V	N	R	S

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

Таблица 3:

Б	Д	А	К	Р
X	V	N	R	S

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

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

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

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

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

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

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

1. Y1i=xi Å h1i

11001 01001 10101 10001 11100

00100 00001 01101 01101 00001

11101 01000 11000 11100 11101.

2. У2i=y1i Å h2i

11101 01000 11000 11100 11101

10011 00110 01011 10010 10011

01110 01110 10011 01110 01110.

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

1. У1i =xi Å h2i

11001 01001 10101 10001 11100

10011 00110 01011 10010 10011

01010 01111 11110 00011 01111.

2. У2i'=y1i' Å h1i

01010 01111 11110 00011 01111

00100 00001 01101 01101 00001

01110 01110 10011 01110 01110.

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

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

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

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

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

11001 01001 10101 10001 11100

00100 00001 01101 01101 00001

11001 01001 10101 10001 11100.

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

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

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

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

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

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

Тонкость, состоит в том, что в одном шифре следует периодически перемежать в различных комбинациях перемешивание (с гораздо меньшими таблицами) и рассеивание. Такой шифр называют составным шифром (product cipher). Иногда блочный шифр, который использует последовательные перестановки и подстановки, называют сетью перестановок-подстановок, или 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 Å f(Ri-1, Ki)

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

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

Li-1 Å f(Ri-1, Ki ) Å Li-1 Å 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 - побитовое дополнение Р, a h - побитовое дополнение C. Это - следствие сложения ключа и текста операцией XOR. Для хорошего блочного шифра простых соотношений нет.

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11