Криптосистема Нидеррайтера

Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером^[1]. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.

Используемый в криптосистеме Нидеррайтера алгоритм основан на сложности декодирования полных линейных кодов.

Несмотря на то, что данная криптосистема была взломана, некоторые её модификации остаются криптостойкими^[2]

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

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

1. Алиса выбирает ${\displaystyle (n,k)}$ код ${\displaystyle C}$ над полем Галуа ${\displaystyle GF(q)}$, исправляющий ${\displaystyle t}$ ошибок. Этот код должен обладать эффективным алгоритмом декодирования^[3].
2. Алиса генерирует ${\displaystyle (n-k)\times n}$ проверочную матрицу ${\displaystyle H}$ кода ${\displaystyle C}$.
3. Алиса выбирает случайную ${\displaystyle (n-k)\times (n-k)}$ невырожденную матрицу ${\displaystyle S}$ над полем ${\displaystyle GF(q)}$ и некоторую ${\displaystyle n\times n}$ матрицу перестановки ${\displaystyle P}$^[3].
4. Алиса вычисляет ${\displaystyle (n-k)\times n}$ матрицу ${\displaystyle H_{pub}=SHP}$
5. Открытым ключом Алисы является пара ${\displaystyle (H_{pub},t)}$. Закрытым ключом является набор ${\displaystyle (S^{-1},H,P^{-1})}$.

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

В данном случае сообщения — это все ${\displaystyle n-}$векторы с координатами из поля ${\displaystyle GF(q)}$ с весом, не превосходящим ${\displaystyle t}$. Таким образом, сообщениями являются все возможные ошибки, которые выбранный код в состоянии исправить^[2].
Предположим, что Боб хочет отправить сообщение Алисе, чей открытый ключ ${\displaystyle (H_{pub},t)}$.

1. Боб представляет своё сообщение в виде двоичной последовательности ${\displaystyle m}$ длины ${\displaystyle n}$, имеющей вес, не превосходящий ${\displaystyle t}$.
2. Боб вычисляет шифротекст по формуле: ${\displaystyle c=mH_{pub}^{T}}$. Таким образом, шифротекстом в криптосистеме Нидеррайтера является зашумленный синдром шифруемого вектора ошибки^[2].

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

После получения сообщения ${\displaystyle c}$, Алиса выполняет следующие действия:

1. Алиса вычисляет ${\displaystyle s=c{(S^{T})}^{-1}=mP^{T}H^{T}S^{T}(S^{T})^{-1}=(mP^{T})H^{T}={\hat {m}}H^{T}}$. Заметим, что, так как ${\displaystyle P}$ — матрица перестановки, вес ${\displaystyle {\hat {m}}=(mP^{T})}$ совпадает с весом ${\displaystyle m}$ и не превосходит ${\displaystyle t}$, и потому алгоритм декодирования для ${\displaystyle C}$ может найти вектор ошибки, соответствующий синдрому ${\displaystyle s}$^[3].
2. Алиса использует алгоритм быстрого декодирования для кода ${\displaystyle C}$, чтобы найти ${\displaystyle {\hat {m}}}$^[3].
3. Алиса вычисляет сообщение ${\displaystyle {\hat {m}}P^{-1}=mPP^{-1}=m}$.

Оригинальная криптосистема и её модификации

В оригинальной криптосистеме Нидеррайтер предлагал использовать коды Рида-Соломона и не использовал матрицу перестановки ${\displaystyle P}$. Однако такая система оказалась нестойкой и была взломана Сидельниковым и Шестаковым в 1992 году^[4]. Авторы показали, что возможно угадать структуру закрытого ключа по открытому и подобрать такие матрицы ${\displaystyle {\hat {H}}}$ и ${\displaystyle {\hat {S}}}$, что ${\displaystyle H_{pub}={\hat {S}}{\hat {H}}}$. После этого для повышения криптостойкости системы было предложено использовать матрицу перестановки ${\displaystyle P}$. Кроме того, появились различные модификации системы, например:

• использующие различные метрики, отличные от классической хэмминговой, например, ранговую^[5]: примером этого является модифицированная система GPT^[3]
• использующие коды со специфическими свойствами. Так, модификации, основанные на кодах Гоппы, все ещё остаются криптостойкими^[2].

Преимущества и недостатки системы

Преимущества

• В отличие от McEliece, в криптосистеме Нидеррайтера не используются случайные параметры. Таким образом, результат шифрования одного и того же текста будет одинаковым. Этот факт позволяет использовать именно систему Нидеррайтера, а не McEliece, для создания электронно-цифровой подписи.
• Размер открытого ключа в криптосистеме Нидеррайтера в ${\displaystyle {\frac {n}{n-k}}}$ раз меньше, чем в McEliece^[6].
• По сравнению с RSA, скорость шифрования выше приблизительно в 50 раз, а дешифрования — в 100 раз^[6].

