2018-02-24

RSA 加密

今天主要介绍的是 RSA 加密。

RSA 加密是目前世界上最流行的非对称加密，它名字的来源于它的三位父亲：罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman），他们在1977年提出了 RSA 加密并且在1987年7月首次在美国公布，RSA 来源于他们的姓氏开头字母。

RSA 加密内容其实很简单，先给出 RSA 加密的步骤

寻找两个质数 $p$、$q$（尽量大一点）。
令 $n=pq,\;\phi(n)=(p-1)(q-1)$ 。
找一个数 $e$，使得 $e$ 与 $\phi(n)$ 互质。
找一个数 $d$，使得 $de\;\%\;\phi(n)=1$。

以上步骤得出了 RSA 的一组公钥和私钥，公钥为 $(e, n)$，私钥为 $(d, n)$。
如果原始数据为 $D$，则加密数据 $S$ 的计算方法为：
$$S=D^e\;\%\;n$$
解密数据的计算方法为：
$$D=S^d\;\%\;n$$

PS：RSA 加密要求 $D<n$，因为根据算法过程可知，最终解密时，解密得到的结果为 $n$ 的余数，余数不可能比 $n$ 大，所以 $D<n$。

是不是很简单？

如果你只是寻找 RSA 加密的方法结论，那么以上内容就是全部了，下面的就不用看了 233。

从这个过程中也可以看出这里非对称加密的意思，普通的加密中，加密方和解密方都是用的同一个加密钥匙，但是 RSA 中二者的钥匙却不一样。
是不是很神奇？

可能你会想：“WTF，为什么会有这种神奇的算法？”，下面我们就从 RSA 加密基础的地方一点一点讲解这个算法的来历。

模运算基础

首先介绍一下什么是模运算。
模运算是数论中引入的一个概念，表示该数在所给的数字范围内的一个特征值。
这个特征值计算方法就是除以所给的数计算余数。
所以说，模运算其实就是余数，不过在数论中起了一个高大上的名字而已。
它的表示方法，这里我只介绍我用的比较多的方法：
$$x\equiv a\;(mod\;n)$$
该式子表示 $x$ 除以 $n$ 的余数为 $a$，相当于 $x\;\%\;n=a$。
模运算有下面这些性质：

如果 $a\equiv b\;(mod\;n)$，则 $b\equiv a\;(mod\;n)$
如果 $a\equiv b\;(mod\;n)$，则 $a + kn\equiv b\;(mod\;n)$
如果 $a\equiv b\;(mod\;n)$，$b\equiv c\;(mod\;n)$，则 $a\equiv c\;(mod\;n)$
如果 $a\equiv b\;(mod\;n)$，则 $ax\equiv bx\;(mod\;n)$
如果 $ax\equiv bx\;(mod\;n)$，且 $x,n$ 互质，则 $a\equiv b\;(mod\;n)$ *
如果 $a\equiv b\;(mod\;n)$，$c\equiv d\;(mod\;n)$，则 $a\pm c\equiv b\pm d\;(mod\;n)$，$ac\equiv bd\;(mod\;n)$
如果 $a\equiv b\;(mod\;n)$，$n=m_1 m_2 … m_n$，则 $a\equiv b\;(mod\;m_1)$，$a\equiv b\;(mod\;m_2)…a\equiv b\;(mod\;m_n)$

其实还有很多性质，这里就不再一一列举。
上面这些性质证明过程都比较简单，这里简单说一下证明思路：$a\equiv b\;(mod\;n)$ 换一种表达方式就是 $a=kn + b$，通过这个转换这些性质都能够得到证明。
关于 * 标记的性质，这里需要解释一下：

如果 $ax\equiv bx\;(mod\;n)$，那么 $ax = kn + bx$，则有 $a = \frac{kn}{x} + b$，由于 $a$ 是整数，所以 $\frac{kn}{x}$ 是整数，又因为 $x,n$ 互质，所以 $k = tx$，所以 $\frac{kn}{x} = tn$，所以 $a = tn + b$，所以 $a\equiv b\;(mod\;n)$。

