Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.5.5. Криптосистема с открытым ключом, основанная на «лазейке» в рюкзаке

Эта схема, известная также как схема Меркла-Хэллмана [15], основана на образовании вектора рюкзака, который не является быстровозрастающим. Следовательно, задача не является легкоразрешимой. При этом данная задача о рюкзаке обязательно включает лазейку, позволяющую разрешенным пользователям решить задачу.

Сначала образуем быстровозрастающий п-кортеж. Затем выберем простое число М, при котором имеет место следующее неравенство.

                                                                                                    (14.43)

Выберем также случайное число W (1<W<M) и сформируем W-1, удовлетворяющее следующему соотношению.

                                  WW-1 по модулю М = 1                                          (14.44)

Вектор а' и числа М, W и W-1 удерживаются скрытыми. Затем из элементов а' формируем а.

                                 ai= Waj’  по модулю М                                           (14.45)

Формирование а с использованием равенства (14.45) — это создание вектора рюкзака с лазейкой. Если нужно передать вектор х, то вначале х умножается на а, что дает число S, которое передается через общедоступный канал. С помощью равенства (14.45) S можно записать следующим образом.

                          S = ах =                     (14.46)

Разрешенный пользователь получает S и, используя равенство (14.44), превращает его в S.

=

                                                =                          (14.47)

Поскольку разрешенный пользователь знает засекреченный быстровозрастающий вектор а', для отыскания х он может использовать S'.



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.