Selective forgery of rsa signatures with fixed-pattern padding

Arjen K. Lenstra; Igor E. Shparlinski

doi:10.1007/3-540-45664-3_16

Selective forgery of rsa signatures with fixed-pattern padding

Arjen K. Lenstra, Igor E. Shparlinski

School of Computing

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

3 Citations (Scopus)

Abstract

We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures that was presented at Crypto 2001. For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64 n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide.

Original language	English
Title of host publication	Public Key Cryptography
Subtitle of host publication	5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings
Editors	David Naccache, Pascal Paillier
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	228-236
Number of pages	9
Volume	2274
ISBN (Print)	3540431683, 9783540431688
DOIs	https://doi.org/10.1007/3-540-45664-3_16
Publication status	Published - 2002
Event	5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 - Paris, France Duration: 12 Feb 2002 → 14 Feb 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2274
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002
Country/Territory	France
City	Paris
Period	12/02/02 → 14/02/02

Access to Document

10.1007/3-540-45664-3_16

Cite this

Lenstra, A. K., & Shparlinski, I. E. (2002). Selective forgery of rsa signatures with fixed-pattern padding. In D. Naccache, & P. Paillier (Eds.), Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings (Vol. 2274, pp. 228-236). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2274). Springer, Springer Nature. https://doi.org/10.1007/3-540-45664-3_16

Lenstra, Arjen K. ; Shparlinski, Igor E. / Selective forgery of rsa signatures with fixed-pattern padding. Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings. editor / David Naccache ; Pascal Paillier. Vol. 2274 Berlin : Springer, Springer Nature, 2002. pp. 228-236 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{d92c183b76a643d0afa2f229c332eede,

title = "Selective forgery of rsa signatures with fixed-pattern padding",

abstract = "We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures that was presented at Crypto 2001. For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64 n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide.",

author = "Lenstra, \{Arjen K.\} and Shparlinski, \{Igor E.\}",

year = "2002",

doi = "10.1007/3-540-45664-3\_16",

language = "English",

isbn = "3540431683",

volume = "2274",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "228--236",

editor = "David Naccache and Pascal Paillier",

booktitle = "Public Key Cryptography",

address = "United States",

note = "5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 ; Conference date: 12-02-2002 Through 14-02-2002",

}

Lenstra, AK & Shparlinski, IE 2002, Selective forgery of rsa signatures with fixed-pattern padding. in D Naccache & P Paillier (eds), Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings. vol. 2274, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2274, Springer, Springer Nature, Berlin, pp. 228-236, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France, 12/02/02. https://doi.org/10.1007/3-540-45664-3_16

Selective forgery of rsa signatures with fixed-pattern padding. / Lenstra, Arjen K.; Shparlinski, Igor E.
Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings. ed. / David Naccache; Pascal Paillier. Vol. 2274 Berlin: Springer, Springer Nature, 2002. p. 228-236 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2274).

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

TY - CHAP

T1 - Selective forgery of rsa signatures with fixed-pattern padding

AU - Lenstra, Arjen K.

AU - Shparlinski, Igor E.

PY - 2002

Y1 - 2002

N2 - We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures that was presented at Crypto 2001. For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64 n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide.

AB - We present a practical selective forgery attack against RSA signatures with fixed-pattern padding shorter than two thirds of the modulus length. Our result extends the practical existential forgery of such RSA signatures that was presented at Crypto 2001. For an n-bit modulus the heuristic asymptotic runtime of our forgery is comparable to the time required to factor a modulus of only 9/64 n bits. Thus, the security provided by short fixed-pattern padding is negligible compared to the security it is supposed to provide.

UR - https://www.scopus.com/pages/publications/84958972563

U2 - 10.1007/3-540-45664-3_16

DO - 10.1007/3-540-45664-3_16

M3 - Chapter

AN - SCOPUS:84958972563

SN - 3540431683

SN - 9783540431688

VL - 2274

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 228

EP - 236

BT - Public Key Cryptography

A2 - Naccache, David

A2 - Paillier, Pascal

PB - Springer, Springer Nature

CY - Berlin

T2 - 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002

Y2 - 12 February 2002 through 14 February 2002

ER -

Lenstra AK, Shparlinski IE. Selective forgery of rsa signatures with fixed-pattern padding. In Naccache D, Paillier P, editors, Public Key Cryptography: 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002 Paris, France, February 12–14, 2002 Proceedings. Vol. 2274. Berlin: Springer, Springer Nature. 2002. p. 228-236. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45664-3_16

Selective forgery of rsa signatures with fixed-pattern padding

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this