American Institute of Mathematical Sciences

Advanced
August  2021, 15(3): 441-469. doi: 10.3934/amc.2020076

Finding small solutions of the equation $ \mathit{{Bx-Ay = z}} $ and its applications to cryptanalysis of the RSA cryptosystem

Shixiong Wang 1, , Longjiang Qu 2,3,, , Chao Li 2,4, , Shaojing Fu 3,4, and  Hao Chen 5,

1. 

National Innovation Institute of Defense Technology, Beijing 100071, China
2. 

College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China
3. 

State Key Laboratory of Cryptology, Beijing 100878, China
4. 

College of Computer National University of Defense Technology, Changsha 410073, China
5. 

College of Information Science and Technology/Collage of Cyber Security, Jinan University, Guangzhou 510632, China

* Corresponding Author: Longjiang Qu

Received  September 2019 Published  April 2020

In this paper, we study the condition of finding small solutions $ (x,y,z) = (x_0, y_0, z_0) $ of the equation $ Bx-Ay = z $. The framework is derived from Wiener's small private exponent attack on RSA and May-Ritzenhofen's investigation about the implicit factorization problem, both of which can be generalized to solve the above equation. We show that these two methods, together with Coppersmith's method, are equivalent for solving $ Bx-Ay = z $ in the general case. Then based on Coppersmith's method, we present two improvements for solving $ Bx-Ay = z $ in some special cases. The first improvement pays attention to the case where either $ \gcd(x_0,z_0,A) $ or $ \gcd(y_0,z_0,B) $ is large enough. As the applications of this improvement, we propose some new cryptanalysis of RSA, such as new results about the generalized implicit factorization problem, attacks with known bits of the prime factor, and so on.

Keywords: RSA, cryptanalysis, lattice, coppersmith's method.
Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.
Citation: Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $ \mathit{{Bx-Ay = z}} $ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076
References:
[1]

Y. Aono, A new lattice construction for partial key exposure attack for RSA, Public Key Cryptography-PKC 2009, Springer Berlin Heidelberg, (2009), 34–53. Google Scholar

[2]

J. Blömer and A. May, New partial key exposure attacks on RSA, Advances in Cryptology - CRYPTO 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2729 (2003), 27-43.  doi: 10.1007/978-3-540-45146-4_2.  Google Scholar

[3]

D. Boneh and G. Durfee, Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$, Advances in Cryptology - EUROCRYPT '99 (Prague), Lecture Notes in Comput. Sci. Springer, Berlin, 1592 (1999), 1-11.  doi: 10.1007/3-540-48910-X_1.  Google Scholar

[4]

D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in Cryptology - ASIACRYPT'98 (Beijing), Lecture Notes in Comput. Sci., Springer, Berlin, 1514 (1998), 25-34.  doi: 10.1007/3-540-49649-1_3.  Google Scholar

[5]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in Cryptology - EUROCRYPT '96 (Saragossa, 1996), Lecture Notes in Comput. Sci., Springer, Berlin, 1070 (1996), 155-165.  doi: 10.1007/3-540-68339-9_14.  Google Scholar

[6]

D. Coppersmith, Finding a small root of a bivariate integer equation, factoring with high bits known, Advances in Cryptology - EUROCRYPT '96 (Saragossa, 1996), Lecture Notes in Comput. Sci., Springer, Berlin, 1070 (1996), 178-189.  doi: 10.1007/3-540-68339-9_16.  Google Scholar

[7]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.  Google Scholar

[8]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations revisited, Advances in Cryptology - EUROCRYPT 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3027 (2004), 492-505.  doi: 10.1007/978-3-540-24676-3_29.  Google Scholar

[9]

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

[10]

B. De Weger, Cryptanalysis of RSA with small prime difference, Appl. Algebra Engrg. Comm. Comput., 13 (2002), 17-28.  doi: 10.1007/s002000100088.  Google Scholar

[11]

M. Ernst, E. Jochemsz, A. May and B. de Weger, Partial key exposure attacks on RSA up to full size exponents, Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Comput. Sci., Springer, Berlin, 3494 (2005), 371-386.  doi: 10.1007/11426639_22.  Google Scholar

[12]

J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, Public Key Cryptography - PKC 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 70-87.  doi: 10.1007/978-3-642-13013-7_5.  Google Scholar

[13]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition, The Clarendon Press, Oxford University Press, New York, 1979.  Google Scholar

[14]

M. Herrmann and A. May, Maximizing small root bounds by linearization and applications to small secret exponent RSA, Public Key Cryptography - PKC 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 53-69.  doi: 10.1007/978-3-642-13013-7_4.  Google Scholar

[15]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and Coding (Cirencester, 1997), Lecture Notes in Comput. Sci., Springer, Berlin, 1355 (1997), 131-142.  doi: 10.1007/BFb0024458.  Google Scholar

[16]

N. Howgrave-Graham, Approximate integer common divisors, Cryptography and Lattices (Providence, RI, 2001), Lecture Notes in Comput. Sci., Springer, Berlin, 2146 (2001), 51-66.  doi: 10.1007/3-540-44670-2_6.  Google Scholar

[17]

A. Joux, Algorithmic Cryptanalysis, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2009. doi: 10.1201/9781420070033.  Google Scholar

[18]

