Ранцевая криптосистема Меркла – Хеллмана

Ранцевая криптосистема Меркла -Хеллмана была одной из первых с открытым ключом криптосистем . Он был опубликован Ральфом Мерклем и Мартином Хеллманом в 1978 году. Полиномиальная атака по времени была опубликована Ади Шамиром в 1984 году. В результате криптосистема теперь считается небезопасной.

История

Концепция криптографии с открытым ключом была введена Уитфилдом Диффи и Мартином Хеллманом в 1976 году. В то время они предложили общую концепцию «односторонней функции с люком», функции, обратную для которой вычислительно невозможно вычислить без некоторой секретной «информации о люке»; но они еще не нашли практического примера такой функции. В течение следующих нескольких лет другие исследователи предложили несколько конкретных криптосистем с открытым ключом, таких как RSA в 1977 году и Меркл-Хеллман в 1978 году.

Описание

Меркла-Хеллмана — это криптосистема с открытым ключом, что означает, что используются два ключа: открытый ключ для шифрования и закрытый ключ для дешифрования. В его основе лежит задача о сумме подмножеств (частный случай задачи о рюкзаке ). Задача состоит в следующем: задан набор целых чисел $A$ и целое число $c$, найдите подмножество $A$ что в сумме равно $c$. В общем случае эта задача известна как NP-полная . Однако, если $A$ является супервозрастающим , что означает, что каждый элемент набора больше, чем сумма всех чисел в наборе, меньших его, проблема «легка» и разрешима за полиномиальное время с помощью простого жадного алгоритма .

В Меркле-Хеллмане расшифровка сообщения требует решения явно «сложной» задачи о рюкзаке. Закрытый ключ содержит супервозрастающий список чисел. $W$, а открытый ключ содержит несупервозрастающий список чисел $B$, что на самом деле является "замаскированной" версией $W$. Закрытый ключ также содержит некоторую информацию о «лазейке», которую можно использовать для решения задачи о твердом рюкзаке с помощью $B$ в простую задачу о рюкзаке, используя $W$.

В отличие от некоторых других криптосистем с открытым ключом, таких как RSA , два ключа в Меркле-Хеллмане не являются взаимозаменяемыми; закрытый ключ не может использоваться для шифрования. Таким образом, метод Меркла-Хеллмана не может напрямую использоваться для аутентификации посредством криптографической подписи , хотя Шамир опубликовал вариант, который можно использовать для подписи.

Генерация ключей

1. Выберите размер блока $n$. Целые числа до $n$ биты длиной могут быть зашифрованы с помощью этого ключа.

2. Выбрать случайную супервозрастающую последовательность $n$ положительные целые числа

$W=(w_{1},w_{2},\dots ,w_{n})$

Требование сверхвозрастания означает, что $w_{k}>\sum _{i=1}^{k-1}w_{i}$, для $1<k\leq n$.

3. Выберите случайное целое число $q$ такой, что

$q>\sum _{i=1}^{n}w_{i}$

4. Выберите случайное целое число $r$ такой, что $\gcd(r,q)=1$ (то есть, $r$ и $q$ взаимнопросты ) .

5. Рассчитаем последовательность

$B=(b_{1},b_{2},\dots ,b_{n})$

где $b_{i}=rw_{i}{\bmod {q}}$.

Открытый ключ $B$ и закрытый ключ $(W,q,r)$.

Шифрование

Позволять $m$ быть $n$-битовое сообщение, состоящее из битов $m_{1}m_{2}\dots m_{n}$, с $m_{1}$ бит высшего порядка. Выберите каждый $b_{i}$ для чего $m_{i}$ не равно нулю, и сложите их вместе. Аналогично, вычислите

$c=\sum _{i=1}^{n}m_{i}b_{i}$.

Зашифрованный текст $c$.

Расшифровка

Чтобы расшифровать зашифрованный текст $c$, мы должны найти подмножество $B$ что в сумме равно $c$. Мы делаем это, преобразуя задачу в задачу поиска подмножества $W$. Эту задачу можно решить за полиномиальное время, поскольку $W$ супервозрастает.

1. Вычислите модульную обратную величину $r$ модуль $q$ используя расширенный алгоритм Евклида . Обратное будет существовать, поскольку $r$ взаимнопроста с $q$.

$r':=r^{-1}{\pmod {q}}$

