RSA 加密算法的实现原理

RSA 加密算法是一种非对称加密算法，在公开密钥加密中被广泛使用。RSA 是 1977 年由 Ron Rivest、Adi Shamir、Leonard Adleman 一起提出的，RSA 就是他们三人姓氏的开头字母。

杨辉三角形和二项式系数

杨辉三角形，又称帕斯卡三角形，是二项式系数的一种几何排列。出现在南宋数学家杨辉所著的《详解九章算法》一书中。

二项式 $(x+1)^n $ 的各项展开式系数就是第 n 行杨辉三角形上的数字。
$$
(x+1)^0=1 \
(x+1)^1=x+1 \
(x+1)^2=x^2+2x+1 \\
(x+1)^3=x^3+3x^2+3x+1 \
(x+1)^4=x^4+4x^3+6x^2+4x+1 \
… \
(x+1)^n=x^n+nx^{n-1}+\frac{n(n-1)}{2}x^{n-2}+\frac{n(n-1)(n-2)}{2\times3}x^{n-3}+…+1
$$

其中每一项的系数都是一个组合数 $ C_n^p $，可以表示成如下形式

$$ C_n^p={\tbinom {n}{p}}={\tfrac {n!}{p!(n-p)!}} $$

特性当 n 为质数时，除了第一项和最后一项，中间所有项的系数均为 n 的倍数。

证明 p 不为 n 或 0 时，由于分子有质数 n，但分母不含 n，故分子的 n 能保留，不会因约分而除去。即 $ {\tbinom {n}{p}} $ 恒为 n 的倍数。

(这里隐含了一个前提条件，即 ${\tbinom {n}{p}}$ 是一个整数。)

费马小定理

假如 a 是一个整数，p 是一个质数，那么 $ a^p-a$ 是 p 的倍数，可以表示为

$$ a^p \equiv a \pmod p $$

例如，
$$ 7^3-7=343-7=336=7\times48 \
6^5-6=7776-6=7770=6\times1296$$

皮埃尔·德·费马于 1636 年发现了这个定理。在一封 1640 年 10 月 18 日的信中他第一次使用了上面的书写方式。

证明可以利用杨辉三角形来证明。

如果 a 不是 p 的倍数，这个定理也可以写成

$$ a^{p-1} \equiv 1 \pmod p ,,,,,,,,,(费马小定理) $$

欧拉 $ \varphi $ 函数

在数论中，对于正整数 n，欧拉函数 $ \varphi (n) $ 是小于或等于 n 的正整数中与 n 互质的数的数量。

例如，$ \varphi (8) =4 $，因为 1，3，5，7 均与 8 互质。由此可以推出，当 n 为素数时， $ \varphi (n) = (n-1) $。

性质欧拉 $\varphi$ 函数是积性函数。即是说若 m,n 互质，则 $ \varphi(mn)=\varphi(m) \varphi(n) $。

费马-欧拉定理

1736 年，欧拉证明了费马小定理。同时还对其进行了拓展，拓展之后的定理被称为『费马-欧拉定理』。

若 n，a 为正整数，且 n，a 互素，则

$$ a^{\varphi(n)}\equiv 1\pmod n ,,,,,,,,,(费马-欧拉定理)$$

当 n 为素数，$\varphi(n)=n-1$，这时就变成了费马小定理

$$ a^{p-1} \equiv 1 \pmod p $$

RSA 算法

公钥与私钥的产生

假设 Alice 想要通过一个不可靠的媒体接收 Bob 的一条私人消息。她可以用下面的方法来产生一对公私钥:

选择任意两个大素数 p 和 q，p 不等于 q，计算 $ N=pq $。
求出 $\varphi(N)$，令 $r = \varphi(N)=\varphi(m) \varphi(n)=(p-1)(q-1)$。
选择一个小于 r 且与 r 互质的整数 e。
选择一个数 d，使得 $ed-1=r,的倍数$。即 d 是 e 关于 r 的模逆元。
销毁 p 和 q。

$(N,e)$ 是公钥， $(N,d)$ 是私钥。Alice 将公钥传给 Bob，而将私钥藏起来。

加密消息

假设 Bob 想给 Alice 发送一个消息 m (m<N)，需要先找到一个正整数 c，使得 $m^e-c=N,的倍数 $ ①。这个 c 就是加密后的密文。

解密消息

Alice 拿到密文 c 后，需要找到一个数 x。使得 $c^d-x=N,的倍数 $ ②。然后你会发现，在小于 N 的正整数中，只有 m 这一个解。

怎么样，加解密过程是不是特别简单？

证明

其实只需要证明从式子 ① 可以变换到式子 ② 即可。

拓展

提问 1

如果消息 m 过长，即 m > N 时怎么办？

提问 2

有没有可能在已知公钥 $(N,e)$ 的情况下，推导出私钥 $(N,d)$？

回答 1

可以先将消息 m 分段，然后再传输。

回答 2

$ed\equiv 1 \pmod {\varphi(N)} $。只有知道 e 和 $\varphi(N)$，才能算出 d。
$\varphi(N)=(p-1)(q-1)$。只有知道 p 和 q，才能算出 $\varphi(N)$。
$N=pq$。只有将 N 因数分解，才能算出 p 和 q。

结论：如果 N 可以被因数分解，d 就可以算出，也就意味着私钥被破解。

大整数的因数分解，是一件非常困难的事情(属于 NPC 问题)。除了暴力破解，目前还没有发现别的有效方法。人类已经分解的最大整数是（232 个十进制位，768 个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长 RSA 密钥就是 768 位。

证明过程的 Latex 语句

\begin{align*}  

& m^e-c=N的倍数 \qquad\qquad\qquad\qquad\qquad\quad (1)将\,c\,提至一边 \\
& c=m^e-N的倍数 \qquad\qquad\qquad\qquad\qquad\quad (2)两边同时进行\,d\,次方 \\
& c^d=(m^e-N的倍数)^d \qquad\qquad\qquad\qquad\quad\,\,\, (3)将\,(m^e-N的倍数)^d\,展开，并且将包含\,N的倍数\,项合并\\
& c^d=m^{ed}-N的倍数 \qquad\qquad\qquad\qquad\qquad\, (4)将\,ed=1+r的倍数\,带入式中 \\
& c^d=m^{1+r的倍数}\,\,\,-N的倍数 \qquad\qquad\qquad\qquad\, (5)将指数\,1\,提出来 \\
& c^d=m \cdot m^{r的倍数}\,\,\,-N的倍数 \qquad\qquad\qquad\quad\,\,\, (6)将\,r=\varphi(N)\,带入式中 \\
& c^d=m \cdot m^{\varphi(N)的倍数}\,\,\,-N的倍数 \qquad\qquad\qquad\,\, (7)根据\,费马-欧拉定理，将\,m^{\varphi(N)}=1+N的倍数\,带入式子 \\
& c^d=m \cdot (1+N的倍数)^{\varphi(N)的倍数-1}\,\,\,-N的倍数 \quad (8) 重复第\,(7)\,步 \\
& c^d=m \cdot (1+N的倍数)-N的倍数 \qquad\qquad\,\,\,\, (9)将\,(1+N的倍数)^{\varphi(N)的倍数-1}\quad展开，并且合并\,N的倍数 \\
& c^d=m+N的倍数 \qquad\qquad\qquad\qquad\qquad\,\,\, (10) 证毕。

\end{align*}