The RSA Cryptosystem:
基础流程：
加密方式：
$$
c\ = m^e\ mod\ n
$$
解密方式：
$$
m\ = c^d\ mod\ n
$$
解密过程推导：
ed ≡ 1(mod N) a^φ(n)^ ≡ 1 (mod N)
$$
\begin{flalign}
&
c^d mod N\ &\ ≡\ (m^e)^d\ (mod\ N)\
&\ ≡\ m^{1+kφ(N)}\ (mod\ N)\\
&\ ≡\ m(m^{φ(N)})^k\ (mod\ N)\
&\ ≡\ m\ (mod\ N) \end{flalign}
$$
对于欧拉函数：
$$
\begin{flalign} &φ(n) = (p-1)(q-1) \& \ \ \ \ \ \ \ \ = gcd(p-1,q-1) * lcm(p-1,q-1)\&\ \ \ \ \ \ \ \ = gcd(p-1,q-1) * λ(N) \end{flalign}
$$
balanced primes(平衡素数):
$$
4 < \frac {1} {2} N^\frac {1} {2} < p < N^\frac {1} {2} < q < 2N^\frac {1} {2}
$$
等价的，我们认为
$$
p < q < 2p
$$
这是因为当RSA的素数平衡时，欧拉函数满足：
$$
\begin{align} & \vert N - \varphi(N) \vert = \vert N\ -\ (p-1)(q-1)\vert \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \vert N\ -\ (N-p-q+1)\vert \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \vert p\ +q\ -1\vert \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ < 3N^ \frac{1}{2} \end{align}
$$
RSA安全性分析：
对于RSA加密算法，公钥(N, e)为公钥，可以任意公开，破解RSA最暴力的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文。
保障RSA的安全性
1.定期更换密钥
2.不同的用户不可以使用相同的模数N
3.p与q的差值要大，最好是差几个比特
4.p-1与q-1都应该有大的素因子，一般建议选择的两个大素数p、q使得p=2p+1和q=2q+1也是素数
5.e的选择不要太小
6.d的选择也是不可以太小，最好满足d>=n的4分之1
常见的攻击方式：
直接分解模数n：
如果n小于256bit，可以使用本地工具进行暴力分解，例如windows平台的RSATool，可以在数分钟之内完成256bit的n的分解。
如果n大于768bit，可以尝试利用在线网站http://factordb.com， 这一类在线网站的原理是储存了部分n分解成功的的值。
dp泄露:
$$
\begin{align*}
&dp\ ≡\ d\ (mod(p-1))\
&∵dp·e\ ≡\ d·e\ ≡\ 1\ (mod(p-1))\
&∴dp·e\ -\ 1\ ≡\ k·(p-1)\
&∴(dp·e\ -\ 1)·d·e ≡\ k^{‘}·(p-1),\ \ \ k^{’}=k·d·e\
&⇔d·e\ =\ -k^{'}·(p-1)\ +\
\end{align*}
$$
共模攻击：
适用于：使用相同的模数N，不同的私钥，加密同一明文消息
e1,e2互素：
基本原理：
c1 = pow(m,e1,N)
c2 = pow(m,e2,N)
分别拿对应的私钥来加密，可以得到相同的明文m
m = pow(c1,d1,N)
m = pow(c2,d2,N)
用扩展欧几里得算法求出
$$
re_1\ +\ se_2\ =\ 1\ mod\ n
$$
的两个整数r和s，由此可得：
$$
\begin{align*}
c_1^rc_2^s\ &≡\ m^{re_1}m^{se_2}\ mod\ n\
&≡\ m^{(re_1+se_2)}\ mod\ n\
&≡\ m\ mod\ n
\end{align*}
$$
e1,e2不互素：
由于e1和e2不互素，所以我们要找他们的最大公因数：
$$
d\ =\ gcd(e_1,e_2)
$$
根据裴蜀定理：
$$
s·e_1\ +\ r·e_2\ =\ gcd(e_1,e_2)
$$
有了s和r，我们可以构造如下表达式：
$$
m^{s·e_1\ +\ r·e_2}\ ≡\ m^{gcd(e_1,e_2)}\ (mod\ n)
$$
如果s或r是负数，则需要对应的c1或c2取模逆元
- 如果gcd(e~1~,e~2~) = 1，就是上面的互素问题
- 当gcd(e~1~，e~2~) > 1，则取gcd(e~1~,e~2~)次根