Some lattice attacks on DSA and ECDSA (Q429782)

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.