CTFlearn: RSA BEGINNER
原题：
RSA BEGINNER
90 points
182 solves
Cryptography
Hard
I found this scribbled on a piece of paper. Can you make sense of it? https://mega.nz/#!zD4wDYiC!iLB3pMJElgWZy6Bv97FF8SJz1KEk9lWsgBSw62mtxQg
下载了链接中的文件，如下：
e: 3
c:219878849218803628752496734037301843801487889344508611639028
n:245841236512478852752909734912575581815967630033049838269083
很明显，e是公钥指数，c是密文，n是大数
首先我尝试了用lowe的方法，将密文用3开方，如果不行加上n再开方。但是尝试了加上很多的n都没有开方成整数。
又看到n的数值不大，应该可以找到n的两个素数因子p和q。利用因式分解数据库http://factordb.com，发现n可以分解成两个素数。知道了两个素数后我们就可以很快地通过公钥e来得到私钥了。
python代码如下：
import gmpy2
e=gmpy2.mpz(3)
c=gmpy2.mpz(219878849218803628752496734037301843801487889344508611639028)
n=gmpy2.mpz(245841236512478852752909734912575581815967630033049838269083)
# 因式分解得到的p和q
p=gmpy2.mpz(590872612825179551336102196593)
q=gmpy2.mpz(416064700201658306196320137931)
phi=gmpy2.mul(p-1,q-1)#计算(p-1)*(q-1)得到phi
d=gmpy2.invert(e,phi)#计算e对于phi的摩反
m=int(gmpy2.powmod(c,d,n))#c的d次方mod n
mt=bytes.fromhex(hex(m)[2:])#将int转换成byte
print(mt)
得到结果：
b'abctf{rs4_is_aw3s0m3}'
