Cryptanalysis of the mceliece pkc based on (k - 1)-reed - muller subcodes.pdf Криптосистема Мак-Элиса предложена в 1978 г. Р. Дж. Мак-Элисом. Её стойкость основана на предположении сложности декодирования кода общего положения. Оригинальная криптосистема Мак-Элиса строится на двоичных кодах Гоппы. Для повышения эксплуатационных характеристик В. М. Сидельников предложил использовать коды Рида - Маллера [1]. Однако в 2007 г. Л. Миндера и А. Шокроллахи предложили достаточно эффективную атаку на такую криптосистему [2]. Кроме того, в 2013г. Бородин и Чижов ещё больше понизили стойкость этой криптосистемы, а также построили полиномиальную атаку в случае использования кода Рида - Маллера RM(r, m) с такими параметрами, что (r, m - 1) = 1 [3]. Бывает, что атаки на кодовые криптосистемы, работающие в случае использования полного кода, оказываются бесполезными в случае использования некоторых подкодов кода. Так была предложена криптосистема Бергера - Луадро, построенная на подко-дах кода Рида - Соломона. В работе рассматриваются два аналога криптосистемы Бергера -Луадро, построенных на (k - 1)-подкодах кода Рида -Маллера RM(r, m). Пусть Vn - множество всех двоичных векторов длины n. Известно, что с каждой булевой функцией f (x1, x2,..., xm) : Vm ^ V1 можно связать вектор значений П/ = (f (0, 0,..., 0), f (0,0,..., 1),..., f (1,1,..., 1)). В дальнейшем не будем делать различий в обозначениях между булевой функцией и её вектором значений. Каждая булева функция может быть представлена полиномом Жегалкина: f (x1, x2,... , xm) = = 0 g/(u)xU, здесь xu = xU1 xU2 ... x^ и xU* = xi, если ui = 1, и xU = 1, если ui = 0, а g/(u) -некоторая булева функция. Определение 1. Степенью булевой функции называется наименьшее целое положительное число d, такое, что g/(u) = 0 для всех u веса больше d, т. е. wt(u) > d. Определение 2. Кодом Рида - Маллера RM(r, m) называется множество всех векторов значений булевых функций от m переменных, степень которых не превосходит r. Базисом кода являются все мономы степени r от m переменных: 1 x1, . . . , xm-^ x1x2, . . . , xm- 1xmo . . . , x1x2 ' ' ' xr, . . . , xm-r-1 ' ' ' xm. (1) Для двоичного набора а = (ат-1,... ,ао) символом |а| обозначим представление двоичной строки в виде десятичного числа а, т.е. |а| = а0 + 2а1 + ... + 2m-1ат-1. Введём отношение порядка для векторов а, в Е V^. Будем считать, что а < в, если либо wt^) < wt^), либо wt^) = wt^) и |а| < |в|. Тогда можно ввести отношение порядка на множестве мономов: < , если а < в. Определение 3. Стандартной формой порождающей матрицы кода RM(r, m) будем называть матрицу, составленную из всех векторов значений мономов (1), стоящих в порядке возрастания. Обозначим также символом A(r, m) множество всех таких наборов а = (ат-1, ...,а0), что моном входит в стандартную форму порождающей матрицы кода RM(r, m). Устройство криптосистемы первого типа McE/RM 1(r,m). Для генерации ключей строится стандартная форма порождающей матрицы R кода RM(r, m). Далее выбирается случайная двоичная невырожденная (k х п)-матрица H = (hj) и случайная подстановка а Е Sn, представленная в виде перестановочной (n х п)-матрицы . Затем вычисляется матрица G' = H • R • = H • RCT и из неё удаляется первая строка, получается ((k - 1) х п)-матрица G. Секретным ключом криптосистемы является набор (H, ) = (H, а), а открытым ключом - матрица G и (r,m) -параметры кода Рида - Маллера, однако, ради удобства, параметры в открытый ключ не включены. Устройство криптосистемы второго типа McE/RM2(r,m). Для генерации ключей строится стандартная форма порождающей матрицы R кода RM(r, m). Далее выбирается случайный номер i, 1 ^ i ^ k. Из матрицы R удаляется строка с номером i. Получившуюся в результате матрицу обозначим через R[i]. Выбирается случайная двоичная невырожденная ((k - 1) х п)-матрица H = (h^j) и случайная перестановочная (n х п)-матрица = (pj). Вычисляется матрица G = H • R[i] • = H • (R[i])CT. Секретным ключом криптосистемы является набор (H, , i) = (H, а, i), а открытым ключом - матрица G. Определение 4. Два секретных ключа (H1 ,а1) и (H2,a2) называются эквивалентными, если соответствующие им открытые ключи G1 и G2 равны. В работе решается задача восстановления секретного ключа криптосистемы или эквивалентного ему по открытому ключу. Пусть (H, а) -некоторый секретный ключ криптосистемы McE/RM 1(r, m); G - соответствующий ему открытый ключ; адь - некоторый автоморфизм кода Рида - Маллера. Тогда для порождающей матрицы R кода Рида - Маллера существует единственная матрица (невырожденная), что H^,bR = RaA,b. Теорема 1. Пусть [(H, а)] -класс эквивалентности секретного ключа (H, а) криптосистемы McE/RM 1. Тогда {(HHA,b, а-1,а) : аА,ь Е Aut(RM(r,m))} С [(H,а)]. Пусть C - произвольный (k - 1)-подкод кода Рида - Маллера RM(r, m). Рассмотрим такой моном fmin = xamin , что для всех а' < ат;п моном Е C, а fmin Е C. Такой моном существует и единственный. Пусть а = am;n. Для всех а' > а либо моном Е C, либо фЕ C, т.е. фа(а')жа Е C для некоторого а(а') Е {0,1}. Введём вектор а = (а(а') : а' Е A(r,m)). Тогда код C однозначно определяется векторами а и а. Будем в дальнейшем такой код обозначать символом Ca,a(r, m), причём а(а') = 0 для всех а' < а и а(а) = 1. Отметим, что открытый ключ G криптосистемы первого типа - это порождающая матрица кода для некоторого а и а. Для построения атаки на криптосистему первого типа используем идеи работы [3]. Определение 5. Пусть C и B - два линейных [n, к]-кода. Произведением C о B назовём код, состоящий из всех возможных произведений кодовых слов c • b, c Е C, b Е B. Здесь c • b = (c1 • b1, c2 • b2,..., cn • bn), если c = (c1,..., cn) и b = (b1,..., bn). Доказаны следующие теоремы. Теорема 2. Пусть r1 + r2 ^ m. Пусть также а1 Е A(r1,m), а2 Е A(r2,m), причём выполнено одно из двух условий: 1) а1 = а2, а1, а2 > 0; 2) а1 = а2 = а и wt^) ^ 2. Тогда для любых а1 и а2 выполняется равенство C«1 ,„1 (ri,m) о Ca2,„2(r2,m) = RM(ri + r2,m). Теорема 3. Пусть 2r < m. Тогда для любых а, таких, что wt^) = 1, либо Ca,„(r, m) о Ca,„(r, m) = RM(2r, m), либо существует такой автоморфизм кода Рида -Маллера RM(r, m), что Ca,„(r, m) о Ca,„(r, m) = C^,A0'b (2r, m). Общая схема атаки на криптосистему первого типа McE/RM 1(r, m): Шаг 1. По матрице G построить порождающую матрицу кода RM(r, m). Шаг 2. Применить атаку Чижова - Бородина к этой матрице. Для реализации первого шага предложен полиномиальный по сложности алгоритм, корректность работы которого доказывается при помощи теорем 2 и 3. Входным значением для алгоритма является открытый ключ криптосистемы McE/RM 1(r, m) - матрица G, которая соответствует подкоду C^a. Выходным значением является порождающая матрица кода RM(r, m). Алгоритм применим для следующих параметров: 2r ^ m - 1 при любом wt^) и для 2r ^ m при wt(a) ^ m - r - 1.

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