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

Si

Ф-Ф

Si

bo

e<—ф

a₀

a

a

16 битов

a 32 бита

a

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

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

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

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

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

32 бита	Блок ключа J64 бита 32 бита
	А0
	'			Во
		г- L
Ко, К,	к р
	А, ^1				•
	'			в,
	А	I- L	(Т>«
Кг, К$	Г		kV*
<	^	| _:'
	А7 ^1	'	D7\ А, 32 бита	в7
KU, Ki5 <		■

а₀

X

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

а 32 бита

a

a

~о<

-е«-

«X

Si

So

й 32 бита

So h©<-х₂

*ф—►

Si

а_и й,. - 8 бит

Y

|32 бита

/ф,й)

Y=S₀(X,X₂)=Rot2((X+X₂) mod 256) Y=Si(Xi,X2)=Rot2((Xi+X₂+1) mod 256) Y: выходные 8 битов, х_ьХ₂ (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных у

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

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

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

Бихам и Шамир применили против FEAL-N дифференциальный криптоанализ, хотя они могли бы еще б ы-стрее вскрыть его грубой силой (с помощью менее, чем 2 ^м шифрований выбранного открытого текста) для N, меньшего 32. [169]. Для вскрытия FEAL-16 нужно 2²⁸ выбранных или 2⁴⁶'⁵ известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 2³⁷'⁵ известных открытых текстов. 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].

Блок ключа («_L|K_R): 128 битов Обработка бита четности Q

K_L

Kb, AC,

Кг, Кз

Кл, Къ

Kn+_A, Kn+5

Kn+ 6, Kn+ 7

Kr1 Kr2

Kr

K_2(M): левая половина в_г(16 битов) К_2(М)+1: правая половина в_г (16 битов) Число итераций: Д//2+4

Q^/CriqKrz, г=1, 4, 7,...
QfKri, r=2, 5, 8,...

Q,=K_R2, r=3, 6, 9,...

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

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

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

Дата добавления: 2014-11-29