Вычисление $r'$ не зависит от сообщения и может быть выполнено только один раз при генерации закрытого ключа.

2. Рассчитать

$c':=cr'{\bmod {q}}$

3. Решите задачу о сумме подмножеств для $c'$ используя супервозрастающую последовательность $W$, с помощью простого жадного алгоритма, описанного ниже. Позволять $X=(x_{1},x_{2},\dots ,x_{k})$ — результирующий список индексов элементов $W$ какая сумма $c'$. (То есть, $c'=\sum _{i=1}^{k}w_{x_{i}}$.)

4. Создайте сообщение $m$ по 1 в каждом $x_{i}$ битовая позиция и 0 во всех остальных битовых позициях:

$m=\sum _{i=1}^{k}2^{n-x_{i}}$

Решение проблемы суммы подмножества

Этот простой жадный алгоритм находит подмножество супервозрастающей последовательности $W$ что в сумме равно $c'$, за полиномиальное время:

1. Инициализируйте $X$ в пустой список.

2. Найдите самый большой элемент в $W$ что меньше или равно $c'$, сказать $w_{j}$.

3. Вычтите: $c':=c'-w_{j}$.

4. Добавить $j$ в список $X$.

5. Если $c'$ больше нуля, вернитесь к шагу 2.

Пример

Генерация ключей

Создайте ключ для шифрования 8-битных чисел, создав случайную супервозрастающую последовательность из 8 значений:

$W=(2,7,11,21,42,89,180,354)$

Их сумма равна 706, поэтому выберите большее значение для $q$:

$q=881$.

Выбирать $r$ быть взаимно простым с $q$:

$r=588$.

Создайте открытый ключ $B$ умножив каждый элемент в $W$ к $r$ модуль $q$:

${\begin{aligned}&(2*588){\bmod {8}}81=295\\&(7*588){\bmod {8}}81=592\\&(11*588){\bmod {8}}81=301\\&(21*588){\bmod {8}}81=14\\&(42*588){\bmod {8}}81=28\\&(89*588){\bmod {8}}81=353\\&(180*588){\bmod {8}}81=120\\&(354*588){\bmod {8}}81=236\end{aligned}}$

Следовательно $B=(295,592,301,14,28,353,120,236)$.

Шифрование

Пусть 8-битное сообщение будет $m=97=01100001_{2}$. Умножаем каждый бит на соответствующее число в $B$ и добавьте результаты:

  0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
    = 1129

Зашифрованный текст $c$ это 1129.

Расшифровка

Чтобы расшифровать число 1129, сначала используйте расширенный алгоритм Евклида, чтобы найти модульное обратное число. $r$ против $q$:

$r'=r^{-1}{\bmod {q}}=588^{-1}{\bmod {8}}81=442$.

Вычислить $c'=cr'{\bmod {q}}=1129*442{\bmod {8}}81=372$.

Используйте жадный алгоритм, чтобы разложить 372 в сумму $w_{i}$ ценности:

${\begin{aligned}c'&=372\\&w_{8}=354\leq 372\\c'&=372-354=18\\&w_{3}=11\leq 18\\c'&=18-11=7\\&w_{2}=7\leq 7\\c'&=7-7=0\end{aligned}}$

Таким образом $372=354+11+7=w_{8}+w_{3}+w_{2}$, а список индексов $X=(8,3,2)$. Теперь сообщение можно вычислить как

$m=\sum _{i=1}^{3}2^{n-x_{i}}=2^{8-8}+2^{8-3}+2^{8-2}=1+32+64=97$.

Криптоанализ

В 1984 году Ади Шамир опубликовал атаку на криптосистему Меркла-Хеллмана, которая может расшифровывать зашифрованные сообщения за полиномиальное время без использования закрытого ключа. Атака анализирует открытый ключ $B=(b_{1},b_{2},\dots ,b_{n})$ и ищет пару чисел $u$ и $m$ такой, что $(ub_{i}{\bmod {m}})$ является супервозрастающей последовательностью. $(u,m)$ пара, найденная атакой, может быть не равна $(r',q)$ в закрытом ключе, но, как и эта пара, ее можно использовать для преобразования задачи о жестком рюкзаке, используя $B$ в простую задачу с использованием супервозрастающей последовательности. Атака осуществляется исключительно с использованием открытого ключа; доступ к зашифрованным сообщениям не требуется.

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