RSA加密攻击练习（一）
RSA相关前置知识概括
RSA算法主要是基于，将一个大数字做质数分解很困难，下面简单介绍一下所需的数学知识，主要写结论，做题拿来用即可，证明过程有兴趣可以自己研究。
欧拉函数
通常用 (n) 表示，表示小于n的正整数中与n互质的数的数目。
当n为质数的时候，有公式 (n) = n – 1
当n可以拆分成两个素数（p和q）的乘积的话，有公式 (n) = (p – 1)(q – 1)
因为大数拆分成两个素数的乘积很难，这一步是RSA算法安全性的关键。
同余
若存在整数a和b，除以m的余数相同，则称a，b mod m同余，记为a ≡ b (mod m)
模逆元
在模运算中，a^-1不是1/a，是 ax ≡ 1 (mod m) 中x的值。
在python中pow(a,-1,m)，就是按照上面这样计算出x的值。
欧拉公式
若m与n互为质数，则满足m^(n) ≡ 1(mod n)
证明过程参考拉格朗日定理。
lcm 与 gcd
分别代表least common multiple（最小公倍数），greatest common devisor（最大公约数）。
互质
两个正整数a、b互质意味着能同时被它们整除的数只有1，即gcd(a, b) = 1
RSA加密解密过程
公钥和私钥都是密钥核心和模数组成的。
假设公钥是 (e,n) ,私钥是 (d,n)，其中n是模数，另外的e或者d就是密钥核心。
明文是m，密文是c。
公钥是公开的，所有人可以随意获取，私钥是只有自己拥有的，必须保密不让其他人知道。
- 首先，发送方有公钥和要加密的明文，也就是e,n,m，我们把它加密为c：
m^e ≡ c (mod n)
c = m^e mod n
- 然后，接收方有私钥和加密的密文，也就是 d,n,c，解密以后就可以读取明文m：
c^d ≡ (m^e)^d ≡ m (mod n)
m = c^d mod n
这样的话，别人用了自己公钥加密的消息，就只有自己可以读取内容了，其他人无法读取。
私钥的计算方法
- 首先我们知道下面这个：
m^e ≡ c (mod n)
c^d ≡ (m^e)^d ≡ m (mod n)
- 所以我们可以推断出：
m^(e*d) ≡ m (mod n)
- 根据前文的欧拉公式我们知道有这样一个结论，在m与n互质的时候：
m^(n) ≡ 1 (mod n)
- 于是我们联立2和3的公式发现以下结论：
e*d=(k*(n) 1)
等价于：
e*d= 1 (mod (n))
也就是说d是 e模(n) 的乘法逆元。同时前文说了我们知道有公式 (n) = (p – 1)(q – 1)，所以拿到p和q，可以算出(n)，就可以求出d了。
常见的做题流程
通常我们是得知了c,e,n，然后需要在不知道密钥d的情况下，求加密前的明文m。
- 首先，我们通过这个小网站去拆分p和q：factordb.com/index.php?q…
- 我们计算出phi，也就是(n)：
phi = (p - 1) * (q - 1)
3.通过python的inverse函数或者pow函数都可以算出d，其中inverse函数需要Crypto.Util.number组件：
d = inverse(e, phi)
或者
d = pow(e, -1, phi)
4.最后用pow函数计算结果：
m = pow(c, d, n)
通常m就是flag了。
实战刷题
由于现在还没有系统的刷完一个平台的RSA题目，所以没有对RSA所有的攻击手段全部总结详细。
暂时在这里把刷题碰上过的一些简单的e和n有关的问题总结一下。
n自己就是个素数
如果n自己就是一个大的素数，那么(n) = p – 1
n拆分出来是两个一样的素数
如果只生成了一个大素数，平方出来的n，那么(n) = p(p – 1)
n拆分出来是很多很多个素数的乘积
那么(n) = (p1 – 1)(p2 – 1)(p3 – 1)(p4 – 1)(p5 – 1)(p6 – 1)(p7 – 1)(p8 – 1)，也就是每一个数字都要参与一次计算。
e=1时
明文会与密文相等，可以直接将密文c转化为字符串解密。
e=3时
通常在题目中，n是一个非常大的数字，而题目要求的flag通常不是一句很长的字符串，所以在公式 m^e ≡ c (mod n) 中，mod n很有可能压根没有用上，因为flag（也就是m）只取三次方，依旧是比n小太多，求余数压根就是自己本身，所以flag^3 = c,直接将c开三次方即可求出明文，如果e太小可以这样计算。这里可以使用gmpy2的iroot函数来计算。
总结
记录了一下rsa的基本原理，需要依赖的数学结论，以及做题的基本流程与目前遇到的部分题目的解题过程，主要是按照cryptohack网站的顺序来学习的，后面的题目暂时还没研究清楚，等后面的题目研究透彻了以后，再根据现有的各类RSA攻击类型来给题目进行归类总结。
