компшифры. Композиционные шифры

Название	Композиционные шифры
Дата	01.03.2022
Размер	80.45 Kb.
Формат файла
Имя файла	компшифры.docx
Тип	Документы #378935

Композиционные шифры
Принятый в США стандарт шифрования DES был основан на алгоритме Lucifer, разработанном в начале 1970-х гг. и его история являются достаточно интересными и заслуживают отдельного рассмотрения.

Lucifer часто называют «первым алгоритмом шифрования для гражданских применений» [338, 395]. На самом деле Lucifer представляет собой не один алгоритм, а целое семейство связанных между собой (разработанных в рамках одноименной исследовательской программы по компьютерной криптографии фирмы IBM [28]), но созданных в разное время, алгоритмов блочного симметричного шифрования данных.

По словам Брюса Шнайера [28], «существует, по меньшей мере, два различных алгоритма с таким именем, что … привело к заметной путанице». А посвященная алгоритму Lucifer статья в интернет-энциклопедии «Wikipedia» [395] упоминает о четырех вариантах этого алгоритма.

Исходный вариант алгоритма Lucifer был разработан коллективом специалистов из компании IBM под руководством Хорста Фейстеля (Horst Feistel). Этот вариант алгоритма был запатентован компанией IBM в 1971 г. (патент выдан в 1974 г.), его подробное описание можно найти в патенте США №3798359 [144].

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

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

1. Обеспечение обратной связи. Выполняется логическая операция «исключающее или» (XOR) между каждым битом обрабатываемого блока и предыдущим значением того же бита в случае, если аналогичный бит ключа раунда имеет единичное значение; в противном случае операция не выполняется. Предыдущие значения каждого обрабатываемого бита сохраняются в регистре блока обратной связи. В первом раунде алгоритма блок обратной связи операцию XOR не выполняет, а только запоминает биты обрабатываемого блока для следующего раунда.

Обобщенная схема варианта

2.     Перемешивающее преобразование. Выполняется нелинейное преобразование данных, полученных в результате предыдущей операции, путем табличной замены, зависящей от значения конкретного бита ключа раунда. Причем такая зависимость является достаточно простой: если значение управляющего бита равно 1, выполняется табличная замена S₀, в противном случае используется таблица Si.

Каждый нибл данных заменяется независимо от других данных; таким образом, таблицы заменяют 4-битное входное значение также на 4-битное выходное.

Стоит сказать, что в патенте [144] не приведены конкретные значения таблиц замен; в качестве примера приведена следующая таблица:

2,5,4,0,7,6,10,1,9,14,3,12,8,15,13,11.

Это означает, что входное значение 0 заменяется значением 2, значение 1 заменяется на 5 и т. д. до значения 15, которое заменяется на 11.

3.     Рассеивающее преобразование, состоящее в простом перенаправлении входных битов таким образом, что значения всех входных битов меняются местами по определенному закону. Как и значения таблиц замен, сам закон, по которому выполняется рассеивание данных, не описан в патенте [144].

Эта операция выполняется абсолютно независимо от значения ключа шифрования.

4.     Наложение ключа. Выполняется путем побитового применения операции XOR к результату предыдущей операции и соответствующим битам ключа раунда.

Как видно из приведенного описания, в каждом раунде шифрования требуется 108 битов ключевой информации:

?        48 битов для блока обратной связи;

?         12 битов для блока перемешивания;

?        48 битов для блока наложения ключа.

Для получения 16 108-битных раундовых ключей из исходного 48-битного

ключа шифрования выполняется процедура расширения ключа (рис. 3.116):

1.    48-битный ключ загружается в 8-битные регистры KRI…KR6.

2.    Из этих регистров «набирается» необходимое количество битов ключевой информации с помощью расширяющей перестановки КЕР. Операция КЕР не выполняет каких-либо вычислений, получение 108 битов ключевой информации из 48 происходит путем неоднократного использования определенных битов ключевых регистров Л7?1…Л7?6. Ключевая перестановка КЕР не описана подробно в спецификации алгоритма.

3.    Для получения ключевой информации для следующего раунда выполняется побитовый циклический сдвиг на 1 бит содержимого каждого из ключевых регистров KRI…KR6. Затем снова производится перестановка КЕР. Этот шаг повторяется в цикле необходимое число раз до завершения работы алгоритма.

Процедура расширения ключа в варианте № 1

Стоит сказать о том, что данный алгоритм строго нацелен на аппаратное шифрование— в патенте [144] приведено несколько подробных схем, описывающих возможные аппаратные реализации алгоритма. Программному же шифрованию, практически, не уделено внимание в данном патенте.

