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

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}$.

• В отличие от 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].

Пусть ${\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 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}}}$