Криптосистема Меркла — Хеллмана¶

Криптосистема Меркла — Хеллмана — это одна из первых криптосистем с открытым ключом, основанная на математической задаче об укладке рюкзака (задача о ранце). Разработана Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мерклом в 1978 году. Криптосистема относится к классу асимметричных шифров, где для шифрования и дешифрования используются разные ключи. Её безопасность основана на вычислительной сложности решения задачи о ранце, которая в общем случае является NP-полной.

¶История

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали концепцию криптосистемы с открытым ключом, но не предложили конкретной реализации. В 1978 году Ральф Меркл, аспирант Стэнфордского университета, совместно с Хеллманом разработал первую практическую систему такого типа, основанную на задаче о ранце. Идея заключалась в том, чтобы использовать «рюкзак» — набор чисел, из которого можно составить сумму, соответствующую сообщению. В 1982 году Ади Шамир показал, что система уязвима для атак на основе линейной алгебры, а в 1984 году Эрнест Бриккелл и Эндрю Однорожко продемонстрировали эффективную атаку, использующую алгоритм Ленстры — Ленстры — Ловаса (LLL). После этого криптосистема Меркла — Хеллмана была признана небезопасной для практического применения, хотя её варианты продолжали изучаться в академических целях.

¶Математические основы

Криптосистема основана на задаче о ранце (subset sum problem): дан набор натуральных чисел \(a_1, a_2, \dots, a_n\) и целевая сумма \(S\). Требуется найти подмножество этих чисел, сумма которых равна \(S\), или доказать, что такого подмножества не существует. В общем случае задача является NP-полной, то есть для больших \(n\) не существует алгоритма, решающего её за полиномиальное время.

Однако для некоторых специальных наборов чисел, называемых «сверхвозрастающими» (superincreasing), задача решается легко. Сверхвозрастающая последовательность — это такая последовательность, в которой каждый следующий элемент больше суммы всех предыдущих. Например, \(1, 2, 4, 8, 16\) — сверхвозрастающая. Для такой последовательности решение задачи о ранце находится жадным алгоритмом за линейное время.

¶Принцип работы

Криптосистема Меркла — Хеллмана использует преобразование сверхвозрастающей последовательности в «случайную» (не сверхвозрастающую) последовательность с помощью умножения на секретный модуль и секретный множитель. Это позволяет скрыть структуру ключа.

¶Генерация ключей

1. Выбирается сверхвозрастающая последовательность \(b_1, b_2, \dots, b_n\).
2. Выбираются два секретных числа: модуль \(M\) и множитель \(W\), такие что \(M > \sum_{i=1}^n b_i\) и \(W\) взаимно просто с \(M\) (то есть \(\gcd(W, M) = 1\)).
3. Вычисляется открытый ключ — последовательность \(a_i = (b_i \cdot W) \bmod M\) для \(i = 1, \dots, n\).
4. Секретный ключ состоит из последовательности \(b_i\), модуля \(M\) и обратного элемента \(W^{-1}\) по модулю \(M\) (такого, что \(W \cdot W^{-1} \equiv 1 \pmod{M}\)).

¶Шифрование

Сообщение представляется в виде двоичного вектора \(m = (m_1, m_2, \dots, m_n)\), где \(m_i \in \{0, 1\}\). Шифротекст \(c\) вычисляется как сумма:

\[ c = \sum_{i=1}^n m_i \cdot a_i \]

То есть шифротекст — это сумма тех элементов открытого ключа, которые соответствуют единичным битам сообщения.

¶Дешифрование