Очевиден и тот факт, что в описании алгоритма [144] существует множество «белых пятен». Например, не приведены таблицы замен, нет подробного описания используемого линейного преобразования, отсутствует описание перестановки КЕР и т. д. Фактически патент устанавливает некий шаблон для разработки на его основе конкретных алгоритмов шифрования с «уточненными» процедурами.

Одновременно с патентом [144] 30 июня 1971 г. Хорстом Фейстелем были поданы еще две заявки на патенты; обе предлагали специфические применения описанного выше алгоритма:

защиту данных, передаваемых и обрабатываемых в многотерминальных системах, с использованием алгоритма Lucifer; запатентованная схема подразумевает также обеспечение целостности данных, а также наличие двух режимов аутентификации пользователей: парольного и «запрос- ответ» [145];

многоступенчатое шифрование данных, обеспечивающее различные уровни защиты информации при ее передаче в многотерминальных системах; эта схема также основана на применении алгоритма Lucifer [146].

Алгоритм IDEA (International Data Encryption Algorithm) является блочным шифром. Он оперирует 64-битовыми блоками открытого текста. Несомненным достоинством алгоритма IDEA является то, что его ключ имеет длину 128 бит. Один и тот же алгоритм используется и для шифрования, и для дешифрования.

Первая версия алгоритма IDEA была предложена в 1990 г., ее авторы - Х.Лей и Дж.Мэсси. Первоначальное алгоритм назывался PES (Proposed Encryption Standard). Улучшенный вариант этого алгоритма, разработанный в 1991 г., получил название IPES (Improved Proposed Encryption Standard). В 1992 г. IPES изменил свое имя на IDEA. Алгоритм IDEA использует при шифровании процессы смешивания и рассеивания, которые легко реализуются аппаратными и программными средствами.

В IDEA используются следующие математические операции:

поразрядное сложение по модулю 2 (операция "исключающее ИЛИ"); операция обозначается как (+);
сложение беззнаковых целых по модулю 2¹⁶; операция обозначается как [+];
умножение беззнаковых целых по модулю (2¹⁶+1), причем блок из 16 нулей рассматривается как 2¹⁶; операция обозначается как (·).

Все операции выполняются над 16-битовыми субблоками.

Эти три операции несовместимы в том смысле, что:

никакая пара из этих трех операций не удовлетворяет ассоциативному закону,
например a[+](b(+)c)#(a[+]b)(+)c;
никакая пара из этих трех операций не удовлетворяет дистрибутивному закону,
например a[+](b(·)c)#(a[+]b)(·)(a[+]с).

Комбинирование этих трех операций обеспечивает комплексное преобразование входных данных, существенно затрудняя крипто-анализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".

Общая схема алгоритма IDEA приведена на рис.1. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле выполняется следующая последовательность операций:

(·) - умножение субблока X₁ и первого подключа.
[+] - сложение субблока X₂ и второго подключа.
[+] - сложение субблока X₃ и третьего подключа.
(·) - умножение субблока X₄ и четвертого подключа.
(+) - сложение результатов шагов 1 и 3.
(+) - сложение результатов шагов 2 и 4.
(·) - умножение результата шага 5 и пятого подключа.
[+] - сложение результатов шагов 6 и 7.
(·) - умножение результата шага 8 и шестого подключа.
[+] - сложение результатов шагов 7 и 9.
(+) - сложение результатов шагов 1 и 9.
(+) - сложение результатов шагов 3 и 9.
(+) - сложение результатов шагов 2 и 10.
(+) - сложение результатов шагов 4 и 10.

Рис.1. Cхема алгоритма IDEA (режим шифрования)

Выходом цикла являются четыре субблока, которые получаются как результаты выполнения шагов 11, 12, 13 и 14. В завершение цикла второй и третий субблоки меняются местами (за исключением последнего цикла). В результате формируется вход для следующего цикла.

После восьмого цикла осуществляется заключительное преобразование выхода:

(·) - умножение субблока X₁ и первого подключа.
[+] - сложение субблока X₂ и второго подключа.
[+] - сложение субблока X₃ и третьего подключа.
(·) - умножение субблока X₄ и четвертого подключа.

Полученные четыре субблока Y₁...Y₄ объединяют в блок шифртекста.

Создание подключей Z₁...Z₆ также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это - первые восемь подключей для алгоритма (шесть подключей - для первого цикла и первые два подключа - для второго). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей (четыре подключа - для второго цикла и четыре подключа - для третьего). Ключ снова циклически сдвигается влево на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.

Дешифрование осуществляется аналогичным образом, за исключением того, что порядок использования подключей становится обратным, причем ряд подключей дешифрования являются или аддитивными (-x), или мультипликативными (1/x) обратными величинами подключей шифрования (табл.1).

Таблица 1

Подключи шифрования и дешифрования алгоритма IDEA

