McEliece

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

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

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

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

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

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

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

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

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

Зафиксируем[7] конечное поле c базисом над полем , а так же множество различных элементов из . Так же зафиксируем неприводимый полином степени , где . Код Гоппы состоит из всех элементов из удовлетворяющих в Размерность как минимум . Для криптографических приложений мы будем предполагать в точности . Матрица вида

,

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

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

McElice состоит из трех алгоритмов:

  • алгоритма случайной генерации ключа, который дает открытый и секретный ключ
  • алгоритма случайного шифрования
  • детерминированного алгоритма расшифрования

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

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

Все вычисления проводятся в -мерном подпространстве пространства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алиса выбирает матрицу

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

Тогда

Если Боб хочет послать сообщение Алисе, то он сначала генерирует вектор с весом , например и вычисляет шифротекст и посылает его Алисе.

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

получая .

После этого Алиса расшифровывает используя быстрый алгоритм декодирования (в этом примере — алгоритм Хэмминга. Синдромом является , таким образом ошибка произошла в позиции (подробности опущены). Тогда сообщение будет . получается путём отбрасывания лишних битов у . Вследствие «правильного» выбора , Алиса знает, что и может теперь получить из путём умножения на матрицу

В итоге Алиса получает

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Размер открытого ключа слишком большой. При использовании кодов Гоппы с параметрами, предложенными Мак-Элисом, открытый ключ составляет бит, что вызывает сложности в реализации. При других параметрах ключа:
Безопасность McEliece в зависимости от параметров
Степень защиты Параметры , кол-во ошибок Размер открытого ключа в Кбит Размер секретного ключа в Кбит
Краткосрочная (60 бит) (1024, 644, 38), 38 644 (0,38, 10, 405)
Среднесрочная (80 бит) (2048, 1751, 27), 27 3,502 (0,30, 22, 2994)
Долгосрочная (256 бит) (6624, 5129, 115), 117 33,178 (1,47, 104, 25690)
  • Зашифрованное сообщение гораздо длиннее исходного. Увеличение полосы пропускания канала делает систему более подверженной ошибкам при передаче сообщения.
  • Криптосистема не может быть использована для аутентификации потому, что схема шифрования не является взаимно-однозначной, а сам алгоритм является асимметричным.

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

  1. 1 2 3 См. (R. J. McEliece 1978) (англ.)
  2. H. Dinh, C. Moore, A. Russell (17 August 2010), "The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks", arΧiv:1008.2390 [cs.CR]   (англ.)
  3. E. Berlekamp, R. McEliece, H. van Tilborg (1978). «On Inherent Intractability of Certain Coding Problems.» 24(3): 384-386. (англ.)
  4. R. Niebuhr, M. Meziani, S. Bulygin, J. Buchmann. «Selecting Parameters for Secure McEliece-based Cryptosystems». (англ.)
  5. (8 August 2008) «Attacking and defending the McEliece cryptosystem». Proc. 2nd International Workshop on Post-Quantum Cryptography 5299: 31–46. DOI:10.1007/978-3-540-88403-3_3. (англ.)
  6. S. Heyse. Code-based cryptography: implementing the McEliece Scheme on Reconfigurable hardware (31 May 2009). Архивировано из первоисточника 23 апреля 2012. (англ.)
  7. Daniel J. Bernstein, Tanja Lange and Christiane Peters. Attacking and defending the McEliece cryptosystem.
  8. R.J.McEliece. A Public-Key Cryptosystem Based On Algebraic Coding Theory.
  9. R. Overbeck, D. Engelbert, A. Schmidt. A Summary of McEliece-Type Cryptosystems and their Security (2006). Архивировано из первоисточника 23 апреля 2012. (англ.)
  10. (2007) «Modeling Bit Flipping Decoding Based on Nonorthodogonal Check Sums With Application to Iterative Decoding Attack of McEliece Cryptosystem.». IEEE Transactions on Information Theory: 402-211. (англ.)
  11. (2009) «Explicit Bounds for Generic Decoding Algortithms for Code-based Cryptography.». (англ.)

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

  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

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