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

На микропроцессоре 80286/10 МГц ассемблерная реализация FEAL-32 может шифровать данные со скор остью 220 Кбит/с. FEAL-64 может шифровать данные со скоростью 120 Кбит/с [1104].

32 бита

Блок ключа

б4 бита 32 бита

K0, K1

K2, K3

т:

K14, K15

32 бита

Рис. 13-5. Обработка ключа в FEAL.

32 бита

-Й 32 бита

a,, bi - 8 бит

32 бита

/k(a,b)

Y=S0(X1,X2)=Rot2((X1+X2) mod 256) Y=S1(X1,X2)=Rot2((X1+X2+1) mod 256) Y: выходные 8 битов, x1,X2 (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных Y

Рис. 13-6. Функция fK.

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

Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбра н-ными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вскр ы-тие, выполненное Сином Мерфи (Sean Murphy), было первым опубликованным вскрытием, использовавшим дифференциальный криптоанализ, и для него потребовалось только 20 выбранных открытых текстов. Ответом разработчиков стал 8-этапный FEAL [1436, 1437, 1108], криптоанализ которого б1л представлен Бихамом и

Шамиром на конференции SECURICOM 89 [1424]. Для вскрытия FEAL-8 с выбранными открытыми текстами потребовалось только 10000 блоков [610], что заставило разработчиков алгоритма засучить рукава и опред е-лить FEAL-N [1102, 1104], алгоритм с переменным числом этапов (конечно же, большим 8).

Бихам и Шамир применили против FEAL-N дифференциальный криптоанализ, хотя они могли бы еще б ы-стрее вскрыть его грубой силой (с помощью менее, чем 2 64 шифрований выбранного открытого текста) для N , меньшего 32. [169]. Для вскрытия FEAL-16 нужно 228 выбранных или 2465 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 237.5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов.

Разработчики FEAL определили также модификацию FEAL - FEAL-NX, в которой используется 128-битовый ключ (см. 6-й) [1103, 1104]. Бихам и Шамир показали, что для любого значения N FEAL-NX со 128-битовым ключом взламывать не сложнее, чем FEAL-N с 64-битовым ключом [169]. Недавно был предложен FEAL-N(X)S, усиливающий FEAL за счет динамической фун кции обмена местами [1525].

32 бита

Блок ключа (Kl Kr): 128 битов

Обработка бита четности Kl,-

K2, K3 4-

K4, K5

......

An/2+2

Kn+4, Kn+5

An/2+3

Kn+6, Kn+7

DN/2+2

Bn/2+2

Qn/2+3

Dn/2+3

32 бита

Bn/2+3

QN/2+4

Kr1 Kr2

К2(Г1): левая половина Br (16 битов) Qr=KR1 e KR2, r=1, 4, 7, ...

К2(Г1)+1: правая половина Br (16 битов) Qr=KR1, r=2, 5, 8, ...

Число итераций: n/2+4 Qr=KR2, r=3, 6, 9, ...

Рис. 13-7. Обработка ключа в FEAL-NX.

Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных откр ы-тых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия прив едены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsuru Matsui) и Атшуиро Ямагиши

(Atshuiro Yamagishi) [1020]. Это было первое применение линейного криптоанализа, и оно позволило вскрыть FEAL-4 с помощью 5 известных открытых текстов, FEAL-6 - с помощью 100 известных открытых текстов, а FEAL-8 - с помощью 215 известных открытых текстов. Дальнейшие уточнения можно найти в [64]. Диффере н-циальный криптоанализ позволяет вскрывать FEAL-8, используя только 12 выбранных открытых текстов [62]. Кто бы не изобрел новый метод криптоаналитического вскрытия, кажется, что он всегда сначала пробует его на

FEAL.

Патенты

FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дера п-таментом интеллектуальной собственности (Intellectual Property Department), NTT, 1-6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.

13.5 REDOC

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

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

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

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

REDOCIII

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

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

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

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

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

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

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

(d) Повторить для M2 этапы (a)-(c).

Этот алгоритм несложен и быстр. На 33 мегагерцовом процессоре 80386 он шифрует данные со скоростью