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

    Спроектировать блочный шифр нетрудно. Если рассматривать 64-битовый блочный шифр как перестановку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудно спроектировать такой блочный шифр, который не только стоек, но также может быть легко описан и реализован.

    Нетрудно спроектировать блочный шифр, если объем памяти достаточен для размещения 48*32-битовых S-блоков. Трудно спроектировать нестойкий вариант алгоритма DES, если нужно использовать в нем 128 раундов. При длине ключа 512 битов нет нужды беспокоиться о какой-либо зависящей от ключа комплементарности.

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

 

Блочные шифры

Алгоритм Lucifer

    В конце шестидесятых годов корпорация IBM запустила исследовательскую программу по компьютерной криптографии, названную Lucifer (Люцифер) и руководимую сначала Хорстом Файстелем (Horst Feistel), а затем Уолтом Тачменом (Walt Tuchman). Такое же имя - Lucifer - получил блочный алгоритм, появившийся в результате этой программы в начале семидесятых годов. В действительности существует, по меньшей мере, два различных алгоритма с таким именем. Один из них содержит ряд пробелов в спецификации алгоритма. Все это привело к заметной путанице.

    Алгоритм Lucifer представляет собой сеть перестановок и подстановок, его основные блоки напоминают блоки алгоритма DES. В DES результат функции f складывается операцией XOR с входом предыдущего раунда, образуя вход следующего раунда. У S-блоков алгоритма Lucifer 4-битовые входы и выходы, вход S-блоков представляет собой перетасованный выход S-блоков предыдущего раунда, входом S-блоков первого раунда служит открытый текст. Для выбора используемого S-блока из двух возможных используется бит ключа. (Lucifer реализует все это в едином Т-блоке с 9 битами на входе и 8 битами на выходе). В отличие от алгоритма DES, половины блока между раундами не переставляются, да и само понятие половины блока в алгоритме Lucifer не используется. У этого алгоритма 16 раундов, 128-битовые блоки и более простая, чем в DES, схема развертки ключа.

    Применив дифференциальный криптоанализ к первой реализации алгоритма Lucifer, Бихам и Шамир показали, что Lucifer с 32-битовыми блоками и 8 раундами можно взломать с помощью 40 подобранных открытых текстов за 2²⁹ операций. Этот же метод позволяет вскрыть Lucifer с 128-битовыми блоками и 8 раундами с помощью 60 подобранных открытых текстов за 2⁵³ шагов. Другая дифференциальная атака вскрывает 18-раундовый, 128-битовый Lucifer с помощью 24 подобранных открытых текстов за 2²¹ операций. Во всех этих вскрытиях использовались стойкие S-блоки алгоритма DES. Применив дифференциальный криптоанализ ко второй реализации Lucifer, Бихам и Шамир обнаружили, что его S-блоки намного слабее, чем в алгоритме DES. Дальнейший анализ показал нестойкость более половины возможных ключей. Криптоанализ на основе связанных ключей позволяет взломать 128-битовый Lucifer с любым числом раундов с помощью 2³³ подобранных открытых текстов для подобранных ключей или 2⁶⁵ известных открытых текстов для подобранных ключей. Вторая реализация Lucifer еще слабее.

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

Алгоритм Madryga

    В. Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году. Его можно эффективно реализовать программным путем: в алгоритме нет раздражающих перестановок, и все операции выполняются над байтами.

    Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

ü Без помощи ключа открытый текст невозможно получить из шифртекста. (Это означает только то, что алгоритм стоек).

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

ü Опубликование алгоритма не влияет на стойкость шифра. (Безопасность полностью определяется ключом).

ü Изменение одного бита ключа должно радикально изменять шифртекст одного и того же открытого текста, а изменение одного бита открытого текста должно радикально изменять шифртекст для того же ключа (лавинный эффект).

ü Алгоритм должен содержать некоммутативную комбинацию подстановок и перестановок.

ü Подстановки и перестановки, используемые в алгоритме, должны определяться как входными данными, так и ключом.

ü Избыточные группы битов открытого текста должны быть полностью замаскированы в шифртексте.

ü Длина шифртекста должна совпадать с длиной открытого текста.

ü Между любыми возможными ключами и особенностями шифртекста недопустимы простые взаимосвязи.