模运算是 RSA 证明过程的基石，必须理解。

扩展欧几里得算法

欧几里得算法即辗转相除法，求两个数最大公约数的算法，这里记求两数最大公约数的函数为 $gcd(x, y)$。
扩展欧几里得算法描述为：两个整数 $a, b$，必存在参数 $x, y$ 使得 $ax + by = gcd(a, b)$。

扩展欧几里得算法其实就是欧几里得算法的逆过程，举例 $37$ 和 $23$：

$\begin{align} 37&=23\times1+14 \\ 23&=14\times1+9 \\ 14&=9\times1+5 \\ 9&=5\times1+4 \\ 5&=4\times1+1 \\ 4&=1\times4 \end{align}$

反推：

$\begin{align} 1 &=5-4 \\ &=5+5-9 \\ &=2\times(14-9)-9 \\ &=2\times14-3\times(23-14) \\ &=5\times(37-23)-3\times23 \\ &=5\times37-8\times23 \end{align}$

每一个欧几里得算法计算过程都能如此反推，所以扩展欧几里得算法成立。

扩展欧几里得算法主要用于证明模逆元的存在必然性，需要了解一下。

模逆元/模倒数

整数 $a$ 在模 $n$ 上的逆元 $b$ 定义如下：
$$ab\equiv 1\;(mod\;n)$$
其中 $a$ 与 $n$ 互质，否则 $b$ 不存在。
证明：

由扩展欧几里得算法，有 $ax+ny=gcd(a,n)$。
如果 $a$ 与 $n$ 互质，则 $gcd(a,n)=1$，所以 $ax+ny=1$。
在模 $n$ 上，$ax+ny\equiv ax\equiv 1\;(mod\;n)$，则由定义可知，$x$ 即为 $a$ 在模 $n$ 上的逆元。
如果 $a$ 与 $n$ 不互质，则 $gcd(a,n)=r$。
设 $a=pr, n=qr$，根据求最大公约数过程易得 $p,q$ 互质，假设存在 $z$ 使得 $az\equiv 1\;(mod\;n)$，我们会得到 $az=kn+1$。
把 $a=pr, n=qr$ 代入式子得到 $pr·z=qr·k+1$，同时除以 $r$ 有 $pz=qk+ \frac{1}{r}$，由于 $r\neq 1$，所以 $\frac{1}{r}$ 不是整数，假设不成立。

由以上过程可知，$a$ 与 $n$ 互质是 $a$ 在模 $n$ 上存在逆元的充要条件。

模逆元会存在多个，假如 $a$ 在模 $n$ 的一个逆元为 $a^{-1}$，那么所有 $a$ 在模 $n$ 的逆元可用如下通式计算：
$$a^{-1}_k = a^{-1} + kn$$
证明很简单：如果 $a·a^{-1}\equiv 1\;(mod\;n)$，则由 $a(a^{-1}+kn)=a·a^{-1}+akn$ 可得 $a(a^{-1}+kn)\equiv a·a^{-1}+akn\equiv a·a^{-1}\equiv 1\;(mod\;n)$，所以 $a^{-1}_k = a^{-1} + kn$ 为 $a$ 在模 $n$ 的逆元通解。

这个概念在后面中国剩余定理和欧拉定理里面都有涉及，简单了解一下。

中国剩余定理

中国剩余定理来源于一个孙子兵法中的问题，问题原话为：
”有物不知数，三三数之余二，五五数之余三，七七数之余二，问物几何？“
这其实描述了一个同余方程组问题，后来宋朝数学家秦九韶和明朝数学家程大为都给出了系统的解法，用现在数学语言描述为：
$$5\times 7\times 2\times 2 + 3\times 7\times 1\times 3 + 3\times 5\times 1\times 2 = 233 = 2\times 105 + 23$$
最小的解为 $23$。