Цикл	Подключи шифрования	Подключи дешифрования
1	Z₁⁽¹⁾ Z₂⁽¹⁾ Z₃⁽¹⁾ Z₄⁽¹⁾ Z₅⁽¹⁾ Z₆⁽¹⁾	Z₁^(9)-1 -Z₂⁽⁹⁾ -Z₃⁽⁹⁾ Z₄^(9)-1 Z₅⁽⁸⁾ Z₆⁽⁸⁾
2	Z₁⁽²⁾ Z₂⁽²⁾ Z₃⁽²⁾ Z₄⁽²⁾ Z₅⁽²⁾ Z₆⁽²⁾	Z₁^(8)-1 -Z₃⁽⁸⁾ -Z₂⁽⁸⁾ Z₄^(8)-1 Z₅⁽⁷⁾ Z₆⁽⁷⁾
3	Z₁⁽³⁾ Z₂⁽³⁾ Z₃⁽³⁾ Z₄⁽³⁾ Z₅⁽³⁾ Z₆⁽³⁾	Z₁^(7)-1 -Z₂⁽⁷⁾ -Z₃⁽⁷⁾ Z₄^(7)-1 Z₅⁽⁶⁾ Z₆⁽⁶⁾
4	Z₁⁽⁴⁾ Z₂⁽⁴⁾ Z₃⁽⁴⁾ Z₄⁽⁴⁾ Z₅⁽⁴⁾ Z₆⁽⁴⁾	Z₁^(6)-1 -Z₃⁽⁶⁾ -Z₂⁽⁶⁾ Z₄^(6)-1 Z₅⁽⁵⁾ Z₆⁽⁵⁾
5	Z₁⁽⁵⁾ Z₂⁽⁵⁾ Z₃⁽⁵⁾ Z₄⁽⁵⁾ Z₅⁽⁵⁾ Z₆⁽⁵⁾	Z₁^(5)-1 -Z₂⁽⁵⁾ -Z₃⁽⁵⁾ Z₄^(5)-1 Z₅⁽⁴⁾ Z₆⁽⁴⁾
6	Z₁⁽⁶⁾ Z₂⁽⁶⁾ Z₃⁽⁶⁾ Z₄⁽⁶⁾ Z₅⁽⁶⁾ Z₆⁽⁶⁾	Z₁^(4)-1 -Z₃⁽⁴⁾ -Z₂⁽⁴⁾ Z₄^(4)-1 Z₅⁽³⁾ Z₆⁽³⁾
7	Z₁⁽⁷⁾ Z₂⁽⁷⁾ Z₃⁽⁷⁾ Z₄⁽⁷⁾ Z₅⁽⁷⁾ Z₆⁽⁷⁾	Z₁^(3)-1 -Z₂⁽³⁾ -Z₃⁽³⁾ Z₄^(3)-1 Z₅⁽²⁾ Z₆⁽²⁾
8	Z₁⁽⁸⁾ Z₂⁽⁸⁾ Z₃⁽⁸⁾ Z₄⁽⁸⁾ Z₅⁽⁸⁾ Z₆⁽⁸⁾	Z₁^(2)-1 -Z₃⁽²⁾ -Z₂⁽²⁾ Z₄^(2)-1 Z₅⁽¹⁾ Z₆⁽¹⁾
Преобра- зование выхода	Z₁⁽⁹⁾ Z₂⁽⁹⁾ Z₃⁽⁹⁾ Z₄⁽⁹⁾	Z₁^(1)-1 -Z₂⁽¹⁾ -Z₃⁽¹⁾ Z₄^(1)-1

Для реализации алгоритма IDEA было принято соглашение, что мультипликативная обратная величина (1/x) от 0 равна 0.

Алгоритм IDEA обладает рядом преимуществ перед алгоритмом DES. Он зачительно безопаснее алгоритма DES, поскольку 128-битовый ключ алгоритма IDEA вдвое больше ключа DES. Внутренняя структура алгоритма IDEA обеспечивает лучшую устойчивость к криптоанализу. Существующие программные реализации примерно вдвое быстрее реализаций алгоритма DES. Алгоритм IDEA запатентован в Европе и США.
Алгоритм LOKI разработан в Австралии и впервые представлен в 1990 году в качестве возможной замены DES. В нем используются 64-битовый блок и 64-битовый ключ.

Используя дифференциальный криптоанализ, Бихам и Шамир взламывали алгоритм LOKI с 11 и менее раундами быстрее, чем лобовым вскрытием [170]. Более того, алгоритм характеризуется 8-битовой комплементарностью, что упрощает лобовое вскрытие в 256 раз.