S. Kumar and C. Narasimham, Cryptanalysis of RSA with small prime difference using unravelled linearization, International Journal of Computer Applications, 61 (2013). Google Scholar

[19]

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

[20]

Y. Lu, L. Q. Peng, R. Zhang, L. Hu and D. D. Lin, Towards optimal bounds for implicit factorization problem, Selected Areas in Cryptography - SAC 2015, Lecture Notes in Comput. Sci., Springer, [Cham], 9566 (2016), 462-476.  doi: 10.1007/978-3-319-31301-6_26.  Google Scholar

[21]

Y. Lu, R. Zhang and D. Lin, Improved bounds for the implicit factorization problem, Advances in Mathematics of Communications, 7 (2013), 243-251.  doi: 10.3934/amc.2013.7.243.  Google Scholar

[22]

Y. Lu, R. Zhang, L. Q. Peng and D. D. Lin, Solving linear equations modulo unknown divisors: Revisited, Advances in Cryptology - ASIACRYPT 2015. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9452 (2015), 189-213.  doi: 10.1007/978-3-662-48797-6_9.  Google Scholar

[23]

A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Dissertation for Ph.D. Degree, University of Paderborn, 2003. Google Scholar

[24]

A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, Advances in Cryptology - CRYPTO 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3152 (2004), 213-219.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar

[25]

A. May and M. Ritzenhofen, Implicit factoring: On polynomial time factoring given only an implicit hint, Public Key Cryptography - PKC 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5443 (2009), 1-14.  doi: 10.1007/978-3-642-00468-1_1.  Google Scholar

[26] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, Cambridge University Press, Cambridge, 2000.   Google Scholar
[27]

H. Minkowski, Geometrie der Zahlen, Bibliotheca Mathematica Teubneriana, Band 40 Johnson Reprint Corp., New York-London, 1968.  Google Scholar

[28]

A. Nitaj and M. R. K. Ariffin, Implicit factorization of unbalanced RSA moduli, Journal of Applied Mathematics and Computing, 48 (2015), 349-363.  doi: 10.1007/s12190-014-0806-1.  Google Scholar

[29]

A. Nitaj, A new attack on RSA and CRT-RSA, Progress in Cryptology-AFRICACRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7374 (2012), 221-233.  doi: 10.1007/978-3-642-31410-0_14.  Google Scholar

[30]

L. Peng, L. Hu, Z. Huang and et al., Partial prime factor exposure attacks on RSA and its Takagi's variant, International Conference on Information Security Practice and Experience-ISPEC 2015, Springer International Publishing, (2015), 96–108. Google Scholar

[31]

L. Peng, L. Hu, Y. Lu and et al., Implicit factorization of RSA moduli revisited (short paper), International Workshop on Security-IWSEC 2015, Springer International Publishing, (2015), 67–76. Google Scholar

[32]

L. Q. Peng, L. Hu, J. Xu, Z. J. Huang and Y. H. Xie, Further improvement of factoring RSA moduli with implicit hint, Progress in Cryptology - AFRICACRYPT 2014, Lecture Notes in Comput. Sci., Springer, Cham, 8469 (2014), 165-177.  doi: 10.1007/978-3-319-06734-6_11.  Google Scholar

[33]

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

[34]

S. Sarkar, Partial key exposure: Generalized framework to attack RSA, Progress in Cryptology - INDOCRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7107 (2011), 76-92.  doi: 10.1007/978-3-642-25578-6_7.  Google Scholar

[35]

S. Sarkar, S. Sen Gupta and S. Maitra, Partial key exposure attack on RSA - improvements for limited lattice dimensions, Progress in Cryptology - INDOCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6498 (2010), 2-16.  doi: 10.1007/978-3-642-17401-8_2.  Google Scholar

[36]

S. Sarkar and S. Maitra, Improved partial key exposure attacks on RSA by guessing a few bits of one of the prime factors, Information Security and Cryptology - ICISC 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5461 (2009), 37-51.  doi: 10.1007/978-3-642-00730-9_3.  Google Scholar

[37]

S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, IEEE Transactions on Information Theory, 57 (2011), 4002-4013.  doi: 10.1109/TIT.2011.2137270.  Google Scholar

[38]

A. Takayasu and N. Kunihiro, Partial key exposure attacks on RSA: Achieving the Boneh-Durfee bound, Selected Areas in Cryptography - SAC 2014, Lecture Notes in Comput. Sci., Springer, Cham, 8781 (2014), 345-362.  doi: 10.1007/978-3-319-13051-4_21.  Google Scholar

[39]

S. Wang, L. Qu, C. Li and et al., Generalized framework to attack RSA with special exposed bits of the private key, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100 (2017), 2113-2122. Google Scholar

[40]

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

show all references

References:
[1]

Y. Aono, A new lattice construction for partial key exposure attack for RSA, Public Key Cryptography-PKC 2009, Springer Berlin Heidelberg, (2009), 34–53. Google Scholar

[2]

J. Blömer and A. May, New partial key exposure attacks on RSA, Advances in Cryptology - CRYPTO 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2729 (2003), 27-43.  doi: 10.1007/978-3-540-45146-4_2.  Google Scholar

[3]

