Криптосистема Нидеррайтера: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Строка 29: | Строка 29: | ||
== Преимущества и недостатки системы == |
== Преимущества и недостатки системы == |
||
Преимущества |
===Преимущества=== |
||
⚫ | * В отличие от McEliece, в криптосистеме Нидеррайтера не используются случайные параметры. Таким образом, результат шифрования одного и того же текста будет одинаковым. Этот факт позволяет использовать именно систему Нидеррайтера, а не McEliece, для создания [[Электронная подпись|электронно-цифровой подписи]]. |
||
#скорость выше, чем у RSA; |
|||
* Размер открытого ключа в криптосистеме Нидеррайтера в <math>\frac {n-k} {n}</math> раз меньше, чем в McEliece<ref name="neiderrcrypto">{{статья |автор=Canteaut A., Sendrier N. |заглавие=Cryptanalysis of the Original McEliece |
|||
⚫ | |||
Cryptosystem |ссылка=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Sendrier98.pdf |издание=Advances in Cryptology — ASIACRYPT’98 |тип=сборник |год=1998 |страницы=187—199 |isbn=978-3-540-65109-3}}</ref>. |
|||
* По сравнению с [[RSA]], скорость шифрования выше приблизительно в 50 раз, а дешифрования - в 100 раз<ref name=neiderrcrypto/>. |
|||
Недостатки |
===Недостатки=== |
||
* Для шифрования произвольного сообщения необходим алгоритм перевода в <math>~q</math>-арный вектор длиной <math>~n</math> веса не более <math>~t</math>. |
|||
* Размер ключей больше, чем в классических криптосистемах с открытым ключом ([[RSA]], [[Схема Эль-Гамаля]], [[ГОСТ_Р_34.10-2012]]). |
|||
* Размер шифротекста намного больше, чем размер шифруемого сообщения (если сообщение размера <math>~t</math> переводится в вектор длиной <math>~n</math> и шифруется, то получается шифротекст размером <math>n-k</math>, что не менее, чем в 2 раза превосходит <math>~t</math>). |
|||
Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостатки<ref name="neiderrcrypto"/>. |
|||
{| class="wikitable" style="text-align:center" |
|||
! |
|||
!align="center" |McEliece |
|||
:n=1024, k=524, t=101 |
|||
:бинарный код |
|||
!align="center" |Криптосистема Нидеррайтера |
|||
:n=1024, k=524, t=101 |
|||
:бинарный код |
|||
!align="center" |RSA |
|||
:1024-битные модули |
|||
:e=17 |
|||
|- |
|||
!Размер открытого ключа |
|||
:в байтах |
|||
|67072 |
|||
|32750 |
|||
|256 |
|||
|- |
|||
!Количество бит |
|||
:полезной информации |
|||
|512 |
|||
|276 |
|||
|1024 |
|||
|- |
|||
!Число бинарных операций |
|||
:для шифрования |
|||
|514 |
|||
|50 |
|||
|2402 |
|||
|- |
|||
!Число бинарных операций |
|||
:для расшифрования |
|||
|5140 |
|||
|7863 |
|||
|738112 |
|||
|} |
|||
== Эквивалентность криптостойкости системы Нидеррайтера и системы McEliece == |
== Эквивалентность криптостойкости системы Нидеррайтера и системы McEliece == |
Версия от 22:15, 24 ноября 2015
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером. В отличие от криптосистемы McEliece в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи.
Алгоритм работы
Генерация ключа
- Алиса выбирает код над полем Галуа , исправляющий ошибок. Этот код должен обладать эффективным алгоритмом декодирования.
- Алиса генерирует проверочную матрицу кода .
- Алиса выбирает случайную невырожденную матрицу над полем и некоторую матрицу перестановки .
- Алиса вычисляет матрицу
- Открытым ключом Алисы является пара . Закрытым ключом является набор .
Шифрование сообщения
В данном случае сообщения - это все векторы с координатами из поля с весом, не превосходящим . Таким образом, сообщениями являются все возможные ошибки, которые выбранный код в состоянии исправить.
Предположим, что Боб хочет отправить сообщение Алисе, чей открытый ключ .
- Боб представляет своё сообщение в виде двоичной последовательности длины , имеющей вес .
- Боб вычисляет шифротекст по формуле: . Таким образом, шифротекстом в криптосистеме Нидеррайтера является зашумленный синдром шифруемого вектора ошибки.
Расшифрование сообщения
После получения сообщения , Алиса выполняет следующие действия:
- Алиса вычисляет . Заметим, что, так как P - матрица перестановки, вес совпадает с весом и не превосходит t, и потому алгоритм декодирования для может найти вектор ошибки, соответствующий синдрому .
- Алиса использует алгоритм быстрого декодирования для кода , чтобы найти .
- Алиса вычисляет сообщение .
Оригинальная криптосистема и ее модификации
В оригинальной криптосистеме Нидеррайтер предлагал использовать коды Рида-Соломона и не использовал матрицу перестановки . Однако такая система она оказалась нестойкой и была взломана Сидельниковым и Шестаковым в 1992 году[1]. Авторы показали, что возможно угадать структуру закрытого ключа по открытому и подобрать такие матрицы и , что . После этого для повышения криптостойкости системы было предложено использовать матрицу перестановки . Кроме того, появились различные модификации системы, например:
- использующие различные метрики, отличные от классической хэмминговой, например, ранговую[2]: примером этого является модифицированная система GPT[3]
- использующие коды со специфическими свойствами. Так модификации, основанные на кодах Гоппы , все ещё остаются криптостойкими.
Преимущества и недостатки системы
Преимущества
- В отличие от McEliece, в криптосистеме Нидеррайтера не используются случайные параметры. Таким образом, результат шифрования одного и того же текста будет одинаковым. Этот факт позволяет использовать именно систему Нидеррайтера, а не McEliece, для создания электронно-цифровой подписи.
- Размер открытого ключа в криптосистеме Нидеррайтера в раз меньше, чем в McEliece[4].
- По сравнению с RSA, скорость шифрования выше приблизительно в 50 раз, а дешифрования - в 100 раз[4].
Недостатки
- Для шифрования произвольного сообщения необходим алгоритм перевода в -арный вектор длиной веса не более .
- Размер ключей больше, чем в классических криптосистемах с открытым ключом (RSA, Схема Эль-Гамаля, ГОСТ_Р_34.10-2012).
- Размер шифротекста намного больше, чем размер шифруемого сообщения (если сообщение размера переводится в вектор длиной и шифруется, то получается шифротекст размером , что не менее, чем в 2 раза превосходит ).
Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостатки[4].
McEliece
|
Криптосистема Нидеррайтера
|
RSA
| |
---|---|---|---|
Размер открытого ключа
|
67072 | 32750 | 256 |
Количество бит
|
512 | 276 | 1024 |
Число бинарных операций
|
514 | 50 | 2402 |
Число бинарных операций
|
5140 | 7863 | 738112 |
Эквивалентность криптостойкости системы Нидеррайтера и системы McEliece
Как показано в оригинальной статье о системе Сидельникова[5], атака на систему Нидеррайтера может быть полиномиально сведена к атаке на систему McEliece и обратно.
Пусть известен синдром . Тогда можно вычислить вектор с некоторым таким, что . Вектор будет рассматриваться как шифротекст в системе McEliece. Если найдена криптографическая атака со сложностью для системы McEliece, то есть известен алгоритм вычисления вектора , который является секретной информацией в этой системе, то вектор , являющийся секретом для системы Нидеррайтера, можно представить в виде . Таким образом, сложность определения совпадает со сложностью определения .
Если же известна криптоатака со сложностью для системы Нидеррайтера, то возможно, используя в качестве шифротекста вектор , вычислить векторы и .
Построение цифровой подписи
В 2001 году Николя Куртуа, Мэттью Финиаз и Николя Сандриер показали, что криптосистема Нидеррайтера может быть использована для создания электронной подписи.
Подпись сообщения
Пусть - открытый ключ криптосистемы Нидеррайтера, использующей -линейный код. Для подписи документа необходимо:
- Выбрать хеш-функцию , дающей символов на выходе. Таким образом, результат данной хеш-функции можно представить в виде синдрома и попытаться декодировать;
- Вычислить хеш ;
- Для каждого вычислить ;
- Найти наименьший номер такой, что синдром будет возможно декодировать. Пусть - результат декодирования синдрома ;
- Подписью документа является пара
Проверка подписи
- Вычислить ;
- Вычислить ;
- Сравнить и : если они совпадают - подпись верна.
Пример работы системы
Пусть для кодирования был выбран (7,3)-код Рида-Соломона над полем Галуа , построенного по модулю неприводимого многочлена , с порождающим многочленом
Порождающая матрица кода:
Проверочная матрица кода:
Заметим, что расстояние данного кода , т.е. число исправляемых ошибок .
Генерация ключей
Пусть выбрана матрица . Тогда обратная к ней матрица
Пусть выбрана матрица перестановки
В этом случае открытым ключом системы будет матрица:
Шифрование
Пусть выбранное сообщение было представлено в виде вектора веса 2.
Зашифрованное сообщение:
Расшифровывание
Принятый вектор
Для него вычислим декодируемый синдром
Используя алгоритм декодирования кода Рида-Соломона, декодируем .
Получится вектор
После чего вычислим исходный вектор
Примечания
- ↑ Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискретная математика : журнал. — 1992. — Т. 4, № 3. — С. 57—63. — ISSN 2305-3143.
- ↑ Габидулин Э.М. Теория кодов с максимальным ранговым расстоянием. — 1985. — Т. 21, № 1. — С. 3—16.
- ↑ Eraj Khan , Ernst Gabidulin, Bahram Honary, Hassan Ahmed. Modified Niederreiter type of GPT cryptosystem based on reducible rank codes // Designs, Codes and Cryptography : журнал. — 2014. — Т. 70, № 1. — ISSN 1573-7586.
- ↑ 1 2 3 Canteaut A., Sendrier N. [https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Sendrier98.pdf Cryptanalysis of the Original McEliece Cryptosystem] // Advances in Cryptology — ASIACRYPT’98 : сборник. — 1998. — С. 187—199. — ISBN 978-3-540-65109-3.
- ↑ Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида–Маллера // Дискретная математика : журнал. — 1994. — Т. 6, № 2. — С. 3—20. — ISSN 2305-3143.
Литература
Самохина М. А. Модификации криптосистемы Нидеррайтера, их стойкость и практические применения // Труды МФТИ : журнал. — М., 2009. — Т. 1, № 2. — С. 121—127. — ISSN 2072-6759.
Wieschebrink C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes (англ.) // Sendrier N. Post-Quantum Cryptography: Third International Workshop, PQCrypto 2010 : сборник. — Berlin: Springer, 2010. — May. — P. 61—72. — ISBN 978-3-642-12928-5. — ISSN 0302-9743.
Соловьёва Ф. И., Лось А. В., Могильных И. Ю. II Криптология // Сборник задач по теории кодирования, криптологии и сжатию данных. — Новосибирск, 2013. — С. 41—49. — 100 с. — 200 экз. — ISBN 978-5-4437-0184-4.