Просмотр кода страницы MISTY1

{{другие значения|Мисти}}
{{Карточка блочного шифра
|название      = MISTY1
|изображение   =
|создатель     = Мицуру Мацуи, Тэцуя Итикава, Дзюн Соримати, Тосио Токита, Ацухиро Ямагиси
|создан        = [[1995]] г.
|опубликован   = [[1996]] г.<ref>Mitsuru Matsui. «Block encryption algorithm MISTY.» Technical report of IEICE ISEC96-11 (1996-07). (In Japanese).</ref>
|размер ключа  = 128 бит
|размер блока  = 64 бит
|число раундов = 4×n (рекомендуется 8)
|тип           = [[Сеть Фейстеля]]
}}
'''MISTY1''' (или '''MISTY-1''') — блочный алгоритм шифрования, созданный на основе «вложенных» [[Сеть Фейстеля|сетей Фейстеля]] в [[1995 год]]у криптологом Мицуру Мацуи (Mitsuru Matsui) совместно с группой специалистов для компании [[Mitsubishi Electric Corporation|Mitsubishi Electric]]. MISTY — это аббревиатура Mitsubishi Improved Security Technology, а также инициалы создателей алгоритма: в разработке алгоритма также приняли участие Тэцуя Итикава (Tetsuya Ichikawa), Дзюн Соримати (Jun Sorimachi), Тосио Токита (Toshio Tokita) и Ацухиро Ямагиси (Atsuhiro Yamagishi) <ref>{{cite web |url=http://global.mitsubishielectric.com/misty/about/road.html |title=アーカイブされたコピー |accessdate=2005-03-23 |deadurl=yes |archiveurl=https://web.archive.org/web/20050322134705/http://global.mitsubishielectric.com/misty/about/road.html |archivedate=2005-03-22 }}</ref>. Алгоритм был разработан в 1995 году, однако прошел лицензирование и был опубликован уже в 1996 году.

MISTY1 — это [[сеть Фейстеля]] с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE <ref>{{Cite web |url=https://www.cosic.esat.kuleuven.be/nessie/deliverables/press_release_feb27.pdf |title=Архивированная копия |access-date=2009-05-03 |archive-date=2016-10-13 |archive-url=https://web.archive.org/web/20161013120418/https://www.cosic.esat.kuleuven.be/nessie/deliverables/press_release_feb27.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://www.panasenko.ru/Articles/66/66.html |title=Конкурс NESSIE и алгоритм MISTY1<!-- Заголовок добавлен ботом --> |access-date=2009-05-03 |archive-date=2011-01-30 |archive-url=https://web.archive.org/web/20110130093747/http://www.panasenko.ru/Articles/66/66.html |deadlink=no }}</ref>. В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ). Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.

MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.<ref>{{Cite web |url=http://tools.ietf.org/html/draft-ietf-tls-misty1-01 |title=IETF Draft TLS MISTY1 01 |access-date=2011-11-25 |archive-date=2012-03-30 |archive-url=https://www.webcitation.org/66Yeq8Sjt?url=http://tools.ietf.org/html/draft-ietf-tls-misty1-01 |deadlink=no }}</ref>

== Структура алгоритма ==
[[Файл:Misty1 alg.png|thumb|Структура алгоритма MISTY1]]
MISTY разрабатывался как криптосистема, которая может быть использована на практике большим числом прикладных систем, к примеру: программное обеспечение для работы со смарт-картами или в быстрых ATM сетях. Поэтому в основе алгоритма MISTY1 лежат три следующих принципа:

# Высокий уровень безопасности шифра;
# Быстрая исполнимость на всех процессорах на время создания алгоритма;
# Быстрота работы аппаратных средств, основанных на данном алгоритме.

Для удовлетворения данным требованиям в алгоритме MISTY1 использовались следующие методы шифрования:

# ''Логические операции.'' Операции AND, OR и XOR — наиболее распространённые элементы шифроалгоритмов. И хотя от них нельзя ожидать высокого уровня защищённости, эти операции выполняются быстро и эффективно любыми аппаратными средствами и легко реализуемы в программном обеспечении.
# ''Арифметические операции.'' Шифрование аппаратными средствами приводит к задержкам и повышает время шифрования и передачи данных. Однако время шифрования таких операций как сложение, вычитание, и иногда умножение, для шифров, ориентированных на программную реализацию, вполне соответствуют предлагаемому уровню безопасности.
# ''Операции сдвига.'' Часто используемая операция в криптосистемах, так как дёшево и легко реализуема аппаратно. Стоит заметить, что программная реализация операции сдвига, к примеру 32-битных слов, может выполняться достаточно медленно на процессорах меньшей разрядности.
# ''Таблицы перестановок.'' Подобные операции требовательны к скорости доступа к памяти, что следует учесть при программной реализации алгоритма. Аппаратные средства в свою очередь следует оптимизировать к данному шифру, для выполнения предполагаемых временных ограничений на обработку и передачу информации.

Алгоритм MISTY1 имеет весьма необычную структуру — он основан на «вложенных» сетях Фейстеля. Сначала 64-битный шифруемый блок данных разбивается на два 32-битных субблока, после чего выполняется r раундов следующих преобразований <ref name=spec>http://web.eecs.utk.edu/~dunigan/cs594-cns96/misty1spec.pdf</ref>:

# Каждый субблок обрабатывается операцией 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> и согласно таблицам ниже.
{| class="wikitable"
|-
! Назначение !! <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>
|}
{| class="wikitable"
|-
! Назначение !! <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.

== См. также ==
* [[KASUMI]]
* [[MISTY2]]
* [[NESSIE]]
* [[CRYPTREC]]

== Примечания ==
{{примечания}}

== Литература ==
# MISTY1 Specification [http://web.eecs.utk.edu/~dunigan/cs594-cns96/misty1spec.pdf]
# MISTY1 Supporting document [http://web.eecs.utk.edu/~dunigan/cns04/misty.pdf]
# [http://www.panasenko.ru/Book2/Fragments/3.36.html 3.36. Алгоритмы MISTY1 и MISTY2] из книги «Алгоритмы шифрования. Специальный справочник», Сергей Панасенко, 2009, ISBN 978-5-9775-0319-8

* {{cite web|url=https://www.cosic.esat.kuleuven.be/nessie/|title=NESSIE|lang=en|description=Официальный сайт NESSIE}}
* {{cite web|url=http://tools.ietf.org/html/draft-ietf-tls-misty1-01|title=License statement|lang=en|description=MISTY1 License statement|archiveurl=https://www.webcitation.org/66Yeq8Sjt?url=http://tools.ietf.org/html/draft-ietf-tls-misty1-01|archivedate=2012-03-30|deadurl=yes}}

== Ссылки ==
* RFC 2994
* [https://web.archive.org/web/20080725114826/http://global.mitsubishielectric.com/misty/about/about.html Mitsubishi — About MISTY] {{ref-en}}
* [http://www.ietf.org/ietf/IPR/MITSUBISHI-MISTY MISTY1 patent statement from Mitsubishi] {{ref-en}}
* [http://www.quadibloc.com/crypto/co040308.htm John Savard’s description of MISTY] {{ref-en}}
* [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#MISTY1 SCAN’s entry on MISTY1] {{ref-en}}
* [http://www2.nict.go.jp/y/y213/cryptrec_publicity/c02_report_english.pdf «CRYPTREC Report 2002; Report of the Cryptographic technique evaluation (FY 2002)» — Детальное описание алгоритма]{{Недоступная ссылка|date=Май 2018 |bot=InternetArchiveBot }} {{ref-en}}
* [https://web.archive.org/web/20080724210408/http://global.mitsubishielectric.com/company/rd/advance/pdf/vol100/vol100.pdf Vol.100/December 2002 Mitsubishi Electric ADVANCE] {{ref-en}}
* [http://www.cs.utk.edu/~dunigan/cs494-cns01/misty.pdf Supporting Document of MISTY1] {{ref-en}}
* [http://lj.streamclub.ru/crypto/theses/piret.pdf Block Ciphers: Security Proofs, Cryptanalysis, Design, and Fault Attacks]{{Недоступная ссылка|date=Май 2018 |bot=InternetArchiveBot }} {{ref-en}}
* [https://web.archive.org/web/20060515080901/http://homes.esat.kuleuven.be/~abiryuko/lecturenotes.pdf Alex Biryukov. Block Ciphers and Stream Ciphers: The State of the Art] {{ref-en}}

{{симметричные криптоалгоритмы}}

[[Категория:Сеть Фейстеля]]