D. Boneh and G. Durfee, Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$, Advances in Cryptology - EUROCRYPT '99 (Prague), Lecture Notes in Comput. Sci. Springer, Berlin, 1592 (1999), 1-11.  doi: 10.1007/3-540-48910-X_1.  Google Scholar

[4]

D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in Cryptology - ASIACRYPT'98 (Beijing), Lecture Notes in Comput. Sci., Springer, Berlin, 1514 (1998), 25-34.  doi: 10.1007/3-540-49649-1_3.  Google Scholar

[5]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in Cryptology - EUROCRYPT '96 (Saragossa, 1996), Lecture Notes in Comput. Sci., Springer, Berlin, 1070 (1996), 155-165.  doi: 10.1007/3-540-68339-9_14.  Google Scholar

[6]

D. Coppersmith, Finding a small root of a bivariate integer equation, factoring with high bits known, Advances in Cryptology - EUROCRYPT '96 (Saragossa, 1996), Lecture Notes in Comput. Sci., Springer, Berlin, 1070 (1996), 178-189.  doi: 10.1007/3-540-68339-9_16.  Google Scholar

[7]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.  Google Scholar

[8]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations revisited, Advances in Cryptology - EUROCRYPT 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3027 (2004), 492-505.  doi: 10.1007/978-3-540-24676-3_29.  Google Scholar

[9]

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

[10]

B. De Weger, Cryptanalysis of RSA with small prime difference, Appl. Algebra Engrg. Comm. Comput., 13 (2002), 17-28.  doi: 10.1007/s002000100088.  Google Scholar

[11]

M. Ernst, E. Jochemsz, A. May and B. de Weger, Partial key exposure attacks on RSA up to full size exponents, Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Comput. Sci., Springer, Berlin, 3494 (2005), 371-386.  doi: 10.1007/11426639_22.  Google Scholar

[12]

J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, Public Key Cryptography - PKC 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 70-87.  doi: 10.1007/978-3-642-13013-7_5.  Google Scholar

[13]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition, The Clarendon Press, Oxford University Press, New York, 1979.  Google Scholar

[14]

M. Herrmann and A. May, Maximizing small root bounds by linearization and applications to small secret exponent RSA, Public Key Cryptography - PKC 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6056 (2010), 53-69.  doi: 10.1007/978-3-642-13013-7_4.  Google Scholar

[15]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and Coding (Cirencester, 1997), Lecture Notes in Comput. Sci., Springer, Berlin, 1355 (1997), 131-142.  doi: 10.1007/BFb0024458.  Google Scholar

[16]

N. Howgrave-Graham, Approximate integer common divisors, Cryptography and Lattices (Providence, RI, 2001), Lecture Notes in Comput. Sci., Springer, Berlin, 2146 (2001), 51-66.  doi: 10.1007/3-540-44670-2_6.  Google Scholar

[17]

A. Joux, Algorithmic Cryptanalysis, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2009. doi: 10.1201/9781420070033.  Google Scholar

[18]

S. Kumar and C. Narasimham, Cryptanalysis of RSA with small prime difference using unravelled linearization, International Journal of Computer Applications, 61 (2013). Google Scholar

[19]

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

[20]

Y. Lu, L. Q. Peng, R. Zhang, L. Hu and D. D. Lin, Towards optimal bounds for implicit factorization problem, Selected Areas in Cryptography - SAC 2015, Lecture Notes in Comput. Sci., Springer, [Cham], 9566 (2016), 462-476.  doi: 10.1007/978-3-319-31301-6_26.  Google Scholar

[21]

Y. Lu, R. Zhang and D. Lin, Improved bounds for the implicit factorization problem, Advances in Mathematics of Communications, 7 (2013), 243-251.  doi: 10.3934/amc.2013.7.243.  Google Scholar

[22]

Y. Lu, R. Zhang, L. Q. Peng and D. D. Lin, Solving linear equations modulo unknown divisors: Revisited, Advances in Cryptology - ASIACRYPT 2015. Part Ⅰ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9452 (2015), 189-213.  doi: 10.1007/978-3-662-48797-6_9.  Google Scholar

[23]

A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Dissertation for Ph.D. Degree, University of Paderborn, 2003. Google Scholar

[24]

A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, Advances in Cryptology - CRYPTO 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3152 (2004), 213-219.  doi: 10.1007/978-3-540-28628-8_13.  Google Scholar

[25]

A. May and M. Ritzenhofen, Implicit factoring: On polynomial time factoring given only an implicit hint, Public Key Cryptography - PKC 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5443 (2009), 1-14.  doi: 10.1007/978-3-642-00468-1_1.  Google Scholar

[26] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, Cambridge University Press, Cambridge, 2000.   Google Scholar
[27]

H. Minkowski, Geometrie der Zahlen, Bibliotheca Mathematica Teubneriana, Band 40 Johnson Reprint Corp., New York-London, 1968.  Google Scholar

[28]

A. Nitaj and M. R. K. Ariffin, Implicit factorization of unbalanced RSA moduli, Journal of Applied Mathematics and Computing, 48 (2015), 349-363.  doi: 10.1007/s12190-014-0806-1.  Google Scholar

[29]

A. Nitaj, A new attack on RSA and CRT-RSA, Progress in Cryptology-AFRICACRYPT 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7374 (2012), 221-233.  doi: 10.1007/978-3-642-31410-0_14.  Google Scholar

[30]

