November  2010, 4(4): 519-531. doi: 10.3934/amc.2010.4.519

Some applications of lattice based root finding techniques

1. 

Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India

2. 

Indian Statistical Institute, 203 B T Road,, Kolkata 700 108

Received  December 2009 Revised  August 2010 Published  November 2010

In this paper we present some problems and their solutions exploiting lattice based root finding techniques.
   In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q$-1 mod $p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA.
   In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique to solve the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.
Citation: Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519
References:
[1]

, , \url{http://www.rsa.com/rsalabs/node.asp?id=2125}., ().   Google Scholar

[2]

D. Boneh, Finding smooth integers in short intervals using CRT decoding,, in, (2000), 265.   Google Scholar

[3]

D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits,, in, (1998), 25.   Google Scholar

[4]

D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities,, Journal of Cryptology, 10 (1997), 223.  doi: 10.1007/s001459900030.  Google Scholar

[5]

J.-S. Coron, Finding small roots of bivariate integer equations revisited,, in, (2004), 492.  doi: 10.1007/978-3-540-24676-3_29.  Google Scholar

[6]

J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring,, Journal of Cryptology, 20 (2007), 39.  doi: 10.1007/s00145-006-0433-6.  Google Scholar

[7]

J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70.  doi: 10.1007/978-3-642-13013-7_5.  Google Scholar

[8]

N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits,, in, (2009), 1.   Google Scholar

[9]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131.   Google Scholar

[10]

N. Howgrave-Graham, Approximate integer common divisors,, in, (2001), 51.   Google Scholar

[11]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants,, in, (2006), 267.   Google Scholar

[12]

A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'', Springer-Verlag, (1993).  doi: 10.1007/BFb0091534.  Google Scholar

[13]

A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients,, Mathematische Annalen, 261 (1982), 513.  doi: 10.1007/BF01457454.  Google Scholar

[14]

A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring,, in, (2004), 213.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar

[15]

A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint,, in, (2009), 1.   Google Scholar

[16]

C. Pomerance, The quadratic sieve factoring algorithm,, in, (1985), 169.   Google Scholar

[17]

J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem,, Electronic Letters, 18 (1982), 905.  doi: 10.1049/el:19820617.  Google Scholar

[18]

R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems,, Communications of ACM, 21 (1978), 120.  doi: 10.1145/359340.359342.  Google Scholar

[19]

S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time,, Advances in Mathematics of Communications, 3 (2009), 205.  doi: 10.3934/amc.2009.3.205.  Google Scholar

[20]

S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization,, available online at \url{http://eprint.iacr.org/2009/626}., ().   Google Scholar

[21]

M. Wiener, Cryptanalysis of short RSA secret exponents,, IEEE Transactions on Information Theory, 36 (1990), 553.  doi: 10.1109/18.54902.  Google Scholar

show all references

References:
[1]

, , \url{http://www.rsa.com/rsalabs/node.asp?id=2125}., ().   Google Scholar

[2]

D. Boneh, Finding smooth integers in short intervals using CRT decoding,, in, (2000), 265.   Google Scholar

[3]

D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits,, in, (1998), 25.   Google Scholar

[4]

D. Coppersmith, Small Solutions to polynomial equations and low exponent vulnerabilities,, Journal of Cryptology, 10 (1997), 223.  doi: 10.1007/s001459900030.  Google Scholar

[5]

J.-S. Coron, Finding small roots of bivariate integer equations revisited,, in, (2004), 492.  doi: 10.1007/978-3-540-24676-3_29.  Google Scholar

[6]

J.-S. Coron and A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring,, Journal of Cryptology, 20 (2007), 39.  doi: 10.1007/s00145-006-0433-6.  Google Scholar

[7]

J.-C. Faugere, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70.  doi: 10.1007/978-3-642-13013-7_5.  Google Scholar

[8]

N. Heninger and H. Shacham, Reconstructing RSA private keys from random key bits,, in, (2009), 1.   Google Scholar

[9]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131.   Google Scholar

[10]

N. Howgrave-Graham, Approximate integer common divisors,, in, (2001), 51.   Google Scholar

[11]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants,, in, (2006), 267.   Google Scholar

[12]

A. K. Lenstra and H. W. Lenstra, Jr., "The Development of the Number Field Sieve,'', Springer-Verlag, (1993).  doi: 10.1007/BFb0091534.  Google Scholar

[13]

A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients,, Mathematische Annalen, 261 (1982), 513.  doi: 10.1007/BF01457454.  Google Scholar

[14]

A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring,, in, (2004), 213.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar

[15]

A. May and M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint,, in, (2009), 1.   Google Scholar

[16]

C. Pomerance, The quadratic sieve factoring algorithm,, in, (1985), 169.   Google Scholar

[17]

J.-J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem,, Electronic Letters, 18 (1982), 905.  doi: 10.1049/el:19820617.  Google Scholar

[18]

R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems,, Communications of ACM, 21 (1978), 120.  doi: 10.1145/359340.359342.  Google Scholar

[19]

S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time,, Advances in Mathematics of Communications, 3 (2009), 205.  doi: 10.3934/amc.2009.3.205.  Google Scholar

[20]

S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization,, available online at \url{http://eprint.iacr.org/2009/626}., ().   Google Scholar

[21]

M. Wiener, Cryptanalysis of short RSA secret exponents,, IEEE Transactions on Information Theory, 36 (1990), 553.  doi: 10.1109/18.54902.  Google Scholar

[1]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[2]

Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385

[3]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[4]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[5]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020448

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (69)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]