Эта статья входит в число добротных статей

McEliece

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

McEliece — криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году Робертом Мак-Элисом[en][1]. Это была первая схема, использующая рандомизацию в процессе шифрования. Алгоритм не получил широко признания в криптографии, но в то же время является кандидатом для постквантовой криптографии, так как устойчив к атаке с использованием Алгоритма Шора[2].

Алгоритм основан на сложности декодирования полных линейных кодов (общая задача декодирования является NP-сложной)[3].

Для описания закрытого ключа выбран код исправляющий ошибки, для которого известен эффективный алгоритм декодирования и который может исправить ошибок. Алгоритм использует двоичные коды Гоппа, которые легко декодируются благодаря алгоритму Петерсона. Открытый ключ получается при помощи маскировки выбранного кода как полного линейного. Для этого порождающая матрица сначала умножается справа на матрицу перестановок , а затем на невырожденную матрицу слева (см. алгоритм работы).

Существует несколько вариантов криптосистемы, использующих различные типы кодов. Большинство из них оказываются менее защищенными. Отдельного рассмотрения заслуживает вопрос выбора параметров криптосистемы[4].

До сих пор McElice с кодами Гоппы не поддается криптоанализу[5]. Наиболее известные атаки используют алгоритм декодирования множества данныx. Последние работы описывают как атаки на систему, так и её защиту[6]. В других работах показано, что для квантовых вычислений размер ключа должен быть увеличен на четыре порядка из-за усовершенствования декодирования множества данных[2].

Криптосистема имеет несколько преимуществ, например, над RSA. Шифрование и дешифрование проходит быстрее и с ростом длины ключа степень защиты данных растет гораздо быстрее. Долгое время считалось, что McEliece не может быть использована для ЭЦП. Однако оказалось возможным построить схему для ЭЦП на основе криптосистемы Нидеррайтера (модификация МcEliece).

Из-за недостатков McEliece используется редко. Одно из исключений — использование McElice для шифрования в Freenet-подобной сети ENTROPY.

Введение в коды Гоппы[править | править вики-текст]

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

Основной источник: [5]

Гоппа полином задается как полином над полем вида , где , а . Также зададим -размерное подмножество над расширением поля : , для которого верно при любых . Далее, для кодового слова над полем определяется функцию .

Код Гоппы состоит из всех кодовых слов , удовлетворяющих . Это означает, что полином делит .

Размерность кода Гоппы длины больше или равна , а минимальное расстояние кода больше или равно .

Проверочная матрица имеет следующий вид:

.

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

В криптологических приложениях используется неприводимый, бинарный код Гоппы с параметрами .

Причины для использования[править | править вики-текст]

Существует несколько причин для применения кодов Гоппы в криптосистеме МcEliece. Во-первых, существует несколько быстрых алгоритмов декодирования за полиномиальное время[7]. Во-вторых, любой неприводимый многочлен над полем подойдет для того, чтобы задать код Гоппы, порождающая матрица кода является почти случайной. Следовательно, коды Гоппы очень легко задать, но, в то же время, сложно распознать. Для фиксированной длины кодового слова существует множество кодов. Например, для кода длины , способного исправлять до ошибок, существует около различных Гоппа кодов. Их количество растет экспоненциально в зависимости от длины слова и степени порождающего полинома.

Алгоритм работы[править | править вики-текст]

Основной источник: [8]
McElice состоит из трех алгоритмов:
  • алгоритма случайной генерации ключа, который дает открытый и секретный ключ;
  • алгоритма случайного шифрования;
  • детерминированного алгоритма расшифрования.

Текст сообщения представляет из себя вектор длины над конечным полем .

Все пользователи в системе совместно используют параметры безопасности: .

Генерация ключа[править | править вики-текст]

  1. Алиса выбирает -линейный код , исправляющий ошибок. Затем для кода высчитывается порождающая матрица .
  2. Для того, чтобы исходный код было сложно восстановить, Алиса генерирует случайную невырожденную матрицу .
  3. Алиса генерирует случайную матрицу перестановки .
  4. Алиса вычисляет матрицу .
  5. Открытым ключом является пара . Закрытым ключом является набор .

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

