Анализ стойкости некоторых кодовых криптосистем, основанный на разложении кодов в прямую сумму

Владимир Михайлович Деундяк; Юрий Владимирович Косолапов

doi:10.14529/mmp190308

Авторы

Владимир Михайлович Деундяк Южный федеральный университет, Научно-исследовательский институт ≪Специализированные вычислительные устройства защиты и автоматика≫
Юрий Владимирович Косолапов Южный федеральный университет

DOI:

https://doi.org/10.14529/mmp190308

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

прямая сумма кодов, криптосистема типа Мак-Элиса, атака на ключ.

Аннотация

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

Биографии авторов

Владимир Михайлович Деундяк, Южный федеральный университет, Научно-исследовательский институт ≪Специализированные вычислительные устройства защиты и автоматика≫

Кандидат физико-математических наук, доцент

Юрий Владимирович Косолапов, Южный федеральный университет

Кандидат технических наук

Библиографические ссылки

McEliece R.J. A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report, 1978, pp. 42–44.

Sidel’nikov V.M., Shestakov S.O. On an Encoding System Constructed on the Basis of Generalized Reed–Solomon Codes. Discrete Mathematics and Applications, 1992, vol. 2, no. 4, pp. 439–444.

Deundyak V.M., Druzhinina M.A., Kosolapov Yu.V. [Modification of the Sidelnikov–Shestakov Cryptanalytic Algorithm for Generalized Reed–Solomon Codes and its Software Implementation]. Izvestiya vysshih uchebnyh zavedenij. Severo-Kavkazskij region. Tekhnicheskie nauki, 2006, no. 4, pp. 15–19. (in Russian)

Wieschebrink C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes. Third International Workshop, Berlin, 2010, pp. 61–72.

Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem. Advances in Cryptology – EUROCRYPT 2007, Lecture Notes Computer Science, 2007, no. 4515, pp. 347–360.

Borodin M.A., Chizhov I.V. Effective Attack on the McEliece Cryptosystem Based on Reed–Muller Codes. Discrete Mathematics and Applications, 2014, vol. 26, no. 1, pp. 273–280.

Deundyak V.M., Kosolapov Yu.V. Cryptosystem on Induced Group Codes. Modelling and Analysis of Information Systems, 2016, vol. 23, no. 2, pp. 137–152.

Kosolapov Yu.V., Shigaev A.N. [On the Support Splitting Algorithm for Induced Codes] Modelling and Analysis of Information Systems, 2018, vol. 25, no. 3, pp. 276–290. (in Russian)

Sidel’nikov V.M. Teoriya kodirovaniya [Coding Theory]. Moscow, Fizmatlit, 2008.

Morelos-Zaragoza R.H. The Art of Error Correcting Coding. Chichester, West Sussex, John Wiley & Sons, 2006.

Massey J.L. Minimal Codewords and Secret Sharing. Proceeding of 6th Joint Swedish-Russian Workshop on Information Theory, 1993, pp. 276–279.

Avgustinovich S.V., Gorkunov E.V. [On Automorphisms of Linear Codes over a Simple Field] Siberian Electronic Mathematical Reports, 2017, vol. 14, pp. 210–217. (in Russian)

Sendrier N. On the Concatenated Structure of a Linear Code. Applicable Algebra in Engineering, Communication and Computing, 1998, vol. 9, no. 3, pp. 221–242.

Berger T.P., Ourivski A.V. Construction of New MDS Codes from Gabidulin Codes. Proceedings of ACCT’9, 2004, pp. 40–47.

Assmus E.F. The Category of Linear Codes. IEEE Transaction on Information Theory, 1998, vol. 44, no. 2, pp. 612–629.

Fripertinger H., Kerber A. Isometry Classes of Indecomposable Linear Codess. Lecture Notes in Computer Science, 1995, vol. 948, pp. 194–204.

Sidel’nikov V.M. A Public-Key Cryptosystem Based on Binary Reed–Muller Codes. Discrete Mathematics and Applications, 1994, vol. 4, no. 3, pp. 191–208.

Deundyak V.M., Kosolapov Yu.V. On the Berger–Loidreau Cryptosystem on the Tensor Product of Codes. Journal of Computational and Engineering Mathematics, 2018, vol. 5,

no. 2, pp. 16–33.

Krasavin A.A. Using the Modified (u|u + v)-Construction in the McEliece Cryptosystem. Trudy MFTI, 2018, vol. 10, no. 2, pp. 189–191. (in Russian)

Kabatiansky G., Tavernier C. A New Code-Based Cryptosystem via Pseudorepetition of Codes. Proceedings of ACCT XVI, 2018, pp. 189–191.

Deundyak V.M., Kosolapov Yu.V. [Using the Tensor Product of Reed–Muller Codes in an Asymmetric McEliece Type Cryptosystem and Analyzing its Resistance to Attacks on a Cipher]. Computational Technologies, 2017, vol. 22, no. 4, pp. 43–60. (in Russian)