1. Получатель вычисляет \(c' = (c \cdot W^{-1}) \bmod M\).
2. Поскольку \(c' = \sum m_i \cdot b_i\) (в силу свойств модульной арифметики), а последовательность \(b_i\) сверхвозрастающая, получатель решает задачу о ранце для \(c'\) с помощью жадного алгоритма: начиная с самого большого элемента, если элемент меньше или равен текущей сумме, он включается в решение, и сумма уменьшается.
3. Восстановленный двоичный вектор \(m\) является исходным сообщением.

¶Пример

Для иллюстрации рассмотрим простой пример с \(n=4\).

1. Сверхвозрастающая последовательность: \(b = (2, 3, 6, 12)\).
2. Выберем \(M = 25\) (сумма \(b_i = 23\), \(M > 23\)), \(W = 7\) (взаимно просто с 25).
3. Открытый ключ: \(a_i = (b_i \cdot 7) \bmod 25\):

• \(a_1 = 14\),
• \(a_2 = 21\),
• \(a_3 = 17\),
• \(a_4 = 9\).

Открытый ключ: \((14, 21, 17, 9)\).

1. Секретный ключ: \(b = (2, 3, 6, 12)\), \(M=25\), \(W^{-1} = 18\) (так как \(7 \cdot 18 = 126 \equiv 1 \pmod{25}\)).

Шифрование сообщения \(m = (1, 0, 1, 1)\): \[ c = 1 \cdot 14 + 0 \cdot 21 + 1 \cdot 17 + 1 \cdot 9 = 14 + 17 + 9 = 40 \]

Дешифрование: \[ c' = (40 \cdot 18) \bmod 25 = 720 \bmod 25 = 20 \] Решение задачи о ранце для \(c'=20\) со сверхвозрастающей последовательностью \((2, 3, 6, 12)\):

• 12 ≤ 20 → включаем, остаток 8,
• 6 ≤ 8 → включаем, остаток 2,
• 3 > 2 → не включаем,
• 2 ≤ 2 → включаем, остаток 0.

Получен вектор \((1, 0, 1, 1)\), что соответствует исходному сообщению.

¶Уязвимости и криптоанализ

Основная уязвимость криптосистемы Меркла — Хеллмана заключается в том, что преобразование сверхвозрастающей последовательности в открытый ключ не является достаточно случайным. Атака Шамира (1982) использовала тот факт, что открытый ключ можно рассматривать как линейную комбинацию секретных параметров, и применяла методы линейного программирования для восстановления секретного ключа. В 1984 году Бриккелл и Однорожко предложили более эффективную атаку, основанную на алгоритме LLL, который находит короткие векторы в решётках. Алгоритм LLL позволяет за полиномиальное время восстановить секретный ключ, если размерность задачи не слишком велика. Для параметров, рекомендованных в оригинальной работе (например, \(n=100\)), атака оказывалась успешной.

После этих работ криптосистема Меркла — Хеллмана была признана небезопасной. Однако её идеи повлияли на развитие криптографии на решётках, которая впоследствии привела к созданию современных постквантовых криптосистем, таких как NTRU и CRYSTALS-Kyber.

¶Применение и значение

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

¶Варианты и модификации

Существует несколько модификаций криптосистемы Меркла — Хеллмана, направленных на повышение безопасности:

• Множественный рюкзак (Multiple Knapsack) — использование нескольких независимых рюкзаков для шифрования одного сообщения.
• Рюкзак с шумом (Noisy Knapsack) — добавление случайного шума к шифротексту для усложнения атак.
• Рюкзак Грэма — Шамира (Graham-Shamir knapsack) — вариант, в котором открытый ключ строится с использованием модулярной арифметики и дополнительных параметров.

Однако все эти варианты были впоследствии взломаны с помощью алгоритма LLL или других методов решёточной редукции.

¶Интересные факты

• Криптосистема Меркла — Хеллмана была запатентована в США в 1980 году (патент № 4,200,770), но срок действия патента истёк в 1997 году.
• Ральф Меркл позже стал известен как один из изобретателей хеш-функций и криптографии на решётках.
• В 1980-х годах система активно рекламировалась как «непробиваемая», но после атаки Шамира её репутация была подорвана.

¶Источники

• Diffie, W., Hellman, M. E. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory.
• Merkle, R. C., Hellman, M. E. (1978). Hiding Information and Signatures in Trapdoor Knapsacks. IEEE Transactions on Information Theory.
• Shamir, A. (1982). A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. Advances in Cryptology — CRYPTO '82.
• Brickell, E. F., Odlyzko, A. M. (1984). Cryptanalysis: A Survey of Recent Results. Proceedings of the IEEE.
• Lenstra, A. K., Lenstra, H. W., Lovász, L. (1982). Factoring Polynomials with Rational Coefficients. Mathematische Annalen.