Недостатки

• Для шифрования произвольного сообщения необходим алгоритм перевода в ${\displaystyle q}$-арный вектор длиной ${\displaystyle n}$ веса не более ${\displaystyle t}$.
• Размер ключей больше, чем в классических криптосистемах с открытым ключом (RSA, Схема Эль-Гамаля, ГОСТ Р 34.10-2012).
• Размер шифротекста намного больше, чем размер шифруемого сообщения (если сообщение размера ${\displaystyle t}$ переводится в вектор длиной ${\displaystyle n}$ и шифруется, то получается шифротекст размером ${\displaystyle n-k}$, что не менее, чем в 2 раза превосходит ${\displaystyle t}$).

Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостатки^[6].

	McEliece n=1024, k=524, t=101 бинарный код	Криптосистема Нидеррайтера n=1024, k=524, t=101 бинарный код	RSA 1024-битные модули e=17
Размер открытого ключа в байтах	67072	32750	256
Количество бит полезной информации	512	276	1024
Число бинарных операций для шифрования	514	50	2402
Число бинарных операций для расшифровывания	5140	7863	738112

Эквивалентность криптостойкости системы Нидеррайтера и системы McEliece

Как показано в оригинальной статье о системе Сидельникова^[7], атака на систему Нидеррайтера может быть полиномиально сведена к атаке на систему McEliece и обратно.

Пусть известен синдром ${\displaystyle c=eD}$. Тогда можно вычислить вектор ${\displaystyle b=aE+e}$ с некоторым ${\displaystyle a}$ таким, что ${\displaystyle c=bD}$. Вектор ${\displaystyle b}$ будет рассматриваться как шифротекст в системе McEliece. Если найдена криптографическая атака со сложностью ${\displaystyle T}$ для системы McEliece, то есть известен алгоритм вычисления вектора ${\displaystyle a}$, который является секретной информацией в этой системе, то вектор ${\displaystyle e}$, являющийся секретом для системы Нидеррайтера, можно представить в виде ${\displaystyle e=aE+b}$. Таким образом, сложность определения ${\displaystyle e}$ совпадает со сложностью определения ${\displaystyle a}$.

Если же известна криптоатака со сложностью ${\displaystyle T}$ для системы Нидеррайтера, то возможно, используя в качестве шифротекста вектор ${\displaystyle (aE+e)D^{T}=eD^{T}}$, вычислить векторы ${\displaystyle e}$ и ${\displaystyle a}$.

Построение цифровой подписи

В 2001 году Николя Куртуа, Мэттью Финиаз и Николя Сандриер показали^[8], что криптосистема Нидеррайтера может быть использована для создания электронной подписи.

Подпись сообщения

Пусть ${\displaystyle H_{pub}}$ — открытый ключ криптосистемы Нидеррайтера, использующей ${\displaystyle (n,k,d)}$-линейный код. Для подписи документа ${\displaystyle D}$ необходимо:

1. Выбрать хеш-функцию ${\displaystyle h()}$, дающей ${\displaystyle n-k}$ символов на выходе. Таким образом, результат данной хеш-функции можно представить в виде синдрома и попытаться декодировать;
2. Вычислить хеш ${\displaystyle s=h(D)}$;
3. Для каждого ${\displaystyle i=0,1,2,...}$ вычислить ${\displaystyle s_{i}=h(s|i)}$;
4. Найти наименьший номер ${\displaystyle i_{min}}$ такой, что синдром ${\displaystyle s_{i_{min}}}$ будет возможно декодировать. Пусть ${\displaystyle z}$ — результат декодирования синдрома ${\displaystyle s_{i_{min}}}$;
5. Подписью документа ${\displaystyle D}$ является пара ${\displaystyle (z,i_{min})}$.

Проверка подписи

1. Вычислить ${\displaystyle s_{1}=zH_{pub}^{T}}$;
2. Вычислить ${\displaystyle s_{2}=h(h(D)|i_{min})}$;
3. Сравнить ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$: если они совпадают — подпись верна.

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

Пусть для кодирования был выбран ${\displaystyle (7,3)}$ код Рида-Соломона над полем Галуа ${\displaystyle GF(2^{3})}$, построенным по модулю неприводимого многочлена ${\displaystyle x^{3}+x+1}$, с порождающим многочленом ${\displaystyle g(x)=(x-1)(x-{\alpha })(x-{\alpha }^{2})(x-{\alpha }^{3})=(x-1)(x-2)(x-4)(x-3)=x^{4}+4x^{3}+7x^{2}+7x+5.}$

