Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/31

Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера

Предлагается новый способ восстановления эквивалентного секретного ключа криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера. Рассматривается криптосистема, для построения которой используются только две копии кода. Задача восстановления эквивалентного секретного ключа криптосистемы Мак-Элиса - Сидельникова сводится к двум задачам поиска эквивалентного секретного ключа криптосистемы Мак-Элиса. Доказано, что предложенный способ имеет полиномиальную сложность. Проведены численные эксперименты на различных параметрах кода Рида - Маллера, подтверждающие возможность восстановления эквивалентного секретного ключа криптосистемы Мак-Элиса - Сидельникова за полиномиальное время.

Search for equivalent keys of the mceliece - sidelnikov cryptosystem built on the reed - muller binary codes.pdf Криптосистема Мак-Элиса - Сидельникова является криптосистемой с открытым ключом, стойкость которой основана на сложности задачи декодирования произвольного кода, исправляющего ошибки. В 1994 г. В. М. Сидельников [1] несколько изменил схему криптосистемы Мак-Элиса, предложив использовать не одну, а u копий кода, что повысило скорость передачи и стойкость криптосистемы. Предложенная схема получила название криптосистемы Мак-Элиса - Сидельникова. В качестве линейного кода, имеющего эффективный алгоритм декодирования, в работе Сидельникова используются коды Рида - Маллера. В 2007 г. Л. Миндер и А. Шокроллахи [2] построили структурную атаку на криптосистему Мак-Элиса. В 2013 г. М. Бородин и И. Чижов в работе [3] существенно понизили стойкость криптосистемы Мак-Элиса, при некоторых параметрах кода реализовав полиномиальную атаку на открытый ключ. Таким образом, вопрос стойкости криптосистемы Мак-Элиса - Сидельникова является достаточно актуальным. Секретным ключом криптосистемы Мак-Элиса - Сидельникова является кортеж (H, P), где H - невырожденная матрица над полем GF(2); P - перестановочная матрица. Открытым ключом является матрица G = (R||HR)P, где R - порождающая матрица кода Рида - Маллера RM(r, m). Определение 1. Код с порождающей матрицей вида G = (R||HR) называется сегментарным кодом Рида - Маллера RM(r, m)[H]. Таким образом, необходимо найти такие матрицы H' и P', что (R||HR)P = = (R||H'R)P'. Для этого необходимо выполнить следующие шаги: 1) построить формулу U над операциями произведения Шура © кодов и взятия ортогонального i кода, такую, что U(RM(r,m)[H]) С RM(m - r ([m/r] - 1) - 1,m) x RM(m - r([m/r] - 1) - 1,m); 2) используя алгоритм Сендрие [4], разделить RM(m - r([m/r] - 1) - 1,m) x xRM(m - r( [m/r] - 1) - 1, m) на две копии кода RM(m - r( [m/r] - 1) - 1, m); 3) найти перестановку для каждого сегмента, используя алгоритм Чижова - Бородина, если (r, m - 1) = 1, либо алгоритм Миндера - Шокроллахи, если ( r, m - 1) = 1 ; 4) найти матрицу H' секретного ключа криптосистемы. Полученные теоретические результаты можно разделить на два случая и кратко представить следующими теоремами. Случай 1: U(RM(r, m)[H]) = RM(d,m) x RM(d,m), где d = (r,m - 1). Теорема 1. Если (r, m - 1) = 1, то существует алгоритм, который по порождающей матрице кода RM (r, m)[H] находит перестановку P', такую, что RMPP'(r, m)[H] = RM(r, m)[H]. Сложность алгоритма O(n4 log2 n). Если (r, m -1) = 1, то существует алгоритм, который по порождающей матрице кода RMP(r, m)[H] находит перестановку P', такую, что RMPP (r, m)[H] = RM(r, m)[H]. Сложность алгоритма O(nd). С л у ч а й 2: U(RM(r,m)[H]) С RM(m - r([m/r] - 1) - 1,m) x RM(m - r([m/r] - 1) - 1,m). Теорема 2. Если m делится на r без остатка, то существует алгоритм, который по порождающей матрице кода RM (r, m)[H] находит перестановку P', такую, что RMPP'(r, m)[H] - RM(r,m)[H]. Сложность алгоритма O(n2r). Если m не делится на r без остатка и (r, m - 1) - 1, то существует алгоритм, который по порождающей матрице кода RM (r, m)[H] находит перестановку P', такую, что RMPP (r,m)[H] - RM(r, m)[H]. Сложность алгоритма O(n2m r mr ). Если m не делится на r без остатка и (r, m - 1) - 1, то существует алгоритм, который по порождающей матрице кода RM (r, m)[H] находит перестановку P', такую, что RMPP (r,m)[H] - RM(r, m)[H]. Сложность алгоритма O(max(n2m r[m/rJ ,nd+1)). Теоретические результаты подтверждаются практическими экспериментами: алгоритм реализован программно и исследован на ноутбуке с процессором 2,5 ГГц. Результаты приведены в табл. 1 для случая 1 и в табл. 2 для случая 2. Т а б л и ц а 1 Данные Параметры кодов (r, m) (2,6) (2,8) (3,8) (3,9) (2,10) (4,10) (3,11) Время работы 1,747 c 46,218 c 52,165c 11м 9с 2 ч 39 м 4 ч 32 м 8ч 19м Размер ключа 352 б 2,3 Кб 5,8 Кб 16,25 Кб 14 Кб 96,5 Кб 116Кб Т а б л и ц а 2 Данные Параметры кодов (r, m) (3,8) (3,9) (2,10) (4,10) (3,11) (3,12) (4,12) Время работы 5 м 34 с 3ч 13 м 4 ч 1 м 5 ч 28 м 12 ч 49 м 32 ч 54 м 51ч 54 с Размер ключа 5,8 Кб 16,25Кб 14 Кб 96,5 Кб 116 Кб 299 Кб 795 Кб

Ключевые слова

криптосистема Мак-Элиса - Сидельникова, код Рида - Маллера, полиномиальная атака, McEliece - Sidelnikov cryptosystem, Reed - Muller code, polynomial attack

Авторы

ФИООрганизацияДополнительноE-mail
Давлетшина Александра МаратовнаМосковский государственный университет имени М.В. Ломоносовааспирантка факультета ВМКvictvlasova@yandex.ru
Всего: 1

Ссылки

Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида - Маллера // Дискретная математика. 1994. Т. 6. №2. С. 3-20.
Minder L. and Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Ann. Intern. Conf. Theory and Appl. of Cryptographic Techniques. Berlin; Heidelberg: Springer, 2007. P. 347-360.
Бородин М. А., ЧижовИ.В. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида - Маллера // Дискретная математика. 2014. Т. 26. № 1. С.10-20.
Sendrier N. On the structure of a randomly permuted concatenated code // Proc. EUROCODE'94. Cote d'Or, France, 1994. P. 169-173.
 Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/31

Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/31