RSA是一种非对称加密算法，它由 公钥（n/e），私钥(n/d)，明文M和密文C组成。我们做CTF题目时，一般题目中会给出公钥和密文让我们推出对应的私钥或者明文。RSA的相关公式都写在上面脑图中，在正式讲解RSA加密算法前我们先来普及一波数学的基本知识。
一、相关数学基础
1.1素数和互质数
素数也称质数，它的定义为除本身和 1 的乘积外，不能表示其他数的乘积。比如2，3，5，7，11，13，17……等都是素数。
互素数也称互质数，定义是公约数只有1的两个自然数，如：
1和任何自然数 1 & 2
任意 2个质数 2 & 3
相邻2个自然数 4 & 5
3 & 10 、7 & 10 、5 & 26等等。
1.2模指数运算
模运算就是取余数，如5 mod 3 =2。而模指数就是，先做指数运算在做mod运算。
如：53 mod 7 = 125 mod 7 =6
我们可以使用python的pow()来求解模指数运算。
1.3同余运算
两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。
二、RSA加密算法
2.1加解密算法
前面已经说过，RSA是一种非对称加密算法，这个算法的特点就是明文使用公钥进行加密得到密文，而密文解密使用私钥来解。
所需的密钥对为n,d,e。密钥对是如何生成的？
2.2生成密钥对
密钥对的生成步骤如下：n→L→e→d（L作为生成过程中的中间数）
三、CTF题目实战
3.1 First Blood已知p、q、e求d
题目链接 ：http://www.shiyanbar.com/ctf/1828
题目：
在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17,求解出d
此题直接告诉我们p、q、e，让我们求解d
而d的计算公式为d*e≡1(mod L*i),i=1,2,3...，
由于1和任何数做mod都为1，所有该公式又可转换为：
d*emod (L*i )=1 , i=1,2,3...。
d*e除(L*i)的余数为1，即d*e= (L*I) + 1。
直接使用脚本进行实现。
p=int(raw_input("Enter
a p: "))
q=int(raw_input("Enter
a q: "))
e=int(raw_input("Enter
a e: "))
t=(p-1)*(q-1)
i=0
whileTrue:
if(1-t*i)%e==0:
breaki-=1
printi
print'ok:'+'%d'%((1-t*i)/e)
求d的脚本，也可以又rsatool.py这个脚本来实现，需要安装gmpy这个模块，链接如下：
链接：http://pan.baidu.com/s/1bCDyoQ密码：09gj
3.2 Double Kill已知p、q、e和密文 求明文
题目链接 ：http://www.shiyanbar.com/ctf/1979
题目：
Use RSA to find the secret message
直接跑上题脚本获取d:
5577446633554466577768879988
3.3 Triple Kill已知n、e和密文 求明文
题目链接 ：http://www.shiyanbar.com/ctf/1918
n=920139713,e=19
因式分解n用yafu或者在线因式分解
使用yafu：链接：http://pan.baidu.com/s/1croXpO密码：w43p
在线地址：
http://www.atool.org/quality_factor.php
p=18443,q=49891
求d:
d=96849619
解密：
flag{13212je2ue28fy71w8u87y31r78eu1e2}
3.4 Quadra Kill已知公钥和密文求明文
题目链接 ：http://www.shiyanbar.com/ctf/1772
题目：
此题只给了公钥，并没有做分解，我们可以对题目所给的公钥进行分解。
python实现：
getn-e.py
fromCrypto.PublicKeyimportRSA
pub=RSA.importKey(open('public.pem').read())
n=long(pub.n)
e=long(pub.e)
print"n=",hex(n)
print"e=",hex(e)
或则使用openssl：
使用yafu分解n的值：
rsa-d.py计算d的值:
明文=密文dmod n
3.5 Penta Kill已知公钥和密文求明文
题目链接 ：http://www.shiyanbar.com/ctf/730
题目：
分解公钥得n、e的值，然后求解d，这边提供另外一种求解d的方案，就是利用github上的一个开源项目。
github:https://github.com/pablocelayes/rsa-wiener-attack
python脚本下载：链接：http://pan.baidu.com/s/1qXVhKpI密码：fuef
三、总结
限于篇幅，本篇先到这里告一个断落，下期会带来一些有一定难度RSA题目的解法，敬请期待，让斗哥带你走上RSA超神之路吧！
网友评论