ü Все возможные ключи должны обеспечивать стойкость шифра. (Не должно быть слабых ключей).

ü Длина ключа и текст должны иметь возможность варьирования для реализации различных требований к безопасности.

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

 

    Алгоритм DES удовлетворял первым девяти требованиям, но последние три появились впервые. Если допустить, что лучший способ взлома алгоритма - лобовое вскрытие, переменная длина ключа, конечно же, заставит замолчать тех, кто считает, что 56 битов - слишком малая величина. Такие люди могут реализовать этот алгоритм с любой длиной ключа. А любой, кто когда-нибудь пытался реализовать DES программными средствами, обрадуется алгоритму, который учитывает особенности программных реализаций.

3.3.1. Описание алгоритма Madryga

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

    Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром (Рис. 1.). Это окно сдвигается на 1 байт за итерацию. (При работе с последними 2 байтами данные полагаются циклически замкнутыми). Первые два байта рабочего кадра циклически сдвигаются на переменное число позиций, а для последнего байта исполняется операция XOR с несколькими битами ключа. По мере перемещения рабочего кадра все байты последовательно циклически сдвигаются и подвергаются операции XOR с частями ключа. Последовательные циклические сдвиги перемешивают результаты предыдущих операций XOR и циклического сдвига, причем на циклический сдвиг влияют результаты XOR. Благодаря этому процесс в целом обратим.

 

Текст

1

2

3

4

5

6

…

TL-2

TL-1

TL

Движущийся рабочий кадр

WF(1)

WF(2)

WF(3)

8 битов

8 битов

8 битов

ROT

Перемещение

Объект сдвига

Счетчик сдвига

16 бит

3 бита

Преобразование

Объект преобразования

8 битов XOR

Ключ

1

2

3

…

KL

XOR

Хэш ключа

1

2

3

…

KL

 

Рис. 1. Одна итерация алгоритма Ma d ryga

 

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

    При зашифровании каждая итерация внутреннего цикла устанавливает рабочий кадр на предпоследний байт открытого текста и циклически перемещает его к третьему с конца байту открытого текста. Сначала весь ключ подвергается операции XOR со случайной константой и затем циклически сдвигается вправо на 3 бита (ключ и данные двигаются в разных направлениях, чтобы минимизировать избыточные операции с битами ключа). Младшие три бита младшего байта рабочего кадра сохраняются, они определяют циклический сдвиг остальных двух байтов. Далее конкатенация двух старших байтом циклически сдвигается влево на переменное число битов (от 0 до 7). Затем над младшим байтом рабочего кадра выполняется операция XOR с младшим байтом ключа. Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

    Случайная константа предназначена для превращения ключа в псевдослучайную последовательность. Длина константы должна быть равной длине ключа. При обмене данными абоненты должны пользоваться одной и той же константой. Для 64-битового ключа Мадрига рекомендует константу 0x0fle2d3c4b5a6978.

    При расшифровании процесс повторяется в обратном порядке. В каждой итерации внутреннего цикла рабочий кадр устанавливается на байт, третий слева от последнего байта шифртекста, и циклически сдвигается в обратном направлении до байта, расположенного на 2 байта левее последнего байта шифртекста. 2 байта шифртекста в процессе циклически сдвигаются вправо, а ключ - влево. После циклических сдвигов выполняется операция XOR.

 

3.2.2. Криптоанализ алгоритма Madryga

    Ученые Квинслендского технического университета (Queensland University of Technology) исследовали алгоритм Madryga и некоторые другие блочные шифры. Они обнаружили, что лавинный эффект при преобразовании открытого текста в шифртекст в этом алгоритме не проявляется. Кроме того, во многих шифртекстах доля единиц превышала доли нулей.

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

Алгоритм состоит только из линейных операций (циклический сдвиг и XOR), незначительно изменяемых в зависимости от данных.

Это ничуть не напоминает мощь S -блоков DES.

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

 

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

 

