Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
One-Round Strong Oblivious Signature-Based Envelope Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Partial Key Exposure Attacks on RSA with Multiple Exponent Pairs

Authors : Atsushi Takayasu, Noboru Kunihiro

Published in: Information Security and Privacy

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

So far, several papers have analyzed attacks on RSA when attackers know the least significant bits of a secret exponent d as well as a public modulus N and a public exponent e, the so-called partial key exposure attacks. Aono (ACISP 2013), and Takayasu and Kunihiro (ACISP 2014) generalized the attacks when there are multiple pairs of a public/secret exponent \((e_1,d_1),\ldots ,(e_n,d_n)\) for the same public modulus N. The standard RSA is a special case of the generalization, i.e., \(n=1\). They revealed that RSA becomes more vulnerable when there are more exponent pairs. However, their results have two obvious drawbacks. First, partial key exposure situations which they considered are restrictive. They have proposed the attacks only for small secret exponents, although attacks for large secret exponents have also been analyzed for the standard RSA. Second, they could not generalize the attacks perfectly. More concretely, their attacks for \(n=1\) do not correspond to the currently known best attacks on the standard RSA.
In this paper, we propose improved partial key exposure attacks on RSA with multiple exponent pairs. Our results completely solve the above drawbacks. Our attacks are the first results for large exponents, and our attacks for \(n=1\) correspond to the currently known best attacks on the standard RSA. Our results for small secret exponents are superior to previous results when \(n=1\) and 2, and when \(n \ge 3\) and \(d_1,\ldots ,d_n>N^{3(n-1)/(3n+1)}\).

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Anonymous Identity-Based Broadcast Encryption with Revocation for File Sharing
next chapter A New Attack on Three Variants of the RSA Cryptosystem
Footnotes
1
At a glance, a situation (b) seems useless, since d is defined as \(d \in \mathbb {Z}^*_{\phi (N)}\) in many cases, and \( \beta \le 1\) always holds. However, some implementations use an exponent which is larger than N. To decrypt/sign, one may use \(d+k \phi (N)\) in turn for some integer \(k>0\). This implementation offers better resistance against side-channel attacks [9] or faster calculation by setting the exponent as low Hamming weight.
 
2
In [2, 26], they use \( \delta \), not \( \beta -\delta \) as ours, to represent portions of exposed bits. However, we follow the notation from [11, 27].
 
3
From May [17] and Coron and May’s [10] results, given whole bits of d then the factorization of N is a trivial. However, it does not immediately suggest that partial key exposure attacks always work when whole bits of d are given. Indeed, Ernst et al. [11] claimed to find such improved attacks is an interesting open problem.
 
Literature
1.
Aono, Y.: A new lattice construction for partial key exposure attack for RSA. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 34–53. Springer, Heidelberg (2009)CrossRef
2.
Aono, Y.: Minkowski sum based lattice construction for multivariate simultaneous coppersmith’s technique and applications to RSA. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 88–103. Springer, Heidelberg (2013)CrossRef
3.
Blömer, J., May, A.: New partial key exposure attacks on RSA. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 27–43. Springer, Heidelberg (2003)CrossRef
4.
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key \(d\) less than \(N^{0.292}\). IEEE Trans. Inf. Theory 46(4), 1339–1349 (2000)MathSciNetCrossRefMATH
5.
Boneh, D., Durfee, G., Frankel, Y.: An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 25–34. Springer, Heidelberg (1998)CrossRef
6.
Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)CrossRef
7.
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH
8.
Coppersmith, D.: Finding small solutions to small degree polynomials. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 20–31. Springer, Heidelberg (2001)CrossRef
9.
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)CrossRef
10.
Coron, J.-S., May, A.: Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J. Cryptol. 20(1), 39–50 (2007)MathSciNetCrossRefMATH
11.
Ernst, M., Jochemsz, E., May, A., de Weger, B.: Partial key exposure attacks on RSA up to full size exponents. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 371–386. Springer, Heidelberg (2005)CrossRef
12.
Herrmann, M., May, A.: Attacking power generators using unravelled linearization: when do we output too much? In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 487–504. Springer, Heidelberg (2009)CrossRef
13.
Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M.J. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
14.
Howgrave-Graham, N., Seifert, J.-P.: Extending wiener’s attack in the presence of many decrypting exponents. In: Baumgart, R. (ed.) CQRE 1999. LNCS, vol. 1740, pp. 153–166. Springer, Heidelberg (1999)CrossRef
15.
Joye, M., Lepoint, T.: Partial key exposure on RSA with private exponents larger than N. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 369–380. Springer, Heidelberg (2012)CrossRef
16.
17.
May, A.: Computing the RSA secret key is deterministic polynomial time equivalent to factoring. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 213–219. Springer, Heidelberg (2004)CrossRef
18.
19.
Nguyên, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146–180. Springer, Heidelberg (2001)CrossRef
20.
Nguyen, P.Q., Valláe, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2010)MATH
21.
Peng, L., Hu, L., Lu, Y., Sarkar, S., Xu, J., Huang, Z.: Cryptanalysis of Variants of RSA with Multiple Small Secret Exponents. In: Biryukov, A., Goyal, V. (eds.) INDOCRYPT 2015. LNCS, vol. 9462, pp. 105–123. Springer, Heidelberg (2015)CrossRef
22.
Sarkar, S., Sen Gupta, S., Maitra, S.: Partial key exposure attack on RSA – improvements for limited lattice dimensions. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 2–16. Springer, Heidelberg (2010)CrossRef
23.
24.
25.
Takayasu, A., Kunihiro, N.: Better lattice constructions for solving multivariate linear equations modulo unknown divisors. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 118–135. Springer, Heidelberg (2013)CrossRef
26.
Takayasu, A., Kunihiro, N.: Cryptanalysis of RSA with multiple small secret exponents. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 176–191. Springer, Heidelberg (2014)
27.
Takayasu, A., Kunihiro, N.: Partial key exposure attacks on RSA: achieving the boneh-durfee bound. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 345–362. Springer, Heidelberg (2014)CrossRef
28.
Metadata
Title
Partial Key Exposure Attacks on RSA with Multiple Exponent Pairs
Authors
Atsushi Takayasu
Noboru Kunihiro
Copyright Year
2016
Book
Information Security and Privacy

Print ISBN: 978-3-319-40366-3

Electronic ISBN: 978-3-319-40367-0

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-40367-0_15

Premium Partner

    Image Credits