В этом топике продолжим тему решения криптографических загадок с MysteryTwister. Ранее уже были опубликованы статьи навеянные задачами с этого ресурса («Угнать SIGABA за 24 часа», часть 1, часть 2). На этот раз возьмём задачу, основанную на классической «задаче о рюкзаке». Автор задачи Peter Uelkes. По этому вопросу на Хабре много статей (уместные я размещу внизу топика), но сегодня мы разберём конкретную задачу дешифровки.

Считается, что концепция криптографии с открытым ключом была введена Уитфилдом Диффи и Мартином Хеллманом ещё в 1976 году. В течение следующих нескольких лет другими исследователями было предложено несколько конкретных криптосистем с открытым ключом, таких как RSA в 1977 году, а в 1978 году Хеллман вместе с Ральфом Мерклом создал криптографическую модель Merkle‑Hellman. Сама система Меркла‑Хеллмана — это криптосистема с открытым ключом, подразумевающая использование двух ключей: открытый ключ для шифрования и закрытый ключ для дешифрования. Система основана на NP‑полной задаче о сумме подмножеств (частный случай «задачи о рюкзаке»). Однако, если для шифрования используется супервозрастающая последовательность (каждый элемент набора больше суммы всех чисел в наборе, меньших его), задача решается за полиномиальное время.

В предложенной системе для расшифровки сообщения требуется решить «сложную» задачу о рюкзаке. Закрытый ключ содержит супервозрастающую последовательность, а открытый — не супервозрастающую, которая на самом деле является «замаскированной» версией закрытого ключа, и большинство алгоритмов взлома основываются на поиске «маскировочной» функции. В отличие от некоторых других криптосистем с открытым ключом, два ключа в оригинальной системе Меркла‑Хеллмана не являются взаимозаменяемыми, и закрытый ключ нельзя использовать для шифрования. Таким образом, система не может напрямую использоваться для аутентификации с помощью криптографической подписи.

Сегодня известно много вариантов «рюкзачных» систем, что в принципе легко объяснимо высокими скоростями алгоритмов шифрования и дешифрования. Большая часть таких криптосистем взломана или признана потенциально небезопасными, хотя разработка и модификация таких систем продолжается.

Ну, что же, приступим к решению.

Упрощённый для задачи «рюкзак» работает следующим образом:

Алиса пожелала послать Бобу зашифрованное сообщение P (P = «MTC3»). Для этого она преобразовала его в десятичное число M, объединив соответствующие коды ASCII. Таким образом, M = 77846751 (M=77, T=84, С=67, 3=51). После этого она перевела M в двоичную систему счисления, получив B=100101000111101100011011111, (=27). У Алисы имеется «рюкзак K», как список следующих непересекающихся натуральных чисел:

K = (593, 13, 6252407, 1327, 958200, 2568118886, 51234, 24023, 6, 3470, 54136509, 160, 930178262, 3, 27, 102299137, 82, 15267027, 395469607, 117674, 2064250, 5494084005, 18363310574, 337256, 2, 38825629419, 7920)

На последнем этапе шифрования Алиса складывает B в «рюкзак», получая на выходе зашифрованное сообщение C = 60846205466, которое она отправляет своему приятелю Бобу.

Долго ли, коротко ли, но Боб получил заветный зашифрованный пакет C = 60846205466 от своей подруги и хотел бы его прочесть, для чего было бы неплохо перевести шифрованное сообщение в открытый текст. Зная содержимое «рюкзака» (небольшая ремарка, K — открытый ключ и это симметричный случай шифрования), он должен выбрать из него те числа, сумма которых даёт C. Математическая версия этой задачи известна как задача суммы подмножеств. Строго говоря, в идеале эта задача является NP-полной и эффективность решения для достаточно больших значений чрезвычайно низка.

Однако варианты задачи о сумме подмножеств, обладающие некоторым «изъяном», легко решаемы, как и в нашем случае. Итак, как только Боб решил задачу о сумме подмножеств, он получил двоичное число B и, преобразовав его обратно в десятичное число M, получил из него исходное сообщение своей подруги Алисы.

Сама задача несколько сложней, чем пример (длина B и, следовательно, также K составляет =179). Открытый текст на английском языке был зашифрован описанным методом «симметричного рюкзака». Используемый «рюкзак» обладает тем же свойством, что и описанный выше. Нужно расшифровать зашифрованный текст (я решил, но спойлерить не буду).

Для заинтересовавшихся оригинал K и зашифрованный текст C будут в конце топика, а мы разберём алгоритм решения этой задачи на основе переписки Алисы и Боба.

Итак, что у нас есть для дешифрования со стороны Боба. Имеется открытый ключ:

K = (593, 13, 6252407, 1327, 958200, 2568118886, 51234, 24023, 6, 3470, 54136509, 160, 930178262, 3, 27, 102299137, 82, 15267027, 395469607, 117674, 2064250, 5494084005, 18363310574, 337256, 2, 38825629419, 7920)

В наличии зашифрованное сообщение C = 60846205466. Нужно его расшифровать и перевести в удобочитаемый вид.

Не буду описывать весь ход моих мыслей, хотя, может быть, это было бы забавно и достойно отдельного описания, потому что я сначала хотел математически вычислить закрытый ключ, но позже понял, что он мне совершенно не нужен. Проникнувшись идеями Ади Шамира и жадными алгоритмами, извёл кучу бумаги и потратил почти целый день (очень стыдно, как обычно бывает, когда решение найдено, оно кажется очевидным). Вычислительная сложность подобных задач зависит от двух параметров — числа элементов ключа и числа разрядов в числах, составляющих множество. Если число элементов мало, обычно используются методы перебора, к которым можно отнести и описанный в топике алгоритм, если количество разрядов — то методы динамического программирования.

Самое важное в описании крылось в мелочах, в нём было явно указано, что алгоритм уязвим и задача дешифрования легко решаема, что не давало мне покоя (учитывая тот факт, что в примере, который мы рассматриваем =27, а решить нужно с =179, а заглянув в «рюкзак» из задачи, вы увидите, что в отличие от примера с 11-значными «грузами» там присутствуют 80+, но это не очень важно, главное было понять принцип, всё остальное дело техники).

С малыми значениями нетрудно провести полный перебор, но при больших значениях это достаточно муторная процедура. В итоге я пришел к следующему варианту решения. Идея решения данной задачи и, таким образом, уязвимость шифрования реализована в следующем алгоритме:

Если описать словами, то всё достаточно просто, парсим открытый ключ и сортируем по «весу», для удобства при этом необходимо соблюсти изначальный порядок ключевой последовательности. Начиная с самого тяжелого, сравниваем с зашифрованным сообщением. Если число из ключа больше, откидываем его и присваиваем этому Кi бинарный ноль. Иначе, отнимаем от C (зашифрованного сообщения) это число, а самому Кi в бинарном B присваиваем "1". Выполняем, пока оставшееся C не добьём до нуля.

В итоге получим бинарное B, которое переведем в десятичное M, а после через ASCII в текст, et voilà.

Вот в основном и всё. Успехов в решении интересных задач.

Приложения:

НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.