现代数学语言对中国剩余定理的描述如下：
下面一元线性同余方程组：
$$\begin{cases}
x \equiv a_1\;(mod\;m_1) \\
x \equiv a_2\;(mod\;m_2) \\
\vdots \\
x \equiv a_n\;(mod\;m_n) \\
\end{cases}
$$
假设整数 $m_1,m_2…m_n$ 两两互质，则对任意整数 $a_1,a_2…a_n$ 方程组有解，通解可以按照如下方式构造：

设 $M=m_1m_2…m_n$，并且 $M_i=M/m_i$，由于 $m_1,m_2…m_n$ 两两互质，易得 $gcd(M_i,m_i)=1$。
设 $t_i=M_i^{-1}$ 为 $M_i$ 在模 $m_i$ 上的模倒数，即 $t_iM_i\equiv 1;(mod;m_i)$。
方程组的通解为：$x=a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n+kM$，在模 $M$ 的意义下，方程组只有一个解：$x=(a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n) % M$。

证明：
首先，$M_i$ 在模 $m_i$ 上肯定存在模逆元 $t_i$ 就不再证明了，$t_iM_i\equiv 1\;(mod\;m_i)$。
考察乘积 $a_it_iM_i$
$$
a_it_iM_i\equiv a_i·1\equiv a_i\;(mod\;m_i) \\
a_it_iM_i\equiv 0\;(mod\;m_j) (i\neq j)
$$
所以关于 $x=a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n$ 有 $x\equiv a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n\equiv a_it_iM_i+0\equiv a_i\;(mod\;m_i)$。
所以 $x$ 是关于方程组的一个解。
若 $x_1,x_2$ 都是方程组的解，则根据模运算性质易得 $x_1-x_2\equiv 0\;(mod\;m_i)$。
另 $X=x_1-x_2$，则由于 $X\equiv 0\;(mod\;m_i)$，所以 $X$ 是所有 $m_i$ 的公倍数。
又由于 $m_1,m_2…m_n$ 两两互质，根据公倍数求解过程，$m_1,m_2…m_n$ 的最小公倍数为 $m_1m_2…m_n$ 即 $M$。
所以 $X$ 只能是 $M$ 的整数倍，即 $X=kM$。
所以两个解之间相差 $kM$。
所以通解为 $x=a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n+kM$

中国剩余定理在后面欧拉函数积性的证明里面会用到。

欧拉函数

