The relationship between structure of the key space and hardness of the Mceliece-Sidelnikov public key crypto system.pdf Криптосистема Мак-Элиса - одна из старейших криптосистем с открытым ключом.Она была предложена в 1978 г. Р. Дж. Мак-Элисом [1]. Эта криптосистема основываетсяна NP-трудной проблеме в теории кодирования. В. М. Сидельников в работе[2] предложил использовать для построения криптосистемы Мак-Элиса коды Рида-Маллера RM(r, m), однако, проведя криптоанализ, В. М. Сидельников пришёл к выводу,что на сегодняшний день такая криптосистема не обеспечивает должного уровнястойкости, и в той же работе предложил усиленную модификацию криптосистемыМак-Элиса на основе РМ-кодов - криптосистему Мак-Элиса-Сидельникова.Рассмотрим оригинальную криптосистему Мак-Элиса, построенную на кодахРида-Маллера RM(r, m). При этом предполагается, что выполнено неравенство2r ^ m, так как именно при таких ограничениях на m и r обеспечивается эффективностьалгоритмов декодирования РМ-кода. Будем понимать под взломом как оригинальнойкриптосистемы Мак-Элиса, так и модифицированной (криптосистемы Мак-Элиса-Сидельникова) восстановление компонентов секретного ключа по открытомуключу. Легко видеть, что в этом случае стойкость оригинальной криптосистемы Мак-Элиса определяется сложностью задачи mcRM (см. далее). Другими словами, еслизлоумышленник научится эффективно решать задачу mcRM, то он тем самым сможетвзломать оригинальную криптосистему Мак-Элиса, построенную на основе РМ-кодов.Задача mcRMВход: матрица G = H ■ R ■ 7 , где H - невырожденная двоичная (k х ^-матрица; R -порождающая (k х п)-матрица кода Рида-Маллера RM(r, m); 7 - перестановочная(n х n) -матрица.Найти: невырожденную матрицу H' размера (k х k) и перестановочную (п х п)-матрицу 7', такие, что H' ■ G ■ 7 ' - порождающая матрица кода Рида-МаллераRM(r, m), то есть найдется невырожденная (k х k)-матрица M , что выполнено равенствоH' ■ G ■ 7' = M ■ R.Введем в рассмотрение семейство mcRMi задач для 1 ^ i ^ k.Задача mcRMiВход: матрица G = H' ■ R' ■ 7', где H' - невырожденная двоичная (k - 1) х (k - 1)-матрица; R' - ((k - 1) х n) -матрица, получающаяся из порождающей матрицы R кодаРида-Маллера RM(r, m) выкидыванием строки с номером i; 7' - перестановочная(n х n) -матрица.Найти: невырожденную матрицу M' размера (k- 1) х (k - 1) и перестановочную (пхп)-матрицу а', такие, что M' ■ G ■ а' - порождающая матрица кода R', порождаемогоматрицей R', то есть найдется невырожденная ((k - 1) х (k - 1))-матрица L', чтовыполнено равенство M' ■ G ■ а' = L' ■ R '.Построение этого семейства полностью продиктовано результатами работы [3], в которойполучено описание ряда классов эквивалентности секретных ключей криптосистемыМак-Элиса-Сидельникова.Рассмотрим теперь задачу, связанную со стойкостью криптосистемы Мак-Элиса-Сидельникова. Однако здесь криптосистема Мак-Элиса-Сидельникова рассматриваетсяне на всем ключевом пространстве, а только на полностью описанных в [3] классахэквивалентности.Задача mcSRMВход: матрица G = (H1 R||H2 R) А, где H1 и H2 - невырожденные двоичные(k х ^-матрицы, принадлежащие классу эквивалентности [(H, H T i, Г)] для некоторойневырожденной (k х ^-матрицы H , некоторой перестановочной (2n х 2n)-матрицы Г,некоторого числа 1 ^ i ^ k и некоторого вектора a; R - порождающая (k х n)-матрицакода Рида-Маллера RM(r, m); А - перестановочная (2n х 2n)-матрица.Найти: невырожденные матрицы H1 и H2 размера (k х k) и перестановочную (2n х 2n)-матрицу А', такие, что G А' = (H1R||H2R).Справедливы следующие теоремы.Теорема 1. Пусть существует набор машин Тьюринга MTmcRMi, каждая изкоторых решает соответствующую задачу mcRMi за полиномиальное время. Тогдасуществует машина Тьюринга MTmcSRM, которая решает задачу mcSRM за полиномиальноевремя.Теорема 2. Пусть существует машина Тьюринга MTmcRM, которая решает задачуmcRM за полиномиальное время. Тогда существует семейство машин ТьюрингаMTmcRMi, которые соответственно решают задачи mcRMi за полиномиальное время.Теорема 3. Пусть существует машина Тьюринга MTmcRM, которая решаетзадачу mcRM за полиномиальное время. Тогда существует машина ТьюрингаMTmcSRM, которая решает задачу mcSRM за полиномиальное время.

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