A new partial key exposure attack on multi-power RSA

Muhammed F. Esgin; Mehmet S. Kiraz; Osmanbey Uzunkol

doi:10.1007/978-3-319-23021-4_10

A new partial key exposure attack on multi-power RSA

Muhammed F. Esgin, Mehmet S. Kiraz, Osmanbey Uzunkol

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

4 Citations (Scopus)

Abstract

An important attack on multi-power RSA (N = p^rq) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that N can be factored efficiently for r = 2 with private exponent d satisfying d < N^0.395. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith’s algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents e (resp. d) when the exponent d (resp. e) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of e. For practical validation of our attack, we demonstrate several computer algebra experiments.

Original language	English
Title of host publication	Algebraic Informatics
Subtitle of host publication	6th International Conference, CAI 2015 Stuttgart, Germany, September 1–4, 2015 Proceedings
Editors	Andreas Maletti
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	103-114
Number of pages	12
ISBN (Print)	9783319230207
DOIs	https://doi.org/10.1007/978-3-319-23021-4_10
Publication status	Published - 2015
Externally published	Yes
Event	International Conference on Algebraic Informatics 2015 - Stuttgart, Germany Duration: 1 Sept 2015 → 4 Sept 2015 Conference number: 6th https://www.springer.com/gp/book/9783319230207 (Proceedings) https://easychair.org/conferences/?conf=cai2015 (Conference website)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9270
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Algebraic Informatics 2015
Abbreviated title	CAI 2015
Country/Territory	Germany
City	Stuttgart
Period	1/09/15 → 4/09/15
Internet address	https://www.springer.com/gp/book/9783319230207 (Proceedings) https://easychair.org/conferences/?conf=cai2015 (Conference website)

Keywords

Coppersmith’s method
Integer factorization
Multi-power RSA
Partial key exposure
Small roots of polynomials

Access to Document

10.1007/978-3-319-23021-4_10

Cite this

@inproceedings{71c21845a5b44024853bdd7e3648a0a1,

title = "A new partial key exposure attack on multi-power RSA",

abstract = "An important attack on multi-power RSA (N = prq) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that N can be factored efficiently for r = 2 with private exponent d satisfying d < N0.395. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith{\textquoteright}s algorithm and Gr{\"o}bner basis computation. Our attack works for all multi-power RSA exponents e (resp. d) when the exponent d (resp. e) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of e. For practical validation of our attack, we demonstrate several computer algebra experiments.",

keywords = "Coppersmith{\textquoteright}s method, Integer factorization, Multi-power RSA, Partial key exposure, Small roots of polynomials",

author = "Esgin, {Muhammed F.} and Kiraz, {Mehmet S.} and Osmanbey Uzunkol",

year = "2015",

doi = "10.1007/978-3-319-23021-4_10",

language = "English",

isbn = "9783319230207",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "103--114",

editor = "Andreas Maletti",

booktitle = "Algebraic Informatics",

note = "International Conference on Algebraic Informatics 2015, CAI 2015 ; Conference date: 01-09-2015 Through 04-09-2015",

url = "https://www.springer.com/gp/book/9783319230207, https://easychair.org/conferences/?conf=cai2015 ",

}

Esgin, MF, Kiraz, MS & Uzunkol, O 2015, A new partial key exposure attack on multi-power RSA. in A Maletti (ed.), Algebraic Informatics: 6th International Conference, CAI 2015 Stuttgart, Germany, September 1–4, 2015 Proceedings. Lecture Notes in Computer Science , vol. 9270, Springer, Cham Switzerland, pp. 103-114, International Conference on Algebraic Informatics 2015, Stuttgart, Baden-Württemberg, Germany, 1/09/15. https://doi.org/10.1007/978-3-319-23021-4_10

A new partial key exposure attack on multi-power RSA. / Esgin, Muhammed F.; Kiraz, Mehmet S.; Uzunkol, Osmanbey.
Algebraic Informatics: 6th International Conference, CAI 2015 Stuttgart, Germany, September 1–4, 2015 Proceedings. ed. / Andreas Maletti. Cham Switzerland: Springer, 2015. p. 103-114 (Lecture Notes in Computer Science ; Vol. 9270).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A new partial key exposure attack on multi-power RSA

AU - Esgin, Muhammed F.

AU - Kiraz, Mehmet S.

AU - Uzunkol, Osmanbey

N1 - Conference code: 6th

PY - 2015

Y1 - 2015

N2 - An important attack on multi-power RSA (N = prq) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that N can be factored efficiently for r = 2 with private exponent d satisfying d < N0.395. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith’s algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents e (resp. d) when the exponent d (resp. e) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of e. For practical validation of our attack, we demonstrate several computer algebra experiments.

AB - An important attack on multi-power RSA (N = prq) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that N can be factored efficiently for r = 2 with private exponent d satisfying d < N0.395. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith’s algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents e (resp. d) when the exponent d (resp. e) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of e. For practical validation of our attack, we demonstrate several computer algebra experiments.

KW - Coppersmith’s method

KW - Integer factorization

KW - Multi-power RSA

KW - Partial key exposure

KW - Small roots of polynomials

UR - http://www.scopus.com/inward/record.url?scp=84949845482&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-23021-4_10

DO - 10.1007/978-3-319-23021-4_10

M3 - Conference Paper

AN - SCOPUS:84949845482

SN - 9783319230207

T3 - Lecture Notes in Computer Science

SP - 103

EP - 114

BT - Algebraic Informatics

A2 - Maletti, Andreas

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Algebraic Informatics 2015

Y2 - 1 September 2015 through 4 September 2015

ER -

A new partial key exposure attack on multi-power RSA

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this