Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An optimal bound for factoring unbalanced RSA moduli by solving Generalized Implicit Factorization Problem

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The integer factorization problem, concerning the product of two primes N = pq, has been a focal point for researchers since its rise to prominence with the RSA algorithm, a renowned public key scheme. It is well known that the integer factorization problem can be solved by the Number Field Sieve (NFS) algorithm in sub-exponential time, this challenge may also find resolution in polynomial time under certain conditions for the primes. In this paper, we revisit the problem of factoring RSA moduli with the implicit hint, where the implicit hint is the shared bits of primes. As for k RSA moduli, we present a novel implicit factorization approach applicable when the unknown multiples ap of the prime factors p share a certain number of most significant bits (MSBs) or least significant bits (LSBs). By drawing inspiration from addressing the Approximate Common Divisor Problem (ACDP), we transform this problem into solving the small roots of k-1 trivariate polynomials. To compute these small roots, we employ Coppersmith’s method to construct a lattice basis for the modular polynomials. We modify the lattice basis by introducing new variables, achieving an optimal bound in the MSB and LSB cases. Our attack breaks the RSA system and improves upon all previous attacks on such variants when the amount of the shared bits is sufficiently large. Concluding our paper, we meticulously validate the theoretical analysis results, with experimental data confirming the full practical feasibility of our attack on such an RSA variant system.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Data Availability

No datasets were generated or analysed during the current study.

