[Viettel MATESCTF 4th Round] – Easy Signature Generator (Crypto 250pts)

crypto250_mates4.py

from gmpy2 import mpz, invert
import hashlib

def hash(data):
    return hashlib.sha1(data).hexdigest()

def recover_k(p, h1, h2, r, s1, s2):
    h = int(h1, 16) - int(h2, 16)
    s = s1 - s2
    k = ((h * invert(s, p-1)) % (p - 1))
    return k

def recover_x(p, h, r, s, k):
    x = ((int(h, 16) - k * s) * invert(r, p - 1)) % (p - 1)
    return x

def sign(p, g, h, r, x, k):
    #r = pow(g, k, p)
    s = ((int(h, 16) - x * r) * invert(k, (p - 1))) % (p - 1)
    return (r, s)
    
p = 9506671452185858935606727872655278032652323186780222821010281587491069866786182771603464240175811938254197330774157129503706399765307524521460723916919297
g = 3
data = "Mat3CtfDummyPKI"

h1 = "17f59949630ac819453764626d9d0fe580b923cf"
h2 = "09c449aac70c64b172da51cb5dac4550f2cc281e"

s1 = 2240204496766576783549562041165185142807437552898578273199351698170081466417526328155141293635371706873996561746899595207237920206870664725396735802001274
s2 = 8348335863576388642188310486843865336569134688700660600480258187773557891687993797499576589511995861855104102121659523823721274926045713617662591074868939

r = 7125743705321220162193204552184386254178134095695921218710035778742280145936606740016138094131065784972295587850682053387702588543961795678996456662553315

k = recover_k(p, h1, h2, r, s1, s2)
x = recover_x(p, h1, r, s1, k)

h = hash(data)
s = sign(p, g, h, r, x, k)[1]
flag = "matesctf{" + hash(hex(s)[2:]) + "}"
print flag

Elgamal signature with using same k.
http://crypto.stackexchange.com/questions/1479/elgamal-signature-scheme-recovering-the-key-when-reusing-randomness