logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 3: 032108(2016) https://doi.org/10.1007/s11432-015-5325-7

Generalized cryptanalysis of RSA with small public exponent

More info
  • ReceivedSep 4, 2015
  • AcceptedDec 27, 2015
  • PublishedJan 15, 2016

Abstract

In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent $e=N^\alpha\leq N^{0.5}$. In 1999, Boneh and Durfee showed that when $\alpha\approx 1$ and the private exponent $d=N^\beta<N^{0.292}$, the system is insecure. Moreover, their attack is still effective for $0.5<\alpha<1.875$. We propose a generalized cryptanalytic method to attack the RSA cryptosystem with $\alpha\leq 0.5$. For $c=\lfloor\frac{1-\alpha}{\alpha}\rfloor$ and $e^{\gamma c}\equiv d\pmod{e^c}$, when $\gamma$, $\beta$ satisfy $\gamma < 1+\frac{1}{c}-\frac{1}{2\alpha c}$ and $\beta <\alpha c+\frac{7}{6}-\alpha\gamma c-\frac{1}{3}\sqrt{6\alpha+6\alpha c+1-6\alpha\gamma c}$, we can perform cryptanalytic attacks based on the LLL algorithm. The basic idea is an application of Coppersmith's techniques and we further adapt the technique of unravelled linearization, which leads to an optimized lattice. Our advantage is that we achieve new attacks on RSA with $\alpha\leq0.5$ and consequently, there exist weak keys in RSA for most $\alpha$.


Acknowledgment

Acknowledgments

This work was supported partially by National Natural Science Foundation of China (Grant No. 61271271), 100 Talents Program of Chinese Academy of Sciences, and Fundamental Research Funds for the Central Universities in China (Grant No. WK2101020005).


References

[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120-126 CrossRef Google Scholar

[2] Coppersmith D. Finding a small root of a univariate modular equation. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, 1996. 155--165. Google Scholar

[3] Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J Cryptol, 1997, 10: 233-260 CrossRef Google Scholar

[4] Howgrave-Graham N. Finding small roots of univariate modular equations revisited. In: Darnell M, ed. Crytography and Coding. Berlin: Springer, 1997. 131--142. Google Scholar

[5] Wiener M J. Cryptanalysis of short RSA secret exponents. IEEE Trans Inform Theory, 1990, 36: 553-558 CrossRef Google Scholar

[6] Boneh D, Durfee G. Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques, Prague, 1999. 1--11. Google Scholar

[7] Boneh D, Durfee G. Cryptanalysis of RSA with private key $d$ less than $N^{0. 292 $. IEEE Trans Inform Theory, 2000, 46: 1339-1349 CrossRef Google Scholar

[8] Blömer J, May A. Low secret exponent RSA revisited. In: Silverman J H, ed. Cryptography and Lattices. Berlin: Springer, 2001. 4--19. Google Scholar

[9] May A. Cryptanalysis of unbalanced RSA with small CRT-exponent. In: Proceedings of 22nd Annual International Cryptology Conference, Santa Barbara, 2002. 242--256. Google Scholar

[10] Jochemsz E, May A. A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In: Proceedings of 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, 2006. 267--282. Google Scholar

[11] Bleichenbacher D, May A. New attacks on RSA with small secret CRT-exponents. In: Proceedings of 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, 2006. 1--13. Google Scholar

[12] Jochemsz E, May A. A polynomial time attack on RSA with private CRT-exponents smaller than $N^{0.073}$. In: Proceedings of 27th Annual International Cryptology Conference, Santa Barbara, 2007. 395--411. Google Scholar

[13] Blömer J, May A. New partial key exposure attacks on RSA. In: Proceedings of 23rd Annual International Cryptology Conference, Santa Barbara, 2003. 27--43. Google Scholar

[14] Ernst M, Jochemsz E, May A, et al. Partial key exposure attacks on RSA up to full size exponents. In: Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, 2005. 371--386. Google Scholar

[15] Aono Y. A new lattice construction for partial key exposure attack for RSA. In: Proceedings of 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, 2009. 34--53. Google Scholar

[16] Sarkar S. Partial key exposure: generalized framework to attack RSA. In: Proceedings of 12th International Conference on Cryptology in India, Chennai, 2011. 76--92. Google Scholar

[17] Joye M, Lepoint T. Partial key exposure on RSA with private exponents larger than $N$. In: Ryan M D, Smyth B, Wang G L, eds. Information Security Practice and Experience. Berlin: Springer, 2012. 369--380. Google Scholar

[18] Luo P, Zhou H J, Wang D S, et al. Cryptanalysis of RSA for a special case with $d>e$. Sci China Ser-F: Inf Sci, 2009, 52: 609-616 Google Scholar

[19] Herrmann M, May A. Attacking power generators using unravelled linearization: When do we output too much? In: Proceedings of 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, 2009. 487--504. Google Scholar

[20] Herrmann M, May A. Maximizing small root bounds by linearization and applications to small secret exponent RSA. In: Proceedings of 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, 2010. 53--69. Google Scholar

[21] Herrmann M. Lattice-based cryptanalysis using unravelled linearization. Dissertation for Doctoral Degree. Germany: Ruhr-Universität Bochum, 2011. Google Scholar

[22] Lenstra A K, Lenstra H W, Lovász L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515-iffalse CrossRef Google Scholar

[23] Xiong H, Chen Y N, Zhu G B, et al. Analysis and improvement of a provable secure fuzzy identity-based signature scheme. Sci China Inf Sci, 2014, 57: 1-5 Google Scholar

[24] Li L, Liu X H, Wang Z, et al. An improved attack on clock-controlled shift registers based on hardware implementation. Sci China Inf Sci, 2013, 56: 1-10 Google Scholar

[25] Huang J L, Lai X J. What is the effective key length for a block cipher: an attack on every practical block cipher. Sci China Inf Sci, 2014, 57: 1-fi Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1