L. Peng, L. Hu, Z. Huang and et al., Partial prime factor exposure attacks on RSA and its Takagi's variant, International Conference on Information Security Practice and Experience-ISPEC 2015, Springer International Publishing, (2015), 96–108. Google Scholar

[31]

L. Peng, L. Hu, Y. Lu and et al., Implicit factorization of RSA moduli revisited (short paper), International Workshop on Security-IWSEC 2015, Springer International Publishing, (2015), 67–76. Google Scholar

[32]

L. Q. Peng, L. Hu, J. Xu, Z. J. Huang and Y. H. Xie, Further improvement of factoring RSA moduli with implicit hint, Progress in Cryptology - AFRICACRYPT 2014, Lecture Notes in Comput. Sci., Springer, Cham, 8469 (2014), 165-177.  doi: 10.1007/978-3-319-06734-6_11.  Google Scholar

[33]

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

[34]

S. Sarkar, Partial key exposure: Generalized framework to attack RSA, Progress in Cryptology - INDOCRYPT 2011, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7107 (2011), 76-92.  doi: 10.1007/978-3-642-25578-6_7.  Google Scholar

[35]

S. Sarkar, S. Sen Gupta and S. Maitra, Partial key exposure attack on RSA - improvements for limited lattice dimensions, Progress in Cryptology - INDOCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6498 (2010), 2-16.  doi: 10.1007/978-3-642-17401-8_2.  Google Scholar

[36]

S. Sarkar and S. Maitra, Improved partial key exposure attacks on RSA by guessing a few bits of one of the prime factors, Information Security and Cryptology - ICISC 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5461 (2009), 37-51.  doi: 10.1007/978-3-642-00730-9_3.  Google Scholar

[37]

S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, IEEE Transactions on Information Theory, 57 (2011), 4002-4013.  doi: 10.1109/TIT.2011.2137270.  Google Scholar

[38]

A. Takayasu and N. Kunihiro, Partial key exposure attacks on RSA: Achieving the Boneh-Durfee bound, Selected Areas in Cryptography - SAC 2014, Lecture Notes in Comput. Sci., Springer, Cham, 8781 (2014), 345-362.  doi: 10.1007/978-3-319-13051-4_21.  Google Scholar

[39]

S. Wang, L. Qu, C. Li and et al., Generalized framework to attack RSA with special exposed bits of the private key, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100 (2017), 2113-2122. Google Scholar

[40]

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

28] for generalized IFP with shared MSBs or LSBs when $ \alpha_1^* \approx \alpha_2^* \approx \alpha^* ,\ \beta_1^* \approx \beta_2^* \approx 1- \alpha^* ,\ \delta_1^* \approx \delta_2^* \approx 0.1 $">Figure 1.  Comparison between our results and those in [28] for generalized IFP with shared MSBs or LSBs when $ \alpha_1^* \approx \alpha_2^* \approx \alpha^* ,\ \beta_1^* \approx \beta_2^* \approx 1- \alpha^* ,\ \delta_1^* \approx \delta_2^* \approx 0.1 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Our generalized result and possible improvement for the attack on RSA with known MSBs or LSBs of the prime factor
Figure Options

Download full-size image

Download as PowerPoint slide

10,18] for the attack on RSA with a small difference of prime factors">Figure 3.  Comparison between the result of our Proposition 5.2 and that in [10,18] for the attack on RSA with a small difference of prime factors
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Results for IFP and generalized IFP
IFP with shared MSBs or LSBs Generalized IFP with shared MSBs or LSBs
(For $ \alpha_1^* \approx \alpha_2^*,\ \beta_1^* \approx \beta_2^*,\ \delta_1^* = \delta_2^* = 0 $) (For any $ \alpha_1^*, \alpha_2^*, \beta_1^*, \beta_2^*, \delta_1^*, \delta_2^* $)
Results in [25] and [12]: $ t^* > 2 \beta_1^* $ Results in [28]: $ t^* > \beta_1^* + \beta_2^* + \delta_1^* + \delta_2^* $
Results in [20]: $ t^* > \frac{2\alpha_1^* \beta_1^*}{\alpha_1^*+\beta_1^*} $ Our results: $ t^* > \frac{\alpha_1^* \beta_1^*}{\alpha_1^*+\beta_1^*} + \frac{\alpha_2^*\beta_2^*}{\alpha_2^*+\beta_2^*} + \delta_1^* + \delta_2^* $
Table Options

Download as excel

