Алгоритмы на основе задачи об укладке ранца

Ранцевый алгоритм, разработанный Ральфом Мерклом и Мартином Хеллманом [713, 1074], стал первым алгоритмом шифрования с открытым ключом широкого назначения. Безопасность ранцевых алгоритмов опирается на известную математическую задачу об укладке ранца (рюкзака), относящуюся к числу NP-полных задач. Впоследствии было обнаружено, что этот алгоритм нестоек, однако его стоит изучить, чтобы продемонстрировать возможность применения NP-полной задачи в криптографии с открытым ключом.

Проблема укладки ранца формулируется просто. Дано множество предметов различного веса; спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений М₁, М₂,..., М_n и суммарное значение S, требуется вычислить значения S такие что:

S = b₁M₁+b₂M₂ +...+b_nM_n

Здесь b, может быть либо нулем, либо единицей. Значение b_i = 1 означает, что предмет кладут в рюкзак, a b_i = 0 - не кладут.

Пусть, например, веса предметов имеют значения 1, 5, 6, 11, 14 и 20. При этом вы можете упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24. Время, необходимое для решения этой проблемы, в общем случае возрастает как экспонен­циальная функция от количества предметов в куче.

В основе алгоритма, предложенного Мерклом и Хеллманом, лежит идея шифрования сообщения на основе решения серии задач укладки ранца. Предметы из кучи выбира­ются с помощью блока открытого текста, длина которого (в битах) равна количеству предметов в куче. При этом биты открытого текста соответствуют значениям b, a шифртекст является полученным суммарным весом. Пример текста, зашифрованного с помощью задача укладки ранца, показан на рис 19.1.

Суть в том, что на самом деле существуют две различные задачи укладки ранца; одна из них решается легко и характеризуется линейным ростом трудоемкости, а другая - как принято считать, нет. Легкий для укладки ранец можно превратить в трудный. Раз так, то можно применить в качестве открытого ключа трудный для укладки ранец, который легко использовать для шифрования, но невозможно - для расшифрования сообщений. А в качестве закрытого ключа применим легко разрешимый для укладки ранец, который предоставляет простой способ расшифрования сообщения. Тому, кто не знает закрытый ключ, придется попытаться решить трудную задачу укладки ранца.