Algorithm for recovering plaintext from ciphertext in Mceliece cryptosystem.pdf Рассматриваются неструктурые атаки на криптосистему с открытым ключом Мак-Элиса [1] с целью дешифрования сообщения. По сути, решается уравнение m-G+e = c, где m и e неизвестны, а wt(e) = t. При этом m — исходное сообщение, G — порождающая матрица кода (открытый ключ), e — вектор ошибки, c — вектор, который подвергается дешифрованию. Найдя вектор ошибки e, мы решим систему полностью, так как вектор m находится из системы линейных уравнений. Все наилучшие алгоритмы неструктурной атаки на систему Мак-Элиса (Штерна, Шабо — Канто и Бернштейна — Ланг — Петерса) основываются на одной идее: итеративно генерируются различные базисы кода и решается задача в предположении, что вектор ошибки e можно выразить через 2p (p — параметр алгоритмов) некоторых из зафиксированных векторов базиса. В 2009 г. М. Финиаз и Н. Синдреир в работе [2] доказали нижнюю теоретическую оценку ожидаемого количества битовых операций, необходимых для дешифрования сообщения в криптосистеме Мак-Элиса. Для кодов Гоппы (1024,524,50) (стандартные параметры криптосистемы Мак-Элиса) эта оценка равна 259'9. Оценка идеальна и недостижима (в силу предположений при доказательстве). В то же время ожидаемое количество битовых операций, необходимых для дешифрования сообщения, закодированного с помощью этого кода, составляет: 1) для алгоритма Штерна - 266'21; 2) для алгоритма Шабо — Канто - 264'1; 3) для алгоритма Бернштейна — Ланг — Петерса - 260'55. То есть существующие алгоритмы уже вплотную приблизились к идеальной оценке ожидаемого количества битовых операций. В работе представляется модификация алгоритма Бернштейна — Ланг — Петер-са [3], которая уменьшает как ожидаемое количество итераций, так и ожидаемое количество битовых операций, выполняемых на одной итерации. Достигается это посредством следующих двух оптимизаций. 1) В алгоритме Бернштейна — Ланг — Петерса на каждой итерации фиксируется некоторый базис кода. Он получается из базиса кода, зафиксированного на предыдущей итерации, путём обмена местами c из первых k столбцов матрицы c c столбцами среди оставшихся, с дальнейшим применением модифицированного преобразования Гаусса. Оптимизация заключается в том, чтобы не менять столбцы, которые менялись на нескольких предыдущих итерациях; тем самым базисы, фиксируемые на итерациях, становятся более независимыми, что немного повышает вероятность найти вектор ошибки e. 2) На очередной итерации алгоритма Бернштейна — Ланг — Петерса ищется вектор ошибки e в виде линейной комбинации ровно 2p векторов базиса. Некоторым образом выбираются линейные комбинации из 2p векторов базиса, которые образуют векторы-кандидаты. Если вес какого-то вектора-кандидата равен t, то это и есть искомый вектор e. Для проверки необходимо вычислить веса всех векторов-кандидатов. Берн-штейн, Ланг и Петерс предлагают считать вес каждого вектора, пока он не превысит t (дальше считать бессмысленно). Оптимизация заключается в том, чтобы отбросить все векторы-кандидаты, у которых среди первых a координат больше чем b координат принимают значение 1 . Для остальных осуществить проверку так же, как её делают Бернштейн, Ланг и Петерс. Здесь a и b — новые параметры алгоритма. Смысл оптимизации заключается в следующем: на раннем этапе будет отброшено очень много неподходящих векторов-кандидатов, в то время как подходящий вектор-кандидат может быть отброшен с очень маленькой вероятностью. Для представленного алгоритма ожидаемое количество битовых операций, необходимых для дешифрования сообщения, закодированного с помощью кодов Гоппы (1024,524,50), равно 260'1. Это на 27,5 % меньше, чем для алгоритма Бернштейна — Ланг — Петерса, самого быстрого из существующих алгоритмов неструктурной атаки на криптосистему Мак-Элиса. Тем самым осуществлено ещё большее приближение к теоретической оценке количества битовых операций при дешифровании сообщения.

Скачать электронную версию публикации