[PlaidCTF 2019] R u SAd?

key.sad.pub, flag.enc, rusad(python script)가 주어진다.

일단 파이썬 스크립트를 살펴보자. 굉장히 길어서 우선 키를 어떻게 생성하는지를 보자.

def action_keygen(args):
    key = genkey(args.bits)
    pickle.dump(key, args.priv)
    pickle.dump(key.pub(), args.pub)

def genkey(bits):
    assert bits % 2 == 0
    while True:
        p = genprime(bits // 2)
        q = genprime(bits // 2)
        e = 65537
        d, _, g = egcd(e, (p-1) * (q-1)) # d = inverse(e, phi), g = 1
        if g != 1: continue
        iQmP, iPmQ, _ = egcd(q, p)
        return Key(
            N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
            iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
        )

def genprime(bits):
    while True:
        p = secrets.randbits(bits-1) | (1 << (bits-1))
        if isprime(p): return p

def egcd(a1, a2):
    x1, x2 = 1, 0
    y1, y2 = 0, 1
    while a2:
        q = a1 // a2
        a1, a2 = a2, a1 - q * a2
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2
    return (x1, y1, a1)    

egcd(a1, a2)에서 리턴되는 x1, y1은 a1*x1+a2*y2=1 을 만족한다.

우리가 얻는 key.sad.pub에는 어떤 값들이 있는지 알아보자.

key.pub은 pickle 모듈을 통해 만들어진다.

def keyfile(private=False):
    def func(string):
        f = argparse.FileType('rb')(string)
        key = pickle.load(f)
        print(key.N)
        print(key.E)
        print(key.iQmP)
        print(key.iPmQ)
        print(key.bits)
        if not isinstance(key, Key):
            raise argparse.ArgumentTypeError(f'{string:r} did not specify a valid key')
        if private and not key.ispriv():
            raise argparse.ArgumentTypeError(f'{string:r} did not specify a private key')
        return key
    return func

keyfile 함수를 다음과 같이 바꾸고,

baek@ubuntu:~/Downloads$ ./rusad encrypt -i data -o data.enc -k key.sad.pub

으로 N, E, iQmP, iPmQ, bits 값을 알아내었다. 사실 여기서 얻은 iQmP, iPmQ는 iQmP % P, iPmQ % Q라서 x, y라고 쓰겠다.

다음과 같이 p를 구할 수 있게 된다. 이 값을 이용해 key.priv를 만들어서 복호화하자.

from Crypto.Util.number import *
from gmpy2 import *
N = 791624863672362607956099356831131364853604534581539305910340202530608819116145635786172280242888006099238658415878726648609085639898441498221890676242989932156153803416798752313174803590881722743224684700892225118961219497620039594839395302098710398557509455737717045746236278723783082574166076253616722351864293093113312339303779100928501715558725523086900830443711904148216534555379563587752574783766585298405162299420015348154910428560999297372318489063379606963196610310541923400713582218574580476129076391874763972417104970428247552426095493102113265356930843209220678746513622763556047230507409813826323653127519641722507761180370551715894779123757799654191386575031709371023058585245770842026072807521354840681453389934373985631297088292594571458141054189461792135505184038113247878020462609475899896639165065556193530858093783580972030229157998906679657691476969608156903485234277862405304786019418734022240703148376923711471550495919780707697498176112050789516280686586774453361477128822533764461655099250507644377378432909816994714226859830198325441550849414355111311567891047645058209193718307670504917114431127025248430544656281369344135327825272092527266146813922316680837029133898187541256581486770086898004104721349717
e = 65537
x = 20800474461367145273340906691597634098910584848634101425530321090829125122241687879745601849248837998876151999592885721935152548674120399809317994565118852444189251158193986225229214950841679795627758099753351375856214350384902504565070917605339475722050666023289412703507879513606009743774089452299903006910942117062241868053983949068811202383614893148995089157210610010137350618698066200655682358324076086051635412942424101514341843621257447734742388939312643974507540634350698445829827074747244048131430269996635105948318032075354212694854013936053043646732168771012778244153439821689497012763977957502463601486569
y = 8576238992571591869339367870140218994273542282194520701664348646682391448576106630680498284621212787593356209740914901168733090823371040699948878786651462518529144026837660123406693635154217830755339457596520608787502271941986487262771708521404416352019507024705430920736421058347439358995939039953228936764295191673752730499288133458713995709946983920103441131785342297881050343614665686721597353967276809964115302170170393367543710777834619256462467499921754735442721965580336508363159554886933283178151617020551042141999581756444339357087838568279392954356241659416168338179236507816144395812356271365879641284797

s = (N+1)*(N+1)-4*x*y*N
p = (N+1-isqrt(s)) / (2*y)
q = N / p
print p, q

genkey 함수의 p, q에 값을 넣어서 key.priv를 생성하였다.

Capture the Flag

---