[Crypto] CR3: What is this encryption?

CTFtime.org / AlexCTF / CR3: What is this encryption?CTFtime

Fady assumed this time that you will be so n00b to tell what encryption he is using he send the following note to his friend in plain sight :

p=0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9

q=0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307

e=0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41

c=0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520

He is underestimating our crypto skills!

RSA 암호화라고 유추하고 파이썬 코드를 짜면 아래와 같다.

import binascii

p = 0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9
q = 0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307
e = 0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41
ct = 0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520


def egcd(a, b):
    '''
    returns (g, x, y) where g is the GCD of a and b and a * x + b * y = g
    '''

    # a = 1 * a + 0 * b
    (r1, x1, y1) = (a, 1, 0)
    # b = 0 * a + 1 * b
    (r2, x2, y2) = (b, 0, 1)

    while r2 != 0:
        # dividing r1 by r2 to get r3:
        # r1 = q3 * r2 + r3
        q3 = r1 // r2
        r3 = r1 % r2

        # r3 = r1 - q3 * r2
        #    = x1 * a + y1 * b - q3 * (x2 * a + y2 * b)
        #    = (x1 - q3 * x2) * a + (y1 - q3 * y2) * b
        x3 = (x1 - q3 * x2)
        y3 = (y1 - q3 * y2)

        # next step r1 will be our current r2
        # and r2 will be our current r3
        (r1, x1, y1) = (r2, x2, y2)
        (r2, x2, y2) = (r3, x3, y3)

    return (r1, x1, y1)


phi = (p - 1) * (q - 1)
_, d, _ = egcd(e, phi)
n = p * q
pt = pow(ct, d, n)

try:
    print(binascii.unhexlify(hex(pt)[2:]).decode('ascii'))
except:
    print(binascii.unhexlify('0' + hex(pt)[2:]).decode('ascii'))

egcd()는 여기를 참조하였다.

ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}