Rating:
# Really Small Algorithm:Cryptography:150pts
Challenge instance ready at 95.216.233.106:50991.
Connect to the network service to get the flag.
# Solution
ncすると以下のように表示される。
```bash
$ nc 95.216.233.106 50991
n: 184356480709259722942004799861065325678140656753168351803587660246754457863055072413486797658613478488594422031971061993664487018310850704623993405767148377
e: 65537
ct: 43099747263520504904736192083958363509633018523690786070309710467119783083688498809183800008128410735825936992197148936314285862620179071589857444668228951
```
RSA暗号らしいので素因数分解を試みる。
```bash
$ ./msieve -q -v -e 184356480709259722942004799861065325678140656753168351803587660246754457863055072413486797658613478488594422031971061993664487018310850704623993405767148377
~~~
random seeds: 6bebb5d2 e840c007
factoring 184356480709259722942004799861065325678140656753168351803587660246754457863055072413486797658613478488594422031971061993664487018310850704623993405767148377 (156 digits)
p2 factor: 17
prp155 factor: 10844498865250571937764988227121489745772979809009903047269862367456144580179710141969811626977263440505554237174768352568499236371226512036705494456891081
elapsed time 00:00:00
```
とんでもない速度で終わってしまった。
素数が小さすぎたようだ。
以下のプログラムで解いてやる。
```python:dec_sp.py
from Crypto.PublicKey import RSA
from Crypto import Random
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
n = 184356480709259722942004799861065325678140656753168351803587660246754457863055072413486797658613478488594422031971061993664487018310850704623993405767148377
e = 65537
c = 43099747263520504904736192083958363509633018523690786070309710467119783083688498809183800008128410735825936992197148936314285862620179071589857444668228951
p = 17
q = 10844498865250571937764988227121489745772979809009903047269862367456144580179710141969811626977263440505554237174768352568499236371226512036705494456891081
d = inverse(e, (p-1)*(q-1))
key = RSA.construct((n, e, d))
print(long_to_bytes(key.decrypt(c)))
```
```bash
$ python dec_sp.py
b'ractf{S0m3t1mesS1zeDoesM4773r}'
```
## ractf{S0m3t1mesS1zeDoesM4773r}
