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

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

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

Криптоанализ и Madryga

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

Хотя у меня нет сведений о проведении формального анализа этого алгоритма, он не производит впечатл е-ние супернадежного. При поверхностном знакомстве с ним Эли Бихам пришел к следующим выводам [160]:

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

В этом нет ничего похожего на мощь S-блоков DES.

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

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

13.3 NewDES

NewDES (новый DES) был спроектирован в 1985 году Робертом Скоттом (Robert Scott) как возможная зам е-на DES [1405, 364]. Алгоритм не является модификацией DES, как может показаться из его названия. 0н оп е-рирует 64-битовыми блоками шифротекста, но использует 120-битовый ключ. NewDES проще, чем DES, в нем нет начальной и заключительной перестановок. Все операции выполняются над целыми байтами. (На самом деле NewDES ни коим образом не является новой версией DES, название было выбрано неудачно.)

Блок открытого текста делится на восемь 1-байтовых подблоков: S0, B1, . . B7. Затем подблоки проходят через 17 этапов. В каждом этапе восемь действий. В каждом действии один из подблоков подвергается опер а-ции XOR с частью ключа (есть одно исключение), заменяется другим байтом с помощью функции f и затем подвергается операции XOR с другим подблоком, который и заменяется результатом. 120-битовый ключ дели т-ся на 15 подблоков ключа: K0, K1, . . K13, K14. Процесс легче понять, увидев его схему, чем прочитав его оп и-сание. Алгоритм шифрования NewDES показан на 11-й.

Этап 1

K0 K3

Этап 2

Этап 16

Этап 17

K12 K14

Bo B1 B2 B3

B4 B5 B6 B7

Этапы 3-15

K4 K6

K8 K9

Bo B1 B2 B3

B4 B5 B6 B7

Рис. 13-2. NewDES.

Функция f выводится из Декларации независимости. Подробности можно найти в [1405].

Скотт показал, что каждый бит блока открытого текста влияет на каждый бит шифротекста уже после 7 эт а-пов. Он также проанализировал функцию f и не нашел каких-либо очевидных проблем. NewDES обладает той же комплиментарностью, что и DES [364]: если (P} = C, то = C. Это уменьшает объем работы, необ-

ходимой для вскрытия грубой силой, с 2110 действий до 2119. Бихам заметил, что любое изменение полного байта, примененное ко всем байтам ключа и данных, также приводит к комплиментарности [160]. Это уменьшает объем грубого вскрытия до 2112 действий.

Это не является критичным, но предложенное Бихамом криптоаналитическое вскрытие со связанными кл ю-чами может вскрыть NewDES с помощью 2 33 выбранных открытых текстов для выбранных ключей за 2 48 действий [160]. Хотя такое вскрытие требует много времени и в большой степени является теоретическим, оно п оказывает, что NewDES слабее, чем DES.

13.4 FEAL

FEAL был предложен Акихиро Шимузу (Akihiro Shimizu) Шоджи Миягучи (Shoji Miyaguchi) из NTT Japan [1435]. В нем используются 64-битовый блок и 64-битовый ключ. Его идея состоит в том, чтобы создать алг о-ритм, подобный DES, но с более сильной функцией этапа. Используя меньше этапов, этот алгоритм мог бы р а-ботать быстрее. К несчастью действительность оказалась далека от целей проекта.

Описание FEAL

На 10-й представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключа. 3 а-

тем блок данных расщепляется не левую и правую половины. 0бъединение левой и правой половин с помощью XOR образует новую правую половину. Левая половина и новая правая половина проходят через n этапов (первоначально четыре). На каждом этапе правая половина объединяется с помощью функции f с шестнадцатью битами ключа и с помощью XOR - с левой половиной, создавая новую правую половину. Исходная правая п о-ловина (на начало этапа) становится новой левой половиной. После n этапов (не забывайте, что левая и правая половины не переставляются после n-го этапа) левая половина снова объединяется с помощью XOR с правой половиной, образуя новую правую половину, затем левая и правая соединяются вместе в 64-битовое целое. Блок данных объединяется с помощью XOR с другими 64 битами ключа, и алгоритм завершается.

32 бита L0 {R8}

Открытый текст

64 бита

64 бита

(K8, K9, K10,

{(K12, K13, K14, K15)} -2 бита

- K0 {K7}

R0 {L8}

L1 {R7}

R8 {Lo}

64 бита

Шифротекст

- K1 {K6} R1 {L7}

- K7 {K0}

R7 {L1}

►Ф

L8 {Ro}

(K12, K13, K14, K15)

{}: Дешифрирование

Рис. 13-3. Один этап FEAL.

Функция f берет 32 бита данных и 16 битов ключа и смешивает их вместе. Сначала блок данных разбивается на 8-битовые кусочки, которые затем объединяются с помощью XOR и заменяют друг друга. Блок-схема фун к-ции f представлена на 9-й. Две функции 50и S1 определяются следующим образом:

S0(a,b) = циклический сдвиг влево на два бита ((a + b) mod 256)

= циклический сдвиг влево на два бита(( a + b + 1) mod 256)

(а,ь)

So I

So к

S1 \* (J)i Ф

16 битов

32 бита

Рис. 13-4. Функция f.

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

На 8-й представлена блок-схема функции генерации ключа. Сначала 64-битовый ключ делится на две пол о-