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

Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 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].

Как показано в оригинальной статье о системе Сидельникова^[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
• Криптосистема Сидельникова

• 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.