csrde2020-ezdsa.py3

# >>> 111
# <<< Your token: 111,9f2f2061e1898665c6ae49e665bc5f344a6005104c242d53f74c8548de7a468569dacd3a006354ef5dfdd8151e996ff1b981f24270287b6462c6b97509490041
# >>> 222
# <<< Your token: 222,9f2f2061e1898665c6ae49e665bc5f344a6005104c242d53f74c8548de7a4685377f65dbb5b54173f4626ccd8b765b2cc75d7a4e4949a43614528f496710c986

# ECDSA overview:
# 0. Private key d, curve generator point G, message m
# 1. Select any number k
# 2. Calculate r = (kG).x, if r = 0 goto 1
# 3. Calculate s = (m+rd)/k, if s = 0 goto 1
# 4. Signature is (r, s)

# Note we're doing calculations modulo some prime N,
# so a/b actually means finding a integer c that satisfies c*b=a (mod N)

# The source code metions "secp256k1", which is the curve name
# Parameter N (order of group) can be found everywhere
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Signatures from the signer
r = r1 = r2 = 0x9f2f2061e1898665c6ae49e665bc5f344a6005104c242d53f74c8548de7a4685
s1 = 0x69dacd3a006354ef5dfdd8151e996ff1b981f24270287b6462c6b97509490041
s2 = 0x377f65dbb5b54173f4626ccd8b765b2cc75d7a4e4949a43614528f496710c986

def xgcd(a,b):
    """Extended Euclidean algorithm to calculate modinv
    Proudly Copied From the Internet(TM)"""
    prevx, x = 1, 0;  prevy, y = 0, 1
    while b:
        q, r = divmod(a,b)
        x, prevx = prevx - q*x, x  
        y, prevy = prevy - q*y, y
        a, b = b, r
    return a, prevx, prevy

# Given r it's generally impossible to calculate k (ECDLP problem),
# so throw the equation in Overview.2 out of the window.

# Now we have
# 1. s1 = (m1 + r1 * d) / k
# 2. s2 = (m2 + r2 * d) / k
#    r1 = r2 = r
#    m1 = sha1(b'111')
#    m2 = sha1(b'222')
#
# py-ecdsa defaults to sha1: https://github.com/warner/python-ecdsa/blob/master/src/ecdsa/keys.py#L854
from hashlib import sha1
m1 = int.from_bytes(sha1(b'111').digest(), "big")
m2 = int.from_bytes(sha1(b'222').digest(), "big")

# Subtract 2 from 1: (s1 - s2) = (m1 - m2) / k
# Rearrange: k = (m1 - m2) / (s1 - s2)
#
# Reminder that we're doing stuff modulo N
ds     = (s1 - s2)          % N
inv_ds = xgcd(ds, N)[1]     % N  # This is 1/(s1 - s2)
k      = (m1 - m2) * inv_ds % N

# Use either 1 or 2, rearrange: d = (s * k - m) / r
inv_r  = xgcd(r, N)[1]         % N  # This is 1/r
d      = (s1 * k - m1) * inv_r % N

# And there's your private key, go ahead and sign stuff
# or hack a PS3 or something, ask Sony, idk
# But first, pip install ecdsa
import ecdsa
sk = ecdsa.SigningKey.from_secret_exponent(d, ecdsa.SECP256k1)
sig = sk.sign(b'admin').hex()
print('admin,' + sig)

# >>> admin,fa4c40b87dd017d864228432e9b506e6807c67f286825ff82e916395f7a058f866cd67b4d915979e7b513927b0abbc6313296aee8310e92c3bb812a95ef21b3e
# <<< Hello admin! Here is your flag: CSR{m33333333333p}