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

Ранцевая криптосистема Меркла-Хеллмана была одной из первых предложенных криптосистем с открытым ключом. Этот шифр использует несколько элементарных, но, тем не менее, умных математических идей. Шифр основан на математической задаче о рюкзаке, которая, как известно, является NP-полной.

Задачу о рюкзаке можно сформулировать следующим образом: пусть задан набор значений W = (w₀, w₁,.., w_r-1) и сумма X. Требуется найти вектор (x₀, x₁,.., x_r-1), где , такой, что X = x₀w₀ + x₁w₁ +..+ x_r-1w_r-1, при условии, что это возможно.

Например, предположим, что веса W = (4,3,9,1,12,17,19,23), и данная сумма равна X = 35. Тогда существует решение задачи в виде вектора x = (01011010), так как 0*4 + 1*3 + 0*9 + 1*1 + 1*12 + 0*17 + 1*19 + 0*23 = 35.

Для этого набора весов при X = 6 задача не имеет решения.

В то время, как общая задача о рюкзаке является NP-полной, специальный тип задачи о рюкзаке, известном как «супервозрастающий», может быть эффективно разрешена. Супервозрастающий рюкзак представляет собой множество W, которое при движении по элементам от наименьшего к наибольшему обладает тем свойством, что каждый вес больше суммы всех предыдущих весов. Например, W = (2,3,6,13,29,55,112,220) является супервозрастающим рюкзаком.

Решить проблему, связанную с супервозрастающим рюкзаком, довольно просто. Например, предположим, что нам дано множество весов W = (2,3,6, 13,29,55,112,220) и сумма X = 76. Так как X меньше 112, мы должны иметь x₇ = x₆ = 0. Тогда, поскольку X > 55, и мы имеем 2 + 3 + 6 + 13 + 29 < 55, должно быть так, что x₅ = 1. То есть, если мы не выберем вес 55, то мы не сможем достичь желаемой суммы, так как сумма всех оставшихся весов меньше 55 из-за свойства супервозрастания.

Пусть теперь X₁ = X – 55 = 21. Поскольку 13 < X₁ < 29, мы получаем, что x₄ = 0 и x₃ = 1. Продолжая, находим вектор x = (10110100), который является корректным, поскольку 76 = 2 + 6 + 13 + 55. Этот процесс дает эффективный алгоритм для решения любой задачи о супервозрастающем рюкзаке.

Идея Меркла и Хеллмана заключалась в том, чтобы замаскировать супервозрастающий рюкзак S посредством использования математического преобразования, чтобы сделать его похожим на произвольный рюкзак T. Замаскированный рюкзак T обнародуется Алисой, а T выступает в качестве открытого ключа Алисы. Когда Алиса получает зашифрованный текст, она применяет обратную трансформацию для преобразования проблемы в супервозрастающий случай. Алиса расшифровывает его, решая возникающую в результате проблему супервозрастающего рюкзака.

Обсудим более подробно криптосистему ранца.

Чтобы создать свои публичные и закрытые ключи, Алиса сначала выбирает супервозрастающий рюкзак S = (s₀, s₁,.., s_r-1). Чтобы преобразовать S в T, она также выбирает коэффициент преобразования m и модуль n, где НОД (m, n) = 1, и n больше суммы всех элементов из S. Преобразованный рюкзак вычисляется как T = (s₀m(mod n), s₁m(mod n),.., s_r-1m(mod n)) и публикуется. Закрытый ключ Алисы состоит из S и m^-l (mod n). Предположим, что Боб хочет отправить сообщение из r бит Алисе. Боб сначала преобразует свой открытый текст в двоичный блок B. Затем он использует биты «1» блока B для выбора элементов из T, которые затем суммируются для получения блока C зашифрованного текста. Алиса восстанавливает открытый текст B, используя закрытый ключ, вычисляет Cm^-1(mod n) и решает задачу о сверхвозрастающем рюкзаке. Чтобы зашифровать более длинные сообщения, необходимо разбивать сообщение на блоки и шифровать каждый блок.

Чтобы конкретизировать, рассмотрим следующий пример. Предположим, что Алиса выбирает супервозрастающий рюкзак S = (2,3,7,14, 30,57,20,251) с m = 41 и модулем n = 491. Чтобы преобразовать S в обычный рюкзак T, Алиса выполняет следующие вычисления:

2m = 2*41 = 82 (mod 491)

3m = 3*41 = 123 (mod 491)

7m = 7*41 = 287 (mod 491)

14m = 14*41 = 83 (mod 491)

30m = 30*41 = 248 (mod 491)

57m = 57*41 = 373 (mod 491)

120m = 120*41 = 10 (mod 491)

251m = 251*41 = 471 (mod 491).

Тогда открытый ключ Алисы T = (82,122,287,83,248,373,10,471). Закрытый ключ Алисы состоит из S = (2,3,7,14,30,57,120,251) а также m^-1(mod n) = 41^-l (mod 491) = 12.

Теперь предположим, что Боб хочет зашифровать сообщение M = 150 для Алисы. Сначала он преобразует 150 в двоичный код, то есть 10010110. Затем он использует биты «1» для выбора элементов из T, которые суммируются для получения зашифрованного текста. В этом примере Боб вычисляет зашифрованный текст C = 82 + 83 + 373 + 10 = 548 и отправляет его Алисе. Чтобы расшифровать этот зашифрованный текст, Алиса использует свой секретный ключ для вычисления Cm^-l (mod n) = 548*12 (mod 491) = 193. Затем она решает супервозрастающий рюкзак S для значения 193 и восстанавливает сообщение в двоичном формате 10010110 или в десятичном значении M = 150.

То, что этот процесс дешифрования работает, можно проверить, используя элементарные свойства модульной арифметики. В конкретном примере, рассмотренном выше, мы имеем

548m^-1 = 82m^-1 + 83m^-1 + 37m^-1 + 10m^-1 = 2mm^-1 + 14mm^-1 + 57mm^-1 + 120mm^-1 = 2 + 14 + 57 + 120 = 193 (mod 491).

В общем: из-за линейности процесса, используемого для преобразования супервозрастающего рюкзака S в рюкзак открытого ключа T, знание m^-1 позволяет легко преобразовать зашифрованный текст в супервозрастающий случай. Без секретного ключа Алисы (S, m^-1(mod n)), злоумышленнику нужно найти подмножество T, которое суммируется со значением C зашифрованного текста. Это, как представляется, является общей задачей о ранце, которая неразрешима. Преобразуя супервозрастающий рюкзак в рюкзак общего вида с помощью модульной арифметики, в рюкзак вводится так называемый «потайной вход». Без m неясно, как найти коэффициент преобразования m^-1. Односторонняя функция здесь возникает из-за того, что ее можно легко зашифровать с помощью рюкзака общего вида, но его трудно расшифровать без закрытого ключа. Но с закрытым ключом проблема может быть преобразована в сверхвозрастающий рюкзак, который легко решить и, таким образом, позволяет предполагаемому получателю легко расшифровывать сообщение.

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