RSA 加密算法的实现原理

发表于 更新于 分类于 阅读次数： 78

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=x2+2x+1(x+1)3=x3+3x2+3x+1 (x+1)4=x4+4x3+6x2+4x+1 … (x+1)n=xn+nxn−1+n(n−1)2xn−2+n(n−1)(n−2)2×3xn−3+…+1

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

Cpn=(np)=n!p!(n−p)!

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

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

(这里隐含了一个前提条件，即 (np) 是一个整数。)

费马小定理

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

ap≡a(modp)

例如，
73−7=343−7=336=7×48 65−6=7776−6=7770=6×1296

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

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

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

ap−1≡1(modp),,,,,,,,,(费马小定理)

欧拉 φ 函数

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

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

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

费马-欧拉定理

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

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

aφ(n)≡1(modn),,,,,,,,,(费马−欧拉定理)

当 n 为素数，φ(n)=n−1，这时就变成了费马小定理

ap−1≡1(modp)

RSA 算法

公钥与私钥的产生

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

  • 选择任意两个大素数 p 和 q，p 不等于 q，计算 N=pq。
  • 求出 φ(N)，令 r=φ(N)=φ(m)φ(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，使得 me−c=N,的倍数 ①。这个 c 就是加密后的密文。

解密消息

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

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

证明

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

拓展

提问 1

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

提问 2

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

回答 1

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

回答 2

  1. ed≡1(modφ(N))。只有知道 e 和 φ(N)，才能算出 d。
  2. φ(N)=(p−1)(q−1)。只有知道 p 和 q，才能算出 φ(N)。
  3. N=pq。只有将 N 因数分解，才能算出 p 和 q。

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

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

证明过程的 Latex 语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
\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*}

引用