McEliece

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

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

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

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

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

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

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

Введение в коды Гоппы

Описание

Основной источник:

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

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

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

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

$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}}$.

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

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

Причины для использования

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

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

Основной источник:

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

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

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

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

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

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

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

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

1. Боб представляет своё сообщение $m$ в виде последовательностей двоичных символов длины $k$.
2. Боб генерирует случайный вектор $z$ длины $n$, имеющий расстояние Хемминга $t$.
3. Боб вычисляет шифротекст как $c'=m{\hat {G}}+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=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})\leq t$, поэтому Алиса получает верное сообщение ${\hat {m}}=mS$. После этого Алиса вычисляет исходное сообщение $m={\hat {m}}S^{-1}=mSS^{-1}$.

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

Основной источник:

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

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

$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}}$,

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

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

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

$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}}$,

Тогда

${\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}}$.

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

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

$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)$

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

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

${\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)$.

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

$mSG=(1,1,1,1,1,1,1,0,1,1,1,0)$.

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

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

Размеры ключа

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

Атаки

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

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

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

Описание алгоритма атаки Штерна

Основной источник:

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

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

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

Поиск кодового слова наименьшего веса

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

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

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

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

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

Недостатки

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

• Размер открытого ключа ${\hat {G}}=SGP$ слишком большой. При использовании кодов Гоппы с параметрами, предложенными Мак-Элисом, открытый ключ составляет $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 (англ.) — Boca Raton: CRC Press, 1997. — 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