Русская Википедия:MISTY1
Шаблон:Другие значения Шаблон:Карточка блочного шифра MISTY1 (или MISTY-1) — блочный алгоритм шифрования, созданный на основе «вложенных» сетей Фейстеля в 1995 году криптологом Мицуру Мацуи (Mitsuru Matsui) совместно с группой специалистов для компании Mitsubishi Electric. MISTY — это аббревиатура Mitsubishi Improved Security Technology, а также инициалы создателей алгоритма: в разработке алгоритма также приняли участие Тэцуя Итикава (Tetsuya Ichikawa), Дзюн Соримати (Jun Sorimachi), Тосио Токита (Toshio Tokita) и Ацухиро Ямагиси (Atsuhiro Yamagishi) [1]. Алгоритм был разработан в 1995 году, однако прошел лицензирование и был опубликован уже в 1996 году.
MISTY1 — это сеть Фейстеля с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE [2][3]. В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ). Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.
MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.[4]
Структура алгоритма
MISTY разрабатывался как криптосистема, которая может быть использована на практике большим числом прикладных систем, к примеру: программное обеспечение для работы со смарт-картами или в быстрых ATM сетях. Поэтому в основе алгоритма MISTY1 лежат три следующих принципа:
- Высокий уровень безопасности шифра;
- Быстрая исполнимость на всех процессорах на время создания алгоритма;
- Быстрота работы аппаратных средств, основанных на данном алгоритме.
Для удовлетворения данным требованиям в алгоритме MISTY1 использовались следующие методы шифрования:
- Логические операции. Операции AND, OR и XOR — наиболее распространённые элементы шифроалгоритмов. И хотя от них нельзя ожидать высокого уровня защищённости, эти операции выполняются быстро и эффективно любыми аппаратными средствами и легко реализуемы в программном обеспечении.
- Арифметические операции. Шифрование аппаратными средствами приводит к задержкам и повышает время шифрования и передачи данных. Однако время шифрования таких операций как сложение, вычитание, и иногда умножение, для шифров, ориентированных на программную реализацию, вполне соответствуют предлагаемому уровню безопасности.
- Операции сдвига. Часто используемая операция в криптосистемах, так как дёшево и легко реализуема аппаратно. Стоит заметить, что программная реализация операции сдвига, к примеру 32-битных слов, может выполняться достаточно медленно на процессорах меньшей разрядности.
- Таблицы перестановок. Подобные операции требовательны к скорости доступа к памяти, что следует учесть при программной реализации алгоритма. Аппаратные средства в свою очередь следует оптимизировать к данному шифру, для выполнения предполагаемых временных ограничений на обработку и передачу информации.
Алгоритм MISTY1 имеет весьма необычную структуру — он основан на «вложенных» сетях Фейстеля. Сначала 64-битный шифруемый блок данных разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований [5]:
- Каждый субблок обрабатывается операцией FL (операции описаны далее). Этот шаг выполняется только в нечётных раундах.
- Над обрабатываемым субблоком выполняется операция FO.
- Результат этих операций накладывается побитовой логической операцией «исключающее или» (XOR) на необработанный субблок.
- Субблоки меняются местами. После заключительного раунда оба субблока ещё раз обрабатываются операцией FL.
Рекомендуемым количеством раундов алгоритма является 8, но количество раундов алгоритма может быть также любым, превышающим 8 и кратным четырём.
Операция FL
Операция FL является достаточно простой. Обрабатываемый ей субблок разбивается на два 16-битных фрагмента, над которыми выполняются следующие действия:
<math>R' = R \oplus (L \& KL_{\text{i,j,1}})</math>
<math>L' = L \oplus (R' | KL_{\text{i,j,2}})</math>
где:
L и R — входные значения левого и правого фрагментов соответственно;
L' и R' — выходные значения;
<math>KL_{\text{i,j,1}}</math> и <math>KL_{\text{i,j,2}}</math> — фрагменты j-го подключа i-го раунда для функции FL (процедура расширения ключа подробно описана далее);
& и | — побитовые логические операции «и» и «или» соответственно.
Операция FO
Функция FO более интересна — именно она является вложенной сетью Фейстеля. Аналогично предыдущим, функцией выполняется разбиение входного значения на два 16-битных фрагмента, после чего выполняются 3 раунда следующих действий:
- На левый фрагмент операцией XOR накладывается фрагмент ключа раунда <math>KO_{\text{i,k}}</math>, где k — номер раунда функции FO.
- Левый фрагмент обрабатывается операцией FI.
- На левый фрагмент накладывается операцией XOR значение правого фрагмента.
- Фрагменты меняются местами.
После третьего раунда операции FO на левый фрагмент накладывается операцией XOR дополнительный фрагмент ключа <math>KO_{\text{i,4}}</math>.
Операция FI
FI также представляет собой сеть Фейстеля, то есть это уже третий уровень вложенности. В отличие от сетей Фейстеля на двух верхних уровнях, данная сеть является несбалансированной: обрабатываемый 16-битный фрагмент делится на две части: 9-битную левую и 7-битную правую. Затем выполняются 3 раунда, которые состоят из следующих действий:
- Левая часть «прогоняется» через таблицу замен. 9-битная часть (в раундах № 1 и 3) обрабатывается таблицей S9, а 7-битная (в раунде № 2) — таблицей S7. Данные таблицы описаны далее.
- На левую часть операцией XOR накладывается текущее значение правой части. При этом, если справа 7-битная часть, она дополняется нулями слева, а у 9-битной части удаляются слева два бита.
- Во втором раунде на левую часть операцией XOR накладывается фрагмент ключа раунда <math>KI_{\text{i,k,1}}</math>, а на правую — фрагмент <math>KI_{\text{i,k,2}}</math>. В остальных раундах эти действия не выполняются.
- Левая и правая части меняются местами.
Для наглядности на рисунке жирными линиями выделен 9-битный поток данных.
Таблицы S7 и S9 алгоритма MISTY1 могут быть реализованы как с помощью вычислений, так и непосредственно таблицами, хранимыми в энергонезависимой памяти шифрующего устройства. При реализации алгоритма должен выбираться вариант использования таблиц в зависимости от ресурсов шифрующего устройства.
Расширение ключа
Задача процедуры расширения ключа состоит в формировании следующего набора используемых фрагментов ключа (для 8 раундов алгоритма):
- 20 фрагментов ключа <math>KL_{\text{i,j,m}}</math> (<math>\text{i}=1,3,5,7,9; 1 \leqslant \text{j} \leqslant 2; 1 \leqslant \text{m} \leqslant 2</math>), каждый из которых имеет размер по 16 битов;
- 32 16-битных фрагмента <math>KO_{\text{i,k}}</math> (<math>1 \leqslant \text{i} \leqslant 2; 1 \leqslant \text{k} \leqslant 4</math>);
- 24 7-битных фрагмента <math>KI_{\text{i,k,1}}</math> (при <math>\text{k}=4</math> , то есть в 4-м раунде функции FO, операция FI не выполняется);
- 24 9-битных фрагмента <math>KI_{\text{i,k,2}}</math>.
Таким образом, процедура расширения ключа вычисляет 1216 битов ключевой информации из 128-битного ключа шифрования алгоритма MISTY1. Выполняется данное вычисление следующим образом:
1. 128-битный ключ делится на 8 фрагментов <math>K_{\text{1}}...K_{\text{8}}</math> по 16 битов каждый.
2. Формируются значения <math>K'_{\text{1}}...K'_{\text{8}}</math>: в качестве <math>K'_{\text{n}}</math> используется результат обработки значения <math>K_{\text{n}}</math> функцией FI, которая в качестве ключа (то есть совокупности требуемых 7- и 9-битного фрагментов) использует значение <math>K'_{\text{n+1}}</math> (здесь и далее, если индекс n фрагмента ключа превышает 8, то вместо него используется индекс n-8).
3. Необходимые фрагменты расширенного ключа «набираются» по мере выполнения преобразований из массивов <math>K_{\text{1}}...K_{\text{8}}</math>, <math>K'_{\text{1}}...K'_{\text{8}}</math> и согласно таблицам ниже.
Назначение | <math>KO_{\text{i,1}}</math> | <math>KO_{\text{i,2}}</math> | <math>KO_{\text{i,3}}</math> | <math>KO_{\text{i,4}}</math> | <math>KI_{\text{i,1}}</math> | <math>KI_{\text{i,2}}</math> | <math>KI_{\text{i,3}}</math> |
---|---|---|---|---|---|---|---|
Фрагмент | <math>K_{\text{i}}</math> | <math>K_{\text{i+2}}</math> | <math>K_{\text{i+7}}</math> | <math>K_{\text{i+4}}</math> | <math>K'_{\text{i+5}}</math> | <math>K'_{\text{i+1}}</math> | <math>K'_{\text{i+3}}</math> |
Назначение | <math>KL_{\text{i,1,1}}</math> | <math>KL_{\text{i,2,1}}</math> | <math>KL_{\text{i,1,2}}</math> | <math>KL_{\text{i,2,2}}</math> |
---|---|---|---|---|
Фрагмент | <math>K_{\text{(i+1)/2}}</math> | <math>K'_{\text{(i+1)2+2}}</math> | <math>K'_{\text{(i+1)2+6}}</math> | <math>K_{\text{(i+1)/2+4}}</math> |
4. 16-битный фрагмент <math>KI_{\text{i,k}}</math> делится на 7-битный фрагмент <math>KI_{\text{i,k,1}}</math> и 9-битный <math>KI_{\text{i,k,2}}</math>.
Расшифрование
Расшифрование производится выполнением тех же операций, что и при зашифровании, но со следующими изменениями:
- фрагменты расширенного ключа используются в обратной последовательности,
- вместо операции FL используется обратная ей операция (обозначим её FLI).
Схема процедуры расшифрования приведена на рис:
Операция FLI
Операция FLI определена следующим образом:
<math>L' = L \oplus (R \& KL_{\text{i,j,2}})</math>
<math>R' = R \oplus (L' | KL_{\text{i,j,1}})</math>
Безопасность
MISTY1 был разработан на основе теории «подтверждённой безопасности» против дифференциального и линейного криптоанализа. Этот алгоритм был спроектирован, чтобы противостоять различным криптоатакам, известным на момент создания.
С момента публикации мисти было проведено много исследований, чтобы оценить его уровень безопасности. Некоторые результаты по исследованию мисти с меньшим количеством раундов представлены ниже.
Дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Мисти содержит 2 look-up таблицы S7 и S9, обе с малой ad, 3 и 2 соответственно. Поэтому достаточно много статей посвящены дифференциальному криптоанализу мисти. Наилучший результат был получен для 5-уровневого алгоритма без FL функций. Однако именно присутствие FL функций и широкобитных AND/OR операции в них сильно затрудняет использование дифференциального криптоанализа высокого порядка.
Невозможный дифференциальный анализ также применим к блочному шрифту с одинаковым значением подключа в каждом раунде (или в каждом n-ом раунде). И так как MISTY1 имеет достаточно простую систему расширения ключа, вполне естественно рассмотреть применимость данной атаки к данному алгоритму. Лучший результата для подобной атаки был также получен при рассмотрении алгоритма без FL функций.
Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE (2000—2003 года). В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ).
Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.
Применение и модификации
Существует модификация данного алгоритма — MISTY2. Однако она не получила широкой известности вследствие низкого уровня криптостойкости.
Так же получила распространение модификация MISTY1 — алгоритм KASUMI — в 2000 году стал стандартом шифрования мобильной связи W-CDMA.
См. также
Примечания
Литература
- MISTY1 Specification [1]
- MISTY1 Supporting document [2]
- 3.36. Алгоритмы MISTY1 и MISTY2 из книги «Алгоритмы шифрования. Специальный справочник», Сергей Панасенко, 2009, ISBN 978-5-9775-0319-8
Ссылки
- RFC 2994
- Mitsubishi — About MISTY Шаблон:Ref-en
- MISTY1 patent statement from Mitsubishi Шаблон:Ref-en
- John Savard’s description of MISTY Шаблон:Ref-en
- SCAN’s entry on MISTY1 Шаблон:Ref-en
- «CRYPTREC Report 2002; Report of the Cryptographic technique evaluation (FY 2002)» — Детальное описание алгоритмаШаблон:Недоступная ссылка Шаблон:Ref-en
- Vol.100/December 2002 Mitsubishi Electric ADVANCE Шаблон:Ref-en
- Supporting Document of MISTY1 Шаблон:Ref-en
- Block Ciphers: Security Proofs, Cryptanalysis, Design, and Fault AttacksШаблон:Недоступная ссылка Шаблон:Ref-en
- Alex Biryukov. Block Ciphers and Stream Ciphers: The State of the Art Шаблон:Ref-en
Шаблон:Симметричные криптоалгоритмы