RSA 算法证明
RSA 算法证明
RSA 算法是加密学中非常重要的一个算法，具体介绍援引 wiki百科：
RSA加密演算法是一种非对称加密演算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。[1]
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。[2]
對极大整数做因数分解的難度決定了 RSA 算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到2020年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。
我在网上找了很多关于 RSA 算法的证明，但总是有某几个步骤语焉不详，花费了一些精力之后，终于搞懂了，因此记录一下。
RSA 用到的几个数学概念：
在进行 RSA 算法证明之前，我们先介绍几个数学概念：
模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，即ab ≡ 1 (mod n)
φ(n):小于n且与n互质的正整数的个数，比如φ(10) = 4,因为小于10且与10互质的的数为1，3，7，9
欧拉定理：m和n互质，则m^φ(n) ≡ 1 (mod n)
欧拉函数：如果n为质数，φ(n)=n-1
欧拉函数是积性函数：若m,n互质， φ(mxn)=(m-1)(n-1)
同余性质：
1).反身性：a≡a (mod n)；
2).对称性：若a≡b(mod n)，则b≡a (mod n)；
3).传递性：若a≡b(mod n)，b≡c(mod n)，则a≡c(mod n)；
4).同余式相加：若a≡b(mod n)，c≡d(mod n)，则a+c≡b+d(mod n)；
5).同余式相乘：若a≡b(mod n)，c≡d(mod n)，则axc≡bxd(mod n)。(特殊情况c=d下也成立)
6).幂运算：如果a≡b(mod n)，那么a^k≡b^k(mod n)；
以上都是已经被证明的数学定律，由于篇幅以及智商（占主要）原因，本篇不研究其证明过程，直接拿来使用。
RSA 算法加解密过程：
随机选取两个大质数 p 和 q，n = pq, 再随机选取一个整数 e，e 与 φ(n) 互质, (e 通常为65537), 再次计算一个 d, 它是 e 对于 φ(n) 的模反元素，也就是 ed ≡ 1 (mod φ(n))
加密过程：m^e ≡ c (mod n)，其中 m 为原信息（注意m < n），c 为加密信息，(n、e) 为公开密钥。
解密过程：c^d ≡ m (mod n)，其中 (n、d) 为解密密钥。
RSA 算法加解密举例
假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？
第一步，随机选择两个不相等的质数p和q。
爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
第二步，计算p和q的乘积n。
爱丽丝就把61和53相乘。
n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
第三步，计算n的欧拉函数φ(n)。
根据公式：
φ(n) = (p-1)(q-1)
爱丽丝算出φ(3233)等于60×52，即3120。
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
第五步，计算e对于φ(n)的模反元素d。
所谓“模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
注意这里的 k，并不是某一个具体的值，而是说，由于 ed 整除 φ(n) 余1，则 ed - 1 总可以表示成 φ(n) 的 k 倍。
于是，带入 e = 17，φ(n) = (p-1)(q-1) = 60×52 = 3120:
17d - 1 = 3120k
这个方程可以用“扩展欧几里得算法”求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (d,k)=(2753,15)，即 d=2753。
至此所有计算完成。
第六步，将n和e封装成公钥，n和d封装成私钥。
在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
实际应用中，公钥和私钥的数据都采用 ASN.1 格式表达。
RSA算法的可靠性
回顾上面的密钥生成步骤，一共出现六个数字：
p
q
n
φ(n)
e
d
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无可能在已知n和e的情况下，推导出d？
（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就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：
“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”
举例来说，你可以对3233进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413
它等于这样两个质数的乘积：
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。实际应用中 RSA 的密钥长度为 1024 位，重要场合 2048 位，破解难度在目前这阶段基本不可能。
加密和解密
有了公钥和密钥，就能进行加密和解密了。
加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓"加密"，就是算出下式的c：
m^e ≡ c (mod n)
爱丽丝的公钥是 (3233, 17)，鲍勃的m假设是65，那么可以算出下面的等式：
65^17 ≡ 2790 (mod 3233)
于是，c等于2790，鲍勃就把2790发给了爱丽丝。
解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
c^d ≡ m (mod n)
也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，爱丽丝算出
2790^2753 ≡ 65 (mod 3233)
因此，爱丽丝知道了鲍勃加密前的原文就是65。
至此，“加密–解密"的整个过程全部完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
RSA 算法加解密证明：
下面，我们来证明，为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子：
c^d ≡ m (mod n)
因为，根据加密规则
ｍ^e ≡ c (mod n)
于是，c可以写成下面的形式：
c = m^e - kn
跟上面的解释同理，k 表示总能找到一个数 k，使得 m^e - c 可以表示成 n 的 k 倍。
将c代入要我们要证明的那个解密规则：
(m^e - kn)^d ≡ m (mod n)
它等同于求证
m^ed ≡ m (mod n)
这里可能有些跳跃，试想，如果 d=2，则
(m^e - kn)^2
= (m^e - kn)(m^e - kn)
= (m^e)(m^e) - kn(m^e) - kn(m^e) + (kn)^2
= m^2e - 2kn(m^e) + (kn)^2
由于 2kn(m^e) 和 (kn)^2 都含有因式 n，因此都可以被 n 整除。
所以上面这个式子等同于求证 m^2e ≡ m (mod n)
同理，将 d 推广到 >2 的情况，由于因式分解产生的中间项和最后项都含有因式 n，因此总能够被 n 整除。
所以只剩下第一项，也就是 m^ed 有可能不被 n 整除。
故：(m^e - kn)^d ≡ m (mod n) 等同于求证 m^ed ≡ m (mod n)
由于
ed ≡ 1 (mod φ(n))
所以
ed = hφ(n)+1
h 的解释同上面的 k，表示φ(n)的倍数。
将ed代入：
m^(hφ(n)+1) ≡ m (mod n)
接下来，分成两种情况证明上面这个式子。
(1) m与n互质。
根据欧拉定理，此时
m^φ(n) ≡ 1 (mod n)
根据上面的数学概念 6).幂运算：如果a≡b(mod n)，那么a^k≡b^k(mod n)； 得到
(m^φ(n))^h ≡ 1^h (mod n)
由于1的任意次方都是1，所以
(m^φ(n))^h ≡ 1 (mod n)
根据上面的数学概念 5).同余式相乘：若a≡b(mod n)，c≡d(mod n)，则axc≡bxd(mod n)。(特殊情况c=d下也成立)
取特殊情况 c=d 都等于 m，得到：
(m^φ(n))^h × m ≡ m (mod n)
则得到
m^(hφ(n)+1) ≡ m (mod n)
原式得到证明。
(2) m与n不是互质关系。
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。
以 m = kp为例，这时k与q必然互质
这里有些难理解，举例：p = 3, q = 7, 则 n = 21
若 m = 6，则 m 与 n 不是互质关系，此时 m = 2p，则 k = 2
此时 2 和 7 必然互质。
因为 m = kp，n = pq，且 m < n，
所以 k < q，由于 q 是质数，所以 k 和 q 必然互质。
因为k与q必然互质，则 kp(也就是m) 与 q 也必然互质
还是有些难理解，继续上面的例子：
m = 6, 6 和 7 也必然互质。
因为 m = kp，n = pq，且 m < n，
如果 m 已经是 p 的倍数，此时 m 还是 q 的倍数，这样 m 就是 p 和 q 的公倍数。
由于 p 和 q 互质，所以 p 和 q 的最小公倍数是 n。则 m >= n，不成立。
所以 m 不是 q 的倍数。由于 q 是质数，所以只要 m 不是 q 的倍数，则 m 和 q 互质。
由于 kp(也就是m) 与 q 互质，根据欧拉定理，下面的式子成立：
(kp)^φ(q) ≡ 1 (mod q)
由于 q 是质数，代入 φ(q) = q-1 得到：
(kp)^(q-1) ≡ 1 (mod q)
根据上面的数学概念 6).幂运算：如果a≡b(mod n)，那么a^k≡b^k(mod n)； 得到
[(kp)^(q-1)]^(h(p-1)) ≡ 1^(h(p-1)) (mod q)
由于 1^(h(p-1)) = 1（1的任意次方等于1)，得到：
[(kp)^(q-1)]^(h(p-1)) ≡ 1 (mod q)
根据上面的数学概念 5).同余式相乘：若a≡b(mod n)，c≡d(mod n)，则axc≡bxd(mod n)。(特殊情况c=d下也成立)
取特殊情况 c=d 都等于 kp，得到：
[(kp)^(q-1)]^(h(p-1)) × kp ≡ kp (mod q)
(kp)^(h(p-1)(q-1)+1) ≡ kp (mod q)
代入 φ(n) = (p-1)(q-1) 和 m = kp 得到：
m^(hφ(n)+1) ≡ m (mod q)
将它改写成下面的等式
m^(hφ(n)+1) = tq + m
t 的解释同上面的 k，表示 q 的倍数。
则有
tq = m^(hφ(n)+1) - m
tq = m(m^(hφ(n)) - 1)
由于 p 是个大质数，则 m = kp 是个比 p 更大的数，所以 (m^(hφ(n)) - 1) 是个整数，则 tq 是 m 的倍数，又 m = kp，tq 当然也是 p 的倍数。
由于 q 是质数，p 和 q 互质，那么 q 不是 p 的倍数，所以 t 一定是 p 的倍数，也就是 t 必然能被 p 整除，即 t=t'p
m^(hφ(n)+1) = t'pq + m
代入 n=pq，得到
m^(hφ(n)+1) = t'n + m
上式可以转写成：
m^(hφ(n)+1) = m (mod n)
原式得到证明。
python 代码演示：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2022/11/28 14:28
# @Author : David Hao
# @File : rsa_demo.py
# @Software: IntelliJ IDEA
import itertools
def find_mod_reverse(e, r):
# 这里直接用模逆元定义的概念，for循环找出d
# 也可以用扩展欧几里得算法或者欧拉定理计算出来
for d in itertools.count(1):
if (e * d) % r == 1:
return d
def get_new_key(p, q, e=3):
# e的定义是比r小和r互质的的正整数
# 【注意】: 这里取3是方便计算演示，一般使用65537
N = p * q
r = (p - 1) * (q - 1)
d = find_mod_reverse(e, r)
return N, e, d
def rsa(N, key, message):
# 加密和解密本质上都是求指数和模的过程，所以可用参数不同的同一个函数
# 这也是为什么公私钥可以互换，但是不建议（原因是公钥出于种种原因一般都很短）
me = message ** key
return me % N
def rsa_demo(raw_message):
# 取2个质数
p = 17
q = 23
# 获取公私钥
(N, e, d) = get_new_key(p, q)
print('public key: (%s, %s)' % (N, e))
print('private key: (%s, %s)' % (N, d))
cipher_message = ''
for char in list(raw_message):
# 加密
char_unicode = ord(char)
char_cipher_unicode = rsa(N, e, char_unicode)
cipher_message += chr(char_cipher_unicode)
decipher_raw_message = ''
for char in list(cipher_message):
# 解密
char_unicode = ord(char)
char_decipher_unicode = rsa(N, d, char_unicode)
decipher_raw_message += chr(char_decipher_unicode)
print('原始消息：%s' % raw_message)
print('加密后的值：%s' % cipher_message)
print('解密后的值：%s' % decipher_raw_message)
if __name__ == '__main__':
rsa_demo('hello rsa algorithm!')
运行之后，得到输出：
public key: (391, 3)
private key: (391, 235)
原始消息：hello rsa algorithm!
加密后的值：ŜĭĭİĻ-ĔOĻOĭđİ-ĉŜ%Ť
解密后的值：hello rsa algorithm!
ssh-keygen生成的id_rsa文件的格式
上面说了那么多，我们都知道在 linux、mac 系统中，使用 ssh-keygen 生成公钥和私钥对默认保存在 ~/.ssh 目录下，文件名分别是 id_rsa（私钥）和 id_rsa.pub（公钥）：
[Local] ~ ll ~/.ssh | grep rsa
-rw------- 1 jiakah staff 1.8K Oct 30 2020 id_rsa
-rw-r--r-- 1 jiakah staff 406B Oct 30 2020 id_rsa.pub
上文提到了公钥的格式是 (N, e)，私钥的格式是 (N, d)，那么到底这两个文件是如何保存这些信息的呢，这里我在知乎上找到一篇比较好的文章：ssh-keygen生成的id_rsa文件的格式
讲的比较详细，直接看上面的文章即可，这里就不重复了。