(EC)DSA lattice attacks based on Coppersmith's method

• We apply a variant of Coppersmith's method to the Digital Signature Algorithm.
• We use a Boneh–Durfee type lattice attack.
• Our attack is feasible if the product of the keys k−1⋅ak−1⋅a is small.

We provide an attack to (EC)DSA digital signature built upon Coppersmith's method. We prove that, if a,ka,k are the private and ephemeral key, respectively, of the (EC)DSA scheme and (k−1modq)2a<0.262⋅q1.157, then we can efficiently find a.