Методы и средства криптографической защиты информации. Жданов О.Н - 151 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

151
Не сверхвозрастающие, или нормальные, рюкзаки представляют собой
трудную проблему - быстрого алгоритма для них не найдено. Единственным
известным способом определить, какие предметы кладутся в рюкзак,
является методическая проверка возможных решений, пока вы не наткнетесь
на правильное . Самый быстрый алгоритм, принимая во внимание различную
эвритсику, имеет экспоненциальную зависимость от числа возможных
предметов. Добавьте к последовательности весов еще один член, и найти
решение станет вдвое труднее. Это намного труднее сверхвозрастающего
рюкзака, где, если вы добавите один предмет к последовательности, поиск
решения увеличится на одну операцию.
Алгоритм Меркла-Хеллмана основан на этом свойстве. Закрытый ключ
является последовательностью весов проблемы сверхвозрастающего
рюкзака. Открытый ключ - это последовательность весов проблемы
нормального рюкзака с тем же решением. Меркл и Хеллман, используя
модульную арифметику, разработали способ преобразования проблемы
сверхвозрастающего рюкзака в проблему нормального рюкзака.
Создание открытого ключа из закрытого
Рассмотрим работу алгоритма, не углубляясь в теорию чисел: чтобы
получить нормальную последовательность рюкзака, возьмем
сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52},
и умножим по модулю т все значения на число п. Значение модуля должно
быть больше суммы всех чисел последовательности, например, 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

Страницы