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

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

Сначала исходный текст необходимо представить в двоичном виде и разбить его на блоки, равные по длине с открытым ключом. Далее из последовательности, образующей открытый ключ, выбираются только те элементы, которые по порядку соответствуют 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' и повторяем эти шаги до тех пор, пока не вычислим α.