# \[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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://donghyunlee.gitbook.io/write-up/ctf/alexctf-2017/crypto-cr3-what-is-this-encryption.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.