Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to CREST Crypto-Math Project Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Recent Progress on Coppersmith’s Lattice-Based Method: A Survey

verfasst von : Yao Lu, Liqiang Peng, Noboru Kunihiro

Erschienen in: Mathematical Modelling for Next-Generation Cryptography

Verlag: Springer Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In 1996, Coppersmith proposed a lattice-based method to solve the small roots of a univariate modular equation in polynomial time. Since its invention, Coppersmith’s method has become an important tool in the cryptanalysis of RSA crypto algorithm and its variants. In 2006, Jochemsz and May introduced a general strategy to solve small roots of any form of multivariate modular equations in polynomial time. Based on Jochemsz–May’s strategy, for any given multivariate equations one can easily construct the desired lattices with triangular matrix basis. However, for some attacks, Jochemsz–May’s general strategy could not fully capture the algebraic structure of the target polynomials. Thus, some sophisticated techniques that can deeply exploit the algebraic relations have been proposed. In this paper, we give a survey of these recent approaches for lattice constructions, and also give small examples to show how these approaches work.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On Analysis of Recovering Short Generator Problems via Upper and Lower Bounds of Dirichlet L-functions: Part 2
Nächstes Kapitel How to Strengthen the Security of Signature Schemes in the Leakage Models: A Survey
Literatur
1.
A. Bauer, D. Vergnaud, J. Zapalowicz, Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith’s methods, in PKC 2012 (2012), pp. 609–626
2.
J. Blömer, A. May, New partial key exposure attacks on RSA, in CRYPTO 2003 (2003), pp. 27–43
3.
D. Boneh, G. Durfee, Cryptanalysis of RSA with private key \(d\) less than \(N^{0.292}\). IEEE Trans. Inf. Theory 46(4), 1339–1349 (2000)MathSciNetCrossRefMATH
4.
D. Boneh, G. Durfee, Y. Frankel, An attack on RSA given a small fraction of the private key bits, in ASIACRYPT 1998 (1998), pp. 25–34
5.
H. Cohn, N. Heninger, Approximate common divisors via lattices, in ANTS-X (2012)
6.
D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, in EUROCRYPT 1996 (1996), pp. 178–189
7.
D. Coppersmith, Finding a small root of a univariate modular equation, in EUROCRYPT 1996 (1996), pp. 155–165
8.
J. Coron, A. May, Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J. Cryptol. 20(1), 39–50 (2007)MathSciNetCrossRefMATH
9.
J. Coron, A. Joux, I. Kizhvatov, D. Naccache, P. Paillier, Fault attacks on RSA signatures with partially unknown messages, in CHES 2009 (2009), pp. 444–456
10.
J. Coron, D. Naccache, M. Tibouchi, Fault attacks against EMV signatures, in CT-RSA 2010 (2010), pp. 208–220
11.
M.J. Coster, B.A. LaMacchia, A.M. Odlyzko, An improved low-density subset sum algorithm, in EUROCRYPT 1991 (1991), pp. 54–67
12.
G. Durfee, P.Q. Nguyen, Cryptanalysis of the RSA schemes with short secret exponent from Asiacrypt’99, in ASIACRYPT 2000 (2000), pp. 14–29
13.
M. Ernst, E. Jochemsz, A. May, B. de Weger, Partial key exposure attacks on RSA up to full size exponents, in EUROCRYPT 2005 (2005), pp. 371–384
14.
P.A. Fouque, N. Guillermin, D. Leresteux, M. Tibouchi, J.C. Zapalowicz, Attacking RSA-CRT signatures with faults on montgomery multiplication. J. Cryptogr. Eng. 3(1), 59–72 (2013)CrossRefMATH
15.
M. Herrmann, Improved cryptanalysis of the multi-prime \(\phi \)-hiding assumption, in AFRICACRYPT 2011 (2011), pp. 92–99
16.
17.
M. Herrmann, A. May, Solving linear equations modulo divisors: on factoring given any bits, in ASIACRYPT 2008 (2008), pp. 406–424
18.
M. Herrmann, A. May, Attacking power generators using unravelled linearization: when do we output too much? in ASIACRYPT 2009 (2009), pp. 487–504
19.
M. Herrmann, A. May, Maximizing small root bounds by linearization and applications to small secret exponent RSA, in PKC 2010 (2010), pp. 53–69
20.
N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in Cryptography and Coding 1997 (1997), pp. 131–142
21.
N. Howgrave-Graham, Approximate integer common divisors, in CaLC 2001 (2001), pp. 51–66
22.
Z. Huang, L. Hu, J. Xu, Attacking RSA with a composed decryption exponent using unravelled linearization, in Inscrypt 2014 (2014), pp. 207–219
23.
E. Jochemsz, A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in ASIACRYPT 2006 (2006), pp. 267–282
24.
E. Jochemsz, A. May, A polynomial time attack on RSA with private CRT-exponents smaller than \(N^{0.073}\), in CRYPTO 2007 (2006), pp. 395–411
25.
T. Kleinjung, K. Aoki, J. Franke, A.K. Lenstra, E. Thomé, J.W. Bos, P. Gaudry, A. Kruppa, P.L. Montgomery, D.A. Osvik, H.J.J. te Riele, A. Timofeev, P. Zimmermann, Factorization of a 768-bit RSA modulus, in CRYPTO 2010 (2010), pp. 333–350
26.
N. Kunihiro, On optimal bounds of small inverse problems and approximate GCD problmes with higher degree, in ISC 2012 (2012), pp. 55–69
27.
N. Kunihiro, K. Kurosawa, Deterministic polynomial time equivalence between factoring and key-recovery attack on Takagi’s RSA, in PKC 2007 (2007), pp. 412–425
28.
N. Kunihiro, N. Shinohara, T. Izu, A unified framework for small secret exponent attack on RSA. IEICE Trans. 97-A(6), 1285–1295 (2014)
29.
J.C. Lagarias, A.M. Odlyzko, Solving low-density subset sum problems. J. ACM 32(1), 229–246 (1985)
30.
A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH
31.
A.K. Lenstra, E. Tromer, A. Shamir, W. Kortsmit, B. Dodson, J.P. Hughes, P.C. Leyland, Factoring estimates for a 1024-bit RSA modulus, in ASIACRYPT 2003 (2003), pp. 55–74
32.
Y. Lu, R. Zhang, D. Lin, Factoring RSA modulus with known bits from both \(p\) and \(q\): a lattice method, in NSS 2013 (2013), pp. 393–404
33.
Y. Lu, R. Zhang, D. Lin, Factoring multi-power RSA modulus \(N=p^rq\) with partial known bits, in ACISP 2013 (2013), pp. 57–71
34.
Y. Lu, R. Zhang, D. Lin, New partial key exposure attacks on CRT-RSA with large public exponents, in ACNS 2014 (2014), pp. 151–162
35.
Y. Lu, R. Zhang, L. Peng, D. Lin, Solving linear equations modulo unknown divisors: revisited, in ASIACRYPT 2015, Part I (2015), pp. 189–213
36.
37.
A. May, Secret exponent attacks on RSA-type schemes with moduli \(N=p^rq\), in PKC 2004 (2004), pp. 218–230
38.
A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, in CRYPTO 2004 (2004), pp. 213–219
39.
A. May, M. Ritzenhofen, Implicit factoring: on polynomial time factoring given only an implicit hint, in Proceedings of the PKC 2009 (2009), pp. 1–14
40.
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1996), pp. 118–122CrossRefMATH
41.
P.Q. Nguyen, B. Vallée (eds.), The LLL Algorithm - Survey and Applications. Information Security and Cryptography (Springer, Heidelberg, 2010)
42.
L. Peng, L. Hu, J. Xu, Z. Huang, Y. Xie, Further improvement of factoring RSA moduli with implicit hint, in AFRICACRYPT 2014 (2014), pp. 165–177
43.
L. Peng, L. Hu, Y. Lu, H. Wei, An improved analysis on three variants of the RSA cryptosystem. To appear in Inscrypt (2016)
44.
45.
R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
46.
47.
S. Sarkar, Revisiting prime power RSA. Discret. Appl. Math. 203, 127–133 (2016)
48.
S. Sarkar, S. Maitra, Partial key exposure attack on CRT-RSA, in ACNS 2009 (2009), pp. 473–484
49.
S. Sarkar, S. Maitra, Approximate integer common divisor problem relates to implicit factorization. IEEE Trans. Inf. Theory 57(6), 4002–4013 (2011)MathSciNetCrossRefMATH
50.
P.W. Shor, Algorithms for quantum computation: discrete log and factoring, in FOCS 1994 (1994), pp. 124–134
51.
52.
A. Takayasu, N. Kunihiro, Better lattice constructions for solving multivariate linear equations modulo unknown divisors, in ACISP 2013 (2013), pp. 118–135
53.
A. Takayasu, N. Kunihiro, Cryptanalysis of RSA with multiple small secret exponents, in ACISP 2014 (2014), pp. 176–191
54.
A. Takayasu, N. Kunihiro, Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound, in SAC 2014 (2014), pp. 345–362
55.
A. Takayasu, N. Kunihiro, Partial key exposure attacks on CRT-RSA: better cryptanalysis to full size encryption exponents, in ACNS 2015 (2015), pp. 518–537
56.
A. Takayasu, N. Kunihiro, Partial key exposure attacks on RSA with multiple exponent pairs, in ACISP 2016 (2016), pp. 243–257
57.
A. Takayasu, N. Kunihiro, How to generalize RSA cryptanalysis, in PKC 2016, Part II (2016), pp. 67–97
58.
A. Takayasu, N. Kunihiro, Partial key exposure attacks on CRT-RSA: general improvement for the exposed least significant bits, in ISC 2016 (2016), pp. 35–47
59.
A. Takayasu, N. Kunihiro, Small secret exponent attacks on RSA with unbalanced prime factors, in ISITA 2016 (2016), pp. 236–240
60.
A. Takayasu, N. Kunihiro, A tool kit for partial key exposure attacks on RSA. To appear in CT-RSA 2017 (2017)
61.
A. Takayasu, N. Kunihiro, General bounds for small inverse problems and its applications to multi-prime RSA. IEICE Trans. 100-A(1), 50–61 (2017)
62.
A. Takayasu, Y. Lu, L. Peng, Small CRT-exponent RSA revisited. To appear in EUROCRYPT 2017 (2017)
63.
K. Tosu, N. Kunihiro, Optimal bounds for multi-prime \(\phi \)-hiding assumption, in ACISP 2012 (2012), pp. 1–14
64.
M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully homomorphic encryption over the integers, in EUROCRYPT 2010 (2010), pp. 24–43
65.
Metadaten
Titel
Recent Progress on Coppersmith’s Lattice-Based Method: A Survey
verfasst von
Yao Lu
Liqiang Peng
Noboru Kunihiro
Copyright-Jahr
2018
Verlag
Springer Singapore
Buch
Mathematical Modelling for Next-Generation Cryptography

Print ISBN: 978-981-10-5064-0

Electronic ISBN: 978-981-10-5065-7

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-981-10-5065-7_16