Пусть Боб хочет передать сообщение Алисе, чей открытый ключ .

  1. Боб представляет своё сообщение в виде последовательностей двоичных символов длины .
  2. Боб генерирует случайный вектор длины , имеющий расстояние Хемминга .
  3. Боб вычисляет шифротекст как и передает его Алисе.

Расшифрование сообщения[править | править вики-текст]

После получения сообщения , Алиса выполняет следующие действия для расшифрования сообщения:

  1. Алиса вычисляет обратную матрицу ;
  2. Алиса вычисляет ;
  3. Алиса использует алгоритм декодирования для кода , чтобы получить из ;
  4. Алиса вычисляет .

Корректность алгоритма[править | править вики-текст]

Покажем, что выполняется главное свойство криптосистемы[5], то есть, что .

Боб посылает . Алиса вычисляет . Поскольку  — матрица перестановки, то вес не более, чем .

Код Гоппа исправляет до ошибок. Расстояние Хемминга , поэтому Алиса получает верное сообщение . После этого Алиса вычисляет исходное сообщение .

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

Основной источник: [5]

Пусть, используется неприводимым, бинарный код Гоппы c параметрами , где  — неприводимый полином степени нам полем , причем.

Алиса случайным образом генерирует порождающую матрицу такого кода

,

выбирает матрицу

и матрицу перестановки

,

Тогда

.

В качестве открытого ключа предоставляется эта матрица и . Если Боб хочет послать сообщение Алисе, то он сначала генерирует вектор с весом , например, .

Вычисляет шифротекст

и посылает его Алисе.

После получения сообщения Алиса сначала вычисляет

.

Из-за перестановок ошибки переместились в первый и шестой символы. Алиса, используя быстрый алгоритм декодирования, находит

.

Находит .

И, в итоге, Алиса получает .

Размеры ключа[править | править вики-текст]

Первоначально были предложены параметры: , в результате размер публичного ключа составлял 524*(1024—524) = 262,000 бит. В недавно проведенном анализе были предложены следующие параметры: для 80 бит безопасности при использовании обычного алгебраического декодирования, или при использовании декодировочной таблицы для кода Гоппы. При этом публичный ключ увеличивается до 520,047 и 460,647 бит соответственно. Для устойчивости против квантового компьютера параметры параметры следует увеличить до , а размер публичного ключа до 8,373,911 бит[1][6].

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

Криптографическая стойкость системы основана на двух сложных вычислительных задачах: исчерпывающего поиска по ключевому пространству и декодирования по максимуму правдоподобия. В литературе описано достаточно большое количество атак на McEliece[8]. Некоторые атаки, называемые структурными атаками, основаны на попытке построить/реконструировать декодер для кода, сгенерированного открытым ключом . Если такая попытка окажется успешной, то закрытый ключ будет раскрыт, а криптосистема полностью взломана. Код , порожденный матрицей и код , порожденный матрицей , принадлежат одному эквивалентному классу. Злоумышленник должен сравнить представителя кода из каждого класса в для того, чтобы определить эквивалентный код. Поскольку эквивалентные классы имеют очень малую мощность, этот процесс выходит за рамки возможностей даже самых мощных компьютеров. Для оригинальных параметров данная структурная атака требует для изучения более кодов[5].

Другие атаки направлены на получения исходного текста сообщения из шифрованного сообщения. Большинство из них основаны на декодировании множества данных (ISD (англ.)) или на парадоксе дней рождения[9], их обобщениях и улучшениях. Существуют такие атаки, как, например, итерационное декодирование[3] и статическое декодирование, но они не являются успешными. Атака ISD оказалась наименее сложной. В последние годы было описано несколько алгоритмов и их улучшения. Наиболее важные перечислены в таблице вместе с их двоичным показателем затрат для декодирования кода Гоппы. Для этих алгоритмов известны их предельные показатели[10].

Год Алгоритм Сложность ()
1986 Адамс-Мейер 80,7
1988 Ли-Брикелл 70,89
1989 Штерн 66,21
1994 Кантеаут-Шабанн 65,5
1998 Кантеаут-Шабант 64,1
2008 Бернштейн-Ланг-Петерс 60,4
2009 Финиаз-Сендреир 59,9

Описание алгоритма атаки Штерна[править | править вики-текст]

