FEAL (англ. Fast data Encipherment ALgorithm) — блочный шифр , разработанный Акихиро Симидзу и Сёдзи Миягути — сотрудниками компании NTT .

В нём используются 64-битовый блок и 64-битовый ключ. Его идея состоит и в том, чтобы создать алгоритм , подобный DES , но с более сильной функцией этапа. Используя меньше этапов, этот алгоритм мог бы работать быстрее. К тому же, в отличие от DES, функция этапа для FEAL не использует S-блоки , поэтому реализация алгоритма не требует дополнительной памяти для хранения таблиц замены .

История

Опубликованный в 1987 году Акихиро Симидзу и Сёдзи Миягути блочный шифр FEAL был разработан с целью повысить скорость шифрования без ухудшения надежности шифра, по сравнению с DES . Первоначально алгоритм использовал блоки размером 64 бита, ключ размером 64 бита и 4 раунда шифрования. Однако, уже в 1988 году была опубликована работа Берта ден Боера ( англ. Bert Den-Boer ) , доказывающая достаточность владения 10000 шифротекстов для проведения успешной атаки на основе подобранного открытого текста . К шифру FEAL одному из первых был применен линейный криптоанализ . В том числе в 1992 году и доказали, что достаточно узнать 5 шифротекстов для проведения успешной атаки .

Для борьбы с обнаруженными уязвимостями создатели удвоили число раундов шифрования, опубликовав стандарт FEAL-8. Однако, уже в 1990 году (англ. Henri Gilbert) обнаружил уязвимость и этого шифра перед атакой на основе подобранного открытого текста . Далее в 1992 году и (Mitsuru Matsui and Atsuhiro Yamagishi) описали атаку на основе открытых текстов, требующую ${\displaystyle 2^{15}}$ известных шифротекстов .

В связи с большим числом успешных атак, разработчиками было принято решение еще усложнить шифр. А именно, в 1990 году был представлен FEAL-N, где N — произвольное четное число раундов шифрования, и представлен FEAL-NX, где X (от англ. extended) обозначает использование расширенного до 128 бит ключа шифрования. Однако данное нововведение помогло лишь частично. В 1991 году Эли Бихам и Ади Шамир , используя методы дифференциального криптоанализа , показали возможность взлома шифра с числом раундов ${\displaystyle N\leq 31}$ быстрее, чем полным перебором .

Тем не менее, благодаря интенсивности исследования алгоритма шифрования сообществом, были доказаны границы уязвимости шифра перед линейным и дифференциальным криптоанализом. Устойчивость алгоритма с числом раундов большим 26 к линейному криптоанализу показали в своей работе Сихо Мораи, Кадзумаро Аоки и Кадзуо Ота , а в работе Казумаро Аоки, Кунио Кобаяси и Шихо Мораи была доказана невозможность применить дифференциальный криптоанализ к алгоритму, использующему больше 32 раундов шифрования .

Описание

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

1. Предобработка
2. Итеративное вычисление
3. Постобработка

Кроме того, описан процесс генерации раундовых ключей, с которого и начинается шифрование, а также функции ${\displaystyle S_{0},\;S_{1},\;F,\;F_{k}}$ , с помощью которых и производятся преобразования.

Определим (A,B) — операцию конкатенации двух последовательностей бит.

Определим ${\displaystyle \phi }$ — нулевой блок длины 32 бита.

Функция S

${\displaystyle S_{0}(a,b)}$ = циклический сдвиг влево на 2 бита ${\displaystyle ((a+b)\mod {256})}$

${\displaystyle S_{1}(a,b)}$ = циклический сдвиг влево на 2 бита ${\displaystyle ((a+b+1)\mod {256})}$

Функция F

Функция F берёт 32 бита данных и 16 битов ключа и смешивает их вместе.

