# Rage Delete

> Help!!! Our Crypto guy left in a furious rage and deleted our company private key and part of our signatures! We use that key to sign all of our important documents and such. This should be enough information for you to figure it out:
>
> Curve: NIST256P
> HASH: SHA256
> Generator X: 48439561293906451759052585252797914202762949526041747995844080717082404635286
> Generator Y: 36134250956749795798585127919587881956611106672985015071877198253568414405109
> Group Order: 115792089210356248762697446949407573529996955224135760342422259061068512044369
> Point X: 62642270921362628024101430148161419180734994811675578761489832783807341294140
> Point Y: 620508080568073990375228521563014425211330352832293590138091382461067773777
>
> I was also told the following gobblygook may be helpful.
>
>-----BEGIN PUBLIC KEY-----
>MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEin5E1fIJtTJ4ICIZ4leN0kT+QguW
>zDv6xizjvWTqcjwBXzHz49NVqrXR1Be16ceYRgtW7iGx1ifF135T0E1HUQ==
>-----END PUBLIC KEY-----
>
>Also so you can see some examples of our signatures... he always was yelling something about incrementing a value.
>
>Message 1: "We are not uncertain with the vote."
>Signature 1: (5469004757321565031662176892324365988603823594146568468219498508892601371422, 79937836276667565200355044792462693868454270095571952117096182814592269649296)
>
>Message 2: "We are uncertain with the vote."
>Signature 2: (???, 30705201908992384075889316247635358307738190041386759684653850381547740770548)
>
>(just give private key in decimal)

First off, this challenge is about ECC (Elliptic Curve Cryptography). If you aren't familiar with that, read [this](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/). It's one of the best primers on the subject, and the third post specifically talks about the scheme this challenge uses: ECDSA.

This challenge uses a standard curve and hash, so we know those are safe. It also specifies a generator point and group order. Finally it gives the coordinates of a public key, which matches the decoded 'gobblygook'. Let's call the generator `G`, the public point `H`, and the private key `d`. To summarize, `H = d*G`.

We also have two ECDSA signatures `(r1, s1), (r2, s2)`, but the second signature's `r2` value is redacted. If you read the description carefully, you'll notice this part: "he always was yelling something about incrementing a value." One idea I had was that this referred to incrementing the nonce `k`.

If the first signature uses nonce `k`, we can check if the second signature uses nonce `k+1` by lifting `r1` to the point `P` and adding `G` to it. That point's x-coordinate should be `r2`, and sure enough verifying `(r2, s2)` as a signature works.

from ecdsa_key_recovery import DsaSignature, EcDsaSignature
import ecdsa
from hashlib import sha256, sha1

curve = ecdsa.NIST256p

pubkey = ecdsa.VerifyingKey.from_string("048a7e44d5f209b53278202219e2578dd244fe420b96cc3bfac62ce3bd64ea723c015f31f3e3d355aab5d1d417b5e9c798460b56ee21b1d627c5d77e53d04d4751".decode("hex"), curve=curve, hashfunc=sha256)

m1 = b"We are not uncertain with the vote."
s1 = (5469004757321565031662176892324365988603823594146568468219498508892601371422, 79937836276667565200355044792462693868454270095571952117096182814592269649296)
# k * G = 5469004757321565031662176892324365988603823594146568468219498508892601371422L, 7165451762017194301012328096083029529851499200823071590277306390578694728304L

m2 = b"We are uncertain with the vote."
s2 = (97235425150499436432951382752836680210691596298588142003835471962448539177044, 30705201908992384075889316247635358307738190041386759684653850381547740770548)
# (k + 1) * G = (97235425150499436432951382752836680210691596298588142003835471962448539177044, 104525973057806235548010884609730795775974001060920532606951113933546346890346)

print pubkey
print pubkey.verify(ecdsa.util.sigencode_string(s1[0], s1[1], curve.order), m1)
print pubkey.verify(ecdsa.util.sigencode_string(s2[0], s2[1], curve.order), m2)

Cool, so we know all of the values as well as their relationships. Something that should stand out is the fact that the nonces are incremented. ECDSA dictates that nonces should be randomly generated, which is obviously not the case here. So how do we exploit that?

One thing you should have read about in the ECDSA post was the danger of repeating nonces. Specifically, we can take two signatures that use the same nonce and learn `k`. This in turn fully leaks the private key `d`.

Can we do something analogous with `k` and `k+1`? Some algebra will do the trick:

s1 = inv(k) * (z1 + r1*d)
s2 = inv(k + 1) * (z2 + r2*d)

k = inv(s1) * (z1 + r1*d)
k + 1 = inv(s2) * (z2 + r2*d)

subtracting the first equation from the second...

1 = inv(s2) * (z2 + r2*d) - inv(s1) * (z1 + r1*d)
1 + inv(s1)*z1 - inv(s2)*z2 = d * (inv(s2)*r2 - inv(s1)*r1)
d = (1 + inv(s1)*z1 - inv(s2)*z2) * inv(inv(s2)*r2 - inv(s1)*r1)

A full solve script:

>>> import gmpy2
>>> r1 = 5469004757321565031662176892324365988603823594146568468219498508892601371422
>>> s1 = 79937836276667565200355044792462693868454270095571952117096182814592269649296
>>> r2 = 97235425150499436432951382752836680210691596298588142003835471962448539177044
>>> s2 = 30705201908992384075889316247635358307738190041386759684653850381547740770548
>>> n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
>>> inv = lambda x: gmpy2.invert(x, n)
>>> from Crypto.Hash import SHA256
>>> h = SHA256.new()
>>> h.update(b"We are not uncertain with the vote.")
>>> z1 = int(h.hexdigest(), 16)
>>> h = SHA256.new()
>>> h.update(b"We are uncertain with the vote.")
>>> z2 = int(h.hexdigest(), 16)
>>> q1 = (1 + inv(s1)*z1 - inv(s2)*z2) % n
>>> q2 = inv(inv(s2)*r2 - inv(s1)*r1)
>>> q1*q2 % n
mpz(51385391163632633269999983613639213146659943335057127399923324554652318101330)