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
$$
的两个整数rs,由此可得:
$$
\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不互素:

由于e1e2不互素,所以我们要找他们的最大公因数:
$$
d\ =\ gcd(e_1,e_2)
$$
根据裴蜀定理
$$
s·e_1\ +\ r·e_2\ =\ gcd(e_1,e_2)
$$
有了sr,我们可以构造如下表达式:
$$
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~)次根