IFP with shared MSBs or LSBs Generalized IFP with shared MSBs or LSBs
(For $ \alpha_1^* \approx \alpha_2^*,\ \beta_1^* \approx \beta_2^*,\ \delta_1^* = \delta_2^* = 0 $) (For any $ \alpha_1^*, \alpha_2^*, \beta_1^*, \beta_2^*, \delta_1^*, \delta_2^* $)
Results in [25] and [12]: $ t^* > 2 \beta_1^* $ Results in [28]: $ t^* > \beta_1^* + \beta_2^* + \delta_1^* + \delta_2^* $
Results in [20]: $ t^* > \frac{2\alpha_1^* \beta_1^*}{\alpha_1^*+\beta_1^*} $ Our results: $ t^* > \frac{\alpha_1^* \beta_1^*}{\alpha_1^*+\beta_1^*} + \frac{\alpha_2^*\beta_2^*}{\alpha_2^*+\beta_2^*} + \delta_1^* + \delta_2^* $
Table 2.  Comparison between the result of our Proposition 5.1 (i.e. $ t_2^* > h(\beta^*,t_1^*) $) and that in [36] (i.e. $ t_2^* > g(\beta^*,t_1^*) $) for $ \beta^* = 0.700,0.650,0.600 $
$ t_1^* $ $ 0.000 $ $ 0.010 $ $ 0.020 $ $ 0.030 $ $ 0.040 $ $ 0.050 $ $ 0.060 $ $ 0.070 $ $ 0.080 $
$ g(0.700,t_1^*) $ $ 0.627 $ $ 0.614 $ $ 0.602 $ $ 0.589 $ $ 0.577 $ $ 0.564 $ $ 0.551 $ $ 0.539 $ $ 0.526 $
$ h(0.700,t_1^*) $ $ 0.592 $ $ 0.580 $ $ 0.567 $ $ 0.555 $ $ 0.542 $ $ 0.530 $ $ 0.517 $ $ 0.504 $ $ 0.491 $
$ g(0.650,t_1^*) $ $ 0.555 $ $ 0.542 $ $ 0.530 $ $ 0.518 $ $ 0.505 $ $ 0.493 $ $ 0.480 $ $ 0.468 $ $ 0.455 $
$ h(0.650,t_1^*) $ $ 0.522 $ $ 0.510 $ $ 0.498 $ $ 0.486 $ $ 0.473 $ $ 0.461 $ $ 0.448 $ $ 0.436 $ $ 0.423 $
$ g(0.600,t_1^*) $ $ 0.482 $ $ 0.470 $ $ 0.457 $ $ 0.445 $ $ 0.433 $ $ 0.421 $ $ 0.409 $ $ 0.396 $ $ 0.384 $
$ h(0.600,t_1^*) $ $ 0.452 $ $ 0.440 $ $ 0.428 $ $ 0.416 $ $ 0.403 $ $ 0.391 $ $ 0.379 $ $ 0.367 $ $ 0.354 $
Table Options

Download as excel

$ t_1^* $ $ 0.000 $ $ 0.010 $ $ 0.020 $ $ 0.030 $ $ 0.040 $ $ 0.050 $ $ 0.060 $ $ 0.070 $ $ 0.080 $
$ g(0.700,t_1^*) $ $ 0.627 $ $ 0.614 $ $ 0.602 $ $ 0.589 $ $ 0.577 $ $ 0.564 $ $ 0.551 $ $ 0.539 $ $ 0.526 $
$ h(0.700,t_1^*) $ $ 0.592 $ $ 0.580 $ $ 0.567 $ $ 0.555 $ $ 0.542 $ $ 0.530 $ $ 0.517 $ $ 0.504 $ $ 0.491 $
$ g(0.650,t_1^*) $ $ 0.555 $ $ 0.542 $ $ 0.530 $ $ 0.518 $ $ 0.505 $ $ 0.493 $ $ 0.480 $ $ 0.468 $ $ 0.455 $
$ h(0.650,t_1^*) $ $ 0.522 $ $ 0.510 $ $ 0.498 $ $ 0.486 $ $ 0.473 $ $ 0.461 $ $ 0.448 $ $ 0.436 $ $ 0.423 $
$ g(0.600,t_1^*) $ $ 0.482 $ $ 0.470 $ $ 0.457 $ $ 0.445 $ $ 0.433 $ $ 0.421 $ $ 0.409 $ $ 0.396 $ $ 0.384 $
$ h(0.600,t_1^*) $ $ 0.452 $ $ 0.440 $ $ 0.428 $ $ 0.416 $ $ 0.403 $ $ 0.391 $ $ 0.379 $ $ 0.367 $ $ 0.354 $
Table 3.  Attacks on RSA related to Proposition 5.1
$ t_1^* = 0 $ $ t_1^*\geqslant 0 $
$ t_2^* = 0 $ Result in [3,14]: Result in [30]:
$ \beta^* < 1 - \sqrt{0.5} \approx 0.292 $ $ \beta^* < 1 - \sqrt{0.5-t_1^*} $
(No extra conditions) ($ t_1^* \leqslant 0.25 $)
$ t_2^*\geqslant 0 $ Result in [39]: Our result:
$ \beta^* < 1+t_2^* - \sqrt{0.5(1+t_2^*)} $ $ \beta^* < 1+t_2^* - \sqrt{(1+t_2^*)(0.5-t_1^*)} $
($ d_l < N^{\beta^*-0.5} $) ($ d_l < N^{\beta^*-t_1^*-0.5},\ 4t_1^* + t_2^* \leqslant 1 $)
Table Options

Download as excel

