# \[Crypto] CR3: What is this encryption?

{% embed url="<https://ctftime.org/task/3354>" %}

{% hint style="info" %}
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!
{% endhint %}

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

```python
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()`는 [여기](http://cedricvanrompay.fr/blog/2017-12-16-extended-gcd.html)를 참조하였다.

{% hint style="success" %}
ALEXCTF{RS4\_I5\_E55ENT1AL\_T0\_D0\_BY\_H4ND}
{% endhint %}