欧拉函数是小于 $n$ 的正整数中与 $n$ 互质的数的数目，计作 $\phi(n)$。
比如：$\phi(2)=1$，$\phi(4)=2$，$\phi(10)=4$。
至于欧拉函数的计算方法这里不是讨论的重点，基础方法就是枚举小于 $n$ 的所有正整数，找出其中与其互质的数并统计个数。
欧拉函数有如下性质：
1. $\phi(1)=1$，$\phi(2)=1$，当 $n>2$ 时，$\phi(n)$ 一定为偶数。
2. $\phi(p)=p-1$，$p$ 为质数。
3. 若 $n=p^k$，$p$ 为质数，则 $\phi(n)=\phi(p^k)=p^k-p^{k-1}$。
证明：若 $n=p^k$，$p$ 为质数，则不大于 $n$ 且与 $n$ 互质的数一定不是 $p$ 的倍数且只能是这些数，不大于 $n$ 的数有 $p^k$ 个，其中 $p$ 的倍数有 $p^{k-1}$ 个 $\{p, 2p, 3p…p^{k-1}p\}$，所以 $\phi(n)=\phi(p^k)=p^k-p^{k-1}$。
4. 若 $n=p_1p_2$，且 $p_1,p_2$ 互质，那么 $\phi(n)=\phi(p_1)\phi(p_2)$，这个性质称为欧拉函数的积性。
证明：搜罗了好多资料，关于这条性质的证明非常复杂，大部分都要牵扯到环、域、剩余集这些概念，非常晦涩难懂，并且要钻研的资料会进一步增多，这里秉承浅显通俗的理念，找到了一个相对来说没那么头疼的证明，这里分享一下：
原文链接：http://blog.sina.com.cn/s/blog_455c7a600102vxpq.html
构造一个矩阵：
$$
\begin{matrix}
1 & 2 & … & r & … & m \\
m+1 & m+2 & … & m+r & … & 2m \\
2m+1 & 2m+2 & … & 2m+r & … & 3m \\
\vdots & \vdots & & \vdots & & \vdots \\
(n-1)m+1 & (n-1)m+2 & … & (n-1)m+r & … & mn
\end{matrix}
$$
矩阵中所有的数即不大于 $mn$ 的所有正整数。
由于 $m,n$ 互质，所以与 $mn$ 互质的整数必与 $m$ 和 $n$ 互质。
考察列：由于 $gcd(km+r,m)=gcd(r,m)$，所以这些列每一个元素与 $m$ 互质的条件为 $r$ 与 $m$ 互质。
这样的 $r$ 有 $\phi(m)$ 个，选中了矩阵 $\phi(m)$ 列。
再考察这些列里面的元素：$\{r, m+r, 2m+r…(n-1)m+r\}$。
根据模运算的性质，这些数在模 $n$ 上恰好取遍所有结果。

展开来说一下：$n$ 的所有模构成集合 $N=\{0, 1, 2…n-1\}$，由于 $m$ 与 $n$ 互质，所以 $mN$ 中所有元素在模 $n$ 上依旧取遍所有结果。

证明：先假设 $mN$ 中存在元素 $mn_i, mn_j$ 同余，那么 $mn_i-mn_j\equiv 0\;(mod\;n)$，则 $m(n_i-n_j)=kn$，由于 $n_i，n_j$ 为 $n$ 的余数，并且都为正整数，所以 $n_i-n_j$ 不可能是 $n$ 的倍数，$m$ 又与 $n$ 互质，所以假设不可能成立，得证。

然后 $mN+r$ 相当于所有元素在数轴上平移相同单位，不难证明它们模循环移动了相同单位，依旧在模 $n$ 上取遍所有结果，得证。

而这些数中与 $n$ 互质的数有 $\phi(n)$ 个，所以总数有 $\phi(m)\phi(n)$ 个，即 $\phi(mn)=\phi(m)\phi(n)$，证明完毕。

其他的证明方法理解起来相对困难，这里给几个参考：
不使用中国剩余定理 http://www.cnblogs.com/372465774y/archive/2012/10/16/2726282.html

这篇文章后来想了一下，其实还是比较好理解的一篇，这里展开讲一下。
假设 $n,m$ 互质，$N$ 为不大于 $n$ 且与 $n$ 互质的数组成的集合，$M$ 为不大于 $m$ 且与 $m$ 互质的数组成的集合，$Z$ 为不大于 $mn$ 且与 $mn$ 互质的数组成的集合。不难发现 $N$ 元素有 $\phi(n)$ 个，$M$ 元素有 $\phi(m)$ 个，$Z$ 元素有 $\phi(mn)$ 个。记 $M,N,Z$ 中元素分别为 $m_{i},n_{i},z_{i}$，那么我们要证明的这条定理只需要证明下面几个结论成立即可：

结论1：$gcd(n_{i}m+m_{j}n,mn)=1$。
结论2：$n_{i}m+m_{j}n$，当 $i，j$ 任意一个取值变化的时候，在模 $mn$ 下两数不同余。
结论3：$n_{i}m+m_{j}n$，$i，j$ 取遍 $M,N$ 所有元素时，它们在 $mn$ 上的模恰好对应 $Z$ 中的所有元素。

