FEAL

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
FEAL
Создатель:

Акихиро Симидзу и Сёдзи Миягути (NTT)

Опубликован:

FEAL-4 в 1987; FEAL-N/NX в 1990

Размер ключа:

64 бит (FEAL), 128 бит (FEAL-NX)

Размер блока:

64 бит

Число раундов:

изначально 4, потом 8 и потом переменное количество (рекомендуемое — 32)

Тип:

Сеть Фейстеля

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

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

История[править | править вики-текст]

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

Для борьбы с обнаруженными уязвимостями создатели удвоили число раундов шифрования, опубликовав стандарт FEAL-8. Однако, уже в 1990 году Генри Гилберт (англ. Henri Gilbert) уязвимость и этого шифра перед атакой на основе подобранного открытого текста.[4] Далее в 1992 году Митсуру Матсуи и Ацухиро Ямагиси (Mitsuru Matsui and Atsuhiro Yamagishi) описали атаку на основе открытых текстов, требующую известных шифротекстов.[3]

В связи с большим числом успешных атак, разработчиками было принято решение еще усложнить шифр. А именно, в 1990 году был представлен FEAL-N, где N — произвольное четное число раундов шифрования, и представлен FEAL-NX, где X (от англ. extended) обозначает использование расширенного до 128 бит ключа шифрования. Однако данное нововведение помогло лишь частично. В 1991 году Эли Бихам и Ади Шамир (Eli Biham and Adi Shamir), используя методы дифференциального криптоанализа, показали возможность взлома шифра с числом раундов быстрее, чем полным перебором.[5]

Тем не менее, благодаря интенсивности исследования алгоритма шифрования сообществом, были доказаны границы уязвимости шифра перед линейным и дифференциальным криптоанализом. Устойчивость алгоритма с числом раундов большим 26 к линейному криптоанализу показали в своей работе Шихо Мораи, Казумаро Аоки и Казуо Охта (Shiho Moriai, Kazumaro Aoki, and Kazuo Ohta)[6], а в работе Казумаро Аоки, Кунио Кобаяси и Шихо Мораи (Kazumaro Aoki, Kunio Kobayashi, and Shiho Moriai) была доказана невозможность применить дифференциальный криптоанализ к алгоритму, использующему больше 32 раундов шифрования.[7]

Описание[править | править вики-текст]

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

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

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

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

Определим  — нулевой блок длины 32 бита.

Функция S[править | править вики-текст]

= циклический сдвиг влево на 2 бита

= циклический сдвиг влево на 2 бита

Функция F[править | править вики-текст]

Схема функции F

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

Функция [править | править вики-текст]

Схема функции

Функция работает с двумя 32 битовыми словами.

Генерация раундовых ключей[править | править вики-текст]

Схема генерации раундовых ключей

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

  1. Разделение входного ключа на левый и правый ключ: , они имеют длину 64 бита.
  2. Обработка ключа
  3. Введение временной переменной для :
  4. Обработка ключа
  5. Введение временной переменной
  6. Последовательное вычисление

Предобработка[править | править вики-текст]

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

Итеративная обработка[править | править вики-текст]

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

Постобработка[править | править вики-текст]

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

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

Применение[править | править вики-текст]

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

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

Вклад в развитие криптографии[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. Панасенко Сергей Петрович. Алгоритмы шифрования. Специальный справочник. — БХВ-Петербург, 2009-01-01. — 577 с. — ISBN 9785977503198.
  2. Bert den Boer Cryptanalysis of F.E.A.L. (англ.) // SpringerLink. — Springer Berlin Heidelberg, 1988-05-25. — P. 293–299. — ISBN 3540459618. — DOI:10.1007/3-540-45961-8_27.
  3. 1 2 Mitsuru Matsui, Atsuhiro Yamagishi A New Method for Known Plaintext Attack of FEAL Cipher (англ.) // SpringerLink. — Springer Berlin Heidelberg, 1992-05-24. — P. 81–91. — ISBN 3540475559. — DOI:10.1007/3-540-47555-9_7.
  4. Henri Gilbert, Guy Chassé A Statistical Attack of the FEAL-8 Cryptosystem (англ.) // SpringerLink. — Springer Berlin Heidelberg, 1990-08-11. — P. 22–33. — ISBN 3540384243. — DOI:10.1007/3-540-38424.
  5. 1 2 Eli Biham, Adi Shamir Differential Cryptanalysis of Feal and N-Hash (англ.) // SpringerLink. — Springer Berlin Heidelberg, 1991-04-08. — P. 1–16. — ISBN 3540464166. — DOI:10.1007/3-540-46416-6_1.
  6. Kazuo Ohta, Shiho Moriai, Kazumaro Aoki Improving the Search Algorithm for the Best Linear Expression // Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology. — London, UK, UK: Springer-Verlag, 1995-01-01. — С. 157–170. — ISBN 3540602216.
  7. Kazumaro Aoki, Kunio Kobayashi, Shiho Moriai Best Differential Characteristic Search of FEAL // Proceedings of the 4th International Workshop on Fast Software Encryption. — London, UK, UK: Springer-Verlag, 1997-01-01. — С. 41–53. — ISBN 3540632476.
  8. Спецификация алгоритма шифрования FEAL-N(NX).
  9. NTT Encryption Archive List. info.isl.ntt.co.jp. Проверено 27 ноября 2016.
  10. Шнайер Б. Курс самоподготовки по криптоанализу блочных шифров. — Пер. с англ.Быбин С.С..

Источники[править | править вики-текст]

Ссылки[править | править вики-текст]

Пример реализации алгоритма шифрования FEAL на языке C.