1. ${\displaystyle F=F(\alpha ,\beta )=(F_{0},F_{1},F_{2},F_{3})}$
2. ${\displaystyle \alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\beta _{1})}$
3. ${\displaystyle F_{1}=\alpha _{1}\oplus \beta _{0}}$
4. ${\displaystyle F_{2}=\alpha _{2}\oplus \beta _{1}}$
5. ${\displaystyle F_{1}=F_{1}\oplus \alpha _{0}}$
6. ${\displaystyle F_{2}=F_{2}\oplus \alpha _{3}}$
7. ${\displaystyle F_{1}=S_{1}(F_{1},F_{2})}$
8. ${\displaystyle F_{2}=S_{0}(F_{2},F_{1})}$
9. ${\displaystyle F_{0}=S_{0}(\alpha _{0},F_{1})}$
10. ${\displaystyle F_{3}=S_{1}(\alpha _{3},F_{2})}$

Функция ${\displaystyle F_{k}}$

Функция ${\displaystyle F_{k}}$ работает с двумя 32 битовыми словами.

1. ${\displaystyle F_{k}=F_{k}(\alpha ,\beta )=(F_{k_{0}},F_{k_{1}},F_{k_{2}},F_{k_{3}})}$
2. ${\displaystyle \alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3});\;\beta =(\beta _{0},\beta _{1},\beta _{2},\beta _{3})}$
3. ${\displaystyle F_{k_{1}}=\alpha _{1}\oplus \alpha _{0}}$
4. ${\displaystyle F_{k_{2}}=\alpha _{2}\oplus \alpha _{3}}$
5. ${\displaystyle F_{k_{1}}=S_{1}(F_{k_{1}},(F_{k_{2}}\oplus \beta _{0}))}$
6. ${\displaystyle F_{k_{2}}=S_{0}(F_{k_{2}},(F_{k_{1}}\oplus \beta _{1}))}$
7. ${\displaystyle F_{k_{0}}=S_{0}(\alpha _{0},(F_{k_{1}}\oplus \beta _{2}))}$
8. ${\displaystyle F_{k_{3}}=S_{1}(\alpha _{3},(F_{k_{2}}\oplus \beta _{3}))}$

Генерация раундовых ключей

В результате генерации раундовых ключей, из полученного на вход ключа длиной 128 бит получается набор из N+8 раундовых ключей ${\displaystyle K_{i}}$ , длиной 16 бит каждый. Данный результат получается в результате следующего алгоритма.

1. Разделение входного ключа на левый и правый ключ: ${\displaystyle K=(K_{L},K_{R})}$ , они имеют длину 64 бита.
2. Обработка ключа ${\displaystyle K_{R}=(K_{R1},K_{R2})}$
3. Введение временной переменной ${\displaystyle Q_{r}}$ для ${\displaystyle 1\leq r\leq {\frac {N}{2}}+4}$ :
   • ${\displaystyle Q_{r}=K_{R1}\oplus K_{R2},\;r=3i-2,\;i\in \mathbb {N} }$
   • ${\displaystyle Q_{r}=K_{R1},\;r=3i-1,\;i\in \mathbb {N} }$
   • ${\displaystyle Q_{r}=K_{R2},\;r=3i,\;i\in \mathbb {N} }$
4. Обработка ключа ${\displaystyle K_{L}=(A_{0},B_{0})}$
5. Введение временной переменной ${\displaystyle D_{0}=\phi }$
6. Последовательное вычисление ${\displaystyle K_{i}}$
   1. ${\displaystyle D_{r}=A_{r-1}}$
   2. ${\displaystyle A_{r}=B_{r-1}}$
   3. ${\displaystyle B_{r}=F_{k}(A_{r-1},(B_{r-1}\oplus D_{r-1})\oplus Q_{r}))=(B_{r_{0}},B_{r_{1}},B_{r_{2}},B_{r_{3}})}$
   4. ${\displaystyle K_{2(r-1)}=(B_{r_{0}},B_{r_{1}})}$
   5. ${\displaystyle K_{2(r-1)+1}=(B_{r_{2}},B_{r_{3}})}$

Предобработка

На начальной стадии блок данных ${\displaystyle P}$ готовится к итеративной процедуре шифрования.

1. ${\displaystyle P=(L_{0},R_{0})}$
2. ${\displaystyle (L_{0},R_{0})=(L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{N+3})}$
3. ${\displaystyle (L_{0},R_{0})=(L_{0},R_{0})\oplus (\phi ,L_{0})}$

