В Merkle-Hellman ранце криптосистема был один из самых ранних открытых ключей криптосистемы . Он был опубликован Ральфом Мерклом и Мартином Хеллманом в 1978 году. Атака с полиномиальным временем была опубликована Ади Шамиром в 1984 году. В результате криптосистема теперь считается небезопасной. [1] : 465 [2] : 190
История
Концепция криптографии с открытым ключом была введена Уитфилдом Диффи и Мартином Хеллманом в 1976 году. [3] В то время они предложили только общую концепцию «функции лазейки», функции, которую невозможно вычислить без какой-либо секретной «лазейки» с вычислительной точки зрения. информации, но пока не нашли практического примера такой функции. Несколько конкретных криптосистем с открытым ключом были затем предложены другими исследователями в течение следующих нескольких лет, например RSA в 1977 году и Меркл-Хеллман в 1978 году [4].
Описание
Меркл – Хеллман - это криптосистема с открытым ключом, что означает, что используются два ключа: открытый ключ для шифрования и закрытый ключ для дешифрования. В его основе лежит задача о сумме подмножеств (частный случай задачи о ранце ). [5] Проблема заключается в следующем: задан набор целых чисел и целое число , найдите подмножество что в сумме . В общем, эта задача, как известно, NP-полная . Однако еслиявляется супервозрастающим , что означает, что каждый элемент набора больше, чем сумма всех чисел в наборе, меньшем, чем он, проблема «легкая» и решаемая за полиномиальное время с помощью простого жадного алгоритма .
В Меркле – Хеллмане для расшифровки сообщения требуется решить явно «сложную» задачу о рюкзаке. Закрытый ключ содержит сверхувеличивающийся список чисел., а открытый ключ содержит нерасширяющийся список чисел , который на самом деле является «замаскированной» версией . Закрытый ключ также содержит некоторую "секретную" информацию, которую можно использовать для решения проблемы с тяжелым рюкзаком, используя в простую задачу о рюкзаке, используя .
В отличие от некоторых других криптосистем с открытым ключом, таких как RSA , два ключа в Merkle-Hellman не взаимозаменяемы; закрытый ключ нельзя использовать для шифрования. Таким образом, Меркл-Хеллман не может напрямую использоваться для аутентификации с помощью криптографической подписи , хотя Шамир опубликовал вариант, который можно использовать для подписи. [6]
Генерация ключей
1. Выберите размер блока . Целые числа до с помощью этого ключа можно зашифровать длину в битах.
2. Выберите случайную супервозрастающую последовательность положительные целые числа
- Сверхувеличивающее требование означает, что , для .
3. Выберите случайное целое число. такой, что
4. Выберите случайное целое число. такой, что (это, а также являются взаимно просты ).
5. Рассчитайте последовательность
- где .
Открытый ключ и закрытый ключ .
Шифрование
Позволять быть -битовое сообщение, состоящее из битов , с участием бит наивысшего порядка. Выберите каждый для которого отлична от нуля, и сложите их вместе. Эквивалентно рассчитать
- .
Зашифрованный текст .
Расшифровка
Расшифровать зашифрованный текст , мы должны найти подмножество что в сумме . Мы делаем это, преобразовывая задачу в задачу поиска подмножества. Эта проблема может быть решена за полиномиальное время, поскольку сверхувеличивается.
1. Вычислить модульный обратный из по модулю с использованием расширенного алгоритма Евклида . Обратное будет существовать, так как взаимно прост с .
- Расчет не зависит от сообщения и может быть выполнен только один раз при генерации закрытого ключа.
2. Рассчитайте
3. Решите задачу о сумме подмножеств для используя супервозрастающую последовательность , с помощью простого жадного алгоритма, описанного ниже. Позволять - результирующий список индексов элементов что в сумме . (Это,.)
4. Составьте сообщение с 1 в каждом битовая позиция и 0 во всех остальных битовых позициях:
Решение проблемы суммы подмножества
Этот простой жадный алгоритм находит подмножество супервозрастающей последовательности что в сумме , за полиномиальное время:
- 1. Инициализировать в пустой список.
- 2. Найдите самый большой элемент в что меньше или равно , сказать .
- 3. Вычтите: .
- 4. Добавить к списку .
- 5. Если больше нуля, вернитесь к шагу 2.
Пример
Генерация ключей
Создайте ключ для шифрования 8-битных чисел, создав случайную супервозрастающую последовательность из 8 значений:
Их сумма составляет 706, поэтому выберите большее значение для :
- .
Выбирать быть взаимно простыми с :
- .
Создайте открытый ключ путем умножения каждого элемента в от по модулю :
Следовательно .
Шифрование
Пусть 8-битное сообщение будет . Умножаем каждый бит на соответствующее число в и добавляем результаты:
0 * 295+ 1 * 592+ 1 * 301+ 0 * 14+ 0 * 28+ 0 * 353+ 0 * 120+ 1 * 236 = 1129
Зашифрованный текст это 1129.
Расшифровка
Чтобы расшифровать 1129, сначала используйте Расширенный алгоритм Евклида, чтобы найти модульную инверсию мод :
- .
Вычислить .
Используйте жадный алгоритм, чтобы разложить 372 на сумму значения:
Таким образом , а список индексов . Сообщение теперь можно вычислить как
- .
Криптоанализ
В 1984 году Ади Шамир опубликовал атаку на криптосистему Меркла-Хеллмана, которая может расшифровывать зашифрованные сообщения за полиномиальное время без использования закрытого ключа. [7] Атака анализирует открытый ключ. и ищет пару чисел а также такой, что является суперврастающей последовательностью. В пара, найденная атакой, может не быть равной в закрытом ключе, но, как и эта пара, его можно использовать для преобразования задачи о тяжелом рюкзаке, в простую задачу, используя супервозрастающую последовательность. Атака действует исключительно на открытый ключ; доступ к зашифрованным сообщениям не требуется.
Рекомендации
- ^ Шнайер, Брюс (1996). Прикладная криптография . Нью-Йорк: Джон Вили и сыновья. ISBN 0-471-12845-7.
- ^ Стинсон, Дуглас Р. (1995). Криптография: теория и практика . Бока-Ратон: CRC Press. ISBN 0-8493-8521-0.
- ^ Уитфилд Диффи; Мартин Хеллман (1976). «Новые направления в криптографии». IEEE Transactions по теории информации . 22 (6): 644. CiteSeerX 10.1.1.37.9720 . DOI : 10.1109 / TIT.1976.1055638 .
- ^ Меркл, Ральф; Хеллман, Мартин (1978). «Скрытие информации и подписей в секретных рюкзаках». IEEE Transactions по теории информации . 24 (5): 525–530. DOI : 10.1109 / TIT.1978.1055927 .
- ^ Черовицо, Уильям (2002-03-02). «Криптосистема ранца Меркла-Хеллмана» . Math 5410 - Современная криптология . Проверено 18 августа 2019 .
- ^ Шамир, Ади (июль 1978 г.). «Схема быстрой подписи». Технический меморандум о лаборатории компьютерных наук Массачусетского технологического института . 79 (MIT / LCS / TM-107): 15240. Bibcode : 1978STIN ... 7915240S .
- ^ Шамир, Ади (1984). «Полиномиальный алгоритм взлома базовой криптосистемы Меркла-Хеллмана». IEEE Transactions по теории информации . 30 (5): 699–704. DOI : 10.1109 / SFCS.1982.5 .