Открытый текст 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 isn't.

Например, пусть полный вес рюкзака - 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.

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

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