Основной источник: [6]

Пусть  — это код длины над полем , а -мерный вектор имеет расстояние от кодового слова , тогда  — это элемент с расстоянием от . И обратное, если  — это код длины над полем с минимальным расстоянием меньше , тогда элемент веса не может быть в , он должен быть в . Или иначе,  — элемент с расстоянием от .

Шифротекст криптосистемы McEliece имеет расстояние от уникального ближайшего кодового слова кода , который имеет расстояние как минимум . Атакующий знает порождающую матрицу кода и может легко добавить для образования порождающей матрицы для . Единственное кодовое слово веса в  — это . Найдя это кодовое слово, атакующий находит и легко получает искомый текст. Стоит учесть, что декодирование дает незначительное упрощение:

если имеет размерность , то имеет размерность . Алгоритм Штерна позволяет найти кодовое слово наименьшего веса.

Поиск кодового слова наименьшего веса[править | править вики-текст]

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

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

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

На втором шаге подматрица есть единичная матрица, множество из столбцов соответствует строчкам. Для каждого размерного подмножества множества вычисляется сумма столбцов в для каждой из этих строчек. В результате получается -битный вектор . Аналогично для каждого размерного подмножества множества .

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

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

Основные недостатки криптосистемы McEliece[6]:

  • Размер открытого ключа слишком большой. При использовании кодов Гоппы с параметрами, предложенными Мак-Элисом, открытый ключ составляет бит, что вызывает сложности в реализации;

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

  1. 1 2 R. J. McEliece A Public-Key Cryptosystem Based On Algebraic Coding Theory // DSN Progress Report 42-44. — 1978.
  2. 1 2 Dinh H., Moore C., Russell A. McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks // Advances in Cryptology — CRYPTO 2011: 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011, Proceedings / P. RogawaySpringer-Verlag Berlin Heidelberg, 2011. — P. 761–779. — 782 p. — ISBN 978-3-642-22791-2doi:10.1007/978-3-642-22792-9_43
  3. 1 2 Berlekamp E. R., McEliece R. J., Henk C. A. van Tilborg On the inherent intractability of certain coding problems // IEEE Trans. Inf. Theory / F. KschischangIEEE, 1978. — Vol. 24, Iss. 3. — P. 384–386. — ISSN 0018-9448doi:10.1109/TIT.1978.1055873
  4. Niebuhr R., Meziani M., Bulygin S. et al. Selecting Parameters for Secure McEliece-based Cryptosystems // International Journal of Information Security Springer Science+Business Media, 2012. — Vol. 11, Iss. 3. — P. 137–147. — ISSN 1615-5262doi:10.1007/S10207-011-0153-2
  5. 1 2 3 4 5 A. Valentijn Goppa Codes and Their Use in the McEliece Cryptosystems // Syracuse University SURFACE. — 2015.
  6. 1 2 3 4 Bernstein D. J., Lange T., Peters C. Attacking and Defending the McEliece Cryptosystem // Post-Quantum Cryptography: Second International Workshop, PQCrypto 2008 Cincinnati, OH, USA October 17-19, 2008 Proceedings / J. Buchmann, J. DingSpringer-Verlag Berlin Heidelberg, 2008. — P. 31–46. — 231 p. — (Lecture Notes in Computer Science; Vol. 5299) — ISBN 978-3-540-88402-6 — ISSN 0302-9743doi:10.1007/978-3-540-88403-3_3 D. J. Bernstein1 ,Tanja Lange, C. Peters. Attacking and defending the McEliece cryptosystem. — 2008.
  7. P. Loidreau. Strengthening McEliece Cryptosystem // Springer-Verlag Berlin Heidelberg. — 2000.
  8. 1 2 D. Engelbert, R. Overbeck, A. Schmidt A Summary of McEliece-Type Cryptosystems and their Security // IACR Eprint archive. — 2006.
  9. N. Courtois, M. Finiasz, N. Sendrier How to achieve a McEliece-based Digital Signature Scheme. — 2001.
  10. D.J. Bernstein, T. Lange, C. Peters, H.C.A. van Tilborg Explicit bounds for generic decoding algorithms for code-based cryptography // International Workshop on Coding and Cryptography. — 2009.

Литература[править | править вики-текст]