в криптографии с открытыми ключами.

Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению ? Более формально, дан набор значений Ml, M2, . . . , Mn и сумма S, вычислить значения b,, такие что

S = blM1 + b2M2 + . . . + b„M„

b; может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут.

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

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

Открытый текст 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0

Рюкзак 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20

Шифротекст 1+5+6+20=32 5+11+14=30 0=0 5+6=11

Рис. 19-1. Шифрование с рюкзаками

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

Сверхвозрастающие рюкзаки

Что такое легкая проблема рюкзака? Если перечень масс представляет собой сверхвозрастающую последовательность, то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов . Например, последовательность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} - нет.

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

Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес, 27, больше 18, поэтому 27 в рюкзак не кладется. вес, 13,меньше 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, получаем 5. Следующий вес, 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении. Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана, открытый текст, полученный из значения шифро-текста 70, был бы равен 110101 .

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

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

Создание открытого ключа из закрытого

Рассмотрим работу алгоритма, не углубляясь в теорию чисел : чтобы получить нормальную последовательность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52}, и умножим по модулю m все значения на число n. Значение модуля должно быть больше суммы всех чисел последов а-тельности, например, 105. Множитель должен быть взаимно простым числом с модулем, например, 31. Нормальной последовательностью рюкзака будет

2*31 mod 105 = 62

3*31 mod 105 = 93

6*31 mod 105 = 81

13*31 mod 105 = 88

27*31 mod 105 = 102

52*31 mod 105 = 37

Итого - {62,93,81,88,102,37}.

Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовател ь-ность рюкзака - открытым.

Шифрование

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

Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использующее предыдущую последовательность рюкзака, будет происходить следующим образом :

сообщение = 011000 110101 101110

011000 соответствует 93 + 81 = 174

110101 соответствует 62 + 93 + 88 + 37 = 280

101110 соответствует 62 + 81 + 88 + 102 = 333

Шифротекстом будет последовательность 174,280,333

Дешифрирование

Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую посл е-довательность, а также значения n и m, использованные для превращения ее в нормальную последовательность рюкзака. Для дешифрирования сообщения получатель должен сначала определить n-1, такое что n(n-1)=1 (mod m). Каждое значение щифротекста умножается на n-1 mod m, а затем разделяется с помощью закрытого ключа, чтобы получить значения открытого текста.

В нашем примере сверхвозрастающая последовательность - {2,3,6,13,27,52), m равно 105, а n - 31. Шифротекстом служит 174,280,333. В этом случае n-1 равно 61, поэтому значения шифротекста должны быть умножены на 61 mod 105.

174*61 mod 105 = 9 = 3 + 6, что соответствует 011000

280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101

333*61 mod 105 = 48 = 2 + 6 + 13 + 27, что соответствует 101110

Расшифрованным открытым текстом является 011000 110101 101110.

Практические реализации

Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовател ь-ность не является сверхвозрастающей . Реальные рюкзаки должны содержать не менее 250 элементов . Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами , а длина модуля должна быть от 100 до 200 битов . Для получения этих значений практические реализации используют генераторы случайной последовательности .

Вскрывать подобные рюкзаки при помощи грубой силы бесполезно . Если компьютер может проверять миллион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10 46 лет. Даже мил-

лион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую зве з-

Безопасность метода рюкзака

Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов . Сначала б1л раскрыт единственный бит открытого текста [725]. Затем Шамир показал, что в определенных обстоятельствах рюкзак может быть взломан [1415, 1416]. Б1ли и другие достижения - [1428, 38, 754, 516, 488] - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel) [1418, 1419, 1421] обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной . Точные доказательства выходят за рамки этой книги, но их хор о-ший обзор можно найти в [1233, 1244]. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II [492, 494].

Варианты рюкзака

После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны , как правило, с использованием одних и тех же криптографич е-ских методов, и их обломки были сметены со скоростного шоссе криптографии [260, 253, 269, 921, 15, 919, 920, 922, 366, 254, 263, 255]. Хороший обзор этих систем и их криптоанализ можно найти в [267, 479, 257, 268].

Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны . Криптосистема Lu-Lee [990, 13] была взломана в [20, 614, 873], ее модификация [507] также оказалась небезопасной [1620]. Вскрытия криптосистемы Goodman-McAuley приведены в [646, 647, 267, 268]. Криптосистема Pieprzyk [1246] была взломана аналогичным образом. Криптосистема Niemi [1169], основанная на модульных рюкзаках, взломана в [345, 788]. Новый, многостадийный рюкзак [747] пока еще не был взломан, но я не оптимистичен. Другим вариантом является [294].

Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest [356], несмотря на "специализированное вскрытие" [743] - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен [958]. Более того, учитывая легкость с которой пали все остальные варианты, д о-верять устоявшим пока вариантом, по видимому, неосторожно .

Патенты

Оригинальный алгоритм Меркла-Хеллмана запатентован в Соединенных Штатах [720] и в остальном мире (см. 18th). Public Key Partners (PKP) получила лицензию на патент вместе с другими патентами криптографии с открытыми ключами (см. раздел 25.5). Время действия патента США истечет 19 августа 1997 года.

Табл. 19-1.

Иностранные патенты на алгоритм рюкзака Меркла-Хеллмана