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

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

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

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

Литература

1. McEliece, R.J. A Public-Key Cryptosystem Based on Algebraic Coding Theory / R.J. McEliece // DSN Progress Report. - 1978. - P. 42-44.
2. Sidel'nikov, V.M. On an Encoding System Constructed on the Basis of Generalized Reed - Solomon Codes / V.M. Sidel'nikov, S.O. Shestakov // Discrete Mathematics and Applications. - 1992. - V. 2, № 4. - P. 439-444.
3. Деундяк, В.М. Модификация криптоаналитического алгоритма Сидельникова - Шестакова для обобщенных кодов Рида - Соломона и ее программная реализация / В.М. Деундяк, М.А. Дружинина, Ю.В. Косолапов // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. - 2006. - № 4. - С. 15-19.
4. Wieschebrink, C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes / C. Wieschebrink // Proceedings of Third International Workshop. - Berlin, 2010. - P. 61-72.
5. Minder, L. Cryptanalysis of the Sidelnikov cryptosystem / L. Minder, A. Shokrollahi // Advances in Cryptology - EUROCRYPT 2007, Lecture Notes Computer Science. - 2007. - № 4515. - P. 347-360.
6. Бородин, М.А. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида - Маллера / М.А. Бородин, И.В. Чижов // Дискретная математика. - 2014. - Т. 26, № 1. - С. 10-20.
7. Деундяк, В.М. Криптосистема на индуцированных групповых кодах / В.М. Деундяк, Ю.В. Косолапов // Моделирование и анализ информационных систем. - 2016. - Т. 23, № 2. - P. 137-152.
8. Косолапов, Ю.В. Об алгоритме расщепления носителя для индуцированных кодов / Ю.В. Косолапов, А.Н. Шигаев // Моделирование и анализ информационных систем. - 2018. - Т. 25, № 3. - P. 276-290.
9. Сидельников, В.М. Теория кодирования / В.М. Сидельников. - М.: Физматлит, 2008.
10. Morelos-Zaragoza, R.H. The Art of Error Correcting Coding / R.H. Morelos-Zaragoza. - Chichester, West Sussex: John Wiley & Sons, 2006.
11. Massey, J.L. Minimal Codewords and Secret Sharing / J.L. Massey // Proceeding of 6th Joint Swedish-Russian Workshop on Information Theory. - 1993. - P. 276-279.
12. Августинович, С.В. Об автоморфизмах линейных кодов над простым полем / С.В. Августинович, Е.В. Горкунов // Сибирские электронные математические известия. - 2017. - № 14. - С. 210-217.
13. Sendrier, N. On the Concatenated Structure of a Linear Code / N. Sendrier // Applicable Algebra in Engineering, Communication and Computing. - 1998. - V. 9, № 3. - P. 221-242.
14. Berger, T.P. Construction of New MDS Codes from Gabidulin Codes / T.P. Berger, A.V. Ourivski // Proceeding of ACCT'9. - 2004. - С. 40-47.
15. Assmus, E.F. The Category of Linear Codes / E.F. Assmus // IEEE Transaction on Information Theory. - 1998. - V. 44, № 2. - P. 612-629.
16. Fripertinger, H. Isometry Classes of Indecomposable Linear Codess / H. Fripertinger, A. Kerber // Lecture Notes in Computer Science. - 1995. - V. 948. - P. 194-204.
17. Сидельников, В.М. Открытое шифрование на основе двоичных кодов Рида - Маллера / В.М. Сидельников // Дискретная математика. - 1994. - Т. 6, № 2. - С. 3-20.
18. Deundyak, V.M. On the Berger - Loidreau Cryptosystem on the Tensor Product of Codes / V.M. Deundyak, Yu.V. Kosolapov // Journal of Computational and Engineering Mathematics. - 2018. - V. 5, № 2. - P. 16-33.
19. Красавин, А.А. Использование модифицированной (u|u+v)-конструкции в криптосистеме McEliece / А.А. Красавин // Труды МФТИ. - 2018. - Т. 10, № 2. - С. 189-191.
20. Kabatiansky, G. A New Code-Based Cryptosystem via Pseudorepetition of Codes / G. Kabatiansky, C. Tavernier // Proceedings of ACCT XVI. - 2018. - P. 189-191.
21. Деундяк, В.М. Использование тензорного произведения кодов Рида - Маллера в асимметричной криптосистеме типа Мак-Элиса и анализ ее стойкости к атакам на шифрограмму / В.М. Деундяк, Ю.В. Косолапов // Вычислительные технологии. - 2017. - Т. 22, № 4. - С. 43-60.