Partial key exposure attacks on RSA and its variant by guessing a few bits of one of the prime factors
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Consider RSA with N = pq, q < p < 2q, public encryption exponent e and private decryption exponent d. We first study cryptanalysis of RSA when certain amount of the Most Significant Bits (MSBs) or Least Significant Bits (LSBs) of d is known. The basic lattice based technique is similar to that of Ernst et al. in Eurocrypt 2005. However, our idea of guessing a few MSBs of the secret prime p substantially reduces the requirement of MSBs or LSBs of d for the key exposure attack. Further, we consider the RSA variant proposed by Sun and Yang in PKC 2005 and show that the partial key exposure attack works significantly on this variant.
Abstract
Consider RSA with N = pq, q < p < 2q, public encryption exponent e and private decryption exponent d. We first study cryptanalysis of RSA when certain amount of the Most Significant Bits (MSBs) or Least Significant Bits (LSBs) of d is known. The basic lattice based technique is similar to that of Ernst et al. in Eurocrypt 2005. However, our idea of guessing a few MSBs of the secret prime p substantially reduces the requirement of MSBs or LSBs of d for the key exposure attack. Further, we consider the RSA variant proposed by Sun and Yang in PKC 2005 and show that the partial key exposure attack works significantly on this variant.
참고문헌 (28)
- J. Bl¨omer, "Low secret exponent RSA revisited, Cryptography and lattices (Providence, RI, 2001)", Lecture Notes in Comput. Sci, 2146, pp.4~19 (2001), Springer
- J. Bl¨omer, "New partial key exposure attacks on RSA, Advances in cryptology—CRYPTO 2003", Lecture Notes in Comput. Sci, 2729, pp.27~43 (2003), Springer
- J. Bl¨omer, "generalized Wiener attack on RSA, Public key cryptography—PKC 2004", Lecture Notes in Comput. Sci, 2947, pp.1~13 (2004), SpringerBerlin
- D. Boneh, "Twenty years of attacks on the RSA cryptosystem", Notices Amer. Math. Soc, 46(2), pp.203~213 (1999)
- D. Boneh, "Cryptanalysis of RSA with private key d less than N0.292", IEEE Trans. Inform. Theory, 46(4), pp.1339~1349 (2000)
- D. Boneh, "Exposing an RSA private key given a small fraction of its bits, AsiaCrypt’98", LNCS, 1514, pp.25~34 (1998), Springer-Verlag
- D. Boneh, "On the importance of checking cryptographic protocols for faults (extended abstract), Advances in cryptology—EUROCRYPT ’97 (Konstanz)", Lecture Notes in Comput. Sci, 1233, pp.37~51 (1997), Springer
- D. Coppersmith, "Small solutions to polynomial equations, and low exponent RSA vulnerabilities", J. Cryptology, 10(4), pp.233~260 (1997)
- A. Duejella, "Continued fractions and RSA with small secret exponent", Tatra Mt. Math. Publ, 29, pp.101~112 (2004)
- M. Ernst, "Partial key exposure attacks on RSA up to full size exponents, Advances in cryptology—EUROCRYPT 2005", Lecture Notes in Comput. Sci, 3494, pp.371~386 (2005), Springer
- J. Hastad, "On using RSA with low exponent in a public key network, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985)", Lecture Notes in Comput. Sci, 218, pp.403~408 (1986), Springer
- N. Howgrave-Graham, "Finding small roots of univariate modular equations revisited, Cryptography and coding (Cirencester, 1997)", Lecture Notes in Comput. Sci, 1355, pp.131~142 (1997), Springer
- E. Jochemsz, "Cryptanalysis of RSA variants using small roots of polynomials", 박사, pp.2007
- P. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems, Proc. Crypto’96", Lecture Notes in Comput. Sci, 1109, pp.104~113 (1996), Springer- Verlag
- P. Kocher, "Differential power analysis, CRYPTO ’99", Lecture Notes in Comput. Sci, 1666, pp.388~397 (1999), Springer
- A. K. Lenstra, "Factoring polynomials with rational coefficients", Math. Ann, 261(4), pp.515~534 (1982)
- "sing LLL-Reduction for Solving RSA and Factorization Problems: A Survey, LLL+25 Conference in honour of the 25th birthday of the LLL algorithm"[URL]
- A. Nitaj, "Another Generalization of Wiener’s Attack on RSA, Progress in Cryptology—AFRICACRYPT 2008", Lecture Notes in Comput. Sci, 5023, pp.174~190 (2008), Springer-Verlag
- J. M. Pollard, "Theorems on factorization and primality testing", Proc. Cambridge Philos. Soc, 76, pp.521~528 (1974)
- R. L. Rivest, "A method for obtaining digital signatures and public-key cryptosystems", Comm. ACM, 21(2), pp.120~126 (1978)
- R. Steinfeld, "Converse results to the Wiener attack on RSA, Public key cryptography—PKC 2005", Lecture Notes in Comput. Sci, 3386, pp.184~198 (2005), Springer
- D. R. Stinson, "Cryptography – Theory and Practice", pp.2002, Chapman & Hall
- H.-M. Sun, "Estimating the prime-factors of an RSA modulus and an extension of the Wiener attack, Applied Cryptography and Network Security", Lecture Notes in Comput. Sci, 4521, pp.116~128 (2007), Sprigner
- H.-M. Sun, "RSA with balanced short exponents and its application to entity authentication, Public key cryptography—PKC 2005", Lecture Notes in Comput. Sci, 3386, pp.199~215 (2005), Springer
- E. R. Verheul, "Cryptanalysis of ‘less short’ RSA secret exponents", Appl. Algebra Engrg. Comm. Comput, 8(5), pp.425~435 (1997)
- B. de Weger, "Cryptanalysis of RSA with small prime difference", Appl. Algebra Engrg. Comm. Comput, 13(1), pp.17~28 (2002)
- M. Wiener, "Cryptanalysis of short RSA secret exponents", IEEE Trans. Inform. Theory, 36(3), pp.553~558 (1990)
- H. C. Williams, "A p+1 method of factoring", Math. Comp, 39(159), pp.225~234 (1982)