McEliece

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

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

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

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

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

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

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

Гоппа полином задаётся как полином над полем ${\displaystyle GF(p^{m})}$ вида ${\displaystyle g(x)=g_{0}+g_{1}x+g_{2}x^{2}+...+g_{t}x^{t}=\sum _{i=0}^{t}g_{i}x^{i}}$, где ${\displaystyle g_{i}\in GF(p^{m})}$, а ${\displaystyle t\in [2,...,(n-1)/d]}$. Также зададим ${\displaystyle n}$-размерное подмножество ${\displaystyle L}$ над расширением поля ${\displaystyle GF(p^{m})}$: ${\displaystyle L=[\alpha _{1},...,\alpha _{n}]\subseteq GF(p^{m})}$, для которого верно ${\displaystyle g(\alpha _{i})\not =0}$ при любых ${\displaystyle \alpha _{i}}$. Далее, для кодового слова ${\displaystyle c=[c_{0},...c_{n}]}$ над полем ${\displaystyle GF(p^{m})}$ определяется функция ${\displaystyle R_{c}(x)=\sum _{i=1}^{n}{\frac {c_{i}}{x-\alpha _{i}}}}$.

Код Гоппы ${\displaystyle \Gamma =\Gamma (L,g)}$ состоит из всех кодовых слов ${\displaystyle \mathbf {c} =(c_{1},...c_{n})}$, удовлетворяющих ${\displaystyle R_{c}(x)\equiv 0\ (mod\ g(x))}$. Это означает, что полином ${\displaystyle g(x)}$ делит ${\displaystyle R_{c}(x)}$.

Размерность ${\displaystyle k}$ кода Гоппы ${\displaystyle \Gamma (L,g)}$ длины ${\displaystyle n}$ больше или равна ${\displaystyle n-mt}$, а минимальное расстояние кода ${\displaystyle d}$ больше или равно ${\displaystyle t-1}$.

Проверочная матрица ${\displaystyle \Gamma (L,g)}$ имеет следующий вид:

${\displaystyle H={\begin{pmatrix}1/g(\alpha _{1})&\cdots &1/g(\alpha _{n})\\\alpha _{1}/g(\alpha _{1})&\cdots &\alpha _{n}/g(\alpha _{n})\\\vdots &\ddots &\vdots \\\alpha _{1}^{t-1}/g(\alpha _{1})&\cdots &\alpha _{n}^{t-1}/g(\alpha _{n})\end{pmatrix}}}$.

Если Гоппа полином представляет собой неприводимый полином ${\displaystyle g(x)}$ над полем ${\displaystyle GF(2^{m})}$, тогда минимальное расстояние ${\displaystyle d}$ такого кода больше или равно ${\displaystyle 2t+1}$. В дальнейшем предполагается, что ${\displaystyle d=2t+1}$.

В криптологических приложениях используется неприводимый, бинарный код Гоппы с параметрами ${\displaystyle [n,k.d]=[n,n-mt,2t+1]}$.

Существует несколько причин для применения кодов Гоппы в криптосистеме МcEliece. Во-первых, существует несколько быстрых алгоритмов декодирования за полиномиальное время^[7]. Во-вторых, любой неприводимый многочлен над полем ${\displaystyle GF(2^{m})}$ подойдёт для того, чтобы задать код Гоппы, порождающая матрица кода является почти случайной. Следовательно, коды Гоппы очень легко задать, но, в то же время, сложно распознать. Для фиксированной длины ${\displaystyle n}$ кодового слова существует множество кодов. Например, для кода длины ${\displaystyle n=128}$, способного исправлять до ${\displaystyle t=10}$ ошибок, существует около ${\displaystyle 10^{15}}$ различных Гоппа кодов. Их количество растёт экспоненциально в зависимости от длины слова и степени порождающего полинома.

McEliece состоит из трёх алгоритмов:

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

Текст сообщения представляет собой вектор длины ${\displaystyle k}$ над конечным полем ${\displaystyle GF(q)}$.

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

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

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

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

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

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

Покажем, что выполняется главное свойство криптосистемы^[5], то есть, что ${\displaystyle D_{t}(E_{z}(m))=m}$.

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

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

Пусть, используется неприводимый, бинарный код Гоппы c параметрами ${\displaystyle [12,4,5]}$, где ${\displaystyle g(x)=x^{2}+x+\alpha ^{3}}$ — неприводимый полином степени ${\displaystyle t=2}$ над полем ${\displaystyle GF(2^{4})}$, причём ${\displaystyle \alpha ^{3}=(0,0,0,1)^{T}\in GF(2^{4})}$.

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

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

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

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

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

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

