ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-2-324-331ntv-165Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEСовременные вариации криптосистем Мак-Элиса и НидеррайтераModern variations of McEliece and Niederreiter cryptosystemshttps://orcid.org/0000-0002-5544-2434ДавыдовВ. В.DavydovV. V.

Давыдов Вадим Валерьевич — преподаватель 

Санкт-Петербург, 197101 

 sc 57203909696 

Vadim V. Davydov — Lecturer 

197101, Saint Petersburg 

vvdavydov@itmo.ruhttps://orcid.org/0000-0002-1067-7483БеляевВ. В.BeliaevV. V.

Беляев Владислав Владиславович — лаборант 

Санкт-Петербург, 197101 

 sc 57217737570 

Vladislav V. Beliaev — Laboratory Assistant

197101, Saint Petersburg 

 sc 57217737570 

v.beliaev@niuitmo.ruhttps://orcid.org/0000-0002-0191-1178КустовЕ. Ф.KustovE. F.

Кустов Елизар Филаретович – аспирант 

Санкт-Петербург, 197101 

Elizar F. Kustov – PhD Student

197101, Saint Petersburg 

efkustov@itmo.ruhttps://orcid.org/0000-0003-1823-7877ЛеевикА. Г.LeevikA. G.

 Леевик Антон Георгиевич — инженер 

 СанктПетербург, 197101 

 sc 57219714571 

Anton G. Leevik — Engineer

197101, Saint Petersburg 

 sc 57219714571 

agleevik@niuitmo.ruhttps://orcid.org/0000-0002-0924-6221БеззатеевС. В.BezzateevS. V.

Беззатеев Сергей Валентинович — доктор технических наук, доцент, профессор;  заведующий кафедрой 

 Санкт-Петербург, 197101 

 Санкт-Петербург, 190000 

 sc 6602425996 

Sergey V. Bezzateev — D. Sc., Full Professor, Associate Professor;  Head of department 

197101, Saint Petersburg 

190000, Saint Petersburg 

 sc 6602425996 

bsv@aanet.ruУниверситет ИТМО;РоссияITMO UniversityRussian FederationУниверситет ИТМОРоссияITMO UniversityRussian FederationУниверситет ИТМО; Санкт-Петербургский государственный университет аэрокосмического приборостроенияРоссияITMO University; Saint-Petersburg State University of Aerospace InstrumentationRussian Federation202214122024222324331Copyright © Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В., 20242024Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В.Davydov V.V., Beliaev V.V., Kustov E.F., Leevik A.G., Bezzateev S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/165

Предмет исследования. Исследованы классические криптосистемы, предложенные Робертом Мак-Элисом в 1978 году и Гарольдом Нидеррайтером в 1986 году и их современные вариации. Метод. Выполнен детальный обзор пяти кодовых криптосистем с открытым ключом. Основные результаты. Показано, что некоторые из современных интерпретаций классических систем Мак-Элиса и Нидеррайтера имеют значительные недостатки. Установлено, что допущен ряд неточностей в описании криптосистемы XGRS на расширенных кодах Рида–Соломона, которая не обеспечивает заявленного уровня безопасности к атаке по информационным совокупностям. Продемонстрировано, что время генерации ключей и время расшифрования в современных кодовых криптосистемах достаточно велико, а открытый и секретный ключи занимают большой объем памяти. Практическая значимость. Выявленные неточности в рассмотренных схемах могут быть учтены при их улучшении и коррекции, а также при построении более точной оценки их уровня безопасности и эффективности. Представленные в работе кодовые криптосистемы могут рассматриваться как стандарты постквантовой криптографии и использоваться для защиты данных после появления мощного квантового компьютера. К

Classical cryptosystems proposed by Robert McEliece (1978) and Harold Niederreiter (1986) and their modern variations are studied. A detailed review of five code-based public key cryptosystems has been presented. It is shown that some of the modern interpretations of the classical McEliece and Niederreiter cryptosystems have significant issues. In particular, it has been established that the XGRS cryptosystem based on extended Reed-Solomon codes does not provide the declared level of security against the information set decoding attack, and also has a number of inaccuracies. It is shown that the time of key generation and decryption in modern cryptosystems is quite large, and the public and private keys take up a large amount of memory. The inaccuracies of the considered schemes revealed in this work can be used to improve and adjust the systems, as well as to build a more accurate assessment of their security level and efficiency. The presented cryptosystems can be considered as standards for post-quantum cryptography and can be used to protect data after development of powerful quantum computers.

