# \[Crypto] CR4: Poor RSA

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

{% hint style="info" %}
This time Fady decided to go for modern cryptography implementations, He is fascinated with choosing his own prime numbers, so he picked up RSA once more. Yet he was unlucky again!

Given files:

* flag.b64
* key.pub
  {% endhint %}

`flag.b64`의 내용은 아래와 같다.

```
Ni45iH4UnXSttNuf0Oy80+G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSi+w=
```

`key.pub`의 내용은 아래와 같다.

```
-----BEGIN PUBLIC KEY-----
ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8
bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ==
-----END PUBLIC KEY-----
```

아래 명령을 통해 public key의 정보를 얻는다.

```bash
$ openssl rsa -pubin -in key.pub -text -noout  
Public-Key: (399 bit)
Modulus:
    52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:
    77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:
    89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:
    ba:5c:32:42:43
Exponent: 65537 (0x10001)
```

399 비트 암호화임을 알 수 있다.

RSA-512 비트 키도 취약하다고 알려져 있는데, 399 비트는 그에 비해 더 짧아 더 취약하다.

n 값을 hex에서 decimal로 바꾸면 아래와 같다.

```bash
$ python -c "print(int('0x52a99e249ee7cf3c0cbf963a009661772bc9cdf6e1e3fbfc6e44a07a5e0f894457a9f81c3ae132ac5683d35b28ba5c324243', 16))"
833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019
```

decimal로 변환한 n 값을 <http://factordb.com>에 넣으면 아래와 같이 p와 q 값을 얻을 수 있다.

![](/files/-M56bJnIYS2C29QHlFAg)

```
p: 863653476616376575308866344984576466644942572246900013156919
q: 965445304326998194798282228842484732438457170595999523426901
```

이를 참고해 파이썬 코드를 짜면 아래와 같다.

```python
from Crypto.PublicKey import RSA
import base64
import gmpy2
import binascii

f = open('key.pub', 'r')
pub = RSA.importKey(f.read())
f.close()

n = pub.n
e = pub.e
p = 863653476616376575308866344984576466644942572246900013156919
q = 965445304326998194798282228842484732438457170595999523426901
assert(n == p * q)

f = open('flag.b64', 'r')
ct = base64.b64decode(f.read())
ct = int.from_bytes(ct, byteorder='big')
f.close()

phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))
key = RSA.construct((n, e, d))
pt = key.decrypt(ct)

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

실행 결과는 아래와 같다.

```bash
b'\x02\x9e&\xded\xa0\x96#H\x8au6L\xdb\xae\x84\x89:\x00ALEXCTF{SMALL_PRIMES_ARE_BAD}\n'
```

{% hint style="success" %}
ALEXCTF{SMALL\_PRIMES\_ARE\_BAD}
{% 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-cr4-poor-rsa.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.