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

'''Ранцевая [[криптосистема]] Меркла — Хеллмана''', основанная на «[[Задача о ранце|задаче о рюкзаке]]», была разработана [[Меркл, Ральф|Ральфом Мерклом]] и [[Хеллман, Мартин|Мартином Хеллманом]] в [[1978 год]]у<ref>Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, ''IEEE Trans. Information Theory'', 24(5), September 1978, pp525-530.</ref>. Это была одна из первых [[Криптосистема с открытым ключом|криптосистем с открытым ключом]], но она оказалась [[Криптографическая стойкость|криптографически нестойкой]]<ref>Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279-288. {{cite web |url=http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF |title=Архивированная копия |accessdate=2005-12-06 |archiveurl=https://web.archive.org/web/20050424093849/http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF |archivedate=2005-04-24 }}</ref> и, как следствие, не приобрела популярности.

== Описание ==
«Задача о рюкзаке» заключается в следующем: зная [[подмножество]] грузов, уложенных в ранец, легко подсчитать суммарный [[вес]], но, зная вес, непросто определить подмножество грузов. Более подробно, пусть задана последовательность из n положительных [[Число|чисел]] (n — «размер» рюкзака)
: ''w'' = (''w''<sub>1</sub>, ''w''<sub>2</sub>, …, ''w''<sub>''n''</sub>) и ''s''.
Задача состоит в том, чтобы найти такой бинарный [[Вектор (математика)|вектор]]
: ''x'' = (''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''n''</sub>), (''x''<sub>i</sub> = 0 или 1),
чтобы
: <math>s=\sum_{i = 1}^n x_iw_i</math>.
Если каждому [[Двоичная система счисления|двоичному числу]] ''x'' поставить в соответствие некоторую букву алфавита, то её можно было бы передавать в зашифрованном виде просто как сумму ''s''. Для произвольного набора чисел ''w''<sub>i</sub> задача восстановления ''x'' по ''s'' является [[Класс NP|NP-трудной]].

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

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

Меркл использовал не произвольную [[последовательность]] ''w''<sub>i</sub>, а супервозрастающую (superincreasing), то есть такую, что
: <math>w_{k+1}>\sum_{i = 1}^k w_i</math>.
Нетрудно убедиться, что для такого набора чисел решение задачи является тривиальным. Чтобы избавиться от этой тривиальности и понадобилось ввести «секретный ключ», а именно два числа: ''q'' такое, что <math>q>\sum_{i = 1}^n w_i</math> и ''r'' такое, что НОД(r, q) =1.
И теперь вместо первоначального набора чисел ''w''<sub>i</sub> будем использовать числа ''b''<sub>i</sub>=r''w''<sub>i</sub> mod ''q''. В оригинальных статьях Меркл рекомендовал использовать ''n'' порядка 100, где n — число элементов супервозрастающей последовательности («размер» рюкзака).

В итоге получаем: открытый ключ — (''b''<sub>1</sub>, ''b''<sub>2</sub>, …, ''b''<sub>''n''</sub>), закрытый ключ — (''w''<sub>1</sub>, ''w''<sub>2</sub>, …, ''w''<sub>''n''</sub>; ''q'', ''r'').

* [[Шифрование]]
   – сообщение ''x'' = (''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub>)
   - вычисляем ''y'' = ''b''<sub>1</sub>''x''<sub>1</sub> + ''b''<sub>2</sub>''x''<sub>2</sub> + , ..., + ''b''<sub>''n''</sub>''x''<sub>''n''</sub>
* Дешифрование
   - вычисляем ''s'' = ''yr''<sup>-1</sup> mod ''q''
   - решаем задачу для ''s'' для супервозрастающей последовательности  (''w''<sub>1</sub>, ''w''<sub>2</sub>, ..., ''w''<sub>''n''</sub>), т.е. находим двоичное число ''x''

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

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

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

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

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

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

=== Генерация ключа ===
Чтобы зашифровать ''n''-битное сообщение, выберем супервозрастающую последовательность из ''n'' ненулевых [[Натуральное число|натуральных чисел]]
: ''w'' = (''w''<sub>1</sub>, ''w''<sub>2</sub>, …, ''w''<sub>''n''</sub>).

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

: <math>q>\sum_{i = 1}^n w_i</math>.

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

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

: β = (β<sub>1</sub>, β<sub>2</sub>, …, β<sub>''n''</sub>),

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

: β<sub>''i''</sub> = ''rw''<sub>''i''</sub> mod ''q''.

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

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

: α = (α<sub>1</sub>, α<sub>2</sub>, …, α<sub>''n''</sub>),

где <math>\alpha_i</math> — это ''i''-ый бит, то есть <math>\alpha_i \boldsymbol{\in}</math>{0, 1}, вычислим число c, которое и будет шифротекстом.

: <math>c = \sum_{i = 1}^n \alpha_i \beta_i.</math>

=== Дешифрование ===
Чтобы прочитать исходный текст, получатель должен определить биты сообщения <math>\alpha_i</math>, которые удовлетворяли бы формуле

: <math>c = \sum_{i = 1}^n \alpha_i \beta_i.</math>

Такая задача была бы [[Класс NP|NP-сложна]] в случае, если бы β<sub>''i''</sub> были случайно выбранными значениями. Однако значения β<sub>''i''</sub> были выбраны таким образом, что дешифровка сводится к простой задаче при условии, что закрытый ключ (''w'', ''q'', ''r'') известен.

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

: <math>c'\equiv cs \pmod{q}.</math>

Отсюда

: <math>c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}.</math>

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

: <math>\beta_i s\equiv w_i r s\equiv w_i\pmod{q}.</math>

Тогда

: <math>c' \equiv \sum_{i = 1}^n \alpha_i w_i\pmod{q}.</math>

Сумма всех ''w''<sub>i</sub> меньше, чем ''q''. Отсюда значение <math>\sum_{i = 1}^n \alpha_i w_i</math> также находится в интервале [0,q-1]. Таким образом, получатель должен определить <math>\alpha_i</math> из условия, что

: <math>c' = \sum_{i = 1}^n \alpha_i w_i.</math>.

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

== Пример ==
 w = {2, 7, 11, 21, 42, 89, 180, 354} - супервозрастающая последовательность.
Она является основой для генерации закрытого ключа.
Посчитаем сумму элементов последовательности

: <math>\sum w = 706</math>

Далее выберем [[простое число]] ''q'', превосходящее полученное нами значение суммы.
 <code>q = 881</code>
Выберем также число ''r'' из интервала [1,q]
 <code>r = 588</code>
''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
Далее она умножает каждый [[бит]] на соответствующее число из последовательности β, а сумму значений отправляет получателю.
 <code>a = 01100001</code>
 0 * 295
 + 1 * 592
 + 1 * 301
 + 0 * 14
 + 0 * 28
 + 0 * 353
 + 0 * 120
 + 1 * 236
 = 1129

Чтобы дешифровать сообщение, [[Алиса, Боб и Ева|Боб]] умножает полученное им значение на мультипликативное обратное ''r'' по модулю ''q''.
 <code>1129 * 442 mod 881 = 372</code>
После этого Боб раскладывает 372 следующим образом. Сначала он выбирает наибольший элемент из w, который меньше, чем 372, и вычисляет их разность. Далее он выбирает следующий наибольший элемент, который меньше, чем полученная разность, и повторяет эти действия, пока разность не станет равной нулю.
 <code>372 - 354 = 18</code>
 <code>18 - 11 = 7</code>
 <code>7 - 7 = 0</code>
Элементы, которые были выбраны из ''w'' , будут соответствовать ''1'' в двоичной записи исходного текста.
 <code>01100001</code>
Переводя обратно из двоичной записи, Боб получает, наконец, искомое «a».

== См. также ==
* [[Криптосистема с открытым ключом]]
* [[Шифрование]]
* [[Сверхвозрастающая последовательность]]

== Примечания ==
{{примечания}}

== Литература ==
* {{Книга:Шнайер Б.: Прикладная криптография}}

== Ссылки ==
{{^}}
{{Knapsack}}
{{криптографические алгоритмы с парой открытый/закрытый ключ}}

[[Категория:Криптография]]