02-07-2023
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером[1]. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.
Используемый в криптосистеме Нидеррайтера алгоритм основан на сложности декодирования полных линейных кодов.
Несмотря на то, что данная криптосистема была взломана, некоторые её модификации остаются криптостойкими[2]
В данном случае сообщения — это все векторы с координатами из поля с весом, не превосходящим . Таким образом, сообщениями являются все возможные ошибки, которые выбранный код в состоянии исправить[2].
Предположим, что Боб хочет отправить сообщение Алисе, чей открытый ключ .
После получения сообщения , Алиса выполняет следующие действия:
В оригинальной криптосистеме Нидеррайтер предлагал использовать коды Рида-Соломона и не использовал матрицу перестановки . Однако такая система она оказалась нестойкой и была взломана Сидельниковым и Шестаковым в 1992 году[4]. Авторы показали, что возможно угадать структуру закрытого ключа по открытому и подобрать такие матрицы и , что . После этого для повышения криптостойкости системы было предложено использовать матрицу перестановки . Кроме того, появились различные модификации системы, например:
Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостатки[6].
McEliece
|
Криптосистема Нидеррайтера
|
RSA
|
|
---|---|---|---|
Размер открытого ключа
|
67072 | 32750 | 256 |
Количество бит
|
512 | 276 | 1024 |
Число бинарных операций
|
514 | 50 | 2402 |
Число бинарных операций
|
5140 | 7863 | 738112 |
Как показано в оригинальной статье о системе Сидельникова[7], атака на систему Нидеррайтера может быть полиномиально сведена к атаке на систему McEliece и обратно.
Пусть известен синдром . Тогда можно вычислить вектор с некоторым таким, что . Вектор будет рассматриваться как шифротекст в системе McEliece. Если найдена криптографическая атака со сложностью для системы McEliece, то есть известен алгоритм вычисления вектора , который является секретной информацией в этой системе, то вектор , являющийся секретом для системы Нидеррайтера, можно представить в виде . Таким образом, сложность определения совпадает со сложностью определения .
Если же известна криптоатака со сложностью для системы Нидеррайтера, то возможно, используя в качестве шифротекста вектор , вычислить векторы и .
В 2001 году Николя Куртуа, Мэттью Финиаз и Николя Сандриер показали[8], что криптосистема Нидеррайтера может быть использована для создания электронной подписи.
Пусть — открытый ключ криптосистемы Нидеррайтера, использующей -линейный код. Для подписи документа необходимо:
Пусть для кодирования был выбран код Рида-Соломона над полем Галуа , построенным по модулю неприводимого многочлена , с порождающим многочленом
Тогда, порождающая матрица кода:
Проверочная матрица кода:
Заметим, что расстояние данного кода , то есть число исправляемых ошибок .
Пусть выбрана матрица . Тогда обратная к ней матрица
Пусть выбрана матрица перестановки
В этом случае открытым ключом системы будет матрица:
Пусть выбранное сообщение было представлено в виде вектора веса 2.
Зашифрованное сообщение:
Принятый вектор
Для него вычислим декодируемый синдром
Используя алгоритм декодирования кода Рида-Соломона, декодируем .
Получится вектор
После чего вычислим исходный вектор