justCTF 2020 | 25519

#justCTF_2020

#!/use/bin/env sage

from sys import exit
from hashlib import sha256


FLAG = open('./flag.txt').read()

ec = EllipticCurve(GF(2**255-19), [0, 486662, 0, 1, 0])
p = ec.order()
ZmodP = Zmod(p)
G = ec.lift_x(9)

ha = lambda x: x if isinstance(x, int) or isinstance(x, Integer) else product(x.xy())
hashs = lambda *x: int.from_bytes(sha256(b'.'.join([b'%X' % ha(x) for x in x])).digest(), 'little') % p


def hashp(x):
    x = hashs((x))
    while True:
        try:
            return ec.lift_x(x)
        except:
            x = hashs((x))


def keygen():
    x = randint(1, p-1)
    P = x * G
    return x, P


def verify(signature, P, m):
    I, e, s = signature
    return e == hashs(m, s*G + e*P, s*hashp(P) + e*I)


if __name__ == "__main__":
    x, P = keygen()
    m = randint(1, p-1)
    print(x, P, m)

    spent = set()
    for i in range(8):
        Ix = int(input('I (x): '))
        Iy = int(input('I (y): '))
        I = ec(Ix, Iy)
        e = int(input('e: '))
        s = int(input('s: '))
        if verify((I, e, s), P, m) and I not in spent:
            print('ok')
            spent.add(I)
        else:
            print('nope')
            exit(1)

    print(FLAG)

要するにEllipticCurve上の が与えられるので

を満たすを探してこい、という問題

両辺にがあって、かつハッシュ関数を経由しているため、一見不可能に見えるが、をうまく使えばなんとかなる。とをそれぞれ適当な点に一致させることを考える

まず で、より、という制約を作る

続いて

についても適当に変形してより

したがって、適当なを作ってと計算して、, の順番で計算するだけで良い

from hashlib import sha256

ec = EllipticCurve(GF(2**255-19), [0, 486662, 0, 1, 0])
p = ec.order()
ZmodP = Zmod(p)
G = ec.lift_x(9)

ha = lambda x: x if isinstance(x, int) or isinstance(x, Integer) else product(x.xy())
hashs = lambda *x: int.from_bytes(sha256(b'.'.join([b'%X' % ha(x) for x in x])).digest(), 'little') % p


def hashp(x):
    x = hashs((x))
    while True:
        try:
            return ec.lift_x(x)
        except:
            x = hashs((x))

def keygen():
    x = randint(1, p-1)
    P = x * G
    return x, P

def verify(signature, P, m):
    I, e, s = signature
    return e == hashs(m, s*G + e*P, s*hashp(P) + e*I)

def solve(x, P, m):
    while True:
        try:
            c = randint(2, p-1)
            cG = c * G
            e = hashs(m, cG, cG)
            s = (c - e*x) % p
            I = inverse_mod(e, p) * (cG - s*hashp(P))
            break
        except ZeroDivisionError:
            pass
    return I, e, s

if __name__ == "__main__":
    x, P = keygen()
    m = randint(1, p-1)
    print(x, P, m)

    spent = set()
    for i in range(8):
        I, e, s = solve(x, P, m)
        if verify((I, e, s), P, m) and I not in spent:
            print('ok')
            spent.add(I)
        else:
            print('nope')
            exit(1)

    print("CLEAR!")

https://www.josephsurin.me/posts/2021-01-31-justctf-2020-crypto-writeups