Описание FEAL

Къ

Кп

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

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

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

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

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

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

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

13.3 NewDES

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

Блок открытого текста делится на восемь 1-байтовых подблоков: В₀, В_ъ . . ., В₆, В_ъ Затем подблоки проходят через 17 этапов. В каждом этапе восемь действий. В каждом действии один из подблоков подвергается опер а-ции XOR с частью ключа (есть одно исключение), заменяется другим байтом с помощью функции f и затем подвергается операции XOR с другим подблоком, который и заменяется результатом. 120-битовый ключ дели т-ся на 15 подблоков ключа: К₀, К_и . . ., К_и, К₁₄. Процесс легче понять, увидев его схему, чем прочитав его оп и-сание. Алгоритм шифрования NewDES показан на 11-й.

Этап 1

Этап 2

Ко К, К₂ К₃

Во B^ Вг Въ

К12

Ki3

K14

е

о

о

о

ф

3>

3>

#

f

/

f

/

t

/

ф

-Ф

/ ■•

е

^

ф

•е

-э

•0

Кэ

Кю

Во Bi B2 Вз

В₄ В₅ В_в В₇

Рис. 13-2. NewDES.

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

Скотт показал, что каждый бит блока открытого текста влияет на каждый бит шифротекста уже после 7 эт а-пов. Он также проанализировал функцию f и не нашел каких-либо очевидных проблем. NewDES обладает той же комплиментарностью, что и DES [364]: если Е^Р} = С, то Е_К(Р'} = С. Это уменьшает объем работы, необ­ходимой для вскрытия грубой силой, с 2¹¹⁰ действий до 2^Ш Бихам заметил, что любое изменение полного бай­та, примененное ко всем байтам ключа и данных, также приводит к комплиментарности [160]. Это уменьшает объем грубого вскрытия до 2¹¹² действий.

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

13.4 FEAL

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

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

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

32 бита

Lo{R_e}

Lo{R₈}

Открытый текст 64 бита i-

64 бита

(Кв. Кэ, Ко, Ки)

{(Kl2, Kl3, Kl4, Kb)}

—32 бита

*ф Ro{L_e}

Ко {К/}

Ro{U}

К {Ke}

L7 {Ri}|

f

— Ki {Ко} RAU)

Rb{L₀}

>Ф

L_B{R₀}

Ж 64 бита

( K12 , K13 , K14 , Kb)

{(Kb, Kb, Ко, Kii)}

Шифротекст

(V Дешифрирование

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

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

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

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

Ъ

f_{ab_}

So

I

So