tailieunhanh - The Digital Signature Algorithm with Partially Known Nonces

We present a polynomial-time algorithm that provably recovers the signer’s secret DSA key when a few bits of the random nonces k (used at eachsignature generation) are known for a number of DSA signatures at most linear inlog q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. | The Insecurity of the Digital Signature Algorithm with Partially Known Nonces Phong Q. Nguyen pnguyen@ Departement d Informatique Ecole Normale Superieure 45 rue d Ulm 75230 Paris Cedex 05 France URL http pnguyen Igor E. Shparlinski igor@ Department of Computing Macquarie University Sydney NSW 2109 Australia URL http igor Abstract. We present a polynomial-time algorithm that provably recovers the signer s secret DSA key when a few bits of the random nonces k used at each signature generation are known for a number of DSA signatures at most linear in log q q denoting as usual the small prime of DSA under a reasonable assumption on the hash function used in DSA. The number of required bits is about log1 2 q and can be further decreased to 2 if one assumes access to ideal lattice basis reduction namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem HNP introduced at Crypto 96 by Boneh and Venkatesan in order to study the bit-security of the Diffie-Hellman key exchange. The HNP consists given a prime number q of recovering a number a Ễ IFq such that for many known random t Ễ IFq a certain number of the most significant bits of the smallest nonnegative residue of ta are known. To handle the DSA case we extend Boneh and Venkatesan s results on HNP to the case where t has not necessarily perfectly uniform distribution and establish uniformity statements on the DSA signatures using exponential sum techniques. The efficiency of our attack has been validated experimentally and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA. Keywords Cryptanalysis DSA lattices LLL closest vector problem distribution discrepancy exponential sums. .