Алгоритм REDOC

    REDOC II представляет собой еще один блочный алгоритм, разработанный Майклом Вудом (Michael Wood) для корпорации Cryptech. В нем используются 20-байтовый (160-битовый) ключ и 80-битовый блок.

    Алгоритм REDOC II выполняет все манипуляции - перестановки, подстановки и операции XOR с ключом - с байтами. Этоталгоритм удобен для программной реализации. В REDOC II использованы переменные таблицы функций. В отличие от алгоритма DES, имеющего фиксированный (хотя и оптимизированный с точки зрения стойкости) набор таблиц подстановок и перестановок, в REDOC II используются зависимые от ключа и открытого текста наборы таблиц ( посути, S-блоки). В REDOC II 10 раундов, каждый раунд состоит из сложной последовательности манипуляций с блоком.

    Другая уникальная особенность REDOC II — использование масок. Это числа - производные таблицы ключей, которые используются для выбора таблиц данной функции для данного раунда. Для выбора таблиц функций используются как значение данных, так и маски.

    При условии, что самое эффективное средство взлома этого алгоритма - лобовое вскрытие, REDOC II весьма надежен: для восстановления ключа требуется 2¹⁶⁰ операций. Томас Кузик (Thomas Cusick) выполнил криптоанализ одного раунда REDOC II, но расширить вскрытие на несколько раундов ему не удалось. Используя дифференциальный криптоанализ, Бихам и Шамир успешно выполнили криптоанализ одного раунда REDOC II с помощью 2300 подобранных открытых текстов. Они не сумели расширить эту атаку на несколько раундов, но им удалось получить три значения маски после четырех раундов. Были и другие попытки криптоанализа.

3.3.1 Алгоритм REDOC III

    Алгоритм REDOC III представляет собой упрощенную версию REDOC II, тоже разработанную Майклом Вудом. Он оперирует с 80-битовым блоком. Длина ключа может изменяться и достигать 2560 байт (204800 бит). Алгоритм состоит только из операций XOR над байтами ключа и открытого текста, перестановки и подстановки не используются.

1) Создают таблицу ключей из 256 10-байтовых ключей, используя секретный ключ.

2) Создают два 10-байтовых блока масок M1 и М2. M1 представляет собой результат операции XOR первых 128 10-байтовых ключей, а М2 - результат операции XOR вторых 128 10-байтовых ключей.

3) Для шифрования 10-байтового блока:

a. Выполняют операцию XOR с первым байтом блока данных и первым байтом M1. Выбирают ключ в таблице ключей, рассчитанной в раунде 1. Используют вычисленное значение XOR в качестве индекса таблицы. Выполняют операцию XOR с каждым, кроме первого, байтом блока данных и соответствующим байтом выбранного ключа.

b. Выполняют операцию XOR со вторым байтом блока данных и вторым байтом M1. Выбирают ключ в таблице ключей, рассчитанной в раунде 1. Используют вычисленное значение XOR в качестве индекса таблицы. Выполните операцию ХОR с каждым, кроме второго, байтом блока данных и соответствующим байтом выбранного ключа.

c. Продолжают эти действия со всем блоком данных (с 3-10 байтами), пока не будет использован каждый байт для выбора ключа из таблицы после выполнения операции XOR с ним и соответствующим значением M1. Затем выполняют операцию XOR с каждым, кроме использованного для выбора ключа, байтом, и ключом.

d. Повторяют этапы а-с для М2.

 

    Это несложный и скоростной алгоритм. На процессоре 80386 с тактовой частотой 33МГц он шифрует данные со скоростью 2.75 Мбит/сек. По оценке Вуда, конвейеризированный процессор с трактом данных 64 бит и тактовой частотой 20 МГц может шифровать данные со скоростью свыше 1.28 Гбиг/сек.

    Алгоритм REDOC III нестоек. Он уязвим к дифференциальному криптоанализу. Для восстановления обеих масок достаточно около 2²³ подобранных открытых текстов.

 

Алгоритм LOKI

    Алгоритм LOKI разработан в Австралии и впервые представлен в 1990 году в качестве возможной замены DES. В нем используются 64-битовый блок и 64-битовый ключ.

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

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

 

3.4.1. Алгоритм LOKI 91

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

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

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

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

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

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

 

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

 

3.4.2. Описание алгоритма LOKI 91

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

 

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

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

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

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

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

        

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

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

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, для зашифрования и расшифрования используется один и тот же алгоритм с некоторыми изменениями в использовании подключей.

 