首先证明结论1：因为 $gcd(m_{j},m)=1$，由于 $m,n$ 互质，所以 $gcd(m_{j}n,m)=1$。
又因为 $gcd(m_{j}n+km,m)=gcd(m_{j}n,m)$，所以 $gcd(m_{j}n+n_{i}m,m)=gcd(m_{j}n,m)=1$。
同理可证 $gcd(n_{i}m+m_{j}n,n)=1$，所以说 $gcd(n_{i}m+m_{j}n,mn)=1$。
结论2证明：假设在 $n_{i}m+m_{j}n$ 在模 $mn$ 下存在同余元素，会得到如下等式
$$n_{i}m+m_{j}n\equiv n_{k}m+m_{l}n\;(mod\;mn)$$
则有
$$\begin{align}
& &n_{i}m+m_{j}n &\equiv n_{k}m+m_{l}n\;(mod\;m) \\
&\Rightarrow &m_{j}n &\equiv m_{l}n\;(mod\;m) \\
&\Rightarrow &m_{j} &\equiv m_{l}\;(mod\;m)
\end{align}$$
由于 $M$ 中元素两两不同余，所以 $j=l$，同理可证 $i=k$，所以假设不成立，如果余数相同必定是同一个数。
由结论1、2证明可得，$n_{i}m+m_{j}n$ 生成的所有元素与 $mn$ 互质且不同余。
下面证明结论3：由于 $gcd(m,n)=1$，所以存在 $am+bn=1$，所以有 $amz_{k}+bnz_{k}=z_{k}$，所以存在 $cm+dn=z_{k}$。
由于 $gcd(z_{k},mn)=1$，所以 $gcd(cm+dn,m)=1 \Rightarrow gcd(dn,m)=1 \Rightarrow gcd(d,m)=1$。
所以 $d\equiv m_{j}\;(mod\;m) \Rightarrow dn\equiv m_{j}n\;(mod\;m)$。

证明：如果 $d$ 在 $m$ 上的模不在 $M$ 中，余数一定与 $m$ 存在公约数设为 $r$。
设 $m=sr$，余数为 $tr$。那么 $d=km+tr=(sk+t)r$，可见 $d$ 与 $m$ 存在公约数 $r$ 与条件相反，假设不成立，得证。

$dn=xm+m_{j}n$，由于 $m,n$ 互质，易得 $x$ 为 $n$ 的倍数，所以 $dn\equiv m_{j}n\;(mod\;mn)$。
同理可得 $cm\equiv n_{i}m\;(mod\;mn)$。
所以 $z_{k}\equiv cm+dn\equiv n_{i}m+m_{j}n\;(mod\;mn)$，即任意一个 $Z$ 中的元素，刚好对应一对 $n_{i},m_{j}$ 与之对应同余。
这样的元素总数有 $\phi(m)\phi(n)$ 个，即 $\phi(mn)=\phi(m)\phi(n)$，证明完毕。

这个写的很散，排版也不好 https://www.cnblogs.com/Liisa/p/7228717.html
文库里面的 https://wenku.baidu.com/view/4cf720a8284ac850ad02423c.html
这个排版稍微好一点 https://weilai5432.github.io/2015/07/29/欧拉函数+中国剩余定理/
这些证明归根结底是通过中国剩余定理，得到一个关于 $p_1$ 的互质同余集与 $p_2$ 的互质同余集到 $p_1p_2$ 的互质同余集的一个映射关系，当取遍前两者所有元素进行一一配对之后恰好也取遍后者所有元素。
如果真的看不懂的话，那就记住这个结论吧……
5. 任何整数都可以拆成若干质数的积，所以对于任意整数 $z$ 有 $\phi(z)=\phi(p_1^{k_1}p_2^{k_2}…p_n^{k_n})=z(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_n})$
证明：由于 $z=p_1^{k_1}p_2^{k_2}…p_n^{k_n}$，并且任意两个质数都是互质关系。所以
$$\begin{align}
\phi(z)&=\phi(p_1^{k_1})\phi(p_2^{k_2})…\phi(p_n^{k_n}) \\
&=p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})…p_n^{k_n}(1-\frac{1}{p_n}) \\
&=p_1^{k_1}p_2^{k_2}…p_n^{k_n}(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_n}) \\
&=z(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_n})
\end{align}$$

