Ранцевая криптосистема Меркла — Хеллмана , основанная на « задаче о рюкзаке », была разработана Ральфом Мерклом и Мартином Хеллманом в 1978 году . Это была одна из первых криптосистем с открытым ключом , но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.

Описание

«Задача о рюкзаке» заключается в следующем: зная подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес , но, зная вес, непросто определить подмножество грузов. Более подробно, пусть задана последовательность из n положительных чисел (n — «размер» рюкзака)

w = ( w ₁ , w ₂ , …, w _n ) и s .

Задача состоит в том, чтобы найти такой бинарный вектор

x = ( x ₁ , x ₂ , …, x _n ), ( x _i = 0 или 1),

чтобы

${\displaystyle s=\sum _{i=1}^{n}x_{i}w_{i}}$ .

Если каждому двоичному числу x поставить в соответствие некоторую букву алфавита, то её можно было бы передавать в зашифрованном виде просто как сумму s . Для произвольного набора чисел w _i задача восстановления x по s является NP-трудной .

Мерклу удалось получить обратную к числу s функцию , которая давала бы вектор x , зная только некий «секретный» ключ , и он предложил $100 тому, кто сможет раскрыть ранцевую систему Меркла — Хеллмана.

Рассмотрим её подробнее.

Меркл использовал не произвольную последовательность w _i , а супервозрастающую (superincreasing), то есть такую, что

${\displaystyle w_{k+1}>\sum _{i=1}^{k}w_{i}}$ .

Нетрудно убедиться, что для такого набора чисел решение задачи является тривиальным. Чтобы избавиться от этой тривиальности и понадобилось ввести «секретный ключ», а именно два числа: q такое, что ${\displaystyle q>\sum _{i=1}^{n}w_{i}}$ и r такое, что НОД(r, q) =1. И теперь вместо первоначального набора чисел w _i будем использовать числа b _i =r w _i mod q . В оригинальных статьях Меркл рекомендовал использовать n порядка 100, где n — число элементов супервозрастающей последовательности («размер» рюкзака).

В итоге получаем: открытый ключ — ( b ₁ , b ₂ , …, b _n ), закрытый ключ — ( w ₁ , w ₂ , …, w _n ; q , r ).

• Шифрование

  – сообщение x = (x1, x2, ..., xn)
  - вычисляем y = b1x1 + b2x2 + , ..., + bnxn

• Дешифрование

  - вычисляем s = yr-1 mod q
  - решаем задачу для s для супервозрастающей последовательности  (w1, w2, ..., wn), т.е. находим двоичное число x

Награда досталась А. Шамиру (Adi Shamir) после публикации им в марте 1982 года сообщения о раскрытии ранцевой системы Меркла — Хеллмана с одной итерацией. Заметим, что Шамир сумел построить ключ, не обязательно равный секретному, но позволяющий раскрыть шифр .

Итак, это была одна из неудачных, но очень интересных попыток построения криптосистемы на основе задачи о рюкзаке.

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

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

Шифрование

Сначала исходный текст необходимо представить в двоичном виде и разбить его на блоки, равные по длине с открытым ключом. Далее из последовательности, образующей открытый ключ, выбираются только те элементы, которые по порядку соответствуют 1 в двоичной записи исходного текста, игнорируя при этом элементы, соответствующие 0 биту . После этого элементы полученного подмножества складываются. Найденная в результате сумма и есть шифротекст.

Дешифрование

Дешифрование является возможным в силу того, что множитель и модуль, используемые для генерации открытого ключа из супервозрастающей последовательности, используются также и для преобразования шифротекста в сумму соответствующих элементов супервозрастающей последовательности. Далее, с помощью простого жадного алгоритма , можно дешифровать сообщение, используя O(n) арифметических операций.

Математическое описание алгоритма

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

Чтобы зашифровать n -битное сообщение, выберем супервозрастающую последовательность из n ненулевых натуральных чисел

w = ( w ₁ , w ₂ , …, w _n ).

Далее случайным образом выберем целые взаимно простые числа q и r такие, что

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

Число q выбирается таким образом, чтобы гарантировать единственность (уникальность) шифротекста. В случае, если оно будет хотя бы чуть меньше, может возникнуть ситуация, что одному шифротексту будут соответствовать несколько исходных (открытых) текстов. r должно быть взаимно просто с q , в противном случае оно не будет иметь мультипликативного обратного по модулю q , существование которого необходимо для дешифровки.

