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

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

Описание

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

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

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

x = (x₁, x₂, …, x_n), (x_i = 0 или 1),

чтобы

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

.

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

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

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

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

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

.

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

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

Шифрование

  – сообщение x = (x₁, x₂, ..., x_n)
  - вычисляем y = b₁x₁ + b₂x₂ + , ..., + b_nx_n

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

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

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

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

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

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

Шифрование

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

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

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

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

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

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

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

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

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

.

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

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

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

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

β_i = rw_i mod q.

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

Шифрование

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

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

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

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

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

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

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 возможно с использованием расширенного алгоритма Евклида. Далее получатель шифротекста вычисляет

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

Отсюда

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

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

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

Тогда

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

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

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} - супервозрастающая последовательность.

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

\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».

См. также

Примечания

↑ Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525-530.
↑ Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279-288. Архивированная копия (неопр.). Дата обращения: 6 декабря 2005. Архивировано 24 апреля 2005 года.

Литература

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

Ссылки

[1] Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525-530.

[2] Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279-288. Архивированная копия (неопр.). Дата обращения: 6 декабря 2005. Архивировано 24 апреля 2005 года.

[1]

[2]