McEliece

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

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

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

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

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

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

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

Алгоритм работы

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

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

Все пользователи в системе совместно используют параметры безопасности: $~n,~k,~t$

Все вычисления проводятся в $~k$-мерном подпростанстве пространства $~\mathbb{F}_2^n$

Генерация ключа

1. Алиса выбирает двоичный $~(n,k)$-линейный код $~C$ исправляющий $~t$ ошибок. Затем для кода $C$ считается $k \times n$ производящая матрица $~G$
2. Для того, чтобы исходный код было сложно восстановить, Алиса генерирует случайную $k \times k$ невырожденную матрицу $~S$
3. Алиса генерирует случайную $n \times k$ матрицу перестановки $~P$
4. Алиса вычисляет $k \times n$ мартрицу ${\hat G}=SGP$
5. Открытым ключом является пара $({\hat G},t)$. Закрытым ключом является набор $~(S,G,P)$

Шифрование соообщения

Пусть Боб хочет передать сообщение $~m$ Алисе, чей открытый ключ $({\hat G},t)$.

1. Боб представляет свое сообщение $~m$ в виде последовательностей двоичных символов длины $~k$
2. Боб вычисляет вектор $~c^{\prime}=m{\hat G}$
3. Боб генерирует случайный вектор $~z$ длины $~n$, имеющий вес $~t$ (в нём ровно $~t$ единиц)^[1]
4. Боб вычисляет шифротекст как $~c = c^{\prime} + z$ и передает его Алисе

Дешифрование сообщения

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

1. Алиса вычисляет обратную матрицу: $~P^{-1}$
2. Алиса вычисляет ${\hat c}=cP^{-1}$
3. Алиса использует алгоритм дешифрования для кода $~C$, чтобы получить ${\hat m}$ из ${\hat c}$
4. Алиса вычисляет $m={\hat m}S^{-1}$

Корректность алгоритма

Покажем, что выполняется главное свойство криптосистемы, т.е что $~D_t(E_z(m))=m$

Боб посылает $c=c^{\prime}+z=m{\hat G}+z=mSGP+z$. Алиса вычисляет ${\hat c}=cP^{-1}=mSG+zP^{-1}$. Поскольку $~P^{-1}$ — матрица перестановки, то вес $~zP^{-1}$ не более, чем $~t$.

Код Гоппа $G$ исправляет до $t$ ошибок. Расстояние Хемминга $d_H(mSG,cP^{-1}) \le t$. Поэтому Алиса получает верное сообщение ${\hat m}=mS$. После этого Алиса вычисляет исходное сообщение $m={\hat m}S^{-1}=mSS^{-1}$.

Пример работы алгоритма

Пусть, например, мы пользуемся $~(7,4)$ кодом Хемминга, который исправляет все единичные ошибки. Производящая матрица

$~G= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$

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

$~S= \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}$

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

$~P= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$

Тогда

${\hat G}=SGP = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}$

Если Боб хочет послать сообщение $~m=\left ( 1101 \right )$ Алисе, то он сначала генерирует вектор с весом $~1$, например $~z=\left ( 0000100 \right )$ и вычисляет шифротекст$~c'=m{\hat G}+z = \left ( 0110010 \right ) + \left ( 00001000 \right ) = \left ( 0110110\right )$ и посылает его Алисе.

После получения сообщения, Алиса сначал вычисляет $~{\hat c}=cP^{-1}$, где

$P^{-1} = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$

получая $~{\hat c}=\left ( 1000111 \right )$.

После этого Алиса расшифровывает $~{\hat c}$ используя быстрый алгоритм декодирования (в этом примере — алгоритм Хэмминга. Синдромом $~{\hat c}$ является $\left ( 1110 \right ) ^{T}$, таким образом ошибка произошла в $~7$ позиции (подробности опущены). Тогда сообщение будет $~{\hat y}' = \left ( 1000110 \right )$. $~{\hat m}$ получается путем отбрасывания лишних битов у $~{\hat y}'$. Вследствие «правильного» выбора $~G$, Алиса знает, что $~mS = \left ( 1000 \right )$ и может теперь получить $~m$ из $~{\hat m}$ путем умножения на матрицу

$S^{-1} = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix}$

В итоге Алиса получает $~m = \left ( 1000 \right ) S^{-1}=\left ( 1101 \right )$

Атаки

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

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

Недостатки

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

• Размер открытого ключа $G'$ слишком большой. При использовании кодов Гоппы с параметрами, предложенными Мак-Элисом, открытый ключ составляет $2^{19}$ бит, что вызывает сложности в реализации. При других параметрах ключа:

Безопасность McEliece в зависимости от параметров

Степень защиты	Параметры $(n, k, t)$, кол-во ошибок	Размер открытого ключа в Кбит	Размер секретного ключа $({\hat G},P,S)$ в Кбит
Краткосрочная (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. ↑ R. Overbeck, D. Engelbert, A. Schmidt A Summary of McEliece-Type Cryptosystems and their Security (2006). Архивировано из первоисточника 23 апреля 2012. (англ.)
8. ↑ (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. (англ.)
9. ↑ (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

Ссылки

• Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes and Paul C. van Oorschot, Handbook of Applied Cryptography.
• Anne Canteaut and Nicolas Sendrier, Cryptanalysis of the Original McEliece Cryptosystem.
• R. J. McEliece (January and February 1978). «A Public-Key Cryptosystem Based On Algebraic Coding Theory». DSN Progress Report 42-44: 114. Bibcode: 1978DSNPR..44..114M. Проверено 21 February 2009.