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

В криптографии криптосистема Нидеррайтера является разновидностью криптосистемы МакЭлиса, разработанной в 1986 году Харальдом Нидеррайтером . Та же идея применяется к проверки четности матрице H линейного кода. Нидеррайтер эквивалентен МакЭлису с точки зрения безопасности. Он использует синдром в качестве зашифрованного текста, а сообщение представляет собой образец ошибки. Шифрование Нидеррайтера примерно в десять раз быстрее, чем шифрование МакЭлиса. Niederreiter можно использовать для построения схемы цифровой подписи .

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

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

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

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

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

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

1. Боб кодирует сообщение m как двоичную строку e ^м' длины n и веса не более t .
2. Боб вычисляет зашифрованный текст как c = H ^паб и ^Т .

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

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

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

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

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

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

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

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

Ссылки

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

Внешние ссылки

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