КРИПТОГРАФИЧЕСКИЕ БЭКДОРЫ В КРИПТОСИСТЕМЕ ЧОРА-РИВЕСТА

Родион В. Плотников, Михаил А. Иванов

Аннотация


Цель работы – проверить гипотезу о том, что в ранцевую криптосистему
Чора-Ривеста (КЧР), перспективную для использования в постквантовой криптографии, возможно встроить сильный криптографический бэкдор. Учитывая глобальный процесс стандартизации пост-квантовых криптосистем, выявление возможных атак такого рода позволит предотвратить компрометацию секретного ключа пользователя Методология исследования базируется на применении концепции атак типа Secretly Embedded Trapdoor with Universal Protection (SETUP) и детальном анализе алгебраической структуры системы для определения способов встраивания скрытых криптографических каналов связи. В результате работы выявлены компоненты секретного ключа, пригодные для использования в качестве целевой информации, определены места встраивания скрытого криптографического канала в открытый ключ пользователя, и рассмотрены криптосистемы, которые может применять разработчик бэкдора. Разработаны и исследованы два варианта реализации сильных бэкдоров на основе модификации алгоритма генерации ключей. Первый вариант основан на манипуляции порядком следования элементов открытого ключа с использованием модификации криптосистемы RSA-OAEP со свойством неотличимости от случайных строк (IND$-CPA) для шифрования целевой информации. Второй вариант использует модификацию в виде механизма инкапсуляции ключа (KEM) самой КЧР для встраивания ключа генератора псевдослучайных чисел (ГПСЧ) в первый элемент открытого ключа. Приведены доказательства теоретической стойкости закладок и их полиномиальной неотличимости от изначальной реализации. Предложена KEM-модификация КЧР, и выдвинута гипотеза, что она обладает свойством IND$-CPA. Рассмотрены меры по обнаружению и предотвращению предлагаемых вариантов бэкдора. Полученные в работе результаты могут быть учтены при стандартизации КЧР.

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


Криптосистема Чора-Ривеста, криптографический бэкдор, клептография, SETUP, постквантовая криптография, ранцевая криптосистема, открытый ключ, генерация ключей, скрытый канал

Полный текст:

PDF

Литература


1. Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., Waller, N. (2025). Status report on the fourth round of the NIST post-quantum cryptography standardization process. National Institute of Standards and Technology. DOI: https://doi.org/10.6028/NIST.IR.8545.

2. Díaz, R.D., Hernández-Álvarez, L., Encinas, L.H., Queiruga-Dios, A. (2021). Chor-Rivest Knapsack Cryptosystem in a Post-quantum World. In: Daimi, K., Arabnia, H.R., Deligiannidis, L., Hwang, MS., Tinetti, F.G. (eds) Advances in Security, Networks, and Internet of Things. Transactions on Computational Science and Computational Intelligence. Springer, Cham. DOI: https://doi.org/10.1007/978-3-030-71017-0_6.

3. Brier, É., Géraud, R., Naccache, D. (2017). Exploring Naccache-Stern Knapsack Encryption. In: Farshim, P., Simion, E. (eds) Innovative Security Solutions for Information Technology and Communications. SecITC 2017. Lecture Notes in Computer Science(), vol 10543. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-69284-5_6.

4. Schneider, C.R.T. (2025). Backdoors in cryptography [Ruhr-Universität Bochum]. DOI: https://doi.org/10.13154/294-12053.

5. Householder, A., Wassermann, G., Manion, A., King, C. (2020). CERT Guide to Coordinated Vulnerability Disclosure. Carnegie Mellon University. DOI: https://doi.org/10.1184/R1/12367340.V1.

6. Иванов, М. (2025). Идея бэкдора в ранцевой криптосистеме. Безопасность информационных технологий, 32(3), 112-120. DOI: http://dx.doi.org/10.26583/bit.2025.3.09.
Ivanov, M. (2025). An idea for knapsack cryptosystem backdor. IT Security (Russia), 32(3), 112-120. DOI: http://dx.doi.org/10.26583/bit.2025.3.09 (in Russian).

7. Young, A. L., Yung, M. (2004). Cryptography: Malicious Cryptography – Exposing Cryptovirology. Computer Law & Security Report, 20(5), 430. DOI: https://doi.org/10.1016/S0267-3649(04)00079-2.

8. Hemmert, T. (2022). How to backdoor LWE-like cryptosystems (No. 2022/1381). Cryptology ePrint Archive. URL: https://eprint.iacr.org/2022/1381 (accessed: 21.04.2026).

9. Hemmert, T., May, A., Mittmann, J., Schneider, C.R.T. (2022). How to Backdoor (Classic) McEliece and How to Guard Against Backdoors. In: Cheon, J.H., Johansson, T. (eds) Post-Quantum Cryptography. PQCrypto 2022. Lecture Notes in Computer Science, v.13512. Springer, Cham. DOI: https://doi.org/10.1007/978-3-031-17234-2_2.

10. Маркелова, А.В. (2022). Клептографические (алгоритмические) закладки в генераторе ключей RSA. Прикладная дискретная математика, (55), 14-34. DOI: https://doi.org/10.17223/20710410/55/2.
Markelova, A.V. (2022). Kleptographic (algorithmic) backdoors in the RSA key generator. Applied Discrete Mathematics, (55), 14-34. DOI: https://doi.org/10.17223/20710410/55/2 (in Russian).

11. Shamir, A. (1982). A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. 23rd Annual Symposium on Foundations of Computer Science (Sfcs 1982), 145-152. DOI: https://doi.org/10.1109/SFCS.1982.5.

12. Lagarias, J.C., Odlyzko, A.M. (1985). Solving low-density subset sum problems. Journal of the ACM, 32(1),
229-246. DOI: https://doi.org/10.1145/2455.2461.

13. Chor, B., Rivest, R.L. (1988). A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, v. 34, no. 5, pp. 901-909. DOI: https://doi.org/10.1109/18.21214.

14. Vaudenay, S. (1998). Cryptanalysis of the Chor-Rivest cryptosystem. In: Krawczyk, H. (eds) Advances in Cryptology – CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, v. 1462. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/BFb0055732.

15. Schnorr, C. P., Hörner, H. H. (1995). Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. I In: Guillou, L.C., Quisquater, JJ. (eds) Advances in Cryptology – EUROCRYPT ’95. EUROCRYPT 1995. Lecture Notes in Computer Science, vol 921. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/3-540-49264-X_1.

16. Barker, E. (2020). Recommendation for key management: part 1 - general (NIST SP 800-57pt1r5). National Institute of Standards and Technology. DOI: https://doi.org/10.6028/NIST.SP.800-57pt1r5.

17. Nojima, R., Imai, H., Kobara, K. et al. Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptogr. 49, 289-305 (2008). DOI: https://doi.org/10.1007/s10623-008-9175-9.

18. Menezes, A. J., Van Oorschot, P. C., Vanstone, S. A. (2018). Handbook of Applied Cryptography (1st ed.). CRC Press. DOI: https://doi.org/10.1201/9780429466335.

19. Russell, A., Tang, Q., Yung, M., Zhou, H.-S. (2017). Generic Semantic Security against a Kleptographic Adversary. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security,
907–922. DOI: https://doi.org/10.1145/3133956.3133993.




DOI: http://dx.doi.org/10.26583/bit.2026.4.08

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.