постквантовая криптографиякриптосистема Мак-Элисакриптосистема Нидеррайтерадвоичные коды Гоппырасширенные коды Рида–Соломонаpost-quantum cryptographyMcEliece cryptosystemNiederreiter cryptosystembinary Goppa codesgeneralized Reed-Solomon codesРабота выполнена в рамках НИР № 620164 Университета ИТМО. Работа частично финансировалась Федеральной программой академического лидерства Приоритет 2030. Выражается благодарность Жан-Мишелю Дакуо за помощь в программной реализации.The work is made as a part of research work no. 620164 at ITMO University. This project has received financial support from the Priority 2030 Federal Academic Leadership Program. We thank Jean-Michelle Dakuo for his help in programming implementation.ReferencesShor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 1994. P. 124–134. https://doi.org/10.1109/SFCS.1994.365700Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 1994. P. 124–134. https://doi.org/10.1109/SFCS.1994.365700McEliece R.J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report 42-44, 1978. P. 114–116.McEliece R.J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42–44, 1978, pp. 114–116.Гоппа В.Д. Рациональное представление кодов и (L,g)-коды // Проблемы передачи информации. 1971. Т. 7. № 3. С. 41–49.Goppa V.D. A Rational Representation of Codes and (L,g)-Codes. Problems Information Transmission, 1971, vol. 7, no.3. pp. 223–229.Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems of Control and Information Theory. 1986. V. 15. N 2. P. 159–166.Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 1986, vol. 15, no. 2, pp. 159–166.Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. С. 506–507.Mac Williams F.J., Sloane N.J.A. The theory of Error-Correcting Codes. Amsterdam, 1977.Сидельников В.М., Шестаков С.О. О системе шифрования, построенной на основе обобщенных кодов Рида–Соломона // Дискретная математика. 1992. Т. 4. № 3. С. 57–63.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.Peters C. Information-set decoding for linear codes over Fq // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. V. 6061. P. 81–94. https://doi.org/10.1007/978-3-642-12929-2_7Peters C. Information-set decoding for linear codes over Fq // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. V. 6061. P. 81–94. https://doi.org/10.1007/978-3-642-12929-2_7Sidelnikov V.M. A public-key cryptosystem based on binary ReedMuller codes // Discrete Mathematics and Applications. 1994. V. 4. N 3. P. 191–207. https://doi.org/10.1515/dma.1994.4.3.191Sidelnikov V.M. A public-key cryptosystem based on binary ReedMuller codes // Discrete Mathematics and Applications. 1994. V. 4. N 3. P. 191–207. https://doi.org/10.1515/dma.1994.4.3.191Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2007. V. 4515. P. 347–360. https://doi.org/10.1007/978-3-540-72540-4_20Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2007. V. 4515. P. 347–360. https://doi.org/10.1007/978-3-540-72540-4_20Gabidulin E.M. Public-key cryptosystems based on linear codes: Report 95-30 / Delft University of Technology, Faculty of Technical Mathematics and Informatics, 1995. P. 17–31.Gabidulin E.M. Public-key cryptosystems based on linear codes: Report 95-30 / Delft University of Technology, Faculty of Technical Mathematics and Informatics, 1995. P. 17–31.Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes // Journal of Cryptology. 2008. V. 21. N 2. P. 280– 301. https://doi.org/10.1007/s00145-007-9003-9Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes // Journal of Cryptology. 2008. V. 21. N 2. P. 280– 301. https://doi.org/10.1007/s00145-007-9003-9Baldi M., Chiaraluce F. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2007. P. 2591–2595. https://doi.org/10.1109/ISIT.2007.4557609Baldi M., Chiaraluce F. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2007. P. 2591–2595. https://doi.org/10.1109/ISIT.2007.4557609Otmani A., Tillich J.P., Dallot L. Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes // Proc. of the First International Conference on Symbolic Computation and Cryptography. LMIB Beihang University, 2008. P. 69–81.Otmani A., Tillich J.P., Dallot L. Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes // Proc. of the First International Conference on Symbolic Computation and Cryptography. LMIB Beihang University, 2008. P. 69–81.Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes // Designs, Codes and Cryptography. 1996. V. 8. N 3. P. 293–307. https://doi.org/10.1023/A:1027351723034Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes // Designs, Codes and Cryptography. 1996. V. 8. N 3. P. 293–307. https://doi.org/10.1023/A:1027351723034Faure C., Minder L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes // Proc. of the 11th International Workshop on Algebraic and Combinatorial Coding Theory. 2008. P. 99–107.Faure C., Minder L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes // Proc. of the 11th International Workshop on Algebraic and Combinatorial Coding Theory. 2008. P. 99–107.Loidreau P. Strengthening McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2000. V. 1976. P. 585–598. https://doi.org/10.1007/3-540-44448-3_45Loidreau P. Strengthening McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2000. V. 1976. P. 585–598. https://doi.org/10.1007/3-540-44448-3_45Kobara K., Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC // IEEE Transactions on Information Theory. 2003. V. 49. N 12. P. 3160–3168. https://doi.org/10.1109/TIT.2003.820016Kobara K., Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC // IEEE Transactions on Information Theory. 2003. V. 49. N 12. P. 3160–3168. https://doi.org/10.1109/TIT.2003.820016Bernstein D.J., Lange T., Peters C. Attacking and defending the McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. V. 5299. P. 31–46. https://doi.org/10.1007/978-3-540-88403-3_3Bernstein D.J., Lange T., Peters C. Attacking and defending the McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. V. 5299. P. 31–46. https://doi.org/10.1007/978-3-540-88403-3_3Bernstein D.J. et al. Classic McEliece: conservative code-based cryptography / NIST. 2017. 20. Khathuria K., Rosenthal J., Weger V. Encryption scheme based on expanded reed-solomon codes // Advances in Mathematics of Communications. 2021. V. 15. N 2. P. 207–218. https://doi.org/10.3934/amc.2020053Bernstein D.J. et al. Classic McEliece: conservative code-based cryptography / NIST. 2017. 20. Khathuria K., Rosenthal J., Weger V. Encryption scheme based on expanded reed-solomon codes // Advances in Mathematics of Communications. 2021. V. 15. N 2. P. 207–218. https://doi.org/10.3934/amc.2020053Reed I.S., Solomon G. Polynomial codes over certain finite fields // Journal of the Society for Industrial and Applied Mathematics. 1960. V. 8. N 2. P. 300–304. https://doi.org/10.1137/0108018Reed I.S., Solomon G. Polynomial codes over certain finite fields // Journal of the Society for Industrial and Applied Mathematics. 1960. V. 8. N 2. P. 300–304. https://doi.org/10.1137/0108018Ivanov F., Kabatiansky G., Krouk E., Rumenko N. A new code-based cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2020. V. 12087. P. 41–49. https://doi.org/10.1007/978-3-030-54074-6_3Ivanov F., Kabatiansky G., Krouk E., Rumenko N. A new code-based cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2020. V. 12087. P. 41–49. https://doi.org/10.1007/978-3-030-54074-6_3Berlekamp E., McEliece R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. 1978. V. 24. N 3. P. 384–386. https://doi.org/10.1109/TIT.1978.1055873Berlekamp E., McEliece R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. 1978. V. 24. N 3. P. 384–386. https://doi.org/10.1109/TIT.1978.1055873Augot D., Finiasz M., Sendrier N. A family of fast syndrome based cryptographic hash functions // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. V. 3715. P. 64–83. https://doi.org/10.1007/11554868_6Augot D., Finiasz M., Sendrier N. A family of fast syndrome based cryptographic hash functions // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2005. V. 3715. P. 64–83. https://doi.org/10.1007/11554868_6Azouaoui A., Chana I., Belkasmi M. Efficient information set decoding based on genetic algorithms // International Journal of Communications, Network and System Sciences. 2012. V. 5. N 7. P. 423–429. https://doi.org/10.4236/ijcns.2012.57052Azouaoui A., Chana I., Belkasmi M. Efficient information set decoding based on genetic algorithms // International Journal of Communications, Network and System Sciences. 2012. V. 5. N 7. P. 423–429. https://doi.org/10.4236/ijcns.2012.57052Gauthier V., Otmani A., Tillich J.P. A Distinguisher-based attack on a variant of McEliece's cryptosystem based on Reed-Solomon codes // arXiv.org. 2012. arXiv:1204.6459. https://doi.org/10.48550/ arXiv.1204.6459Gauthier V., Otmani A., Tillich J.P. A Distinguisher-based attack on a variant of McEliece's cryptosystem based on Reed-Solomon codes // arXiv.org. 2012. arXiv:1204.6459. https://doi.org/10.48550/ arXiv.1204.6459Torres R.C., Sendrier N. Analysis of information set decoding for a sub-linear error weight // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2016. V. 9606. P. 144–161. https://doi.org/10.1007/978-3-319-29360-8_10Torres R.C., Sendrier N. Analysis of information set decoding for a sub-linear error weight // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2016. V. 9606. P. 144–161. https://doi.org/10.1007/978-3-319-29360-8_10Lee Y., Cho J., Kim Y.-S., No J.-S. Cryptanalysis of the IvanovKabatiansky-Krouk-Rumenko cryptosystems // IEEE Communications Letters. 2020. V. 24. N 12. P. 2678–2681. https://doi.org/10.1109/LCOMM.2020.3019054Lee Y., Cho J., Kim Y.-S., No J.-S. Cryptanalysis of the IvanovKabatiansky-Krouk-Rumenko cryptosystems // IEEE Communications Letters. 2020. V. 24. N 12. P. 2678–2681. https://doi.org/10.1109/LCOMM.2020.3019054Patterson N. The algebraic decoding of Goppa codes // IEEE Transactions on Information Theory. 1975. V. 21. N 2. P. 203–207. https://doi.org/10.1109/TIT.1975.1055350Patterson N. The algebraic decoding of Goppa codes // IEEE Transactions on Information Theory. 1975. V. 21. N 2. P. 203–207. https://doi.org/10.1109/TIT.1975.1055350Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.Berlekamp E.R. Non-binary BCH decoding. North Carolina State University. Dept. of Statistics, 1966.

The authors declare that there are no conflicts of interest present.