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

В криптография, то Криптосистема Нидеррайтера это вариант Криптосистема Мак-Элиса разработан в 1986 г. Харальд Нидеррайтер.^[1] Он применяет ту же идею к матрица проверки на четность, ЧАС, линейного кода. Niederreiter эквивалентен Мак-Элису с точки зрения безопасности. Он использует синдром как зашифрованный текст, а сообщение представляет собой образец ошибки. Шифрование Niederreiter примерно в десять раз быстрее, чем шифрование McEliece. Нидеррайтер может быть использован для построения цифровой подписи схема.

Определение схемы

Особый случай первоначального предложения Нидеррайтера был нарушен^[2] но система безопасна при использовании с Двоичный код Goppa.

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

1. Алиса выбирает двоичный файл (п, k) -линейный код Гоппа, грамм, способный исправить т ошибки. Этот код обладает эффективным алгоритмом декодирования.
2. Алиса генерирует (п − k) × п матрица проверки на четность, ЧАС, для кода, грамм.
3. Алиса выбирает случайный (п − k) × (п − k) двоичный невырожденная матрица, S.
4. Алиса выбирает случайный п × п матрица перестановок, п.
5. Алиса вычисляет (п − k) × п матрица ЧАС^паб = SHP.
6. Открытый ключ Алисы (ЧАС^паб, т); ее закрытый ключ (S, ЧАС, п).

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

Предположим, Боб хочет отправить сообщение, м, Алисе, открытый ключ которой (ЧАС^паб, т):

1. Боб кодирует сообщение, м, как двоичную строку e^{м '} длины п и вес не более т.
2. Боб вычисляет зашифрованный текст как c = ЧАС^пабе^Т.

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

При получении c = ЧАС^пабм^Т от Боба Алиса выполняет следующее, чтобы получить сообщение, м.

1. Алиса вычисляет S⁻¹c = HPm^Т.
2. Алиса применяет расшифровка синдрома алгоритм для грамм восстановить Вечера^Т.
3. Алиса вычисляет сообщение, м, через м^Т = п⁻¹Вечера^Т.

Схема подписи

Куртуа, Финиас и Сендриер показали, как криптосистему Нидеррайтера можно использовать для получения схемы подписи.^[3]

1. Хеш документ, d, который будет подписан (с помощью публичного алгоритма хеширования).
2. Расшифруйте это хеш-значение, как если бы это был экземпляр зашифрованного текста.
3. Добавьте расшифрованное сообщение к документу в качестве подписи.

Затем проверка применяет к подписи общедоступную функцию шифрования и проверяет, совпадает ли она с хеш-значением документа. При использовании Niederreiter или фактически любой криптосистемы, основанной на кодах исправления ошибок, второй шаг в схеме подписи почти всегда терпит неудачу. Это связано с тем, что случайный синдром обычно соответствует модели ошибок с весом больше, чем т. Затем система определяет детерминированный способ настройки d пока не будет найден тот, который можно расшифровать.

Выбор параметров кода связан с вероятностью того, что случайный синдром поддается декодированию. Куртуа, Финиаз и Сендриер предлагают значения параметров п = 2¹⁶ и т = 9. Тогда вероятность расшифровать случайный синдром равна ${\displaystyle {\frac {1}{9!}}}$. Следовательно, декодируемый синдром обнаруживается после ожидаемого числа 9! попытки. Добавить счетчик, я, в исходный документ d, чтобы получить слегка измененный документ, d_я. Хеширование d_я дает синдром, который зависит от я. Позволять я бегать от 0 до я₀, с я₀ первое значение я для которого d_я декодируется. В этом случае расшифрованное сообщение - это слово, z, длины п и вес 9, такой что Гц^Т равно хэш-значению d_я0. Подпись будет z в сочетании со значением я₀ для подтверждения. Эта подпись прикреплена к оригиналу документа, d.

Рекомендации

• Хенк К. А. ван Тилборг. Основы криптологии, 11.4.

1. Х. Нидеррайтер (1986). «Криптосистемы ранцевого типа и алгебраическая теория кодирования». Проблемы теории управления и информации. Проблемы Управления и теории информации. 15: 159–166.
2. Сидельников В.М., Шестаков С.О. (1992). «О незащищенности криптосистем на основе обобщенных кодов Рида-Соломона». Дискретная математика и приложения. 2 (4): 439–444. Дои:10.1515 / dma.1992.2.4.439. S2CID  120779674.
3. Н. Куртуа; М. Финиаз; Н. Сендриер (2001). «Как создать схему цифровой подписи на основе Мак-Элиса». Достижения в криптологии - ASIACRYPT 2001. Конспект лекций по информатике. LNCS 2248: 157–174. Дои:10.1007/3-540-45682-1_10. ISBN  978-3-540-42987-6.

внешняя ссылка

• Атака и защита криптосистемы Мак-Элиса Дэниел Дж. Бернштейн и Таня Ланге и Кристиан Петерс