ГлавнаяАрхивКлептографические (алгоритмические) закладки в генераторе ключей RSA

Клептографические (алгоритмические) закладки в генераторе ключей RSA | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/2

Рассмотрены основные виды алгоритмических закладок. Представлен способ построения асимметричных клептографических закладок в генераторе ключей RSA, позволяющий владельцу ключа закладки (разработчику или авторизованной спецслужбе) получать доступ к пользовательскому ключу, сгенерированному инфицированным алгоритмом. Сформулированы теоремы, иллюстрирующие работоспособность описанных алгоритмов, оценена вычислительная сложность этих алгоритмов. Продемонстрирована стойкость построенных закладок к некоторым классам атак даже при условии, что противник знает используемые методы и имеет доступ к исходному коду ключевого генератора.
  • Title Клептографические (алгоритмические) закладки в генераторе ключей RSA
  • Headline Клептографические (алгоритмические) закладки в генераторе ключей RSA
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 55
  • Date:
  • DOI 10.17223/20710410/55/2
Ключевые слова
RSA, клептография, алгоритмическая закладка, лазейка, клептографическая закладка, бэкдор
Авторы
Ссылки
Young A. and Yung M. Kleptography: using cryptography against cryptography // EUROCRYPT’97. LNCS. 1998. V.1233. P.62-74.
Anderson R. J. Practical RSA trapdoor // Electronics Lett. 1993. V.29. No. 11. P.995.
FBI ’planted backdoor’ in OpenBSD. 2010. https://www.theregister.com/2010/12/15/openbsd\\_backdoor\\_claim.
Жуков А. Е. Криптосистемы со встроенными лазейками // BYTE/Россия. 2007. №2. С. 45-51.
Bernstein D. J, Lange T., and Niederhagen R. Dual EC: A standardized back door // The New Codebreakers. LNCS. 2016. V.9100. P.256-281.
Desmedt Y. Abuses in cryptography and how to fight them //LNCS. 1990. V. 403. P. 375-389.
Lenstra A. K. Generating RSA moduli with a predetermined portion // LNCS. 1998. V. 1514. P. 1-10.
Crepeau C. and Slakmon A. Simple backdoors for RSA key generation // LNCS. 2003. V. 2612. P. 403-416.
Blaze M. Protocol failure in the Escrowed Encryption Standard // Proc. CCS’94. 1994. http://www.mattblaze.org/papers/eesproto.pdf.
Deputy Attorney General Rod J. Rosenstein Delivers Remarks on Encryption at the United States Naval Academ. Annapolis, MD, October 10, 2017. https://www.justice.gov/opa/speech/deputy-attorney-general-rod-j-rosenstein-delivers-remarks-encryption-united-states-naval.
Levy I. and Robinson C. Principles for a More Informed Exceptional Access Debate. 2018. https://www.lawfareblog.com/principles-more-informed-exceptional-access-debate.
Barker E. and Kelsey J. NIST Special Publication 800-90. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. June 2006. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90.pdf.
Menn J. Exclusive: Secret contract tied NSA and security industry pioneer. December 21, 2013. https://www.reuters.com/article/us-usa-security-rsa/exclusive-secret-contract-tied-nsa-and-security-industry-pioneer-idUSBRE9BJ1C220131220.
Thomson K. Reflection on trusting trust // Comm. ACM. 1984. V. 27. No. 8. P. 761-763.
Schneier B. Evaluating the GCHQ Exceptional Access Proposal. January 17, 2019. https: //www.lawfareblog.com/evaluating-gchq- exceptional-access-proposal.
Markelova A. V. Embedding asymmetric backdoors into the RSA key generator //j.Computer Virology Hacking Techniques. 2021. No. 17. P.37-46.
Методический документ. Методика определения угроз безопасности информации. Утвержден ФСТЭК России 5 февраля 2021 г.
Словарь криптографических терминов / под ред. Б. А. Погорелова, В. Н. Сачкова. М.: Изд-во МЦМНО, 2006.
Жуков А. Е., Маркелова А. В. Криптография и клептография: скрытые каналы и лазейки в криптоалгоритмах // Информационная безопасность. 2019. №1. C. 36-41.
Young A. and Yung M. Malicious Cryptography. Exposing Cryptovirology. Wiley Publ., 2004. 392 p.
ГОСТ Р 53113.1-2008. Информационная технология. Защита информационных технологий и автоматизированных систем от угроз информационной безопасности, реализуемых с использованием скрытых каналов. Ч. 1. Общие положения. М.: Стандартинформ, 2018.
Rivest R. L., Shamir A., and Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Comm. ACM. 1978. V. 21. P.120-126.
Жуков А. Е., Маркелова А. В. Криптография и клептография. Скрытые каналы и клептографические закладки на их основе в криптосистеме RSA // Защита информации. Инсайд. 2020. №2(92). C.58-67.
Svenda P., Nemec M., Sekan P., et al. The million-key question - investigating the origins of RSA public keys // Proc. 25th USENIX Security’16. USENIX Association, 2016. P.893-910.
Nemec M., Sys M., Svenda P., et al. The return of Coppersmith’s attack: Practical factorization of widely used RSA moduli // Proc. CCS’17. ACM, 2017. P. 1631-1648.
Kaliski B. S. Anderson’s RSA trapdoor can be broken // Electronics Lett. 1993. V. 29. No. 15. P. 1387.
Дэвенпорт Г. Мультипликативная теория чисел. М.: Наука, 1971. 200с.
Кнут Д. Искусство программированя. Т. 2. Получисленные алгоритмы. 3-е изд. М.: Вильямс, 2001. 832 с.
Young A. and Yung M. The dark side of black-box cryptography // CRYPTO’96. LNCS. 1997. V. 1109. P.89-103.
Linnik Yu. V. On the least prime in an arithmetic progression I. The basic theorem // Матем. сб. 1944. Т. 15(57). №2. С. 139-178.
Клептографические (алгоритмические) закладки в генераторе ключей RSA | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/2
Клептографические (алгоритмические) закладки в генераторе ключей RSA | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/2