非对称加密：为什么RSA让“公开传密”成为可能

在1977年之前，加密世界遵循一个铁律：想要安全通信，必须先秘密交换密钥。无论是凯撒密码还是二战时的恩尼格玛机，都依赖发送方和接收方预先共享同一把“钥匙”。但RSA算法的出现颠覆了这一规则——它让陌生人可以在完全公开的环境下建立安全通信，而无需事先约定任何秘密。

今天，RSA（Rivest-Shamir-Adleman）算法支撑着HTTPS、数字签名、SSH等关键技术，成为现代互联网的加密基石。但它是如何做到“公开传密”的？背后的数学原理又是什么？

一、非对称加密

非对称加密，也称为公钥加密，是一种使用一对密钥（公钥和私钥）进行加密和解密的密码学方法。与对称加密（如 AES）不同，非对称加密的公钥和私钥在数学上相关，但不能互相推导，使得通信更安全。

• 公钥（Public Key）：公开给所有人，用于加密数据或验证签名。
• 私钥（Private Key）：严格保密，用于解密数据或生成签名。

类比：想象一个带锁的邮箱，任何人都能往里面投递信件（公钥加密），但只有你有钥匙能打开查看（私钥解密）。

二、RSA秘钥的生成过程

1、选择两个大质数 $p$ 与 $q$

2、两个大质数相乘得到 $N=p\times q$

3、计算欧拉函数 $\varphi (p,q)=(p-1)\times (q-1)$

4、选择公钥 $E$ ，$E$ 需要满足 （1）$1<E<\varphi (p,q)$ （2）$E$ 与 $\varphi (p,q)$ 互质，即 $GCD(E,\varphi (p,q))=1$

5、获得私钥 $D$，$D$ 需要满足 $(D\times E)\%T=1$

注意：$E$ 和 $D$ 都不需要是质数

最终秘钥

• 公钥：(E, N)
• 私钥：(D, N)

举个例子

1、选择两个质数 61 和 67

2、计算模数 N = 61 * 67 = 4087

3、计算欧拉函数 $\varphi$ = 60 * 66 = 3960

4、选择公钥 E = 17

5、获得私钥 D = 233

获得公钥 (17,4087) 私钥 (233, 4087)

三、如何加密解密

假设我现在要加密一个单词 DOG，可以发现他的ASCII码是 68 79 71 。那么用公钥加密也是一件简单的事情。

加密：

明文 $m$	加密 $c=m^E\text{mod}N$	密文 $c$
68	$68^{17}\text{mod}4087$	3284
79	$79^{17}\text{mod}4087$	453
71	$71^{17}\text{mod}4087$	4085

获得加密后的密文 3284 453 4085。

解密：

密文	解密 $m=c^{D}modN$	明文 $m$
3284	$3287^{233}\text{mod}4087$	68
453	$453^{233}\text{mod}4087$	79
4085	$4085^{233}\text{mod}4087$	71

明文公钥加密后被私钥破解。

四、为什么非对称加密难以破解

RSA加密的核心在于于大整数的质因数分解问题。公钥包含模数 N = q * p ， p 和 q 是大质数，而私钥需要知道这两个质数才能计算。所以破解 RSA 就约等于分解 N，但对于足够大的 N即使是超级计算机也需要数万年才能计算成功，目前没有已知的高效算法可以在多项式时间内分解大整数。

• RSA-1024：曾被认为是安全的，但现代计算能力已能威胁它（需要数月到数年）。
• RSA-2048：当前标准，破解需要 $10^{20}$ 年（远超宇宙年龄）。
• ECC-256：等效于RSA-3072的安全性，但密钥更短、计算更快。

五、RSA的局限性

计算量大，通常仅用于密钥交换或签名，而非加密大量数据（实际结合AES等对称加密使用）

Shor算法能在量子计算机上快速分解大数，威胁RSA安全（后量子密码学正在发展）