[Codegate CTF 2020 Finals] cloud9

현금영수증_1083(강두호).pdf

0.05MB

chall.sage

#!/usr/bin/env sage
from secret import P1, Q1, a, b
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES

P0 = P1 & ord('?')
Q0 = Q1 & ord('?')
assert is_prime(P0) and is_prime(P1)
assert is_prime(Q0) and is_prime(Q1)


class Chall:

    def __init__(self, p, q):
        self.p = p
        self.q = q
        self.n = p * q
        self.E  = EllipticCurve(Zmod(self.n), [a, b])
        self.E1 = EllipticCurve(Zmod(p), [a, b])

        # Not Implemented, but you get the point :D
        self.G = E.random_point()
        self.d = randint(1, 1 << 128) & (p >> 1)
        self.Q = self.d * self.G

    def expose(self):
        print(self.n)
        print(self.E1.order())
        print(self.G.xy())
        print(self.Q.xy())

    def getkey(self):
        return self.d


if __name__ == '__main__':
    s = Chall(P0, Q0)
    s.expose()
    sd = s.getkey()

    l = Chall(P1, Q1)
    l.expose()
    ld = l.getkey()

    size = 16
    flag = pad(open('flag.txt', 'rb').read(), size)

    key = int(sd + ld)
    key = key.to_bytes(size, byteorder='big')
    cipher = AES.new(key, AES.MODE_ECB)
    enc_flag = cipher.encrypt(flag).hex()

    print(enc_flag)

s는 p, q 값이 작아 sd를 쉽게 구할 수 있었다.

타원곡선의 점 2개를 알고 있어 쉽게 a,b를 구할 수 있다.

 

E1의 order을 알고 있어 G에 그 값을 곱해준 후 나오는 오류 메시지를 통해 p,q를 구할 수 있었다.

d가 p와 1<<128보다 작다는 점을 이용해 E1 위에서의 ECDLP 문제를 풀어주면 된다.

 

E1의 order을 구한 후 그 값을 소인수분해하면 다음과 같다.

ord_fac = [4,81 , 13 , 151 , 37277 , 63737, 743689, 14743331, 20904431, 3659465143, 38635749385473505471502894387389]

마지막 값을 제외하고는 그 값이 작고, 제외한 나머지 요소들의 곱이 128비트 이상이기 때문에

Pohlig-Hellman 기법을 이용하여 ld 값을 구해줄 수 있다.

ord_fac = [4,81 , 13 , 151 , 37277 , 63737, 743689, 14743331, 20904431, 3659465143, 38635749385473505471502894387389]
dlogs = []
ord = tmp_g2.order()
print(ord)

for fac in ord_fac[:-1]:
    t = int(ord) // int(fac)
    dlog = (t*tmp_g2).discrete_log(t*tmp_point2)
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlogs)) #calculates discrete logarithm for each prime order
l = crt(dlogs, ord_fac[:-1])

알게 된 ld, sd 값을 이용해 key 값을 구한 후 flag를 딸 수 있다.

CODEGATE2020{Here_comes_the_crypto_genius}

github.com/timmykang/study/blob/master/codegate2020/final/cloud9/sol.sage