Система шифрования методом укладки рюкзака. (Ранцевая система шифрования)

 

Классическая задача об укладке рюкзака формулируется следующим образом. Пусть имеется множество предметов с указанием их веса, некоторые представители которого укладываются в рюкзак. Зная вес наполненного рюкзака (без учета веса самого рюкзака), необходимо определить содержимое рюкзака.

Опишем задачу о рюкзаке с использованием вектора рюкзака и вектора данных. Вектор рюкзака представляет собой набор из n различных чисел (аналогично множеству различных предметов, укладываемых в рюкзак), т.е. . Вектор данных – множество двоичных символов, т.е. , где . Вес наполненного рюкзака есть сумма подмножества компонентов вектора рюкзака, определяемая как

.

Тогда задачу о рюкзаке можно сформулировать следующим образом: по заданному значению S и известном определить .

Пример 13.2.1. Пусть . Пусть . Требуется определить . Методом проб можно установить, что

.

Тогда . ð

В этом простом примере решение было найдено методом проб и ошибок, однако если в заданном множестве не 10, а 100 и более различных чисел, то задача может стать вычислительно неосуществимой. Следовательно, по заданному вектору нахождение S при известном осуществляется просто, как . Однако решение обратной задачи, т.е. нахождение по известному и заданному S представляет собой трудную в вычислительном плане задачу, и, значит, может рассматриваться как односторонняя функция.

Для организации схемы шифрования на основе этой задачи необходима не просто односторонняя функция, а функция с лазейкой, в качестве которой выступает быстровозрастающая последовательность компонентов вектора . Вектор будет быстровозрастающим, если для его компонентов выполняется соотношение

,

т.е. каждый компонент вектора больше суммы предшествующих ему компонентов. Тогда если является быстровозрастающим, то последний элемент , т.е. принимает значение единица, если , и – в противном случае. Все предшествующие элементы находятся согласно соотношению

(13.3)

где .

Пример 13.2.2. Пусть , а . Очевидно, что является быстровозрастающим. Тогда из (13.3) следует, что . ð

Из примера очевидным образом следует, что в случае наличия быстровозрастающего , т.е. лазейки, определение осуществляется достаточно просто, в противном же случае задача отыскания становится трудно осуществимой. Следовательно, в качестве части секретного ключа необходимо использовать быстровозрастающую последовательность и именно с учетом этого положения строить схему шифрования.

Данная схема шифрования, известная также как схема Меркла–Хэллмана, основана на образовании вектора , который не является быстровозрастающим. Следовательно, задача отыскания по при известном S не является легкоразрешимой. При этом схема обязательно должна содержать лазейку в виде быстровозрастающего вектора , который позволит разрешенным пользователям легко решить задачу.

Первоначально образуем быстро возрастающий вектор и выберем простое число P, при котором выполняется следующее неравенство

.

Затем случайным образом выберем число и вычислим , такое что

. (13.4)

Вектор и числа являются секретными. Затем из элементов сформируем вектор , компоненты которого определяются как

.

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

,

которое и передается по открытому каналу связи.

Санкционированный пользователь получает S и, используя соотношение (13.4), превращает его в вида

.

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

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

и число W, такое что , при котором . Пусть, например, , , так, что , которые и образуют секретный ключ пользователя.

Образовав секретный ключ, абонент A переходит к формированию общедоступного ключа, в качестве которого выступает вектор , содержащий «лазейку»:

,

так что

.

Предположим, что пользователь B собирается послать сообщение абоненту A. Если , то пользователь B создает следующее число

и передает его пользователю A. Последний преобразует его в по алгоритму

,

которое, в свою очередь, определяется как . Учитывая, что вектор является быстровозрастающим, на основании алгоритма (13.3) абонент A легко восстановит вектор .

Поскольку , то . Далее

,

следовательно, . Аналогично для :

,

то . Продолжая следовать алгоритму (13.3), получаем . Так что в итоге имеем .

Схем Меркла–Хэллмана в настоящее время считается взломанной, поэтому для реализации криптосистем с открытыми ключами используется алгоритм RSA.