Plaid CTF 2015 Strength

문제에서 제공해주는 파일은 아래와 같다.

captured_a4ff19205b4a6b0a221111296439b9c7

{N : e : c}

{0xfd2066554e7f2005082570ddf50e535f956679bf5611a11eb1734268ffe32eb0f2fc0f105dd117d9d739767f300918a67dd97f52a3985483aca8aa54998a5c475842a16f2a022a3f5c389a70faeaf0500fa2d906537802ee2088a83f068aba828cc24cc83acc74f04b59a0764de7b64c82f469db4fecd71876eb6021090c7981L : 0xa23ac312c144ce829c251457b81d60171161655744b2755af9b2bd6b70923456a02116b54136e848eb19756c89c4c46f229926a48d5ac030415ef40f3ea185446fa15b5b5f11f2ec2f0f971394e285054182d77490dc2e7352d7e9f72ce25793a154939721b6a2fa176087125ee4f0c3fb6ec7a9fdb15510c97bd3783e998719L : 0x593c561db9a04917e6992328d1ecadf22aefe0741e5d9abbbc12d5b6f9485a1f3f1bb7c010b19907fe7bdecb7dbc2d6f5e9b350270002e23bd7ae2b298e06ada5f4caa1f5233f33969075c5c2798a98dd2fd57646ad906797b9e1ce77194791d3d0b097de31f135ba2dc7323deb5c1adabcf625d97a7bd84cdf96417f05269f4L}

{0xcb26469a1b726d964cc0d3c8f2e486860b7252643b3c974857abc04cc93eca7167138e0cc5cbaa39b4c47daa6ccc5d546d6bfd4171f3ed3f1b0bfe30c22010e3376ec551ba46380cfa25495c7b1299ae7b02409523845fc1b3ccba46a19a4f58dd92c330a8a1ccb5f9000fd8d2b526be54528a237bfc34e24e3c59b2dffba473L : 0xb2a434913ffa775d4204165e30f875eecbdd1be46ef437ee4b93822ccd983a53a5860fd81b5c3f7aabe4c4a04c0ff9440729b50e5386db77c396b9f59a1eb8fb6986c1c4a4c3b2da75ae9c84fc589330f597442f526e2303a83ce75b58821a41238c0f2c30065cc44341d742b30605cc651ee57ed42255a34b173bdba31ee567L : 0x99f2c46f900977a329de45c070b8323ba4927a9d09ae28eb72b8d6741eb7929e88f3c619df2f73e7bcb540ca1e342b6644883834ade9e49cfa534a60e60259222ddf4b7465aa5519654aa576c7b27dbfd5d9b7f8ad68ce99373b4cde87fdde3f2209067d8774c8512e75e32a359a555c62e4ac95f9063a14cb15516a5b9121a3L}

..생략..

위와 같은 형태로 {N : e : c}에 해당하는 값들이 여러개 존재하는데 e 값을 상당히 크게 잡아서 winner Attack 공격 가능성이 존재한다.

위의 모든 N:e:c 쌍 중 winner Attack이 먹히는 값이 있는지 브포돌려서 개인키 구하고 복호화하면 된다.

https://github.com/pablocelayes/rsa-wiener-attack

위 소스를 다운받아서 RSAwienerHacker.py 파일을 조금 수정해서 돌려줬다.

solve.py

Created on Dec 14, 2011
  
@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)

    for (k,d) in convergents:

        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d



if __name__ == "__main__":
    f = open("./capture","r")
    capture_list = f.read().split("\n")
    capture_list.pop(0)
    for i in capture_list:
        tmp = i.replace("{","").replace("}","").replace(" ","").replace("L","").split(":")
        n = int(tmp[0][2:],16)
        e = int(tmp[1][2:],16)
        c = int(tmp[2][2:],16)
        d = hack_RSA(e,n)
        if d!=None:
            print "d = " + str(d)
            print("%x"%pow(c,d,n)).decode("hex")