Тогда

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

В качестве открытого ключа предоставляется эта матрица и ${\displaystyle t=2}$. Если Боб хочет послать сообщение ${\displaystyle m=(1,0,1,0)}$ Алисе, то он сначала генерирует вектор с весом ${\displaystyle 2}$, например, ${\displaystyle z=(1,1,0,0,0,0,0,0,0,0,0,0)}$.

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

${\displaystyle c'=m{\hat {G}}+z=(1,1,1,1,1,1,0,1,1,1,1,0)+(1,1,0,0,0,0,0,0,0,0,0,0)=(0,0,1,1,1,1,0,1,1,1,1,0)}$

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

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

${\displaystyle {\hat {c}}=c'P^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=m(SGP)P^{-1}+zP^{-1}=(mS)G+y'=(0,1,1,1,1,0,1,0,1,1,1,0)}$.

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

${\displaystyle mSG=(1,1,1,1,1,1,1,0,1,1,1,0)}$.

Находит ${\displaystyle mS=(1,1,0,1)}$.

И, в итоге, Алиса получает ${\displaystyle m=(1,1,0,1)S^{-1}=(1,0,1,0)}$.

Первоначально были предложены параметры: ${\displaystyle n=1024,k=524,t=50}$, в результате размер публичного ключа составлял 524*(1024—524) = 262,000 бит. В недавно проведённом анализе были предложены следующие параметры: ${\displaystyle n=2048,k=1751,t=27}$ для 80 бит безопасности при использовании обычного алгебраического декодирования, или ${\displaystyle n=1632,k=1269,t=34}$ при использовании декодировочной таблицы для кода Гоппы. При этом публичный ключ увеличивается до 520,047 и 460,647 бит соответственно. Для устойчивости против квантового компьютера параметры следует увеличить до ${\displaystyle n=6960,k=5413,t=119}$, а размер публичного ключа до 8,373,911 бит^[1][6].

Криптографическая стойкость системы основана на двух сложных вычислительных задачах: исчерпывающего поиска по ключевому пространству и декодирования по максимуму правдоподобия. В литературе описано достаточно большое количество атак на McEliece^[8]. Некоторые атаки, называемые структурными атаками, основаны на попытке построить/реконструировать декодер для кода, сгенерированного открытым ключом ${\displaystyle {\hat {G}}}$. Если такая попытка окажется успешной, то закрытый ключ ${\displaystyle G}$ будет раскрыт, а криптосистема полностью взломана. Код ${\displaystyle {\hat {C}}}$, порождённый матрицей ${\displaystyle {\hat {G}}}$ и код ${\displaystyle C}$, порождённый матрицей ${\displaystyle G}$, принадлежат одному эквивалентному классу. Злоумышленник должен сравнить представителя кода из каждого класса в ${\displaystyle {\hat {C}}}$ для того, чтобы определить эквивалентный код. Поскольку эквивалентные классы имеют очень малую мощность, этот процесс выходит за рамки возможностей даже самых мощных компьютеров. Для оригинальных параметров ${\displaystyle (1024,524,50)}$ данная структурная атака требует для изучения более ${\displaystyle 2^{466}}$ кодов^[5].

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

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

Пусть ${\displaystyle C}$ — это код длины ${\displaystyle n}$ над полем ${\displaystyle GF(2)}$, а ${\displaystyle n}$-мерный вектор ${\displaystyle y}$ имеет расстояние ${\displaystyle \omega }$ от кодового слова ${\displaystyle c\in C}$, тогда ${\displaystyle y-c}$ — это элемент ${\displaystyle C}$ с расстоянием ${\displaystyle \omega }$ от ${\displaystyle y}$. И обратное, если ${\displaystyle C}$ — это код длины ${\displaystyle n}$ над полем ${\displaystyle GF(2)}$ с минимальным расстоянием меньше ${\displaystyle \omega }$, тогда элемент ${\displaystyle e\in C+[0,y]}$ веса ${\displaystyle \omega }$ не может быть в ${\displaystyle C}$, он должен быть в ${\displaystyle C+[y]}$. Или иначе, ${\displaystyle y-e}$ — элемент ${\displaystyle C}$ с расстоянием ${\displaystyle \omega }$ от ${\displaystyle y}$.

Шифротекст криптосистемы McEliece ${\displaystyle y}$ имеет расстояние ${\displaystyle t}$ от уникального ближайшего кодового слова ${\displaystyle c}$ кода ${\displaystyle C}$, который имеет расстояние как минимум ${\displaystyle 2t+1}$. Атакующий знает порождающую матрицу кода ${\displaystyle C}$ и может легко добавить ${\displaystyle y}$ для образования порождающей матрицы для ${\displaystyle C+[0,y]}$. Единственное кодовое слово веса ${\displaystyle t}$ в ${\displaystyle C+[0,y]}$ — это ${\displaystyle y-c}$. Найдя это кодовое слово, атакующий находит ${\displaystyle c}$ и легко получает искомый текст. Стоит учесть, что декодирование даёт незначительное упрощение:

если ${\displaystyle C}$ имеет размерность ${\displaystyle k}$, то ${\displaystyle C+[0,y]}$ имеет размерность ${\displaystyle k+1}$. Алгоритм Штерна позволяет найти кодовое слово наименьшего веса.

На вход алгоритма поступает число ${\displaystyle \omega >0}$ и проверочная матрица ${\displaystyle H}$ размера ${\displaystyle (n-k)\times n}$ для ${\displaystyle (n,k)}$ кода над полем ${\displaystyle \mathbb {F} _{2}}$. С помощью методов линейной алгебры всегда можно получить из порождающей матрицы проверочную.

Случайным образом выбирается ${\displaystyle n-k}$ из ${\displaystyle n}$ столбцов матрицы ${\displaystyle H}$. Затем случайным образом выбирается ${\displaystyle l}$-размерное подпространство ${\displaystyle Z}$, которое разделяет оставшиеся ${\displaystyle k}$ на два подмножества ${\displaystyle X}$ и ${\displaystyle Y}$. Для кодового слова имеющего ровно ${\displaystyle p}$ не нулевых бит в ${\displaystyle X}$, ровно ${\displaystyle p}$ не нулевых бит в ${\displaystyle Y}$, ${\displaystyle 0}$ не нулевых бит в ${\displaystyle Z}$ и ровно ${\displaystyle \omega -2p}$ не нулевых бит в других столбцах.

Поиск состоит из трёх шагов. На первом шаге применяя простейшие операции к ${\displaystyle H}$ получаем из выбранных ${\displaystyle n-k}$ столбцов единичную матрицу. Этого сделать не получиться, если оригинальная ${\displaystyle (n-k)\times (n-k)}$ подматрица ${\displaystyle H}$ не является обратимой, тогда алгоритм запускается заново. Потери на перезапусках избегаются благодаря адаптивному выбору каждого столбца.

На втором шаге ${\displaystyle (n-k)\times (n-k)}$ подматрица ${\displaystyle H}$ есть единичная матрица, множество ${\displaystyle Z}$ из ${\displaystyle l}$ столбцов соответствует ${\displaystyle l}$ строчкам. Для каждого ${\displaystyle p}$ размерного подмножества ${\displaystyle A}$ множества ${\displaystyle X}$ вычисляется сумма столбцов в ${\displaystyle A}$ для каждой из этих ${\displaystyle l}$ строчек. В результате получается ${\displaystyle l}$-битный вектор ${\displaystyle \pi (A)}$. Аналогично для каждого ${\displaystyle p}$ размерного подмножества ${\displaystyle B}$ множества ${\displaystyle Y}$.

На третьем шаге для каждой коллизии ${\displaystyle \pi (A)=\pi (B)}$ считается сумма ${\displaystyle 2p}$ столбцов в ${\displaystyle A\cup B}$. Эта сумма будет являться ${\displaystyle (n-k)}$-битным вектором. Если сумма имеет вес ${\displaystyle \omega -2p}$, то получается ${\displaystyle 0}$ путём добавления соответствующих ${\displaystyle \omega -2p}$ столбцов в ${\displaystyle (n-k)\times (n-k)}$ подматрицу. Эти ${\displaystyle \omega -2p}$ столбцов вместе с ${\displaystyle A}$ и ${\displaystyle B}$ формируют искомое кодовое слово веса ${\displaystyle \omega }$.

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

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

• Зашифрованное сообщение гораздо длиннее исходного;

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

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
• Canteaut A., Sendrier N. Cryptanalysis of the Original McEliece Cryptosystem (англ.) // Advances in Cryptology — ASIACRYPT 1998: International Conference on the Theory and Applications of Cryptology and Information Security, Beijing, China, October 18-22, 1998, Proceedings — Berlin: Springer Berlin Heidelberg, 1998. — P. 187—199. — (Lecture Notes in Computer Science; Vol. 1514) — ISBN 978-3-540-65109-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-49649-1_16