Как показал Ларе Кнудсен (Lars Knudsen), алгоритм LOKI с 14 и менее раундами уязвим дифференциальному криптоанализу. Кроме того, если в LOKI используются альтернативные S-блоки, то полученный шифр, вероятно, тоже уязвим дифференциальному криптоанализу.

В ответ на описанные выше вскрытия разработчики LOKI вернулись за чертежную доску и пересмотрели свой алгоритм. В результате появился алгоритм LOKI91. (Предыдущая версия LOKI была переименована в LOKI89).

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

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

2.   Алгоритм генерации подключей модифицирован так, что число позиций циклического сдвига левого подключа составляло то 12, то 13 битов.

3.   Исключены начальная и заключительная операции XOR с блоком и ключом.

4.   Изменена функция S-блока с целью сгладить профили XOR S-блоков (чтобы повысить их устойчивость к дифференциальному криптоанализу), и исключить все значения х, для которых f(x) = 0, где f - комбинация Е-, S- и Р-блоков.

Алгоритм LOKI не запатентован - реализовать и использовать LOKI может кто угодно.

Описание алгоритма LOKI91

Механизм алгоритма LOKI91 подобен DES (Рис. 2). Блок данных расщепляется на левую и правую половины и проходит 16 раундов, что весьма напоминает DES. В каждом раунде правая половина сначала подвергается операции XOR с частью ключа, а затем расширяющей перестановке (Табл. 3).

Рис. Алгоритм LOKI91

Таблица. Перестановка с расширением

4,	3,	2,	1,	32,	31,	30,	29,	28,	27,	26,	25,
28,	27,	26,	25,	24,	23,	22,	21,	20,	19,	18,	17,
20,	19,	18,	17,	16,	15,	14,	13,	12,	11,	10,	9,
12,	11,	10,	9,	8,	7,	6,	5,	4,	3,	2,	1

48-битовый выход разделяется на четыре 12-битовых блока. В каждом блоке выполняется такая подстановка с использованием S-блока: берется каждый 12-битовый вход, 2 старших и 2 младших бита используются для образования номера r, а восемь внутренних битов образуют номер с. Выход S-блока, О, имеет следующее значение:

О(r,с) = (с + ((r*17) Å 0xff) & 0xff)³¹ mod P_r

Таблица. Значения P_r

r	1,	2,	3,	4,	5,	6,	7,	8,	9,	10,	11,	12,	13,	14,	15,	16
P_r	375,	379,	391,	395,	397,	415,	419,	425,	433,	445,	451,	463,	471,	477,	487,	499

Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки, описанной в табл. 3. Наконец, для получения новой левой половины выполняется операция XOR правой половины с прежней левой половиной, а левая половина становится новой правой половиной. После 16 раундов для получения окончательного шифртекста снова выполняется операция XOR над блоком и ключом.

Таблица. Перестановка с помощью Р-блока

32,	24,	16,	8,	31,	23,	15,	7,	30,	22,	14,	6,	29,	21,	13,	5,
28,	20,	12,	4,	27,	19,	11,	3,	26,	18,	10,	2,	25,	17,	9,	1

Подключи генерируются из ключа достаточно прямолинейно. 64-битовый ключ разбивается на левую и правую половины. На каждом раунде подключом служит левая половина. Далее она циклически сдвигается влево на 12 или 1 3 битов, затем после каждых двух раундов левая и правая половины меняются местами. Как и в DES, для зашифрования и расшифрования используется один и тот же алгоритм с некоторыми изменениями в использовании подключей.
CAST был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares) [10, 7]. Они утверждают, что название обусловлено ходом разработки и должно напоминать о вероятностном характере процесса, а не об инициалах авторов. Описываемый алгоритм CAST использует 64-битовый блок и 64-битовый ключ.

CAST имеет знакомую структуру. Алгоритм использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Работа этих S-блоков сложна и зависит от реализации, подробности можно найти в литературе.

Для шифрования сначала блок открытого текста разбивается на левую и правую половины. Алгоритм состоит из 8 этапов. На каждом этапе правая половина объединяется с частью ключа с помощью функции f, а затем XOR результата и левой половины выполняется для получения новой правой половины. Первоначальная (до этапа) правая половина становится новой левой половиной. После 8 этапов (не переставьте левую и правую половины после восьмого этапа) две половины объединяются, образуя шифротекст. Функция f проста:

Разбейте 32-битовый вход на четыре 8-битовых части: a, b, c, d.
Разбейте 16-битовый подключ на две 8-битовых половины: e, f.
Подайте a на вход S-блока 1, b - на вход S-блока 2, c - на вход S-блока 3, d - на вход S-блока 4, e - на вход S-блока 5 и f - на вход S-блока 6.
Выполните XOR шести выходов S-блоков, получая 32-битовый результат.