$ t_1^* = 0 $ $ t_1^*\geqslant 0 $
$ t_2^* = 0 $ Result in [3,14]: Result in [30]:
$ \beta^* < 1 - \sqrt{0.5} \approx 0.292 $ $ \beta^* < 1 - \sqrt{0.5-t_1^*} $
(No extra conditions) ($ t_1^* \leqslant 0.25 $)
$ t_2^*\geqslant 0 $ Result in [39]: Our result:
$ \beta^* < 1+t_2^* - \sqrt{0.5(1+t_2^*)} $ $ \beta^* < 1+t_2^* - \sqrt{(1+t_2^*)(0.5-t_1^*)} $
($ d_l < N^{\beta^*-0.5} $) ($ d_l < N^{\beta^*-t_1^*-0.5},\ 4t_1^* + t_2^* \leqslant 1 $)
Table 4.  Some experimental examples for Proposition 4.1 (the case of MSBs) and Proposition 4.2 (the case of LSBs) with $ \beta_1^*\approx 1- \alpha_1^*,\ \beta_2^*\approx 1- \alpha_2^* $ and $ \log_2M\approx \log_2N_1\approx \log_2N_2\approx 1500 $
Case $ t^* $ $ \alpha_1^* $ $ \alpha_2^* $ $ \delta_1^* $ $ \delta_2^* $ $ m $ $ \tau $ $ i $ $ \dim(\Lambda) $ Bit size Time(LLL)
MSBs $ 0.606 $ $ 0.679 $ $ 0.684 $ $ 0.066 $ $ 0.061 $ $ 15 $ $ 10 $ $ 10 $ $ 16 $ $ 1.008 \times 10^{4} $ 6.596 seconds
MSBs $ 0.533 $ $ 0.666 $ $ 0.799 $ $ 0.133 $ $ 0.000 $ $ 15 $ $ 11 $ $ 9 $ $ 16 $ $ 1.198 \times 10^{4} $ 7.649 seconds
MSBs $ 0.687 $ $ 0.733 $ $ 0.500 $ $ 0.000 $ $ 0.233 $ $ 23 $ $ 16 $ $ 11 $ $ 24 $ $ 1.725 \times 10^{4} $ 116.3 seconds
LSBs $ 0.529 $ $ 0.580 $ $ 0.579 $ $ 0.000 $ $ 0.000 $ $ 23 $ $ 13 $ $ 13 $ $ 24 $ $ 1.093 \times 10^{4} $ 27.73 seconds
LSBs $ 0.433 $ $ 0.752 $ $ 0.805 $ $ 0.053 $ $ 0.000 $ $ 19 $ $ 15 $ $ 14 $ $ 20 $ $ 1.782 \times 10^{4} $ 35.12 seconds
LSBs $ 0.756 $ $ 0.803 $ $ 0.479 $ $ 0.000 $ $ 0.324 $ $ 19 $ $ 15 $ $ 9 $ $ 20 $ $ 1.802 \times 10^{4} $ 88.97 seconds
Table Options

Download as excel

Case $ t^* $ $ \alpha_1^* $ $ \alpha_2^* $ $ \delta_1^* $ $ \delta_2^* $ $ m $ $ \tau $ $ i $ $ \dim(\Lambda) $ Bit size Time(LLL)
MSBs $ 0.606 $ $ 0.679 $ $ 0.684 $ $ 0.066 $ $ 0.061 $ $ 15 $ $ 10 $ $ 10 $ $ 16 $ $ 1.008 \times 10^{4} $ 6.596 seconds
MSBs $ 0.533 $ $ 0.666 $ $ 0.799 $ $ 0.133 $ $ 0.000 $ $ 15 $ $ 11 $ $ 9 $ $ 16 $ $ 1.198 \times 10^{4} $ 7.649 seconds
MSBs $ 0.687 $ $ 0.733 $ $ 0.500 $ $ 0.000 $ $ 0.233 $ $ 23 $ $ 16 $ $ 11 $ $ 24 $ $ 1.725 \times 10^{4} $ 116.3 seconds
LSBs $ 0.529 $ $ 0.580 $ $ 0.579 $ $ 0.000 $ $ 0.000 $ $ 23 $ $ 13 $ $ 13 $ $ 24 $ $ 1.093 \times 10^{4} $ 27.73 seconds
LSBs $ 0.433 $ $ 0.752 $ $ 0.805 $ $ 0.053 $ $ 0.000 $ $ 19 $ $ 15 $ $ 14 $ $ 20 $ $ 1.782 \times 10^{4} $ 35.12 seconds
LSBs $ 0.756 $ $ 0.803 $ $ 0.479 $ $ 0.000 $ $ 0.324 $ $ 19 $ $ 15 $ $ 9 $ $ 20 $ $ 1.802 \times 10^{4} $ 88.97 seconds
Table 5.  Some experimental examples for Proposition 4.3 (the case of MSBs) and Proposition 4.4 (the case of LSBs) with $ k = 1 $ and $ \log_2N\approx1000 $
Case $ t^* $ $ \alpha^* $ $ \theta^* $ $ m $ $ \tau $ $ i $ $ \dim(\Lambda) $ Bit size Time(LLL)
MSBs $ 0.240 $ $ 0.500 $ $ 0.165 $ $ 27 $ $ 13 $ $ 22 $ $ 28 $ $ 6.474 \times 10^{3} $ 23.14 seconds
MSBs $ 0.203 $ $ 0.603 $ $ 0.247 $ $ 27 $ $ 16 $ $ 20 $ $ 28 $ $ 9.531 \times 10^{3} $ 48.51 seconds
MSBs $ 0.260 $ $ 0.400 $ $ 0.000 $ $ 42 $ $ 16 $ $ 42 $ $ 43 $ $ 6.101 \times 10^{3} $ 102.1 seconds
LSBs $ 0.156 $ $ 0.501 $ $ 0.332 $ $ 42 $ $ 21 $ $ 28 $ $ 43 $ $ 1.043 \times 10^{4} $ 756.2 seconds
LSBs $ 0.255 $ $ 0.473 $ $ 0.071 $ $ 34 $ $ 16 $ $ 31 $ $ 35 $ $ 7.582 \times 10^{3} $ 65.23 seconds
LSBs $ 0.220 $ $ 0.720 $ $ 0.000 $ $ 34 $ $ 24 $ $ 34 $ $ 35 $ $ 1.709 \times 10^{4} $ 117.4 seconds
Table Options

