McEliece: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м r2.6.5) (робот изменил: nl:McEliece-cryptosysteem
оформление, интервики, шаблон, дополнение, обновление данных
Строка 1: Строка 1:
'''McEliece''' — [[криптосистема]] с [[Открытый ключ|открытыми ключами]] на основе теории алгебраического кодирования, разработанная в [[1978 год]]у [[Мак-Элис, Роберт|Робертом Мак-Элисом]].
'''McEliece''' — [[криптосистема]] с [[Открытый ключ|открытыми ключами]] на основе теории алгебраического кодирования, разработанная в [[1978 год]]у [[Мак-Элис, Роберт|Робертом Мак-Элисом]].<ref name="McEliece"> См. {{harv|R. J. McElice|1978}}</ref>
Это была первая схема, использующая [[рандомизация|рандомизацию]] в процессе шифрования.
Этот алгоритм использует существование определённого класса исправляющих ошибки кодов, называемых [[Код Гоппа|кодами Гоппа]] (Goppa). Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной.
Алгоритм не получил широко признания в [[криптография|криптографии]], но в то же время является кандидатом для [[постквантовая криптография|постквантовой криптографии]], так как устойчив к атаке с использованием [[Алгоритм Шора|Алгоритма Шора]].
<ref name="quantum-fourier">
{{cite arxiv
|date=17 August 2010
|title=The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
|eprint=1008.2390
|author=H. Dinh, C. Moore, A. Russell
|class=cs.CR
|lang = en
}}</ref>


Алгоритм основан на сложности [[декодирование|декодирования]]
== Описание алгоритма ==
полных [[линейный код|линейных кодов]] (общая задача декодирования является [[класс NP|NP-сложной]]).
<ref name="NP">
{{ cite journal
|author = E. Berlekamp, R. McEliece, H. van Tilborg
|date=1978
|title=On Inherent Intractability of Certain Coding Problems.
|pages=384-386
|volume=24(3)
|lang = en
}}</ref>


Для описания [[закрытый ключ|закрытого ключа]] выбран [[прямая коррекция ошибок|код исправляющий ошибки]], для которого известен эффективный алгоритм декодирования и который может исправить <math>t</math> ошибок. Алгорим использует двоичные [[коды Гоппа|код Гоппа]], которые легко декодируются благодаря [[алгоритм Петерсона|алгоритму Петерсона]]. [[криптосистема с открытым ключом|Открытый ключ]] получается при помощи маскировки выбранного кода как полного линейного. Для этого производящая матрица <math>G</math> умножается на две случайных [[невырожденная матрица|невырожденных матрицы]] <math>~S</math> и <math>~P</math> (см. [[#Алгоритм работы|алгоритм работы]]).
Пусть <math>d_H(x,y)</math> обозначает [[расстояние Хэмминга]] между <math>y</math> и <math>x</math>. Числа <math>n</math>, <math>k</math> и <math>t</math> служат параметрами системы. Закрытый ключ состоит из трёх частей: <math>G'</math> — это матрица генерации кода Гоппа, исправляющего <math>t</math> ошибок; <math>P</math> — это матрица перестановок размером <math>n*n</math>; <math>S</math> — это не[[Сингулярная матрица|сингулярная]] матрица размером <math>k*k</math>.
Открытым ключом служит матрица G размером <math>k*n</math>: <math>G=SG'P</math>.
Открытый текст сообщений представляет собой строку <math>k</math> битов в виде k-элементного вектора над полем <math>GF(2)</math>.


Существует несколько вариантов криптосистемы, использующие различные типы кодов. Большинство из них оказываются менее защищенными. Отдельного рассмотрения заслуживает вопрос выбора параметров криптосистемы.<ref name="parameters">
Для шифрования сообщения случайным образом выбирается n-элементный вектор <math>z</math> над полем <math>GF(2)</math>, для которого расстояние Хэмминга меньше или равно <math>t</math>.
{{cite journal
|author=R. Niebuhr, M. Meziani, S. Bulygin, J. Buchmann
|title=Selecting Parameters for Secure McEliece-based Cryptosystems
|url=http://eprint.iacr.org/2010/271.pdf
|lang = en
}}</ref>


До сих пор, McElice с кодами Гоппы не поддается криптоанализу. Наиболее известные атаки используют алгоритм [[декодирование множества данных|декодирования множества данныx]]. Последние работы описывают как атаки на систему, так и ее защиту.<ref name="fix">
<math>C=mG+z</math>.
{{cite journal
|last1=Bernstein |first1=Daniel J.
|last2=Lange |first2=Tanja
|last3=Peters |first3=Christiane
|date=8 August 2008
|title=Attacking and defending the McEliece cryptosystem
|journal=Proc. 2nd International Workshop on Post-Quantum Cryptography
|series=Lecture Notes In Computer Science
|volume=5299 |pages=31–46
|doi=10.1007/978-3-540-88403-3_3
|url=http://eprint.iacr.org/2008/318
|lan = en
}}</ref>
В других работах показано, что для [[квантовый компьютер|квантовых вычислений]] размер ключа должен быть увеличен на четыре порядка из-за усовершенствования декодирования множества данных.
Криптосистема имеет несколько преимуществ, например, над [[RSA]]. Шифрование и дешифрование проходит быстрее (для сравнения [[тест производительности|бенчмарков]] см. проект eBats [http://bech.cr.yp.to bech.cr.yp.to]) и с ростом длины ключа степень защиты растет гораздо быстрее. Долгое время считалось, что McEliece не может быть использована для [[электронная цифровая подпись|ЭЦП]]. Однако оказалось возможным построить схему для ЭЦП на основе криптосистемы Niederreiter (модификация МcEliece).


Из-за [[#Недостатки|недостатков]] McEliece используется редко. Одно из исключений — использование McElice для шифрования в [[Freenet]]-подобной сети [[Энтропия (сеть)| ENTROPY]]. Существуют реализации McEliece на [[ПЛИС]].<ref name="FPGA">
Для дешифрования сообщения сначала вычисляется <math>c'=cP^{-1}</math>. Затем с помощью декодирующего алгоритма для кодов Гоппа находится <math>m'</math>, для которого <math>d_H(m'G,c)</math> меньше или равно <math>t</math>. Наконец вычисляется <math>m=m'S^{-1}</math>.
{{cite web
|author=S. Heyse
|date=31 May 2009
|title=Code-based cryptography: implementing the McEliece Scheme on Reconfigurable hardware
|url=http://www.emsec.rub.de/media/crypto/attachments/files/2010/04/da_heyse.pdf
}}{{ref-en}}</ref>


== Алгоритм работы ==
В своей оригинальной работе МакЭлис предложил значения <math>n=1024</math>, <math>t=50</math> и <math>k=524</math>, Это минимальные значения, требуемые для безопасности.
McElice состоит из трех алгоритмов:
Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и не появилось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографичесом сообществе. Схема на два-три порядка быстрее чем [[RSA]], но у неё есть ряд недостатков. Открытый ключ огромен: <math>2^{19}</math> битов. Сильно увеличивается объём данных — [[шифротекст]] в два раза длиннее открытого текста.
* алгоритма случайной генерации [[ключ (криптография)|ключа]], который дает открытый и секретный ключ
* алгоритма [[вероятностное шифрование|случайного шифрования]]
* детерминированного алгоритма дешифрования

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

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

# Алиса выбирает двоичный <math>(n,k)</math>-линейный код <math>C</math> исправляющий <math>t</math> ошибок. Затем для кода <math>C</math> считается <math>k \times n</math> [[производящая матрица]] <math>~G</math>
# Для того, чтобы исходный код было сложно восстановить, Алиса генерирует ''случайную'' <math>k \times k</math> невырожденную матрицу <math>~S</math>
# Алиса генерирует случайную <math>n \times k</math> [[матрица перестановки|матрицу перестановки]] <math>~P</math>
# Алиса вычисляет <math>k \times n</math> мартрицу <math>{\hat G}=SGP</math>
# ''Открытым ключом'' является пара <math>({\hat G},t)</math>. ''Закрытым ключом'' является набор <math>~(S,G,P)</math>

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

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

# Боб представляет свое сообщение <math>m</math> в виде последовательностей двоичных символов длины <math>~k</math>
# Боб вычисляет вектор <math>~c^{\prime}=m{\hat G}</math>
# Боб генерирует случайный вектор длины <math>~n </math>, имеющий вес <math>~t</math> (в нем ровно <math>~t</math> единиц)<ref name="McEliece"/>
# Боб вычисляет шифротекст как <math>~c = c^{\prime} + z</math> и передает его Алисе

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

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

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

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

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

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

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

== Пример работы ==

== Безопасность системы ==

В литературе описано достаточно большое количество атак на McElice. Некоторые атаки, называемые [[cтруктурная атака|структурными атаками]], основаны на получении закрытого ключа из открытого.
<ref name="attack1">
{{cite web
|author=R. Overbeck, D. Engelbert, A. Schmidt
|date=2006
|title=A Summary of McEliece-Type Cryptosystems and their Security
|url=http://eprint.iacr.org/
}}{{ref-en}}</ref>
Другие атаки направлены на получения исходного текста сообщения из шифрованного сообщения. Большинство из них основаны на декодировании множества данных (ISD {{ref-en}}) или на [[парадокс дней рождения|алгоритме Дня Рождения]], их обобщениях и улучшениях. Существуют такие атаки, как, например, итерационное декодирование
<ref name="iteration">
{{cite journal
|authors=M. P. C. Fossorier, K. Kobara, H. Imai
|date=2007
|title=Modeling Bit Flipping Decoding Based on Nonorthodogonal Check Sums With Application to Iterative Decoding Attack of McEliece Cryptosystem.
|journal=IEEE Transactions on Information Theory
|pages=402-211
|lan = en
}}{{ref-en}}</ref>
и статическое декодирование, но они не являются успешными. Атака ISD оказалась наименее сложной. В последние годы было описано нескольно алгоритмов и их улучшения. Наиболее важные перечислены в таблице вместе с их двоичным показателем затрат для декодирования (1024, 524, 50) кода Гоппа (стандартные параметры для McEliece<ref name="McEliece"></ref>). Для этих алгоритом известны их предельные показатели.
<ref name="limit">
{{cite journal
|authors=C. Peters, D. J. Bernstein, T. Lange, H. van Tilborg
|date=2009
|title=Explicit Bounds for Generic Decoding Algortithms for Code-based Cryptography.
|lan = en
}}{{ref-en}}</ref>

{|border="1"
!Год||Алгоритм||Сложность (<math>log_2</math>)
|-
|1986||Адамс-Мейер||80.7
|-
|1988||Ли-Брикелл||70.89
|-
|1989||Штерн||66.21
|-
|1994||Кантеаут-Шабанн||65.5
|-
|1998||Кантеаут-Шабант||64.1
|-
|2008||Бернштейн-Ланг-Петерс||60.4
|-
|2009||Финиаз-Сендреир||59.9
|-
|}

== Недостатки ==

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

{|border="1" width = "100%"
|+Безопасность McEliece в зависимости от параметров
!Степень защиты||Параметры <math>(n, k, t)</math>,кол-во ошибок ||Размер открытого ключа в Кбит || Размер секретного ключа <math>({\hat G},P,S)</math> в Кбит
|-
|Краткосрочная (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)
|-
|}

== Примечания ==
{{примечания}}


== Литература ==
== Литература ==
Строка 23: Строка 181:
* Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes and Paul C. van Oorschot, Handbook of Applied Cryptography.
* 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.
* Anne Canteaut and Nicolas Sendrier, Cryptanalysis of the Original McEliece Cryptosystem.
* {{cite journal
* R. J. McEliece (January and February 1978). "A Public-Key Cryptosystem Based On Algebraic Coding Theory".
|ref={{harvid|R. J. McEliece|1978}}
|url=http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
|author=R. J. McEliece
|bibcode=1978DSNPR..44..114M
|title=A Public-Key Cryptosystem Based On Algebraic Coding Theory
|journal=DSN Progress Report
|volume=42-44
|pages=114
|date=January and February 1978
|accessdate = 21 February 2009
}}


{{Crypto-stub}}
{{Crypto-stub}}
Строка 30: Строка 199:


[[en:McEliece cryptosystem]]
[[en:McEliece cryptosystem]]
[[fr:Cryptosystème de McEliece]]
[[fr:Cryptosysteme de McEliece]]
[[ko:매켈리스 암호체계]]
[[ko:???? ????]]
[[nl:McEliece-cryptosysteem]]
[[nl:McEliece-cryptosysteem]]
[[pl:Algorytm McEliece'a]]
[[pl:Algorytm McEliece'a]]

Версия от 18:41, 8 ноября 2011

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

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

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

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

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

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

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

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

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

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

Все пользователи в системе совместно используют параметры безопасности:

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

  1. Алиса выбирает двоичный -линейный код исправляющий ошибок. Затем для кода считается производящая матрица
  2. Для того, чтобы исходный код было сложно восстановить, Алиса генерирует случайную невырожденную матрицу
  3. Алиса генерирует случайную матрицу перестановки
  4. Алиса вычисляет мартрицу
  5. Открытым ключом является пара . Закрытым ключом является набор

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

Пусть Боб хочет передать сообщение Алисе, чей открытый ключ .

  1. Боб представляет свое сообщение в виде последовательностей двоичных символов длины
  2. Боб вычисляет вектор
  3. Боб генерирует случайный вектор длины , имеющий вес (в нем ровно единиц)[1]
  4. Боб вычисляет шифротекст как и передает его Алисе

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

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

  1. Алиса вычисляет обратную матрицу:
  2. Алиса вычисляет
  3. Алиса использует алгоритм дешифрования для кода , чтобы получить из
  4. Алиса вычисляет


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

Покажем, что выполняется главное свойство криптосистемы, т.е что

Боб посылает . Алиса вычисляет . Поскольку  — матрица перестановки, то вес не более, чем .

Код Гоппа исправляет до ошибок. Расстояние Хемминга . Поэтому Алиса получает верное сообщение . После этого Алиса вычисляет исходное сообщение .


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

Безопасность системы

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

Год Алгоритм Сложность ()
1986 Адамс-Мейер 80.7
1988 Ли-Брикелл 70.89
1989 Штерн 66.21
1994 Кантеаут-Шабанн 65.5
1998 Кантеаут-Шабант 64.1
2008 Бернштейн-Ланг-Петерс 60.4
2009 Финиаз-Сендреир 59.9

Недостатки

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

  • Размер открытого ключа слишком большой. При использовании кодов Гоппы с параметрами, предложенными Мак-Элисом, открытый ключ составляет бит, что вызывает сложности в реализации. При других параметрах ключа:
Безопасность McEliece в зависимости от параметров
Степень защиты Параметры ,кол-во ошибок Размер открытого ключа в Кбит Размер секретного ключа в Кбит
Краткосрочная (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. McElice 1978)
  2. ↑ H. Dinh, C. Moore, A. Russell (17 August 2010). "The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks". arXiv:1008.2390 [cs.CR]. {{cite arXiv}}: Неизвестный параметр |lang= игнорируется (справка)Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  3. ↑ E. Berlekamp, R. McEliece, H. van Tilborg (1978). "On Inherent Intractability of Certain Coding Problems" (англ.). 24(3): 384–386. {{cite journal}}: Cite journal требует |journal= (справка)Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  4. ↑ R. Niebuhr, M. Meziani, S. Bulygin, J. Buchmann. "Selecting Parameters for Secure McEliece-based Cryptosystems" (PDF) (англ.). {{cite journal}}: Cite journal требует |journal= (справка)Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  5. ↑ Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 August 2008). "Attacking and defending the McEliece cryptosystem". Proc. 2nd International Workshop on Post-Quantum Cryptography. Lecture Notes In Computer Science. 5299: 31—46. doi:10.1007/978-3-540-88403-3_3. {{cite journal}}: Неизвестный параметр |lan= игнорируется (справка)
  6. ↑ S. Heyse. Code-based cryptography: implementing the McEliece Scheme on Reconfigurable hardware (31 мая 2009). (англ.)
  7. ↑ R. Overbeck, D. Engelbert, A. Schmidt. A Summary of McEliece-Type Cryptosystems and their Security (2006). (англ.)
  8. ↑ "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. 2007. {{cite journal}}: Источник использует устаревший параметр |authors= (справка); Неизвестный параметр |lan= игнорируется (справка) (англ.)
  9. ↑ "Explicit Bounds for Generic Decoding Algortithms for Code-based Cryptography". 2009. {{cite journal}}: Cite journal требует |journal= (справка); Источник использует устаревший параметр |authors= (справка); Неизвестный параметр |lan= игнорируется (справка) (англ.)

Литература

  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке C = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз.

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=McEliece&oldid=39084655