{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:30:41Z","timestamp":1768519841002,"version":"3.49.0"},"reference-count":48,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T00:00:00Z","timestamp":1695254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>This article proposes a new method to inject backdoors in RSA (the public-key cryptosystem invented by Rivest, Shamir, and Adleman) and other cryptographic primitives based on the integer factorization problem for balanced semi-primes. The method relies on mathematical congruences among the factors of the semi-primes based on a large prime number, which acts as a \u201cdesigner key\u201d or \u201cescrow key\u201d. In particular, two different backdoors are proposed, one targeting a single semi-prime and the other one a pair of semi-primes. This article also describes the results of tests performed on a SageMath implementation of the backdoors.<\/jats:p>","DOI":"10.3390\/cryptography7030045","type":"journal-article","created":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T21:16:49Z","timestamp":1695331009000},"page":"45","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A New Idea for RSA Backdoors"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7492-3129","authenticated-orcid":false,"given":"Marco","family":"Cesati","sequence":"first","affiliation":[{"name":"Department of Civil Engineering and Computer Science Engineering (DICII), University of Rome Tor Vergata, Via del Politecnico 1, 00133 Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"key":"ref_1","unstructured":"Bannier, A., and Filiol, E. (2017, January 4\u20137). By-design Backdooring of Encryption System\u2014Can We Trust Foreign Encryption Algorithms?. Proceedings of the Black Hat Europe 2017, London, UK."},{"key":"ref_2","unstructured":"Strehle, R. (1994). Verschl\u00fcsselt: Der Fall Hans B\u00fchler, Werd Verlag."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Barker, E., and Kelsey, J. (2006). Recommendation for Random Number Generation Using Deterministic Random Bit Generators, National Institute for Standards and Technologies. Technical Report NIST Special Publication 800-90.","DOI":"10.6028\/NIST.SP.800-90"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-662-49301-4_17","article-title":"Dual EC: A standardized back door","volume":"Volume 9100","author":"Ryan","year":"2016","journal-title":"The New Codebreakers: Essays Dedicated to David Kahn on the Occasion of His 85th Birthday"},{"key":"ref_5","unstructured":"Leyden, J. (2021, August 17). FBI `Planted Backdoor\u2019 in OpenBSD. Available online: https:\/\/www.theregister.com\/2010\/12\/15\/openbsd_backdoor_claim."},{"key":"ref_6","unstructured":"Paul, R. (2021, August 17). FBI Accused of Planting Backdoor in OpenBSD IPSEC Stack. Available online: https:\/\/arstechnica.com\/information-technology\/2010\/12\/fbi-accused-of-planting-backdoor-in-openbsd-ipsec-stack\/."},{"key":"ref_7","unstructured":"Rosenstein, R.J. (2021, August 17). Deputy Attorney General Rod J. Rosenstein Delivers Remarks on Encryption at the United States Naval Academy, Available online: https:\/\/www.justice.gov\/opa\/speech\/deputy-attorney-general-rod-j-rosenstein-delivers-remarks-encryption-united-states-naval."},{"key":"ref_8","unstructured":"Levy, I., and Robinson, C. (2021, August 17). Principles for a More Informed Exceptional Access Debate. Available online: https:\/\/www.lawfareblog.com\/principles-more-informed-exceptional-access-debate."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bannier, A., and Filiol, E. (2017). Partition-Based Trapdoor Ciphers, IntechOpen.","DOI":"10.5772\/intechopen.70420"},{"key":"ref_10","unstructured":"Heninger, N., Durumeric, Z., Wustrow, E., and Halderman, J.A. (2012, January 8\u201310). Mining your Ps and Qs: Detection of widespread weak keys in network devices. Proceedings of the 21st USENIX Security Symposium (USENIX Security 11), Bellevue, WA, USA."},{"key":"ref_11","unstructured":"Sako, K., and Sarkar, P. (2013, January 1\u20135). Factoring RSA Keys from Certified Smart Cards: Coppersmith in the Wild. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2013, Bengaluru, India."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/09720529.2018.1564201","article-title":"Forty years of attacks on the RSA cryptosystem: A brief survey","volume":"22","author":"Mumtaz","year":"2019","journal-title":"J. Discret. Math. Sci. Cryptogr."},{"key":"ref_14","unstructured":"Arboit, G. (2008). Two Mathematical Security Aspects of the RSA Cryptosystem: Signature Padding Schemes and Key Generation with a Backdoor. [Ph.D. Thesis, School of Computer Science, McGill University]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-00468-1_1","article-title":"Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint","volume":"Volume 5443","author":"Jarecki","year":"2009","journal-title":"Proceedings of the Public Key Cryptography\u2014PKC 2009"},{"key":"ref_16","unstructured":"Cesati, M. (2022). A new idea for RSA backdoors. arXiv."},{"key":"ref_17","first-page":"155","article-title":"Finding a Small Root of a Univariate Modular Equation","volume":"Volume 1070","author":"Maurer","year":"1996","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201996"},{"key":"ref_18","first-page":"178","article-title":"Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known","volume":"Volume 1070","author":"Maurer","year":"1996","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201996"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s11416-020-00363-x","article-title":"Embedding asymmetric backdoors into the RSA key generator","volume":"17","author":"Markelova","year":"2021","journal-title":"J. Comput. Virol. Hacking Tech."},{"key":"ref_20","first-page":"89","article-title":"The Dark Side of \u201cBlack-Box\u201d Cryptography or: Should We Trust Capstone?","volume":"Volume 1109","author":"Koblitz","year":"1996","journal-title":"Proceedings of the Advances in Cryptology\u2014CRYPTO\u201996"},{"key":"ref_21","first-page":"62","article-title":"Kleptography: Using Cryptography against Cryptography","volume":"Volume 1233","author":"Fumy","year":"1997","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201997"},{"key":"ref_22","first-page":"51","article-title":"Approximate Integer Common Divisors","volume":"Volume 2146","year":"2001","journal-title":"Proceedings of the CaLC 2001"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/3-540-36563-X_28","article-title":"Simple Backdoors for RSA Key Generation","volume":"Volume 2612","author":"Joye","year":"2003","journal-title":"Proceedings of the Topics in Cryptology\u2014CT-RSA 2003"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2326","DOI":"10.1587\/transfun.E92.A.2326","article-title":"Simple Backdoors on RSA Modulus by Using RSA Vulnerability","volume":"E92-A","author":"Sun","year":"2009","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1049\/el:19930662","article-title":"Practical RSA trapdoor","volume":"29","author":"Anderson","year":"1993","journal-title":"Electron. Lett."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1049\/el:19930929","article-title":"Anderson\u2019s RSA Trapdoor Can Be Broken","volume":"29","year":"1993","journal-title":"Electron. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/978-3-540-79104-1_9","article-title":"RSA Moduli with a Predetermined Portion: Techniques and Applications","volume":"Volume 4991","author":"Chen","year":"2008","journal-title":"Proceedings of the Information Security Practice and Experience ISPEC 2008"},{"key":"ref_28","first-page":"191","article-title":"Number theoretic SETUPs for RSA like factoring based algorithms","volume":"3","author":"Patsakis","year":"2012","journal-title":"J. Inf. Hiding Multimed. Signal Process."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Nemec, M., Sys, M., Svenda, P., Klinec, D., and Matyas, V. (November, January 30). The Return of Coppersmith\u2019s Attack: Practical Factorization of Widely Used RSA Moduli. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS\u201917, New York, NY, USA.","DOI":"10.1145\/3133956.3133969"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","article-title":"An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance","volume":"24","author":"Pohlig","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/978-3-540-30574-3_2","article-title":"Malicious Cryptography: Kleptographic Aspects","volume":"Volume 3376","author":"Menezes","year":"2005","journal-title":"Proceedings of the Topics in Cryptology\u2014CT-RSA 2005"},{"key":"ref_32","first-page":"128","article-title":"A Space Efficient Backdoor in RSA and Its Applications","volume":"Volume 3897","author":"Preneel","year":"2006","journal-title":"Proceedings of the Selected Areas in Cryptography SAC 2005"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/978-3-540-79499-8_33","article-title":"A Timing-Resistant Elliptic Curve Backdoor in RSA","volume":"Volume 4990","author":"Pei","year":"2008","journal-title":"Proceedings of the Information Security and Cryptology"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms","volume":"31","author":"ElGamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","unstructured":"Rabin, M.O. (1979). Digitalized Signatures and Public-Key Functions as Intractable as Factorization, Massachusetts Institute of Technology. Technical Report."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Patsakis, C., and Alexandris, N. (2010, January 15\u201317). A New SETUP for Factoring Based Algorithms. Proceedings of the Sixth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, Darmstadt, Germany.","DOI":"10.1109\/IIHMSP.2010.57"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"W\u00fcller, S., K\u00fchnel, M., and Meyer, U. (2016, January 20\u201322). Information Hiding in the RSA Modulus. Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security, IH&MMSec\u201916, Vigo Galicia, Spain.","DOI":"10.1145\/2909827.2930804"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/3-540-39805-8_3","article-title":"Efficient Factoring Based on Partial Information","volume":"Volume 219","author":"Pichler","year":"1986","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201985"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_40","first-page":"131","article-title":"Finding small roots of univariate modular equations revisited","volume":"Volume 1355","author":"Darnell","year":"1997","journal-title":"Proceedings of the Cryptography and Coding"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1007\/978-3-540-24676-3_29","article-title":"Finding Small Roots of Bivariate Integer Polynomial Equations Revisited","volume":"Volume 3027","author":"Cachin","year":"2004","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2004"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Takagi, T., Wakayama, M., Tanaka, K., Kunihiro, N., Kimoto, K., and Duong, D.H. (2018). Mathematical Modelling for Next-Generation Cryptography: CREST Crypto-Math Project, Springer.","DOI":"10.1007\/978-981-10-5065-7"},{"key":"ref_43","unstructured":"Tonelli, A. (1891). Nachrichten von der K\u00f6niglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universit\u00e4t zu G\u00f6ttingen, Universit\u00e4t G\u00f6ttingen."},{"key":"ref_44","unstructured":"Shanks, D. Five Number Theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics, Winnipeg, MB, Canada."},{"key":"ref_45","unstructured":"Bernstein, D.J. (2023, September 17). Faster Square Roots in Annoying Finite Fields. Available online: http:\/\/cr.yp.to\/papers\/sqroot.pdf."},{"key":"ref_46","unstructured":"The Sage Developers (2023, September 17). SageMath, the Sage Mathematics Software System (Version 9.1). Available online: https:\/\/www.sagemath.org."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","article-title":"On a problem of Oppenheim concerning \u201cFactorisatio Numerorum\u201d","volume":"17","author":"Canfield","year":"1983","journal-title":"J. Number Theory"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1080\/00029890.1983.11971262","article-title":"On the Number of Multiplicative Partitions","volume":"90","author":"Hughes","year":"1983","journal-title":"Am. Math. Mon."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/3\/45\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:55:03Z","timestamp":1760129703000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/3\/45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,21]]},"references-count":48,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9]]}},"alternative-id":["cryptography7030045"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7030045","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,21]]}}}