Some lattice attacks on DSA and ECDSA (Q429782)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some lattice attacks on DSA and ECDSA |
scientific article |
Statements
Some lattice attacks on DSA and ECDSA (English)
0 references
20 June 2012
0 references
This paper develops attacks on DSA and ECDSA using the algorithm for LLL reduction and two algorithms for the computation of the integral points of two classes of conics, provided that the secret and the ephemeral key of a signed message or their modular inverses are sufficiently small and in case the ephemeral keys or their modular inverses of two signed messages are sufficiently small. These attacks are based on the equality \(s=k^{-1}(h(m)+ar)\bmod q\). Assuming that a signature is available and each number in at least one of the sets \(\{a, k^{-1}\bmod q\}\), \(\{k, a^{-1}\bmod q\}\) and \(\{a^{-1}\bmod q, k^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, the secret keys \(a\) and \(k\) can be revealed. Moreover, if two signatures with ephemeral keys \(k_1\) and \(k_2\) are available and each number in at least one of the sets \(\{k_1, k_2^{-1}\bmod q\}\), \(\{k_2, k_1^{-1}\bmod q\}\) and \(\{k_1^{-1}\bmod q, k_2^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, then \(k_1\), \(k_2\) and subsequently \(a\) can be computed.
0 references
public key cryptography
0 references
digital signature algorithm
0 references
elliptic curve algorithm LLL
0 references
discrete logarithm
0 references
Diophantine equations
0 references