×

Factoring multi-power RSA moduli with primes sharing least or most significant bits. (English) Zbl 1401.11158

Summary: We study the factorization of a balanced multi-power RSA moduli \(N=p^{r}q\) when the unknown primes \(p\) and \(q\) share \(t\) least or most significant bits. We show that if \(t\geq \frac{1}{1+r} \log p\), then it is possible to compute the prime decomposition of \(N\) in polynomial time in \(\log N\). This result can be used to mount attacks against several cryptographic protocols that are based on the moduli \(N\).

MSC:

11Y05 Factorization
94A60 Cryptography

Software:

ESIGN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Bach and J. Shallit, Algorithmic Number Theory. Volume 1: Efficient Algorithms, MIT Press, Cambridge, 1996.; Bach, E.; Shallit, J., Algorithmic Number Theory. Volume 1: Efficient Algorithms (1996) · Zbl 0873.11070
[2] D. Boneh, G. Durfee and N. Howgrave-Graham, Factoring \(N = p^r\) q for large r, Advances in Cryptology (CRYPTO’99), Lecture Notes in Comput. Sci. 1666, Springer, Berlin (1999), 326-337.; Boneh, D.; Durfee, G.; Howgrave-Graham, N., Factoring \(N = p^r\) q for large r, Advances in Cryptology, 326-337 (1999) · Zbl 1007.11077
[3] D. Boneh and H. Shacham, Fast variants of RSA, CryptoBytes 5 (2002), 1, 1-9.; Boneh, D.; Shacham, H., Fast variants of RSA, CryptoBytes, 5, 1, 1-9 (2002)
[4] D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), 4, 233-260.; Coppersmith, D., Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10, 4, 233-260 (1997) · Zbl 0912.11056
[5] B. De Weger, Cryptanalysis of RSA with small prime difference, Appl. Algebra Engrg. Comm. Comput. 13 (2002), 1, 17-28.; De Weger, B., Cryptanalysis of RSA with small prime difference, Appl. Algebra Engrg. Comm. Comput., 13, 1, 17-28 (2002) · Zbl 1010.94007
[6] A. Fujioka, T. Okamoto and S. Miyaguchi, ESIGN: An efficient digital signature implementation for smart cards, Advances in Cryptology (EUROCRYPT’91), Lecture Notes in Comput. Sci. 547, Springer, Berlin (1991), 446-457.; Fujioka, A.; Okamoto, T.; Miyaguchi, S., ESIGN: An efficient digital signature implementation for smart cards, Advances in Cryptology, 446-457 (1991) · Zbl 0825.94184
[7] S. D. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, Cambridge, 2012.; Galbraith, S. D., Mathematics of Public Key Cryptography (2012) · Zbl 1238.94027
[8] K. Itoh, N. Kunihiro and K. Kurosawa, Small secret key attack on a variant of RSA (due to Takagi), Topics in Cryptology (CT-RSA 2008), Lecture Notes in Comput. Sci. 4964, Springer, Berlin (2008), 387-406.; Itoh, K.; Kunihiro, N.; Kurosawa, K., Small secret key attack on a variant of RSA (due to Takagi), Topics in Cryptology, 387-406 (2008) · Zbl 1161.94408
[9] D. H. Lehmer and R. E. Powers, On factoring large numbers, Bull. Amer. Math. Soc. 37 (1931), 10, 770-776.; Lehmer, D. H.; Powers, R. E., On factoring large numbers, Bull. Amer. Math. Soc., 37, 10, 770-776 (1931) · JFM 57.0185.01
[10] A. K. Lenstra and H. W. Lenstra, Jr., The development of the number field sieve, Lecture Notes in Math. 1554, Springer, Berlin, 1993.; Lenstra, A. K.; Lenstra, Jr., H. W., The development of the number field sieve (1993) · Zbl 0777.00017
[11] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 3, 649-673.; Lenstra, Jr., H. W., Factoring integers with elliptic curves, Ann. of Math. (2), 126, 3, 649-673 (1987) · Zbl 0629.10006
[12] W. J. LeVeque, Fundamentals of Number Theory, Dover Publications, New York, 1996.; LeVeque, W. J., Fundamentals of Number Theory (1996) · Zbl 1141.11300
[13] S. Lim, S. Kim, I. Yie and H. Lee, A generalized takagi-cryptosystem with a modulus of the form \(p^r q^s\), Progress in Cryptology (INDOCRYPT 2000), Lecture Notes in Comput. Sci. 1977, Springer, Berlin (2000), 283-294.; Lim, S.; Kim, S.; Yie, I.; Lee, H., A generalized takagi-cryptosystem with a modulus of the form \(p^r q^s\), Progress in Cryptology, 283-294 (2000) · Zbl 0963.94025
[14] Y. Lu, R. Zhang and D. Lin, Factoring multi-power RSA modulus \(N = p^r\) q with partial known bits, Information Security and Privacy (ACISP 2013), Lecture Notes in Comput. Sci. 7959, Springer, Berlin (2013), 57-71.; Lu, Y.; Zhang, R.; Lin, D., Factoring multi-power RSA modulus \(N = p^r\) q with partial known bits, Information Security and Privacy, 57-71 (2013) · Zbl 1285.94078
[15] A. May, Secret exponent attacks on RSA-type schemes with moduli \(N = p^r\) q, Public Key Cryptography (PKC 2004), Lecture Notes in Comput. Sci. 2947, Springer, Berlin (2004), 218-230.; May, A., Secret exponent attacks on RSA-type schemes with moduli \(N = p^r\) q, Public Key Cryptography, 218-230 (2004) · Zbl 1198.94113
[16] A. May, Using LLL-reduction for solving RSA and factorization problems, The LLL Algorithm, Inf. Secur. Cryptography, Springer, Dordrecht (2010), 315-348.; May, A., Using LLL-reduction for solving RSA and factorization problems, The LLL Algorithm, 315-348 (2010) · Zbl 1237.94078
[17] T. Okamoto and S. Uchiyama, A new public-key cryptosystem as secure as factoring, Advances in Cryptology (EUROCRYPT’98), Lecture Notes in Comput. Sci. 1403, Springer, Berlin (1998), 308-318.; Okamoto, T.; Uchiyama, S., A new public-key cryptosystem as secure as factoring, Advances in Cryptology, 308-318 (1998) · Zbl 0919.94028
[18] J. M. Pollard, Theorems on factorization and primality testing, Math. Proc. Cambridge Philos. Soc. 76 (1974), 3, 521-528.; Pollard, J. M., Theorems on factorization and primality testing, Math. Proc. Cambridge Philos. Soc., 76, 3, 521-528 (1974) · Zbl 0294.10005
[19] J. M. Pollard, A monte carlo method for factorization, BIT 15 (1975), 3, 331-334.; Pollard, J. M., A monte carlo method for factorization, BIT, 15, 3, 331-334 (1975) · Zbl 0312.10006
[20] C. Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology (EUROCRYPT’84), Lecture Notes in Comput. Sci. 209, Springer, Berlin (1985), 169-182.; Pomerance, C., The quadratic sieve factoring algorithm, Advances in Cryptology, 169-182 (1985) · Zbl 0596.10006
[21] R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (1978), 2, 120-126.; Rivest, R. L.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005
[22] S. Sarkar, Small secret exponent attack on RSA variant with modulus \(N = p^r\) q, Des. Codes Cryptogr. 73 (2014), 2, 383-392.; Sarkar, S., Small secret exponent attack on RSA variant with modulus \(N = p^r\) q, Des. Codes Cryptogr., 73, 2, 383-392 (2014) · Zbl 1335.94076
[23] V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Cambridge, 2005.; Shoup, V., A Computational Introduction to Number Theory and Algebra (2005) · Zbl 1116.11002
[24] R. Steinfeld and Y. Zheng, On the security of RSA with primes sharing least-significant bits, Appl. Algebra Engrg. Comm. Comput. 15 (2004), 3, 179-200.; Steinfeld, R.; Zheng, Y., On the security of RSA with primes sharing least-significant bits, Appl. Algebra Engrg. Comm. Comput., 15, 3, 179-200 (2004) · Zbl 1065.94008
[25] T. Takagi, Fast RSA-type cryptosystem modulo \(p^k\) q, Advances in Cryptology (CRYPTO’98), Lecture Notes in Comput. Sci. 1462, Springer, Berlin (1998), 318-326.; Takagi, T., Fast RSA-type cryptosystem modulo \(p^k\) q, Advances in Cryptology, 318-326 (1998) · Zbl 0931.94041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.