Кодовые конструкции

Метод укладки (упаковки) рюкзака (ранца)

Реализацией задачи об укладке рюкзака является криптоалгоритм Мер-кле и Хелмана. Рассмотрим этот криптоалгоритм на примере. Пусть задан набор чисел

(а,,а₂,...а_п) = А.

Задачей является нахождение таких чисел а_|5 если это возможно, сумма которых равна числу к. В простейшем случае это число к указывает размер рюкзака, а каждое из чисел а. указывает размер предмета, который может быть упакован в рюкзак. Задачей является нахождение тако­го набора предметов, чтобы рюкзак был полностью заполнен.

В качестве примера возьмем число к=3231 и набор из 10 целых чисел а^...,

^аю^:

43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523.

Заметим, что число k получается при сложении только некоторых чи­сел а:

Рис. 5.28. Метод укладки рюкзака

3231 = 129+ 473 + 903 + 561 + 1165

Таким образом, сложив эти числа, мы нашли решение, то есть заполни­ли рюкзак. Ситуация наглядно проиллюстрирована на рис. 5.28.

В принципе решение всегда может быть найдено полным перебором подмножеств А и проверкой, какая из сумм равна числу к. В нашем случае это означает перебор 2¹⁰=1024 подмножеств (включая при этом и пустое множество). Это вполне осуществимо.

Но что будет, если существует несколько сотен чисел а/? В нашем примере п=10, чтобы не усложнять положение и расчеты. В реальных условиях при­мер будет иметь, скажем, 300 чисел а.. Суть здесь в том, что неизвестны алго­ритмы, имеющие существенно меньшую сложность по сравнению с полным перебором. Поиск правильного решения среди 2³⁰⁰ подмножеств не поддается обработке.

Алгоритм преобразований на основе кодовых конструкций с исправле­нием ошибок различаются по способам маскирования исходного кода. Наи­более известными являются криптоалгоритмы Мак-Элайса, использующие исправляющие ошибки коды Гоппы, Нидеррайгера, Крука, Габидулина и др.

Сравнительные характеристики некоторых известных двухключевых криптоалгоритмов приведены в табл. 5.2.

Таблица 5.2. Характеристики двухключевых криптоалгоритмов

Алгоритм	Длина ключа, бит	Примечание
RSA	до 1	Используется для шифрования и формирования ЭЦП
DHE (алгоритм Диффи-Хелмана в версии Эль-Гамаля)	до 4	Используется для шифрования
DSS	до 2	Используется для формирования ЭЦП

Дата добавления: 2014-01-05