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 n матрицу перестановки ~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 ( 0000100 \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.». (англ.)

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

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