欧拉定理

欧拉定理内容：若 $n,a$ 为正整数，并且 $n,a$ 互质，则 $a^{\phi(n)}\equiv 1\;(mod\;n)$
证明：
将 $[1,n]$ 中与 $n$ 互质的数按照从小到大顺序排列，这些数构成集合：$\{x_1,x_2…x_{\phi(n)}\}$。
考察这些数：$m_1=ax_1,m_2=ax_2…m_{\phi(n)}=ax_{\phi(n)}$
这些数有如下性质：
(1)任意两个数模 $n$ 不同余
因为若 $m_j-m_i\equiv 0\;(mod\;n)$，则 $a(x_j-x_i)=kn$，由于 $x_j-x_i$ 一定小于 $n$ 不可能是 $n$ 的倍数，$n,a$ 互质，所以等式不可能成立。所以任意两个数模 $n$ 不同余
(2)任意一个数模 $n$，结果与 $n$ 互质
因为在 $ax_i\equiv t\;(mod\;n)$，有 $ax_i=kn+t$。
若 $gcd(t,n)=r$，假设 $n=pr,t=qr$，则 $ax_i=(kp+q)r$。
说明 $m_i$ 也是 $r$ 的倍数，$ax_i,n$ 存在公约数 $r$。
而 $gcd(a,n)=1,gcd(x_i,n)=1$，所以 $ax_i,n$ 的公约数不可能为 $r$。
所以任意一个数模 $n$，结果与 $n$ 互质。
由(1)(2)可知，$ax_1,ax_2…ax_{\phi(n)}$ 一定一一对应同余于 $x_1,x_2…x_{\phi(n)}$
则有：$ax_1⋅ax_2⋅…⋅ax_{\phi(n)}\equiv x_1x_2…x_{\phi(n)}\;(mod\;n)$。
则有：$a^{\phi(n)}\equiv 1\;(mod\;n)$，得证。

到这里，RSA 的基本原理中的重要定理欧拉定理算是从根源到表面完全探究了一遍，下面来看 RSA 自己的证明。

正篇：RSA 算法的证明

把上面 RSA 加密算法中出现的各个项目按照刚刚讲所有知识点再表达一遍：$\phi(n)$ 是欧拉函数，$d,e$ 是关于模 $\phi(n)$ 的模逆元且 $e,\phi(n)$ 互质。
再来看加密和解密的公式：
$$
Encode: S=D^e\;\%\;n \\
Decode: D=S^d\;\%\;n
$$
要证明解密过程的正确性，我们先将它们表示成我们刚刚熟悉的表达形式
$$
D^e\equiv S\;(mod\;n) \\
S^d\equiv D\;(mod\;n)
$$
加密公式换一种形式：
$$
D^e=kn+S \Rightarrow S=D^e-kn
$$
带入到解密式子中
$$
(D^e-kn)^d\equiv D\;(mod\;n) \Rightarrow D^{de}\equiv D\;(mod\;n)
$$
由于 $de\equiv 1\;(mod\;\phi(n))$，所以 $de=t\phi(n) + 1$。
因此问题转化为了证明 $D^{t\phi(n) + 1}\equiv D\;(mod\;n)$ 成立。
分两种情况讨论
(1)若 $D,n$ 互质
根据欧拉定理有 $D^{\phi(n)}\equiv 1\;(mod\;n)$，因此 $D^{t\phi(n) + 1}\equiv D\;(mod\;n)$ 成立。
(2)若 $D,n$ 不互质
由于 $n=pq$，$p,q$ 都是质数。
所以 $D$ 一定是 $p$ 或者 $q$ 的倍数，并且由于 $D<n$，$D$ 不会为 $p，q$ 的公倍数。
所以 $D=hp$ 或者 $D=hq$。
这里令 $D=hp$，容易证明 $D,q$ 一定互质。
则有：$D^{\phi(q)}\equiv 1\;(mod\;q)$。
所以：
$$\begin{align}
& &(D^{\phi(q)})^{t\phi(p)} &\equiv 1\;(mod\;q) \\
&\Rightarrow &D^{t\phi(q)\phi(p)} &\equiv 1\;(mod\;q) \\
&\Rightarrow &D^{t\phi(n) + 1} &\equiv D\;(mod\;q) \\
&\Rightarrow &D^{de} &\equiv D\;(mod\;q) \\
&\Rightarrow &D^{de} &=rq + D
\end{align}$$
根据假设，$D$ 为 $p$ 的倍数，$p,q$ 互质，所以 $r$ 为 $p$ 的倍数，假设 $rq=spq=sn$，则有
$$
D^{de}\equiv sn + D\equiv D\;(mod\;n)
$$
得证。

