Введение
Криптосистема Меркла — Хеллмана была одной из первых криптосистем с открытым ключом. Она была опубликована Ральфом Мерклом и Мартином Хеллманом в 1978 году. В 1984 году Ади Шамир опубликовал атаку за полиномиальное время. В результате, эта криптосистема в настоящее время считается небезопасной.
История
Концепция криптографии с открытым ключом была представлена Уитфилдом Диффи и Мартином Хеллманом в 1976 году. Тогда они предложили общую концепцию "односторонней функции с секретным ключом", функции, для которой вычисление обратной функции вычислительно невыполнимо без некоторой секретной "информации о секретном ключе"; однако они еще не нашли практического примера такой функции. В последующие несколько лет другие исследователи предложили несколько конкретных криптосистем с открытым ключом, таких как RSA в 1977 году и Merkle-Hellman в 1978 году.
Описание
Merkle–Hellman — это криптосистема с открытым ключом, что означает использование двух ключей: открытого для шифрования и закрытого для расшифровки. Она основана на задаче о сумме подмножества (частный случай задачи о рюкзаке). Задача формулируется следующим образом: задано множество целых чисел и целое число , необходимо найти подмножество, сумма элементов которого равна . В общем случае, эта задача является NP-полной. Однако, если множество является супервозрастающим, то есть каждый его элемент больше суммы всех предшествующих элементов, задача становится "простой" и может быть решена за полиномиальное время с помощью простого жадного алгоритма. В Merkle–Hellman расшифровка сообщения требует решения, на первый взгляд, "сложной" задачи о рюкзаке. Закрытый ключ содержит супервозрастающий список чисел , а открытый ключ – несупервозрастающий список чисел , который является "замаскированной" версией . Закрытый ключ также содержит дополнительную информацию, своего рода "лазейку", позволяющую преобразовать сложную задачу о рюкзаке с использованием в простую задачу о рюкзаке с использованием . В отличие от некоторых других криптосистем с открытым ключом, таких как RSA, ключи в Merkle–Hellman не взаимозаменяемы; закрытый ключ нельзя использовать для шифрования. Таким образом, Merkle–Hellman нельзя напрямую использовать для аутентификации посредством криптографической подписи, хотя Shamir опубликовал вариант, пригодный для подписи.
Unlike some other public key cryptosystems such as RSA, the two keys in Merkle Hellman are not interchangeable; the private key cannot be used for encryption. Thus Merkle Hellman is not directly usable for authentication by cryptographic signing, although Shamir published a variant that can be used for signing.
Генерация ключей
1. Выберите размер блока. Целые числа длиной до битов могут быть зашифрованы с помощью этого ключа. 2. Выберите случайную супервозрастающую последовательность из положительных целых чисел.
Супервозрастающее требование означает, что , для
3. Выберите случайное целое число такое, что
3. Choose a random integer such that
4. Выберите случайное целое число такое, что (то есть, и являются взаимно простыми). 5. Вычислите последовательность , где
Открытый ключ — , а закрытый ключ — .
The public key is and the private key is .
Шифрование
Пусть будет n-битовое сообщение, состоящее из битов b₁, b₂, ..., bₙ, где bₙ — старший бит. Выберите все i, для которых bᵢ не равно нулю, и сложите соответствующие биты вместе. Эквивалентно, вычислите S = Σᵢ bᵢ. Шифротекст равен S.
Расшифровка
Чтобы расшифровать шифротекст, мы должны найти подмножество, сумма элементов которого равна . Мы делаем это, преобразуя задачу к поиску подмножества. Эта задача может быть решена за полиномиальное время, поскольку последовательность является супервозрастающей. 1. Вычислите модульный обратный к по модулю , используя расширенный алгоритм Евклида. Обратный существует, так как взаимно прост с . Вычисление выполняется независимо от сообщения и может быть выполнено только один раз при генерации секретного ключа. 2. Вычислите 3. Решите задачу о сумме подмножеств для , используя супервозрастающую последовательность , с помощью простого жадного алгоритма, описанного ниже. Пусть будет результирующим списком индексов элементов , сумма которых равна (то есть, ). 4. Сформируйте сообщение , установив 1 в каждой -й битовой позиции и 0 во всех остальных битовых позициях:
The computation of is independent of the message, and can be done just once when the private key is generated. 2. Calculate
3. Solve the subset sum problem for using the superincreasing sequence , by the simple greedy algorithm described below. Let be the resulting list of indexes of the elements of which sum to (That is, .) 4. Construct the message with a 1 in each bit position and a 0 in all other bit positions:
Криптоанализ
В 1984 году Ади Шамир опубликовал атаку на криптосистему Меркла — Хеллмана, которая позволяет расшифровывать зашифрованные сообщения за полиномиальное время без использования секретного ключа. Атака анализирует открытый ключ и ищет пару чисел *w* и *t* такую, что последовательность *w* является супервозрастающей. Пара, найденная в результате атаки, может не совпадать с парой, используемой в секретном ключе, но, подобно ей, может быть использована для преобразования сложной задачи о рюкзаке, использующей *w*, в простую задачу, использующую супервозрастающую последовательность. Атака оперирует исключительно с открытым ключом; доступ к зашифрованным сообщениям не требуется. Атака Шамира на криптосистему Меркла — Хеллмана работает за полиномиальное время, даже если числа в открытом ключе случайным образом перемешаны, что обычно не указывается в описании криптосистемы, но может быть полезно для защиты от некоторых более простых атак.