「RSA暗号」 SECCON Beginners CTF 2018 RSA is power

import Crypto.PublicKey.RSA as RSA

# 与えられたもの
N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

# ./mesieve を使ってN=p*qのp,qを求める
p = 299681192390656691733849646142066664329
q = 324144336644773773047359441106332937713
l = (p-1)*(q-1)

# dを求めるときは、どっちでもok
d = RSA.inverse(E, (p-1)*(q-1))
d = pow(E, -1, l)
m = pow(C, d, N)

print(RSA.long_to_bytes(m))

b'ctf4b{5imple_rs4_1s_3asy_f0r_u}'

が与えられる。そこから秘密鍵dを求めて、平文mを復号する。

nを素因数分解してとなる素数を求める。nが大きすぎるため、Linux上でmsieveを利用して素因数分解を行うか、factordb.comを使って行う。msieveについてはは以下の記事を参照してください。

nyaonn.hatenablog.com

Pythonのライブラリを使うためにpycryptoをインストール

$ pip install pycrypto