References

  1. Adeniyi EA, Falola PB, Maashi MS et al (2022) Secure sensitive data sharing using RSA and ElGamal cryptographic algorithms with hash functions. Information 13(10):442

    Article  Google Scholar 

  2. Aono Y (2009) A New Lattice Construction for Partial Key Exposure Attack for RSA. Public Key Cryptography-PKC 2009: 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings 12. Springer Berlin Heidelberg: 34-53

  3. Barenghi A, Carrera D, Mella S et al (2022) Profiled side channel attacks against the RSA cryptosystem using neural networks. J Inf Secur Appl 66:103122

    Google Scholar 

  4. Bauer A, Jaulmes E, Lomné V (2014) Side-Channel Attack Against RSA Key Generation Algorithms. Cryptographic Hardware and Embedded Systems-CHES, et al (2014) 16th International Workshop, Busan, South Korea, September 23–26, 2014. Proceedings 16. Springer, Berlin Heidelberg:223–241

  5. Boneh D (1999) Twenty years of attacks on the RSA cryptosystem. Not AMS 46(2):203–213

    MathSciNet  Google Scholar 

  6. Boneh D, Durfee G (2000) Cryptanalysis of RSA with private key d less than N/sup 0.292. IEEE trans Inf Theory 46(4):1339–1349

    Article  Google Scholar 

  7. Brumley D, Boneh D (2005) Remote timing attacks are practical. Comput Netw 48(5):701–716

    Article  Google Scholar 

  8. Carmon E, Seifert JP, Wool A (2017) Photonic Side Channel Attacks Against RSA. (2017) IEEE International Symposium on Hardware Oriented Security and Trust (HOST). IEEE:74–78

  9. Chen Z, Ye G (2022) An asymmetric image encryption scheme based on hash SHA-3, RSA and compressive sensing. Optik 267:169676

    Article  Google Scholar 

  10. Coppersmith D (1996) Finding a Amall Root of a Bivariate Integer Equation; Factoring with High Bits Known. International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg: 178–189

  11. Coppersmith D (1996) Finding a Small Root of a Univariate Modular Equation. International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg: 155–165

  12. Coppersmith D (1997) Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J cryptol 10(4):233–260

    Article  MathSciNet  Google Scholar 

  13. Coron JS, May A (2007) Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J Cryptol 20:39–50

    Article  MathSciNet  Google Scholar 

  14. Cohn H, Heninger N (2013) Approximate common divisors via lattices. Open B Ser 1(1):271–293

    Article  MathSciNet  Google Scholar 

  15. Ernst M, Jochemsz E, May A et al (2005) Partial Key Exposure Attacks on RSA Up to Full Size Exponents. Advances in Cryptology-EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings 24. Springer Berlin Heidelberg: 371–386

  16. Faugère JC, Marinier R, Renault G (2010) Implicit Factoring with Shared Most Significant and Middle Bits. Public Key Cryptography-PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings 13. Springer Berlin Heidelberg: 70–87

  17. Feng Y, Nitaj A, Pan Y (2023) Generalized Implicit Factorization Problem. International Conference on Selected Areas in Cryptography. Cham: Springer Nature Switzerland: 369–384

  18. Feng Y, Nitaj A, Pan Y (2024) Partial prime factor exposure attacks on some RSA variants. Theor Comput Sci 999:114549

    Article  MathSciNet  Google Scholar 

  19. Ghayvat H, Pandya S, Bhattacharya P et al (2021) CP-BDHCA: Blockchain-based Confidentiality-Privacy preserving Big Data scheme for healthcare clouds and applications. IEEE J Biomed Health Inform 26(5):1937–1948

    Article  Google Scholar 

  20. Howgrave-Graham N (1997) Finding Small Roots of Univariate Modular Equations Revisited. IMA International Conference on Cryptography and Coding. Springer, Berlin, Heidelberg: 131–142

  21. Kamel Ariffin MR, Abubakar SI, Yunos F et al (2018) New cryptanalytic attack on RSA modulus N= pq using small prime difference method. Cryptography 3(1):2

    Article  Google Scholar 

  22. Kota C M, Aissi C (2022) Implementation of the RSA algorithm and its cryptanalysis. 2002 GSW

  23. Kumar R, Liu X, Suresh V et al (2021) A time-/frequency-domain side-channel attack resistant AES-128 and RSA-4K crypto-processor in 14-nm CMOS. IEEE J Solid-State Circuits 56(4):1141–1151

    Article  Google Scholar 

  24. Lenstra AK, Lenstra Jr HW, Manasse MS, et al. (1990) The Number Field Sieve. Proceedings of the twenty-second annual ACM symposium on Theory of computing: 564–572

  25. Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math ann 261:515–534

    Article  MathSciNet  Google Scholar 

  26. Lu Y, Zhang R, Lin D (2013) Improved bounds for the implicit factorization problem. Adv Math Commun 7:243–251

    Article  MathSciNet  Google Scholar 

  27. Lu Y, Peng L, Zhang R, (2016) Towards Optimal Bounds for Implicit Factorization Problem. Selected Areas in Cryptography-SAC (2015) 22nd International Conference, Sackville, NB, Canada, August 12–14, 2015, Revised Selected Papers 22. Springer International Publishing 2016:462–476

  28. Luo P, Zhou HJ, Wang DS et al (2009) Cryptanalysis of RSA for a special case with d> e. Sci China Ser F: Inf Sci 52(4):609–616

    MathSciNet  Google Scholar 

  29. Luo C, Fei Y, Kaeli D (2019) Side-channel timing attack of RSA on a GPU. ACM Trans Archit Code Optim (TACO) 16(3):1–18

    Article  Google Scholar 

  30. May A (2003) New RSA Vulnerabilities Using Lattice Reduction Methods. University of Paderborn. http://ubdata.uni-paderborn.de/ediss/17/2003/may/disserta.pdf

  31. May A (2004) Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring. Advances in Cryptology-CRYPTO, (2004) 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15–19, 2004. Proceedings 24. Springer, Berlin Heidelberg :213–219

  32. May A, Ritzenhofen M (2009) Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint. International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg: 1–14

  33. May A, Nowakowski J, Sarkar S (2022) Approximate Divisor Multiples-Factoring with Only a Third of the Secret CRT-Exponents. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing: 147–167

  34. Nitaj A, Ariffin MRK (2015) Implicit factorization of unbalanced RSA moduli. J Appl Math Comput 48:349–363

    Article  MathSciNet  Google Scholar 

  35. Nitaj A, Susilo W, Tonien J (2023) A new attack on some RSA variants. Theor Comput Sci 960:113898

    Article  MathSciNet  Google Scholar 

  36. Nitaj A, Adenan NNH, Ariffin MRK (2024) Cryptanalysis of a New Variant of the RSA Cryptosystem. International Conference on Cryptology in Africa. Cham: Springer Nature Switzerland: 327–345

  37. Peng L, Hu L, Xu J, et al (2014) Further Improvement of Factoring RSA Moduli with Implicit Hint. International Conference on Cryptology in Africa. Cham: Springer International Publishing: 165–177

  38. Peng L, Hu L, Lu Y, et al. (2015) Implicit factorization of RSA Moduli Revisited (short paper). Advances in Information and Computer Security: 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26-28, 2015, Proceedings 10. Springer International Publishing: 67–76

  39. Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 21(2):120–126

    Article  MathSciNet  Google Scholar 

  40. Rivest RL, Shamir A (1986) Efficient Factoring Based on Partial Information. Advances in Cryptology—EUROCRYPT’85: Proceedings of a Workshop on the Theory and Application of Cryptographic Techniques Linz, Austria, April 1985 4. Springer Berlin Heidelberg: 31–34

  41. Ruzai WNAWM, Nitaj A, Ariffin MRK et al (2022) Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis. Comput Stand Interfaces 80:103584

    Article  Google Scholar 

  42. Ruzai WNA, Ariffin MRK, Asbullah MA et al (2024) New simultaneous Diophantine attacks on generalized RSA key equations. J K Saud Univ-Comput Inf Sci 36:102074

    Google Scholar 

  43. Sarkar S, Maitra S (2009) Further results on implicit factoring in polynomial time. Cryptology ePrint Archive https://eprint.iacr.org/2009/108

  44. Sarkar S, Sen Gupta S, Maitra S (2010) Partial Key Exposure Attack on RSA-Improvements for Limited Lattice Dimensions. Progress in Cryptology-INDOCRYPT 2010: 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings 11. Springer Berlin Heidelberg: 2–16

  45. Sarkar S (2011) Partial Key Exposure: Generalized Framework to Attack RSA. Progress in Cryptology-INDOCRYPT 2011: 12th International Conference on Cryptology in India, Chennai, India, December 11-14, 2011. Proceedings 12. Springer Berlin Heidelberg: 76–92

  46. Sarkar S, Maitra S (2011) Approximate integer common divisor problem relates to implicit factorization. IEEE Trans Inf Theory 57(6):4002–4013

    Article  MathSciNet  Google Scholar 

  47. Sun Z, Zhang T, Zheng X, et al (2018) A Method for Solving Generalized Implicit Factorization Problem. International Conference On Signal And Information Processing, Networking And Computers. Singapore: Springer Singapore: 284–290

  48. Susilo W, Tonien J, Yang G (2021) Divide and capture: an improved cryptanalysis of the encryption standard algorithm RSA. Comput Stand Interfaces 74:103470

    Article  Google Scholar 

  49. Thirumalai C, Mohan S, Srivastava G (2020) An efficient public key secure scheme for cloud and IoT security. Comput Commun 150:634–643

    Article  Google Scholar 

  50. Wang S, Qu L, Li C et al (2018) A better bound for implicit factorization problem with shared middle bits. Sci China Inf Sci 61:1–10

    MathSciNet  Google Scholar 

  51. Zheng M, Hu H, Wang Z (2016) Generalized cryptanalysis of RSA with small public exponent. Sci China Inf Sci 59(3):32108

    Article  Google Scholar 

