Interested Article - Ранцевая криптосистема Меркла — Хеллмана
![](/images/007/671/7671163/1.jpg?rand=62695)
![](https://cdn.wafarin.com/avatars/0f65015d6407a6165630a4250ff4a4c5.jpg)
- 2020-02-25
- 2
Ранцевая криптосистема Меркла — Хеллмана , основанная на « задаче о рюкзаке », была разработана Ральфом Мерклом и Мартином Хеллманом в 1978 году . Это была одна из первых криптосистем с открытым ключом , но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.
Описание
«Задача о рюкзаке» заключается в следующем: зная подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес , но, зная вес, непросто определить подмножество грузов. Более подробно, пусть задана последовательность из n положительных чисел (n — «размер» рюкзака)
- w = ( w 1 , w 2 , …, w n ) и s .
Задача состоит в том, чтобы найти такой бинарный вектор
- x = ( x 1 , x 2 , …, x n ), ( x i = 0 или 1),
чтобы
- .
Если каждому двоичному числу x поставить в соответствие некоторую букву алфавита, то её можно было бы передавать в зашифрованном виде просто как сумму s . Для произвольного набора чисел w i задача восстановления x по s является NP-трудной .
Мерклу удалось получить обратную к числу s функцию , которая давала бы вектор x , зная только некий «секретный» ключ , и он предложил $100 тому, кто сможет раскрыть ранцевую систему Меркла — Хеллмана.
Рассмотрим её подробнее.
Меркл использовал не произвольную последовательность w i , а супервозрастающую (superincreasing), то есть такую, что
- .
Нетрудно убедиться, что для такого набора чисел решение задачи является тривиальным. Чтобы избавиться от этой тривиальности и понадобилось ввести «секретный ключ», а именно два числа: q такое, что и r такое, что НОД(r, q) =1. И теперь вместо первоначального набора чисел w i будем использовать числа b i =r w i mod q . В оригинальных статьях Меркл рекомендовал использовать n порядка 100, где n — число элементов супервозрастающей последовательности («размер» рюкзака).
В итоге получаем: открытый ключ — ( b 1 , b 2 , …, b n ), закрытый ключ — ( w 1 , w 2 , …, 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 1 , w 2 , …, w n ).
Далее случайным образом выберем целые взаимно простые числа q и r такие, что
- .
Число q выбирается таким образом, чтобы гарантировать единственность (уникальность) шифротекста. В случае, если оно будет хотя бы чуть меньше, может возникнуть ситуация, что одному шифротексту будут соответствовать несколько исходных (открытых) текстов. r должно быть взаимно просто с q , в противном случае оно не будет иметь мультипликативного обратного по модулю q , существование которого необходимо для дешифровки.
Теперь построим последовательность
- β = (β 1 , β 2 , …, β n ),
где каждый элемент вычисляется по следующей формуле
- β i = rw i mod q .
β будет открытым ключом, в то время как закрытый ключ образует последовательность ( w , q , r ).
Шифрование
Чтобы зашифровать n -битное сообщение
- α = (α 1 , α 2 , …, α n ),
где — это i -ый бит, то есть {0, 1}, вычислим число c, которое и будет шифротекстом.
Дешифрование
Чтобы прочитать исходный текст, получатель должен определить биты сообщения , которые удовлетворяли бы формуле
Такая задача была бы NP-сложна в случае, если бы β i были случайно выбранными значениями. Однако значения β i были выбраны таким образом, что дешифровка сводится к простой задаче при условии, что закрытый ключ ( w , q , r ) известен.
Ключ к определению исходного текста заключается в том, чтобы найти целое число s , которое является мультипликативным обратным r по модулю q . Это значит, что s удовлетворяет уравнению sr mod q = 1, что эквивалентно существованию целого числа k такого, что sr = kq + 1. Поскольку r взаимно просто с q , найти s и k возможно с использованием расширенного алгоритма Евклида . Далее получатель шифротекста вычисляет
Отсюда
Из того, что rs mod q = 1 и β i = rwi mod q , следует
Тогда
Сумма всех w i меньше, чем q . Отсюда значение также находится в интервале [0,q-1]. Таким образом, получатель должен определить из условия, что
- .
А это уже простая задача, поскольку 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} - супервозрастающая последовательность.
Она является основой для генерации закрытого ключа. Посчитаем сумму элементов последовательности
Далее выберем простое число 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 .
Ссылки
![](https://cdn.wafarin.com/avatars/0f65015d6407a6165630a4250ff4a4c5.jpg)
- 2020-02-25
- 2