Криптосистема Меркля-Хеллмана

Предположим, что элементы открытого текста имеют в качестве своих числовых эквивалентов k -разрядные двоичные числа n.

Каждый пользователь выбирает быстрорастущий набор { v ₀, …, v_{k – 1}}, целое число и целое число a, такое что a < 0 < m и НОД(a, m) = 1.

После этого вычисляются b = a ^-1 (mod m) и k -элементный набор { W_i } = { W ₀, …, W_{k –1}}, пределяемый равенствами W_i = av_i (mod m). Пользователь держит числа { v_i }, m, a и b в секрете, а набор { W_i } делает общеизвестным. Таким образом, ключом зашифрования является набор

{ W ₀, …, W_{k –1}},

а ключом расшифрования – пара

(b, m),

которая вместе с ключом зашифрования позволяет определить набор { v ₀, …, v_{k – 1}}.

Желающий передать сообщение n = (n ₀… n_{k – 1})₂ пользователю с ключом шифрования { W_i } вычисляет

и передает это число.

Чтобы прочесть это сообщение, пользователь сначала находит s = bC:

,

поскольку bW_i ≡ bav _i ≡ v_i (mod m). Теперь можно воспользоваться приведенным выше алгоритмом для быстровозрастающего рюкзака и найти единственное решение

(n ₀… n_{k – 1})₂ = n задачи о подмножестве { v_i } с суммой равной s.

Пример. Элементы открытого текста – двоичные представления букв 26-буквенного алфавита от «A» = 0 = (00000)₂ до «Z» = 25 = (11001)₂.

Cекретный быстровозрастающий набор { v ₀, …, v_{k – 1}} = {2, 3, 7, 15, 31}.

Выберем m = 61, a = 17, тогда b = 18 и открытый ключ шифрования

{ W ₀, …, W_{k –1}} = {34, 51, 58, 11, 39}.

Чтобы послать сообщение «WHY» корреспондент должен вычислить:

«W» = (10110)₂ ® 51 + 58 + 39 = 148,

«H» = (00111)₂ ® 34 + 51 + 58 = 143,

«Y» = (11000)₂ ® 11 + 39 = 50.

N = n ₁, n ₂, n ₃ = 148, 143, 50.

Чтобы прочитать сообщение N, сначала умножают эти числа на 18 и приводят результаты по модулю 61, получают S = s ₁, s ₂, s ₃ = 41, 12, 46 далее, пользуясь алгоритмом для быстрорастущего рюкзака для всех s_i, восстанавливают сообщение

(10110)₂, (00111)₂, (11000)₂