Статья:

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

Конференция: XLVI Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Технические науки

Выходные данные
Андросова Т.Е., Курочкин В.М., Болдырев А.С. [и др.] Ранцевая криптосистема Меркла-Хеллмана // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XLVI междунар. студ. науч.-практ. конф. № 6(46). URL: https://nauchforum.ru/archive/MNF_tech/6(46).pdf (дата обращения: 19.08.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Андросова Татьяна Евгеньевна
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Курочкин Владислав Михайлович
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Болдырев Артем Сергеевич
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Чернов Роман Вячеславович
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара

 

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

Задачу о рюкзаке можно сформулировать следующим образом: пусть задан набор значений W = (w0, w1,.., wr-1) и сумма X. Требуется найти вектор (x0, x1,.., xr-1), где , такой, что X = x0w0 + x1w1 +..+ xr-1wr-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, мы должны иметь x7 = x6 = 0. Тогда, поскольку X > 55, и мы имеем 2 + 3 + 6 + 13 + 29 < 55, должно быть так, что x5 = 1. То есть, если мы не выберем вес 55, то мы не сможем достичь желаемой суммы, так как сумма всех оставшихся весов меньше 55 из-за свойства супервозрастания.

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

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

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

Чтобы создать свои публичные и закрытые ключи, Алиса сначала выбирает супервозрастающий рюкзак S = (s0, s1,.., sr-1). Чтобы преобразовать S в T, она также выбирает коэффициент преобразования m и модуль n, где НОД (m, n) = 1, и n больше суммы всех элементов из S. Преобразованный рюкзак вычисляется как T = (s0m(mod n), s1m(mod n),.., sr-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 году эта криптосистема была признана небезопасной Ади Шамиром. Оказывается, «основной рюкзак» (открытый ключ), который возникает в криптосистеме Меркла-Хелмана, недостаточно общий. Вместо этого, это очень структурированный случай рюкзака, и атака редукции решетки Шамира способна воспользоваться этим фактом.

 

Список литературы:
1. Stamp M. Applied cryptanalysis: breaking ciphers in the real world / Mark Stamp, Richard M. Low. – New Jersey: John Wiley & Sons, Inc., 2007. – 401 c.