# 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.

# DSA nonce recovery from repeated nonce (cont.)

[In this file find a collection of DSA-signed messages](https://depp.brause.cc/cryptopals/06/44.txt). (NB: each
msg has a trailing space.)

These were signed under the following pubkey:

    y = 2d026f4bf30195ede3a088da85e398ef869611d0f68f07
        13d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b8
        5519b1c23cc3ecdc6062650462e3063bd179c2a6581519
        f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430
        f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d3
        2971c3de5084cce04a2e147821

(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!)

# DSA nonce recovery from repeated nonce (cont.)

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

    ca8f6f7c66fa362d40760d135b763eb8527d3d52