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

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

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

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

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

Криптосистема имеет несколько преимуществ, например, над 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. Во-первых, существует несколько быстрых алгоритмов декодирования за полиномиальное время . Во-вторых, любой неприводимый многочлен над полем ${\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}}$ .

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

Покажем, что выполняется главное свойство криптосистемы , то есть, что ${\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 бит .

Атаки

Криптографическая стойкость системы основана на двух сложных вычислительных задачах: исчерпывающего поиска по ключевому пространству и декодирования по максимуму правдоподобия. В литературе описано достаточно большое количество атак на McEliece . Некоторые атаки, называемые , основаны на попытке построить/реконструировать декодер для кода, сгенерированного открытым ключом ${\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}}$ кодов .

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

Год	Алгоритм	Сложность ( ${\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 :

• Размер открытого ключа ${\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. (англ.) — CRC Press , 1996. — 816 p. — ( ) — ISBN 978-0-8493-8523-0
• , (англ.) // : International Conference on the Theory and Applications of Cryptology and Information Security, Beijing, China, October 18-22, 1998, Proceedings — Berlin: , 1998. — P. 187—199. — ( ; Vol. 1514) — ISBN 978-3-540-65109-3 — ISSN ; —