Итеративная обработка

На этой стадии с блоком данных производится N раундов перемешивания битов по следующему алгоритму.

1. ${\displaystyle R_{r}=L_{r-1}\oplus F(R_{r-1},K_{r-1})}$
2. ${\displaystyle L_{r}=R_{r-1}}$

Постобработка

Задача этой стадии — подготовить почти готовый шифротекст к выдаче.

1. ${\displaystyle P=(R_{N},L_{N})}$
2. ${\displaystyle P=P\oplus (\phi ,R_{N})}$
3. ${\displaystyle P=P\oplus (K_{N+4},K_{N+5},K_{N+6},K_{N+7})}$

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

Применение

Хотя изначально алгоритм FEAL задумывался, как более быстродействующая замена DES, в том числе, для применения шифрования в смарт-картах, количество быстро найденных в нем уязвимостей поставило точку на перспективах использования данного алгоритма. К примеру, в работе Эли Бихама и Ади Шамира , опубликованной в 1991 году, доказана достаточность 8 выбранных открытых текстов для взлома шифра FEAL-4, 2000 — для взлома FEAL-8, ${\displaystyle 2^{28}}$ — для FEAL-16 . Все эти числа значительно меньше необходимого числа выбранных открытых текстов для атаки на DES, а тот факт, что FEAL-32 достаточно надежен, достаточно бесполезен, так как DES добивается сравнимой надежности при значительно меньшем числе раундов, тем самым лишая FEAL преимущества, изначально задумывавшегося создателями.

На данный момент на официальном сайте авторов шифра — компании NTT , в описании шифра FEAL вывешено предупреждение, о том что компания NTT рекомендует не использовать шифр FEAL, а использовать шифр Camelia , также разработанный этой компанией ради надежности и скорости шифрования .

Вклад в развитие криптографии

Благодаря тому, что шифр FEAL был разработан достаточно рано, он послужил отличным объектом для тренировок для криптологов всего мира .

Кроме того, на его примере был открыт линейный криптоанализ. , изобретатель линейного криптоанализа, в первой своей работе на эту тему рассматривал как раз FEAL и DES.

Примечания

Литература

• , (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Amsterdam, The Netherlands, April 13–15, 1987 Proceedings / D. Chaum , — Springer Science+Business Media , 1988. — P. 267—278. — 316 p. — ISBN 978-3-540-19102-5 —
• (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques, Davos, Switzerland, May 25-27, 1988. Proceedings / — Springer Science+Business Media , 1988. — P. 293—299. — 383 p. — ISBN 978-3-540-45961-3 —
• (англ.) // : 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York City, London: , 1990. — P. 624—627. — ( ; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN ; —
• (англ.) // : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone — Berlin, Heidelberg, New York City, London: , 1991. — P. 628—638. — ( ; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN ; —
• Murphy S. (англ.) // / — Springer Science+Business Media , International Association for Cryptologic Research , 1990. — Vol. 2, Iss. 3. — P. 145—154. — ISSN ; —
• , (англ.) // : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone — Berlin, Heidelberg, New York City, London: , 1991. — P. 22—33. — ( ; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN ; —
• Biham E. , Shamir A. (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991. Proceedings / — Berlin: , 1991. — P. 1—16. — ISBN 978-3-540-54620-7 —
• , (англ.) // : 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 1991, Proceedings / — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 1992. — 484 p. — ( ; Vol. 576) — ISBN 978-3-540-55188-1 — ISSN ; —
• , (англ.) // : Workshop on the Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24–28, 1992 Proceedings / — , 1993. — P. 81—91. — 491 p. — ISBN 978-3-540-56413-3 —
• , , (англ.) // : 4th International Workshop, FSE'97, Haifa, Israel, January 20-22, 1997, Proceedings / E. Biham — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 1997. — P. 41—53. — 299 p. — ( ; Vol. 1267) — ISBN 978-3-540-63247-4 — ISSN ; —
• — СПб. : , 2009. — С. 206—212. — 576 с. — ISBN 978-5-9775-0319