zbMATH — the first resource for mathematics

The insecurity of the elliptic curve digital signature algorithm with partially known nonces. (English) Zbl 1039.94008
This paper contains the first provable polynomial-time attack against the elliptic curve digital signature algorithm, when the nonces are partially known. The “nonces” are the random integers used to disguise the contribution of the secret key in the digital signature. N. Howgrave-Graham and N. Smart [Des. Codes Cryptography 23, 283–290 (2001; Zbl 1006.94022)] proposed several heuristic attacks against DSA assuming that a certain (not too small) number of bits of the nonces are known. P. Q. Nguyen and I. E. Shparlinski [J. Cryptology 15, 151–176 (2002; Zbl 1009.94011)] obtained provable polynomial-time attacks to DSA when the nonces are partially known, based on a generalization of the work of Boneh-Venkatesan on the hidden number problem. In this paper these ideas are extended to the case of ECDSA, building on results on the distribution of ECDSA signatures, based on bounds of exponential sums valuated on \(x\)-coordinates of elliptic curves over finite fields.

94A62 Authentication, digital signatures and secret sharing
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T23 Exponential sums
14H52 Elliptic curves
94A60 Cryptography
Full Text: DOI