3.4.3. Криптоанализ алгоритма LOKI 91

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

    Другая атака со связанными ключами позволяет вскрыть алгоритм LOKI91 с помощью 2³² подобранных открытых текстов для выбранных ключей или с помощью 2⁴⁸ известных открытых текстов для выбранных ключей. Эффективность атаки не зависит от числа раундов алгоритма. (В той же работе Бихам вскрывает LOKI89 криптоанализом со связанными ключами, используя 2¹⁷ подобранных открытых текстов для выбранных ключей или 2³³ известных открытых текстов для выбранных ключей). Усложнив схему развертки ключа, несложно повысить устойчивость LOKI91 к подобной атаке.

 

Алгоритмы Khufu и Khafre

    В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основу конструкции заложены следующие принципы:

ü 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа пренебрежимо мала (компьютерная память недорога и доступна), длину ключа следует увеличить.

ü Широкое использование в DES перестановок, хотя и удобно для аппаратных реализаций, чрезвычайно затрудняет программные реализации. Самые скоростные реализации DES выполняют перестановки с помощью таблиц подстановок. Таблицы подстановок могут обеспечить те же характеристики «рассеивания», что и собственно перестановки, и намного повысить гибкость реализации.

ü S-блоки DES, содержащие всего 64 4-битовых элементов, слишком малы. Теперь, с увеличением объема памяти, должны возрасти и S-блоки. Более того, все восемь S-блоков в DES используются одновременно. Хотя это и удобнее для аппаратуры, для программной реализации это представляется ненужным ограничением. Должны быть реализованы больший размер S-блоков и последовательное (а не параллельное) их использование.

ü Общепризнанно, что начальная и заключительная перестановки криптографически бессмысленны, а поэтому должны быть исключены.

ü Все скоростные реализации DES заранее вычисляют ключи для каждого раунда. Отсюда, нет причин не сделать эти вычисления более сложными.

ü В отличие от DES, критерии проектирования S-блоков должны быть общедоступны.

        

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

3.5.1 Алгоритм Khufu

    Khufu - это 64-битовый блочный шифр. 64-битовый открытый тест сначала расщепляется на две 32-битовые половины, L и R. Над обеими половинами и определенными частями ключа выполняется операция XOR. Затем, аналогично DES, результаты проходят некоторую последовательность раундов. В каждом раунде младший значащий байт L используется как вход S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее выбранный в S-блоке 32-битовый элемент подвергается операции XOR с R. Затем L циклически сдвигается на число, кратное восьми битам, L и R меняются местами, и раунд завершается. Сам S-блок не статичен, он меняется каждые восемь раундов. Наконец, по окончании последнего раунда, над L и R выполняется операция XOR с другими частями ключа, и половины объединяются, образуя блок шифртекста.

    Хотя части ключа используются для операции XOR с блоком шифрования в начале и конце исполнения алгоритма, главное назначение ключа - генерация S-блоков. Эти S-блоки секретны, по существу, это часть ключа. Полный размер ключа алгоритма Khufu равен 512 бит (64 байт), алгоритм предоставляет способ генерации S-блоков по ключу. Вопрос о достаточном числе раундов остается открытым. Как указывает Меркл, 8-раундовый алгоритм Khufu уязвим к вскрытию с подобранным открытым текстом. Он рекомендует использовать 16, 24 или 32 раунда. (Меркл ограничивает количество раундов числами, кратными восьми).

    Поскольку S-блоки Khufu зависят от ключа и секретны, алгоритм устойчив к дифференциальному криптоанализу. Известна дифференциальная атака на 16-раундовый Khufu, которая восстанавливает ключ с помощью 2³¹ подобранных открытых текстов, однако этот метод не удалось расширить на большее число раундов. Если принять, что лучший метод взлома Khufu - лобовое вскрытие, стойкость алгоритма впечатляет. 512-би-овый ключ обеспечивает сложность вскрытия 2⁵¹² - это огромное число в любом случае.

