RSA加密算法笔记 | 田山泉 Webpage

不知道你有没有想过，当我们在网上付款、发送邮件，甚至和朋友分享秘密时，这些信息到底是怎么保护起来不被别人窃取的？这些服务都得益于现代密码通信技术，其中最常用也最有名的算法即RSA加密算法。

什么是非对称加密算法？

在RSA出现之前，人类使用的都是"对称加密"的方式，也就是通信双方共用一个相同的密钥，一旦密钥泄露，通信就会完全暴露。那么，有没有可能不用共享相同的密钥，而实现安全通信呢？

答案是非对称加密算法。非对称加密算法的原理其实很简单：

接收方（比如阿明）首先生成一对密钥：一把公钥、一把私钥。公钥可以公开，任何人都能获取，而私钥则必须严格保密，只能由自己掌握。
发送方（比如你）获取阿明的公钥，并用它将要发送的信息加密。
阿明收到加密后的信息后，使用自己的私钥进行解密，从而恢复出原始内容。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

RSA算法的前世今生

人类苦苦寻觅着有效的安全通信方式，孰不知答案早些在玄妙的数论中。早在1874年，William Stanley Jevons 在他的著作 The Principles of Science 提到了大质数分解问题： “读者能否说出哪两个数相乘得到8616460799 我想，除了我自己之外，很难有人知道”

历史的齿轮似乎开始缓缓转动。然而，这个齿轮却稍微卡了壳，直到20世纪70年代，随着Diffie–Hellman key exchange技术的横空出世，这个问题才迎来了重大突破。就在这一波密码学革命的大潮中，1977年，三位数学家Rivest、Shamir和Adleman共同创造了RSA算法。RSA之所以广泛流行，是因为它使用了的正是一种巧妙的数学机制：利用大数分解的困难性来保证加密信息的安全性。

对于大数分解的困难性，简单理解就是，把两个质数相乘很容易，但想把乘积再还原成原来的质数却极其困难，这正是RSA算法安全的基石。

RSA到底是如何运作的？

第一步：制作钥匙

阿明想要接受你的消息，他首先会制造一对钥匙：

公钥：任何人都可以用来加密。
私钥：只有他自己知道，用来解密。

具体如何制作？很简单又很巧妙：

阿明先随意选两个超大的质数p和q。举例：17 和 19。
计算乘积$N = p \times q$。举例：$17 \times 19 = 323$.
计算欧拉函数$\varphi(N) = (p-1) \times (q-1)$。其中欧拉函数为“小于等于n的正整数之中，有多少个与n构成互质关系”。举例：$16 \times 18 = 288$.
再选择一个数e，满足e与$\varphi(N)$互质。举例：5
最后计算d，使得$(e \times d) \mod \varphi(N) = 1$。举例：这里$d=173$，因为$5 \times 173 = 865, 865 mod 288 = 1$

现在，阿明的公钥是$(N, e)$，私钥则是$(N, d)$。公钥他可以放心地告诉你，而私钥则深藏于他的"保险柜"中。在这个例子里，阿明的公钥是(323, 5)，私钥是(323, 173)。

第二步：安全通信开始！

现在，你想向阿明发送秘密消息，比如一句话：“我找到了藏宝图！” 你需要：

将这句话转化为数字，比如按照字符的ASCII码。
使用阿明的公钥$(N, e)$进行加密，形成一串新的数字。

就算有人截获了你的信息，没有阿明的私钥$(N, d)$，他们也无法读懂。

阿明收到消息后，用他私藏的私钥轻松解开这串数字，还原出你的秘密信息。

举个例子，假设你想传送数字信息"9"（比如家里保险柜密码就是9），

加密过程： $$9^5\ mod\ 323 = 263$$. 我们可以放心用明文跟对方说“Hey，263”。
解密过程：收到263之后，$$263^{173}\ mod\ 323 =\ a\ big\ number = 9$$ 解密过程参考
```
$ python3 -c "print(263**173 % 323)"
9
```

所有人都可以知道保险柜密码是“Hey，263”。但是只有拥有密钥的人才可以解开谜底“9”。

为什么RSA如此安全？

RSA的神奇之处在于，即使你知道了公钥，也无法轻易算出对应的私钥。这就是著名的"质因数分解难题"。即便计算机日新月异，到量子计算机还远未实现的今天为止，人类仍然无法高效地破解足够大的RSA密钥。

随着量子计算机的发展，传统RSA算法可能面临严峻的挑战，因为量子计算机有望迅速破解传统计算机难以解决的问题，比如Shor’s algorithm。
因此，未来的密码学研究仍然需要不断探索新的算法，以确保我们的数字秘密永远安全。参见Post-Quantum Cryptography PQC。

写在最后

RSA算法不仅仅是一串公式或代码，更是一段数字时代的安全传奇。它保护了我们每天的隐私通信、银行交易和数据安全。下一次，当你在网络上分享重要信息时，别忘了背后有RSA算法这样默默无闻的守护者在保护着你的隐私。

(This post is based on my learning note in 2019.)