Теперь построим последовательность

β = (β ₁ , β ₂ , …, β _n ),

где каждый элемент вычисляется по следующей формуле

β _i = rw _i mod q .

β будет открытым ключом, в то время как закрытый ключ образует последовательность ( w , q , r ).

Шифрование

Чтобы зашифровать n -битное сообщение

α = (α ₁ , α ₂ , …, α _n ),

где ${\displaystyle \alpha _{i}}$ — это i -ый бит, то есть ${\displaystyle \alpha _{i}{\boldsymbol {\in }}}$ {0, 1}, вычислим число c, которое и будет шифротекстом.

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.}$

Дешифрование

Чтобы прочитать исходный текст, получатель должен определить биты сообщения ${\displaystyle \alpha _{i}}$ , которые удовлетворяли бы формуле

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.}$

Такая задача была бы NP-сложна в случае, если бы β _i были случайно выбранными значениями. Однако значения β _i были выбраны таким образом, что дешифровка сводится к простой задаче при условии, что закрытый ключ ( w , q , r ) известен.

Ключ к определению исходного текста заключается в том, чтобы найти целое число s , которое является мультипликативным обратным r по модулю q . Это значит, что s удовлетворяет уравнению sr mod q = 1, что эквивалентно существованию целого числа k такого, что sr = kq + 1. Поскольку r взаимно просто с q , найти s и k возможно с использованием расширенного алгоритма Евклида . Далее получатель шифротекста вычисляет

${\displaystyle c'\equiv cs{\pmod {q}}.}$

Отсюда

${\displaystyle c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.}$

Из того, что rs mod q = 1 и β i = rwi mod q , следует

${\displaystyle \beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.}$

Тогда

${\displaystyle c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.}$

Сумма всех w _i меньше, чем q . Отсюда значение ${\displaystyle \sum _{i=1}^{n}\alpha _{i}w_{i}}$ также находится в интервале [0,q-1]. Таким образом, получатель должен определить ${\displaystyle \alpha _{i}}$ из условия, что

${\displaystyle c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.}$ .

А это уже простая задача, поскольку w — супервозрастающая последовательность. Пусть w _k — наибольший элемент в w . Если w _k > c' , то α _k = 0; если w _k ≤c' , то α _k = 1. Далее вычитаем произведение w _k × α _k из c' и повторяем эти шаги до тех пор, пока не вычислим α.

Пример

w = {2, 7, 11, 21, 42, 89, 180, 354} - супервозрастающая последовательность.

Она является основой для генерации закрытого ключа. Посчитаем сумму элементов последовательности

${\displaystyle \sum w=706}$

Далее выберем простое число q , превосходящее полученное нами значение суммы.

q = 881

Выберем также число r из интервала [1,q]

r = 588

w , q и r образуют закрытый ключ.

Чтобы сгенерировать открытый ключ, построим последовательность β, умножая каждый элемент из последовательности w на r по модулю q .

2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236

Получим  β = (295, 592, 301, 14, 28, 353, 120, 236).

Последовательность β образует открытый ключ.

Пусть Алиса хочет зашифровать «a». Сначала она должна перевести «a» в двоичный код

01100001

Далее она умножает каждый бит на соответствующее число из последовательности β, а сумму значений отправляет получателю.

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

Чтобы дешифровать сообщение, Боб умножает полученное им значение на мультипликативное обратное r по модулю q .

1129 * 442 mod 881 = 372

После этого Боб раскладывает 372 следующим образом. Сначала он выбирает наибольший элемент из w, который меньше, чем 372, и вычисляет их разность. Далее он выбирает следующий наибольший элемент, который меньше, чем полученная разность, и повторяет эти действия, пока разность не станет равной нулю.

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0

Элементы, которые были выбраны из w , будут соответствовать 1 в двоичной записи исходного текста.

01100001

Переводя обратно из двоичной записи, Боб получает, наконец, искомое «a».

См. также

• Криптосистема с открытым ключом
• Шифрование
• Сверхвозрастающая последовательность

Примечания

Литература

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М. : Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4 .

Ссылки