3.5.2. Алгоритм Khafre

    Khafre - это вторая криптосистема, предложенная Мерклом. (Khufu (Хуфу) и Khafre (Хафр) - имена египетских фараонов). Конструкция этого алгоритма близка Khufu, однако он спроектирован для приложений, где невозможны предварительные вычисления. S-блоки не зависят от ключа. Вместо этого в Khafre используются фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым раундом и после последнего, но и после каждых восьми раундов шифрования.

    Меркл предполагал, что в алгоритме Khafre следует использовать 64- или 128-битовые ключи и что в этом алгоритме понадобится большее число раундов, чем в Khufu. Это, наряду с тем, что каждый раунд Khafre сложнее раунда Khufu, делает Khafre менее скоростным. Зато алгоритму Khafre не нужны никакие предварительные расчеты, что ускорит шифрование небольших порций данных.

    В 1990 году Бихам и Шамир применили свой метод дифференциального криптоанализа к алгоритму Khafre. Им удалось взломать 16-раундовый Khafre атакой с подобранным открытым текстом, используя около 1500 различных шифрований. На их персональном компьютере это заняло около часа. Преобразование этой атаки в атаку с известным открытым текстом потребует около 2³⁸ шифрований. Алгоритм Khafre с 24 раундами можно взломать с помощью атаки с подобранным открытым текстом за 2⁵³ шифрования, а с помощью атаки с известным открытым текстом – за 2⁵⁹ шифрования.

 

    Алгоритмы Khufu и Khafre запатентованы. Исходный код этих алгоритмов приведен в патенте.

 

Алгоритм ММВ

   Недовольство использованием в одном из криптоалгоритмов 64-битового блока шифрования привело к созданию Джоаной Дэймен алгоритма под названием ММВ (Modular Multiplication-based Block cipher - модулярный мультипликативный блочный шифр). В основе ММВ лежит смешивание операций различных алгебраических групп. ММВ - итеративный алгоритм, главным образом состоящий из линейных действий (XOR и использование ключа) и параллельного применения четырех крупных обратимых нелинейных подстановок. Эти подстановки определяются с помощью умножения по модулю 2³²-1 с постоянными множителями. В итоге появляется алгоритм, использующий 128-битовый ключ и 128-битовый блок.

    Алгоритм ММВ оперирует 32-битовыми подблоками текста (х₀, х₁, х₂, x₃) и 32-битовыми подблоками ключа (k ₀, k ₁, k ₂, k ₃). Это упрощает реализацию алгоритма на современных 32-битовых процессорах. Чередуясь с операцией XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 4):

    x_i = x _i Å k_i для i = 0..3

    f(х₀, х₁, х₂, x₃)

    x_i = x _i Å k_{i +1} для i = 0..3

    f(х₀, х₁, х₂, x₃)

    x_i = x _i Å k_{i +2} для i = 0..3

    f(х₀, х₁, х₂, x₃)

    x_i = x _i Å k_i для i = 0..3

    f(х₀, х₁, х₂, x₃)

    x_i = x _i Å k_{i +1} для i = 0..3

    f(х₀, х₁, х₂, x₃)

    x_i = x _i Å k_{i +2} для i = 0..3

    f(х₀, х₁, х₂, x₃)

 

    Функция f исполняется в три шага:

1. x_i = с _i * x_i для i = 0..3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы).

2. Если младший значащий бит х ₀ = 1, то x ₀ = х ₀Å С. Если младший значащий байт х ₃ = 0, то х ₃ = х₃ Å С.

3. x_i = х _{i -1} Å x_i Å х _{i +1}для i = 0..3. 

    Все операции с индексами выполняются по модулю 4. Операция умножения на шаге 1 выполняется по модулю 2³²-1. Специальный случай для данного алгоритма: если второй операнд равен 2³²-1, результат тоже равен 2³²-1. В алгоритме используются следующие константы:

С = 2ааааааа

c₀ = 025f1cdb            

c₁ = 2*c₀

с₂=2³ *с₀

с₃=2⁷ *с₀

           Константа С - «простейшая» константа без круговой симметрии, высоким троичным весом и нулевым младшим значащим битом. У константы с₀ есть другие особые характеристики. Константы c₁, с₂ и с₃ - сдвинутые версии с₀, и служат для предотвращения атак, основанных на симметрии.

    Расшифрование выполняется в обратном порядке, Этапы 2 и 3 инверсны им самим. На этапе 1 вместо с _i используется с _i ^-1. Значение с₀^-1 = 0dad4694.

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

    Схема алгоритма ММВ обеспечивает на каждом раунде значительное и независимое от ключа рассеивание. ММВ изначально проектировался в расчете на отсутствие слабых ключей.

    ММВ – это уже мертвый алгоритм. Это утверждение справедливо по многим причинам, хотя криптоанализ ММВ и не был опубликован. Во-первых, алгоритм проектировался без учета требования устойчивости к линейному криптоанализу. Устойчивость к дифференциальному криптоанализу обеспечил выбор мультипликативных множителей, но о существовании линейного криптоанализа авторы не знали.

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

    Дэймен предлагает желающим улучшить алгоритм ММВ сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу С различной на каждом раунде. Затем улучшить развертку ключа, добавляя к ключам раундов константы с целью устранения смещения. Однако сам он не стал заниматься этим, а разработал алгоритм 3-Way.

 

