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

Генерация ключа: фиксируем k, n, t.

Каждый участникделает следующее.

1.Выбрать проверочную матрицу кода H размера (n-k) × n для (n, k)-линейного кода, исправляющего t ошибок, для которого известен эффективный алгоритм декодирования (например, код Гоппы).

2.Выбрать случайную невырожденную матрицу S размера

(n-k) × (n-k).

3.Выбрать случайную матрицу перестановки P размера n ×

n.

4.Выдать как публичный ключ t и H’ = SHP; секретный ключ

— (S, H,P).

Алгоритмы шифрования -дешифрования

Алгоритмшифрования:

(даны t, H’, F(x) и сообщение m).

1.Представитьсообщение как F(m) строкудлины n веса от 0 до t.

2.Зашифровать c = F(m.)H ′T

Алгоритмдекодирования
(даны c и ключ (S, H, P)).
1.	Вычислить c′ = cS−1	.
2.	Декодироватьто, что получилось,алгоритмом

декодирования кода; получитсяe’ . Проверить,

что вес e’ < t	m	=	F	−1	(e P	−1	)
3. Вычислить					′			.

Сообщение передается не информационным блоком кодового слова, а вектором ошибок.Криптограммаже получается в виде синдрома – произведения проверочнойматрицына вектор ошибок.

Выводы

•Стойкость КС Мак-Элис основывается на сложности переборного алгоритма декодирования линейного кода. Для криптоанализа можно применить квантовый компьютер (алгоритм Гровера). Это позволит уменьшить объем

вычислений вN раз. Однако при соответствующем выборе параметров кода, объем вычислений все равно останется нереализуемо большим, поэтому КС Мак-Элис остается

стойкой и по отношению к квантовому компьютеру.

•Доказано, что схема Ниддерайтера по стойкости эквивалентна КС Мак-Элис.

•Эти схемы легли в основу новых алгоритмов обмена ключами (методов инкапсуляции ключей) для постквантовых гибридных систем шифрования.

31