DSA nonce recovery from repeated nonce

Cryptanalytic MVP award.

This attack (in an elliptic curve group) broke the PS3. It is a great, great attack.

In this file find a collection of DSA-signed messages. (NB: each msg has a trailing space.)

These were signed under the following pubkey:

y = 2d026f4bf30195ede3a088da85e398ef869611d0f68f07

(using the same domain parameters as the previous exercise)

It should not be hard to find the messages for which we have accidentally used a repeated "k". Given a pair of such messages, you can discover the "k" we used with the following formula:

         (m1 - m2)
     k = --------- mod q
         (s1 - s2)

9th Grade Math: Study It!

If you want to demystify this, work out that equation from the original DSA equations.

Basic cyclic group math operations want to screw you

Remember all this math is mod q; s2 may be larger than s1, for instance, which isn't a problem if you're doing the subtraction mod q. If you're like me, you'll definitely lose an hour to forgetting a paren or a mod q. (And don't forget that modular inverse function!)

What's my private key? Its SHA-1 (from hex) is:

Cryptography Services | NCC Group