Алгоритм Blowfish

    Blowfish - это алгоритм, разработанный Брюсом Шнайером специально для реализации на больших микропроцессорах. Алгоритм Blowfish не запатентован. При проектировании алгоритма Blowfish Шнайер пытался удовлетворить следующим критериям:

ü Скорость. Программа, реализующая алгоритм Blowfish на 32-битовых микропроцессорах, шифрует данные со скоростью 26 тактов на байт.

ü Компактность. Для исполнения программной реализации алгоритма Blowfish достаточно 5 Кбайт памяти.

ü Простота. В алгоритме Blowfish используются только простые операции: сложение, XOR и подстановка из таблицы по 32-битовому операнду. Анализ его схемы несложен, что снижает риск ошибок реализации алгоритма.

ü Настраиваемая стойкость. Длина ключа Blowfish переменна и может достигать 448 бит.

 

    Алгоритм Blowfish оптимизирован для применения в системах, не практикующих частой смены ключей, например, в линиях связи и программах автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим размером кэша данных, например, процессорах Pentium и PowerPC, алгоритм Blowfish заметно быстрее DES. Алгоритм Blowfish не годится для применения в случаях, где требуется частая смена ключей, например, в коммутаторах пакетов, или в качестве однонаправленной хэш-функции. Большие требования к памяти не позволяют использовать этот алгоритм в смарт-картах.

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

    Blowfish представляет собой 64-битовый блочный алгоритм шифрования с ключом переменной длины. Алгоритм состоит из двух частей: расширения ключа и шифрования данных. Расширение ключа преобразует ключ длиной до 448 битов в несколько массивов подключей общим размером 4168 байт.

    Шифрование данных заключается в последовательном исполнении простой функции 16 раз. На каждом раунде выполняются зависимая от ключа перестановка и зависимая от ключа и данных подстановка. Используются только операции сложения и XOR над 32-битовыми словами. Единственные дополнительные операции каждого раунда - четыре взятия данных из индексированного массива.

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

Рис 3. Алгоритм Blowfish

Р -массив состоит из восемнадцати 32-битовых подключей:

    Р₁,Р₂,...,Р₁₈

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

    S _1,0, S _1,1,…, S _1,255

           S _2,0, S _2,2,…, S _2,255

           S _3,0, S _3,3,…, S _3,255

           S _4,0, S _4,4,…, S _4,255

Алгоритм Blowfish представляет собой сеть Файстеля, состоящей из 16 раундов. На вход подается 64-битовый элемент данных х. Для зашифрования данных:

    Разбить х на две 32-битовых половины: x_L, x_R

    Для i от 1 до 16:

              x_L = x_L Å P_i

                          x_R = F (x_L) Å x_R

                          Переставить x_L и x_R

           Переставить x_L и x_R (отнять последнюю перестановку)

    x_R = x_R Å P₁₇

           x_L = x_L Å P₁₈

           Объединить x_L и x_R

Рис. 4. Функция F

        

Функция F рассчитывается следующим образом (Рис. 4.):

    Разделить x_L на четыре 8-битовых фрагмента: а, b, с и d

    F(x_L) = ((S _{1, a} + S _{2, b} mod2³²)Å  S _{3, c} ) + S _{4, d} mod2³²                                          

Расшифрование выполняется точно так же, как и зашифрование, но Р₁,Р₂,...,Р₁₈ используются в обратном порядке.

    В реализациях Blowfish, в которых требуется очень высокая скорость, цикл должен быть развернут, а все ключи храниться в кэше.

    Подключи рассчитываются с помощью самого алгоритма Blowfish. Вот какова точная последовательность действий.

1. Сначала Р-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр π.

2. Выполняется операция XOR над Р _1<