ВУЗ:
Составители:
150
значениям b), а шифротекст является полученной суммой. Пример
шифротекста, зашифрованного с помощью проблемы рюкзака.
Открытый
текст
111001 010110 000000 011000
Рюкзак
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
Рис. 13 Шифрование с рюкзаками
Фокус в том, что на самом деле существуют две различные проблемы
рюкзака, одна решается за линейное время, а другая, как считается, - нет.
Легкую проблему можно превратить в трудную. Открытый ключ представ-
ляет собой трудную проблему, которую легко использовать для шифрования,
но невозможно для дешифрирования сообщений. Закрытый ключ является
легкой проблемой, давая простой способ дешифрировать сообщения . Тому,
кто не знает закрытый ключ, придется попытаться решить трудную проблему
рюкзака .
Сверхвозрастающие рюкзаки
Что такое легкая проблема рюкзака? Если перечень масс представляет
собой сверхвозрастающую последовательность, то полученную проблему
рюкзака легко решить. Сверхвозрастающая последовательность - это
последовательность, в которой каждой член больше суммы всех предыдущих
членов . Например, последовательность {1,3,6,13,27,52} является
сверхвозрастающей, а {1,3,4,9, 15,25} - нет.
Решение сверхвозрастающего рюкзака найти легко. Возьмите
полный вес и сравните его с самым большим числом последовательности.
Если полный вес меньше, чем это число, то его не кладут в рюкзак. Если пол-
ный вес больше или равен этому числу, то оно кладется в рюкзак. Уменьшим
массу рюкзака на это значение и перейдем к следующему по величине числу
последовательности. Будем повторять, пока процесс не закончится. Если
полный вес уменьшится до нуля, то решение найдено. В противном случае
нет.
Например, пусть полный вес рюкзака - 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.
Страницы
- « первая
- ‹ предыдущая
- …
- 148
- 149
- 150
- 151
- 152
- …
- следующая ›
- последняя »
