The insecurity of the digital signature algorithm with partially known nonces (Q1849602)

The authors look at an attack on the Digital Signature Algorithm (DSA) which suggests cautionary use of pseudo-random generation of a nonce within DSA. In particular, they present a polynomial-time algorithm which recovers (provably) the signer's secret DSA key (under suitable and reasonable assumptions). Previous attacks were only heuristic, while this attack (which extends work of Boneh and Venkatesan) establishes uniformity statements on the DSA signatures. The efficiency of the attack has been verified experimentally.