Download as excel

Case $ t^* $ $ \alpha^* $ $ \theta^* $ $ m $ $ \tau $ $ i $ $ \dim(\Lambda) $ Bit size Time(LLL)
MSBs $ 0.240 $ $ 0.500 $ $ 0.165 $ $ 27 $ $ 13 $ $ 22 $ $ 28 $ $ 6.474 \times 10^{3} $ 23.14 seconds
MSBs $ 0.203 $ $ 0.603 $ $ 0.247 $ $ 27 $ $ 16 $ $ 20 $ $ 28 $ $ 9.531 \times 10^{3} $ 48.51 seconds
MSBs $ 0.260 $ $ 0.400 $ $ 0.000 $ $ 42 $ $ 16 $ $ 42 $ $ 43 $ $ 6.101 \times 10^{3} $ 102.1 seconds
LSBs $ 0.156 $ $ 0.501 $ $ 0.332 $ $ 42 $ $ 21 $ $ 28 $ $ 43 $ $ 1.043 \times 10^{4} $ 756.2 seconds
LSBs $ 0.255 $ $ 0.473 $ $ 0.071 $ $ 34 $ $ 16 $ $ 31 $ $ 35 $ $ 7.582 \times 10^{3} $ 65.23 seconds
LSBs $ 0.220 $ $ 0.720 $ $ 0.000 $ $ 34 $ $ 24 $ $ 34 $ $ 35 $ $ 1.709 \times 10^{4} $ 117.4 seconds
Table 6.  Some experimental examples for Proposition 5.1 (under the extra condition $ d_l < N^{\beta^*-t_1^*-0.5},\ 4t_1^* + t_2^* \leqslant 1 $) with $ \log_2N\approx2000 $
$ \beta^* $ $ t_1^* $ $ t_2^* $ $ m $ $ \tau $ $ \theta_1,\theta_2,\cdots,\theta_{\tau} $ $ \dim(\Lambda) $ Bit size Time(LLL)
$ 0.650 $ $ 0.100 $ $ 0.500 $ $ 5 $ $ 4 $ $ 2,3,4,5 $ $ 31 $ $ 1.480 \times 10^{4} $ 40.83 seconds
$ 0.656 $ $ 0.141 $ $ 0.435 $ $ 5 $ $ 4 $ $ 2,3,4,5 $ $ 31 $ $ 1.426 \times 10^{4} $ 36.50 seconds
$ 0.580 $ $ 0.049 $ $ 0.480 $ $ 7 $ $ 5 $ $ 2,3,4,5,7 $ $ 55 $ $ 2.024 \times 10^{4} $ 1282 seconds
$ 0.543 $ $ 0.012 $ $ 0.440 $ $ 7 $ $ 5 $ $ 2,3,5,6,7 $ $ 53 $ $ 1.989 \times 10^{4} $ 680.9 seconds
$ 0.784 $ $ 0.072 $ $ 0.692 $ $ 6 $ $ 5 $ $ 2,3,4,5,6 $ $ 43 $ $ 2.022 \times 10^{4} $ 238.9 seconds
$ 0.708 $ $ 0.118 $ $ 0.525 $ $ 6 $ $ 5 $ $ 2,3,4,5,6 $ $ 43 $ $ 1.820 \times 10^{4} $ 225.9 seconds
Table Options

Download as excel

