NDLI: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces

Please wait, while we are loading the content...

The Insecurity of the Digital Signature Algorithm with Partially Known Nonces

Content Provider	Springer Nature Link
Copyright Year	2002
Abstract	We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive 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. For most significant or least significant bits, the number of required bits is about log 1/2 q , but can be decreased to log log q with a running time q O(1/log log q ) subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. 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 α ∈ F q such that for many known random t ∈ F q a certain approximation of t α is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the 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.
Starting Page	151
Ending Page	176
Page Count	26
File Format	PDF
ISSN	09332790
Journal	Journal of Cryptology
Volume Number	15
Issue Number	3
e-ISSN	14321378
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2015-07-23
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Coding and Information Theory Computational Mathematics and Numerical Analysis Combinatorics Probability Theory and Stochastic Processes Communications Engineering, Networks
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Schnorr’s preprocessing for digital signature schemes

A Software-Optimized Encryption Algorithm

An Efficient Existentially Unforgeable Signature Scheme and Its Applications

The security of the birational permutation signature schemes

Improving the exact security of digital signature schemes

Signature Schemes Secure Against Hard-to-Invert Leakage

Fully Leakage-Resilient Signatures

Efficient Signature Schemes with Tight Reductions to the Diffie-Hellman Problems

OAEP Reconsidered

The Insecurity of the Digital Signature Algorithm with Partially Known Nonces

Similar Documents

On Schnorr’s preprocessing for digital signature schemes

A Software-Optimized Encryption Algorithm

An Efficient Existentially Unforgeable Signature Scheme and Its Applications

The security of the birational permutation signature schemes

Improving the exact security of digital signature schemes

Signature Schemes Secure Against Hard-to-Invert Leakage

Fully Leakage-Resilient Signatures

Efficient Signature Schemes with Tight Reductions to the Diffie-Hellman Problems

OAEP Reconsidered

The Insecurity of the Digital Signature Algorithm with Partially Known Nonces