Основы современной криптографии


Криптосистемы Меркля-Хеллмана и Хора-Ривеста


Криптосистемы Меркля-Хеллмана и Хора-Ривеста основаны на использовании односторонней функции, известной под названием "задача укладки рюкзака.

Пусть имеется n объектов, так что можно составить n-компонентный вектор f, так что i-й компонент f

представляет собой место, занимаемое i-м объектом. Имеется рюкзак общим объемом K.

Теперь задачу укладки рюкзака может быть сформулирована следующим образом: нам даны f и K, и требуется найти битовый вектор x, такой что fx=K. Доказано, что не существует эффективного алгоритма вычисления x по f

и K в общем случае. Таким образом, мы можем использовать вектор f

для шифрования n-битового сообщения x путем вычисления произведения K = fx.

Важно отметить, что выбор f является критическим. Например, предположим, что f выбирается в виде супервозрастающей последовательности. В этой ситуации для любого i

.

В этом случае при данных f и К

вычислить x очень просто. Мы проверим, является ли K

большим, чем последний элемент f, и если да, то мы делаем последний элемент x равным 1, вычитаем это значение из K и рекурсивно решаем меньшую проблему. Этот метод работает, поскольку когда K

больше последнего элемента f, даже если мы выберем x=(1 1 1 … 1 0), то произведение fx все равно будет слишком маленьким, благодаря тому, что последовательность супервозрастающая. Таким образом, мы должны выбирать 1 в последней позиции x.

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

Пользователь A получает свой открытый ключ следующим образом:

1.        Выбирает супервозрастающую последовательность f' примерно из 100 элементов;

2.        Выбирает случайное целое m, большее суммы элементов f';

3.        Выбирает другое случайное целое w, взаимно простое с m.




Начало  Назад  Вперед