本文为原创文章，转载请注明出处！
RSA加密基本原理
加密过程
选择两个大素数p和q，计算出模数N= p * q
计算φ= (p−1) * (q−1) 即N的欧拉函数，然后选择一个e(1<e<φ)，且e和φ互质
取e的模反数为d，计算方法:e * d ≡ 1 (mod φ)
对明文A进行加密：B≡A^e(mod n) 或B= pow(A,e,n)，得到的B即为密文
对密文B进行解密，A≡B^d(mod n) 或A= pow(B,d,n)，得到的A即为明文
p 和q：大整数N的两个因子（factor）
N：大整数N，我们称之为模数（modulus）
e 和d：互为模反数的两个指数（exponent）
c 和m：分别是密文和明文，这里一般指的是一个十进制的数
一般有如下称呼：
（N，e）：公钥
（N，d）：私钥
加密分析
RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e、d。
其中，n是两个大质数p、q的积，n以二进制表示时所占用的位数，就是所谓的密钥长度。
e和d是一对相关的值，e可以任意取，但要求e与(p-1)*(q-1)互质；再选择d，要求(e*d)≡ 1(mod(p-1)×(q-1))。
令φ= (p-1)(q-1) 上式即 d*e= 1 mod φ 即：(d*e- 1)% φ = 0
（n，e),(n，d)就是密钥对。其中(n，e)为公钥，(n，d)为私钥。RSA加解密的算法完全相同，设A为明文，B为密文，则：A≡B^d(mod n)；B≡A^e(mod n)；（公钥加密体制中，一般用公钥加密，私钥解密）
e和d可以互换使用，即：
A≡B^e (modn)；B≡A^d(mod n);
附加解释
同余符号“ ≡ ”
数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)。对模m同余是整数的一个等价关系
比如26≡14(mod12)
互质
公约数只有1的两个数，称为互质
RSA常见攻击及分解方法
RSA的非对称体制是建立在大整数分解难题上的，所以最基本的攻击方法就是当模数N过小时，直接计算它的因子。但是大部分情况下稍微有点难度的rsa题目都不会是直接暴力分解N，而是需要一定的攻击手法。
N如果是256bits可以直接分解，如果超过了就基本别想暴力分解了，需要用到下面的一些攻击手法，下面列举一下一些攻击手法。
Wiener’sattack
当d < (1/3)N^(1/4)时，我们可以通过Wiener’sattack分解得到d
费马分解
当大整数N的两个因子p和q相近时，我们可以通过费马分解的办法很快分解大整数
Smallq
当q较小时，即|p-q|较大时，我们可以直接爆破因子
BonehDurfee Method
当d满足d ≤ N^0.292时，我们可以利用该方法分解N，理论上比wienerattack要强一些。
yafu
yafu使用最强大的现代算法去自动化的分解输入的整数。大多数的算法都实现了多线程，让yafu能充分利用多核处理器（算法包括SNFS, GNFS,SIQS, 和ECM）。
factordb
如果对一个大整数用一些特殊算法也分解不了的时候，我们可以在 http://factordb.com/ 中查询一下数据库，说不定就能找到其因子
看完攻击手法，我们拿例题来更好的认识一下攻击手法。
mediumRSA
下载地址：
https://dn.jarvisoj.com/challengefiles/mediumRSA.rar.07aab25c9c54464a8c9821ca28503330
给出两个文件：
flag.enc
pubkey.pem
可以看到一个公钥，一个加密后的文件
正常分解的解决方法
openssl分解公钥得到N、E
可以看到N(256bits)很短直接分解即可(几分钟之内)
python代码生成私钥
openssl解密
RSActfTOOL
下载地址：
https://github.com/Ganapati/RsaCtfTool
可以用公钥直接生成私钥
私钥解密：
低加密指数攻击
Extremelyhard RSA
题目信息：没想到RSA4096都被你给破了，一定是我的问题，给了你太多信息，这次我只给你一个flag的加密值和公钥，仍然是RSA4096，我就不信你还能解出来。
题目链接：
https://dn.jarvisoj.com/challengefiles/extremelyhardRSA.rar.8782e822c895a2af3d8ba4ffbb3e280b
解题思路：openssl 解码一下piblic.pem可以看到E=3（一般情况下E=0x10001），典型的低加密指数攻击
注：flag.enc以十六进制方式来读取，因为文件中含有很多不可打印字符。
破电脑跑了快半个小时，期间以为卡了，还好跑出来了&……
另一道ctf
正常e的值通常情况下是0x10001，上面这个e明显值过小，而且是3，所以还是低加密指数攻击
脚本如下：
共模攻击
VeryHard RSA
题目链接：
https://www.jarvisoj.com/challenges
题目给出加密代码如下：
注：N后面的L是为了强制编译器把常量作为长整数来处理，只需在后边加上一个字母L（或l）
首先看这个N长度（4096bit）就别想暴力分解了。
代码可以看到是相同的N，不同的E加密的，那就使用共模攻击
解密代码如下：
rabin算法
hardRSA
题目链接：
https://www.jarvisoj.com/challenges
也是给了和上面一样的两个文件pubkey.pem和flag.enc
提取公钥发现e=2，N与上面mediumrsa例题一样，用rabin算法(该算法只适合e=2的情况)
N在上面已经用yafu分解出来p,q了，直接用就可以了。
python脚本如下：
网友评论