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