写在最后

加密算法在安全领域里面是最重要的算法，RSA 作为最早的非对称加密算法绝对是具有学习的价值的，后来发展的非对称加密算法或多或少都受到一点 RSA 算法的影响，或者是在 RSA 算法基础上的拓展（比如不用整数域改用圆锥曲线上的有限域等）。
RSA 算法可靠吗？答案是在选取足够大的质数下是很可靠的。
我们考察一下 RSA 在加密信息用到的值，可发现只传递加密值 $S$，$n$ 双方各保留一份，解密所需的私钥为 $d$，那么有没有可能通过公钥 $e$ 和 $n$ 推出私钥 $d$ 呢（伪装发送方）？或者反过来通过 $d$ 和 $n$ 推出公钥 $e$ 呢（伪装接收方）？
RSA 加密过程中，如果要得到私钥 $d$，与私钥 $d$ 有关的变量只有 $e,\phi(n)$，$de\equiv 1\;(mod\;\phi(n))$。也就是要得到 $\phi(n)$ 的值。
要计算 $\phi(n)$，有两种方法，一种是枚举，显然在两个质数足够大的时候这个耗时是不现实的；一种是得知 $n$ 算得时的两个质数 $p,q$，利用欧拉函数性质计算，这样就需要对 $n$ 进行因式分解。
如果将来发展出一种快速的因式分解方法，那么 RSA 加密可靠性将大大下降，然而事实是现阶段没有任何一种有效的因式分解方法，所以 RSA 在现阶段依旧是安全的。
目前针对 RSA 的因式分解，一个是在 1999 年分解的 RSA-155 (512 bits)，花了五个月时间（约 8000 MIPS 年）和 224 CPU hours 在一台有 3.2G 中央内存的 Cray C916 计算机上完成。一个是在 2009 年 12 月 12 日分解的编号为 RSA-768 (768 bits, 232 digits)。这一事件威胁了现通行的 1024-bit 密钥的安全性，普遍认为用户应尽快升级到 2048-bit 或以上。
所以在现阶段，RSA 加密领域在 1024 位以上是相对安全的。
所以从这段描述中，你是不是发现了啥？没错，要实现现阶段可靠的 RSA 算法，你必须实现大数计算算法，因为现阶段的数据结构中达不到 RSA 计算要求的位数。
也可以说，现阶段实现可靠的 RSA 加密算法，其实就是实现一个大数运算算法。
当然 Java 有自带类可以帮助完成的，但是那样就感觉有点无聊了。
关于大数运算的逻辑，这里不在过多叙述，感兴趣的我这里有一个 C# 类，除了除法其他的都实现了，想要的可以联系我。

OK，今天就先写到这里，Have a nice day～

Stefenson's Blog

一个渣渣程序员的笔记