> For the complete documentation index, see [llms.txt](https://donghyunlee.gitbook.io/write-up/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://donghyunlee.gitbook.io/write-up/ctf/alexctf-2017/crypto-cr4-poor-rsa.md).

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