Download references

Acknowledgements

This paper is partially supported by the National Key Research and Development Program of China (Grant No. 2022YFB2902202), the Youth Science and Technology Innovation Talent Support Program Project of Beijing University of Posts and Telecommunications (Grant No. 2023ZCJH10), the National Natural Science Foundation of China (Grant No. 62032002, 62272051) and the 111 Project (Grant No. B21049).

Author information

Author notes

  1. Jingguo Bi, Lixiang Li and Haipeng Peng have contributed equally to this work.

Authors and Affiliations

  1. School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, 100876, China

    Ran Zhang, Jingguo Bi, Lixiang Li & Haipeng Peng

  2. Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China

    Ran Zhang, Lixiang Li & Haipeng Peng

  3. State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878, China

    Ran Zhang & Jingguo Bi

Authors
  1. Ran Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jingguo Bi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lixiang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Haipeng Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

R.Z. wrote the main manuscript text. J.B. and L.L. and H.P. are all supervisor. All authors reviewed the manuscript.

Corresponding author

Correspondence to Jingguo Bi.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, R., Bi, J., Li, L. et al. An optimal bound for factoring unbalanced RSA moduli by solving Generalized Implicit Factorization Problem. J Supercomput 81, 102 (2025). https://doi.org/10.1007/s11227-024-06478-y

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11227-024-06478-y

Keywords

Search

Navigation