Тогда, порождающая матрица кода: ${\displaystyle G={\begin{pmatrix}1&4&7&7&5&0&0\\0&1&4&7&7&5&0\\0&0&1&4&7&7&5\end{pmatrix}}}$

Проверочная матрица кода: ${\displaystyle H={\begin{pmatrix}1&1&1&1&1&1&1\\1&2&4&3&6&7&5\\1&4&6&5&2&3&7\\1&3&5&4&7&2&6\end{pmatrix}}}$

Заметим, что расстояние данного кода ${\displaystyle d=n-k+1=5}$, то есть число исправляемых ошибок ${\displaystyle t=(d-1)/2=2}$.

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

Пусть выбрана матрица ${\displaystyle S={\begin{pmatrix}4&1&3&5\\7&1&5&2\\2&6&5&4\\1&7&2&1\end{pmatrix}}}$ . Тогда обратная к ней матрица ${\displaystyle S^{-1}={\begin{pmatrix}1&5&2&7\\7&5&0&7\\4&4&1&5\\1&0&0&4\end{pmatrix}}}$

Пусть выбрана матрица перестановки ${\displaystyle P={\begin{pmatrix}0&1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\1&0&0&0&0&0&0\\0&0&0&0&0&0&1\\0&0&1&0&0&0&0\\0&0&0&0&0&1&0\\\end{pmatrix}}}$

В этом случае открытым ключом системы будет матрица: ${\displaystyle H_{pub}=SHP={\begin{pmatrix}1&3&7&5&6&0&2\\0&1&0&1&1&3&5\\2&5&1&0&6&2&0\\6&5&6&4&2&4&6\end{pmatrix}}}$

Шифрование

Пусть выбранное сообщение было представлено в виде вектора ${\displaystyle m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}}$ веса 2.

Зашифрованное сообщение: ${\displaystyle M=mH_{pub}^{T}={\begin{pmatrix}7&2&7&7\end{pmatrix}}}$

Расшифровывание

Принятый вектор ${\displaystyle M={\begin{pmatrix}7&2&7&7\end{pmatrix}}}$

Для него вычислим декодируемый синдром ${\displaystyle s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}}$

Используя алгоритм декодирования кода Рида-Соломона, декодируем ${\displaystyle s}$.

Получится вектор ${\displaystyle {\hat {m}}={\begin{pmatrix}2&0&0&0&0&0&5\end{pmatrix}}}$

После чего вычислим исходный вектор ${\displaystyle m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}}$

См. также

• McEliece
• Криптосистема Сидельникова

Примечания

1. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory (англ.) // Problems of Control and Information Theory — 1986. — Vol. 15, Iss. 2. — P. 159—166.
2. Самохина М. А. Модификации криптосистемы Нидеррайтера, их стойкость и практические применения // Труды МФТИ — М.: 2009. — Т. 1, вып. 2. — С. 121—127. — ISSN 2072-6759
3. Khan E., Gabidulin E., Honary B., Ahmed H. Modified Niederreiter type of GPT cryptosystem based on reducible rank codes (англ.) // Designs, Codes and Cryptography — Springer US, Springer Science+Business Media, 2014. — Vol. 70, Iss. 1. — P. 231—239. — ISSN 0925-1022; 1573-7586 — doi:10.1007/S10623-012-9757-4
4. Сидельников В. М., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискретная математика — 1992. — Т. 4, вып. 3. — С. 57—63. — ISSN 2305-3143; 0234-0860
5. Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Теория информации и теория кодирования — 1985. — Т. 21, вып. 1. — С. 3—16.
6. 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
7. Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида–Маллера // Дискретная математика — 1994. — Т. 4, вып. 3. — С. 191—207. — ISSN 2305-3143; 0234-0860
8. Courtois N., Finiasz M., Sendrier N. How to Achieve a McEliece-Based Digital Signature Scheme (англ.) // Advances in Cryptology — ASIACRYPT 2001: 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings / C. Boyd — London: Springer Science+Business Media, 2001. — P. 157—174. — (Lecture Notes in Computer Science; Vol. 2248) — ISBN 978-3-540-42987-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-45682-1

Литература

• Wieschebrink C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes (англ.) // Post-Quantum Cryptography: Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings / N. Sendrier — Berlin: Springer Berlin Heidelberg, 2010. — P. 61—72. — (Lecture Notes in Computer Science; Vol. 6061) — ISBN 978-3-642-12928-5 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-642-12929-2
• Соловьева Ф. И., Лось А. В., Могильных И. Ю. II Криптология // Сборник задач по теории кодирования, криптологии и сжатию данных — Новосибирск: НГУ, 2013. — С. 41—49. — 100 с. — ISBN 978-5-4437-0184-4
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.