$ \beta^* $ $ t_1^* $ $ t_2^* $ $ m $ $ \tau $ $ \theta_1,\theta_2,\cdots,\theta_{\tau} $ $ \dim(\Lambda) $ Bit size Time(LLL)
$ 0.650 $ $ 0.100 $ $ 0.500 $ $ 5 $ $ 4 $ $ 2,3,4,5 $ $ 31 $ $ 1.480 \times 10^{4} $ 40.83 seconds
$ 0.656 $ $ 0.141 $ $ 0.435 $ $ 5 $ $ 4 $ $ 2,3,4,5 $ $ 31 $ $ 1.426 \times 10^{4} $ 36.50 seconds
$ 0.580 $ $ 0.049 $ $ 0.480 $ $ 7 $ $ 5 $ $ 2,3,4,5,7 $ $ 55 $ $ 2.024 \times 10^{4} $ 1282 seconds
$ 0.543 $ $ 0.012 $ $ 0.440 $ $ 7 $ $ 5 $ $ 2,3,5,6,7 $ $ 53 $ $ 1.989 \times 10^{4} $ 680.9 seconds
$ 0.784 $ $ 0.072 $ $ 0.692 $ $ 6 $ $ 5 $ $ 2,3,4,5,6 $ $ 43 $ $ 2.022 \times 10^{4} $ 238.9 seconds
$ 0.708 $ $ 0.118 $ $ 0.525 $ $ 6 $ $ 5 $ $ 2,3,4,5,6 $ $ 43 $ $ 1.820 \times 10^{4} $ 225.9 seconds
Table 7.  The basis matrix $ \mathcal{B} $ when $ m = 5, \tau = 4, i = 3 $
$ (b')^2 (x')^5 $ $ b' (x')^4 z^* $ $ (x')^3 (z^*)^2 $ $ v (x')^2 (z^*)^3 $ $ v^2 x' (z^*)^4 $ $ v^3 (z^*)^5 $
$ g_0 $ $ A^4(B')^2 (X')^5 $
$ g_1 $ $ * $ $ A^3 B' (X')^4 Z^* $
$ g_2 $ $ * $ $ * $ $ A^2(X')^3 (Z^*)^2 $
$ g_3 $ $ * $ $ * $ $ * $ $ A V (X')^2 (Z^*)^3 $
$ g_4 $ $ * $ $ * $ $ * $ $ * $ $ V^2 X' (Z^*)^4 $
$ g_5 $ $ * $ $ * $ $ * $ $ * $ $ * $ $ V^3 (Z^*)^5 $
Table Options

Download as excel

$ (b')^2 (x')^5 $ $ b' (x')^4 z^* $ $ (x')^3 (z^*)^2 $ $ v (x')^2 (z^*)^3 $ $ v^2 x' (z^*)^4 $ $ v^3 (z^*)^5 $
$ g_0 $ $ A^4(B')^2 (X')^5 $
$ g_1 $ $ * $ $ A^3 B' (X')^4 Z^* $
$ g_2 $ $ * $ $ * $ $ A^2(X')^3 (Z^*)^2 $
$ g_3 $ $ * $ $ * $ $ * $ $ A V (X')^2 (Z^*)^3 $
$ g_4 $ $ * $ $ * $ $ * $ $ * $ $ V^2 X' (Z^*)^4 $
$ g_5 $ $ * $ $ * $ $ * $ $ * $ $ * $ $ V^3 (Z^*)^5 $
[1]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311
[2]

Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1
[3]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042
[4]

Michele Barbi, Angelo Di Garbo, Rita Balocchi. Improved integrate-and-fire model for RSA. Mathematical Biosciences & Engineering, 2007, 4 (4) : 609-615. doi: 10.3934/mbe.2007.4.609
[5]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[6]

Matthias Eller. A remark on Littman's method of boundary controllability. Evolution Equations & Control Theory, 2013, 2 (4) : 621-630. doi: 10.3934/eect.2013.2.621
[7]

Christopher M. Kellett. Classical converse theorems in Lyapunov's second method. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2333-2360. doi: 10.3934/dcdsb.2015.20.2333
[8]

Mikhail Dokuchaev, Guanglu Zhou, Song Wang. A modification of Galerkin's method for option pricing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021077
[9]

Lars Grüne, Peter E. Kloeden, Stefan Siegmund, Fabian R. Wirth. Lyapunov's second method for nonautonomous differential equations. Discrete & Continuous Dynamical Systems, 2007, 18 (2&3) : 375-403. doi: 10.3934/dcds.2007.18.375
[10]

Darya V. Verveyko, Andrey Yu. Verisokin. Application of He's method to the modified Rayleigh equation. Conference Publications, 2011, 2011 (Special) : 1423-1431. doi: 10.3934/proc.2011.2011.1423
[11]

Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219
[12]

Bernd Hofmann, Barbara Kaltenbacher, Elena Resmerita. Lavrentiev's regularization method in Hilbert spaces revisited. Inverse Problems & Imaging, 2016, 10 (3) : 741-764. doi: 10.3934/ipi.2016019
[13]

Pavel Eichler, Radek Fučík, Robert Straka. Computational study of immersed boundary - lattice Boltzmann method for fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 819-833. doi: 10.3934/dcdss.2020349
[14]

Zhonghua Qiao, Xuguang Yang. A multiple-relaxation-time lattice Boltzmann method with Beam-Warming scheme for a coupled chemotaxis-fluid model. Electronic Research Archive, 2020, 28 (3) : 1207-1225. doi: 10.3934/era.2020066
[15]

Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040
[16]

Rua Murray. Ulam's method for some non-uniformly expanding maps. Discrete & Continuous Dynamical Systems, 2010, 26 (3) : 1007-1018. doi: 10.3934/dcds.2010.26.1007
[17]

David Blázquez-Sanz, Juan J. Morales-Ruiz. Lie's reduction method and differential Galois theory in the complex analytic context. Discrete & Continuous Dynamical Systems, 2012, 32 (2) : 353-379. doi: 10.3934/dcds.2012.32.353
[18]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[19]

R. Baier, M. Dellnitz, M. Hessel-von Molo, S. Sertl, I. G. Kevrekidis. The computation of convex invariant sets via Newton's method. Journal of Computational Dynamics, 2014, 1 (1) : 39-69. doi: 10.3934/jcd.2014.1.39
[20]

Jutta Bikowski, Jennifer L. Mueller. 2D EIT reconstructions using Calderon's method. Inverse Problems & Imaging, 2008, 2 (1) : 43-61. doi: 10.3934/ipi.2008.2.43

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences