CrewCTF 2022 | signsystem

#CrewCTF_2022

import sys
import random
from hashlib import sha256
from Crypto.Util.number import inverse
import ecdsa

from secret import FLAG

curve = ecdsa.curves.SECP112r1
p = int(curve.curve.p())
G = curve.generator
n = int(curve.order)

class SignSystem:
    def __init__(self):
        self.key = ecdsa.SigningKey.generate(curve=curve)
        self.nonce = [random.randint(1, n-1) for _ in range(112)]

    def sign(self, msg):
        e = int.from_bytes(sha256(msg).digest(), 'big') % n
        h = bin(e)[2:].zfill(112)
        k = sum([int(h[i])*self.nonce[i] for i in range(112)]) % n
        r = int((k * G).x()) % n
        s = inverse(k, n) * (e + r * self.key.privkey.secret_multiplier) % n
        return (int(r), int(s))

    def verify(self, msg, sig):
        (r, s) = sig
        e = int.from_bytes(sha256(msg).digest(), 'big')
        if s == 0:
            return False
        w = inverse(s, n)
        u1 = e*w % n
        u2 = r*w % n
        x1 = int((u1*G + u2*self.key.privkey.public_key.point).x()) % n
        return (r % n) == x1

if __name__ == '__main__':
    HDR = 'Welcome to sign system.'
    print(HDR)
    MENU = "1:sign\n2:verify\n3:getflag\n"
    S = SignSystem()
    try:
        while(True):
            print('')
            print(MENU)
            i = int(input('>> '))
            if i == 1:
                msghex = input('msg(hex): ')
                sig = S.sign(bytes.fromhex(msghex))
                print(f'signature: ({hex(sig[0])}, {hex(sig[1])})')
            elif i == 2:
                msghex = input('msg(hex): ')
                sig0hex = input('sig[0](hex): ')
                sig1hex = input('sig[1](hex): ')
                result = S.verify(bytes.fromhex(msghex), (int(sig0hex, 16), int(sig1hex, 16)))
                if result:
                    print('Verification success.')
                else:
                    print('Verification failed.')
            elif i == 3:
                target = random.randint(2**511, 2**512-1)
                print(f'target: {hex(target)}')
                sig0hex = input('sig[0](hex): ')
                sig1hex = input('sig[1](hex): ')
                result = S.verify(bytes.fromhex(hex(target)[2:]), (int(sig0hex, 16), int(sig1hex, 16)))
                if result:
                    print('OK, give you a flag.')
                    print(FLAG.decode())
                    break
                else:
                    print('NG.')
                    break
    except KeyboardInterrupt:
        print('bye')
        sys.exit(0)
    except:
        print('error occured')
        sys.exit(-1)

ECDSA だが、の計算方法が特殊で、事前計算された112個のの112bitをピックしてきてとおいて、 との内積で計算される

目的は与えられた任意のメッセージについて署名ができること

つまり任意のに対して が求められれば良い

全てのはの線型結合で表されるので、と合わせて未知変数は113個である

から113個式を建てると解ける

解くのはgroebner basisってやつに任せたらできた。行列を書いて解くのもできそうですね

from ptrlib import Socket
from hashlib import sha256
import secrets


p = 0xdb7c2abf62e35e668076bead208b
K = GF(p)
a = K(0xdb7c2abf62e35e668076bead2088)
b = K(0x659ef8ba043916eede8911702b22)
E = EllipticCurve(K, (a, b))
G = E(0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500)
E.set_order(0xdb7c2abf62e35e7628dfac6561c5 * 0x01)
n = 0xdb7c2abf62e35e7628dfac6561c5

def h(msg):
    e = int.from_bytes(sha256(msg).digest(), 'big') % n
    return e, [int(b) for b in bin(e)[2:].zfill(112)]

PR = PolynomialRing(GF(n), names=["d"] + ["k{}".format(i) for i in range(112)])
d, *nonce = PR.gens()

sock = Socket("localhost", 9999)

# collect polynomials
polys = []
for _ in range(113):
    msg = secrets.token_bytes(16)
    sock.sendlineafter(">> ", "1")
    sock.sendlineafter("hex): ", msg.hex())
    r, s = sock.recvregex(r"signature: \(0x([0-9a-f]+), 0x([0-9a-f]+)\)")
    z, bits = h(msg)
    k = sum(bits[i]*nonce[i] for i in range(112))

    polys.append(int(s, 16)*k - (z + int(r, 16)*d))

# solve and find d
I = Ideal(polys)
B = I.groebner_basis()
for poly in B:
    if poly.variables() == (d,):
        break
else:
    raise ValueError(":(")

d = poly.univariate_polynomial().roots()[0][0]


# forgery
sock.sendlineafter(">> ", "3")
target = int(sock.recvlineafter("target: "), 16)
z, _ = h(target.to_bytes((target.bit_length() + 7) // 8, "big"))
k = 1
r = G[0]
s = (z + int(r)*int(d)) % n

sock.sendlineafter("hex): ", hex(r))
sock.sendlineafter("hex): ", hex(s))

sock.interactive()