RSA 加密算法详解（纯知识版，由浅入深）

RSA 是非对称加密算法的经典代表，由 Ron Rivest、Adi Shamir 和 Leonard Adleman 于 1977 年提出，核心特征是 “公钥加密、私钥解密”（或私钥签名、公钥验证），无需提前共享密钥，是现代网络安全、数据加密传输的基础技术（广泛应用于 HTTPS、SSH、数字证书、电子签名等场景）。

一、核心前提：为什么需要非对称加密？（RSA 的诞生意义）

在 RSA 出现前，主流加密方式是对称加密（如 AES、DES）：加密和解密使用同一把 “密钥”。但对称加密存在两个致命缺陷：

1. 密钥传输难题：要给对方发加密数据，必须先安全传递密钥 —— 一旦密钥在传输中被拦截，数据就会被破解；
2. 密钥管理难题：多用户通信时，密钥数量呈指数增长（n 个用户需 n (n-1)/2 个密钥），维护成本极高。

RSA 的非对称特性彻底解决了这两个问题：

• 生成一对关联密钥：公钥（Public Key） 和私钥（Private Key） ；
• 公钥可完全公开（如发布在网站、传给任意第三方），私钥必须严格保密（仅持有者保存）；
• 核心规则：
  1. 公钥加密的数据，仅对应的私钥能解密；
  2. 私钥加密的数据（用于 “数字签名”），仅对应的公钥能验证。

通俗类比：

• 你生成 “公开锁”（公钥）和 “专属钥匙”（私钥），把 “公开锁” 分发给所有人；
• 别人要给你发秘密消息，用你的 “公开锁” 把消息锁起来（加密），只有你的 “专属钥匙” 能打开；
• 你要证明消息是自己发的，用 “专属钥匙” 锁上消息（签名），别人用你的 “公开锁” 能打开，就说明消息未被篡改且来自你。

二、必备数学基础（无需深究证明，懂定义和作用即可）

RSA 的安全性基于 “大整数分解难题”（将一个极大的合数分解为两个质数的乘积，目前无高效算法），需先掌握 5 个核心数学概念：

1. 质数（素数）

• 定义：大于 1 的自然数，除了 1 和自身，无法被其他整数整除（如 2、3、5、7、11、101...）；
• 作用：RSA 密钥生成的核心基础，需选择两个大质数作为 “秘密种子”。

2. 互质（互素）

• 定义：两个整数的最大公约数（GCD）为 1（如 6 和 25 互质，GCD (6,25)=1；8 和 12 不互质，GCD (8,12)=4）；
• 作用：确保公钥和私钥的唯一性、有效性，是模逆元存在的前提。

3. 模运算（取余运算）

• 定义：a mod n 表示 a 除以 n 后的余数（如 7 mod 3=1，10 mod 4=2）；
• 核心性质（RSA 运算基础）：(a × b) mod n = [(a mod n) × (b mod n)] mod n（避免大整数直接运算溢出）。

4. 欧拉函数 φ(n)

• 定义：小于 n 且与 n 互质的正整数个数（如 φ(6)=2，因为 1、5 与 6 互质）；
• 关键性质：若 n 是两个不同质数 p 和 q 的乘积（n=p×q），则 φ(n)=(p-1)×(q-1)（RSA 的核心数学依据，直接用于密钥计算）。

5. 模逆元

• 定义：若整数 e 和 φ(n) 互质，则存在唯一整数 d，使得 (e × d) mod φ(n) = 1，称 d 为 e 在模 φ(n) 下的逆元（记为 d=e⁻¹ mod φ(n)）；
• 作用：d 是私钥的核心，确保解密过程能准确还原明文。

三、RSA 核心流程：密钥生成→加密→解密（ step by step ）

RSA 的核心是 “三大步骤”，下面用 “通俗语言 + 数学公式 + 小示例” 结合讲解，确保可落地理解。

1. 第一步：生成密钥对（公钥 + 私钥）

目标：生成公开的公钥（e, n）和保密的私钥（d, n），n 是两者的共同参数（称为 “模”）。

具体步骤：

1. 选择两个大质数 p 和 q

   （实际应用中需是 1024 位以上的大质数，示例用小质数方便计算）；

   • 示例：p=61，q=53（均为质数）；

2. 计算 n = p × q

   （n 是公钥和私钥的共同 “模”，公开参数）；

   • 示例：n=61×53=3233；

3. 计算 φ(n) = (p-1)×(q-1)

   （利用欧拉函数性质）；

   • 示例：φ(3233)=(61-1)×(53-1)=60×52=3120；

4. 选择公钥指数 e

   （满足两个条件：1<e<φ(n)，且 e 与 φ(n) 互质）；

   • 行业标准选择：e=65537（兼顾安全性和计算效率，几乎所有场景通用）；
   • 示例：e=65537（验证：GCD (65537, 3120)=1，满足互质条件）；

5. 计算私钥指数 d

   （d 是 e 在模 φ(n) 下的逆元，即 d=e⁻¹ mod φ(n)）；

   • 计算方法：用 “扩展欧几里得算法”（无需手动实现，编程语言均有现成库）；
   • 示例：已知 e=65537、φ(n)=3120，求 d 使得 (65537×d) mod 3120=1，计算得 d=2753（验证：65537×2753 mod 3120=1）；

6. 最终密钥对

   ：

   • 公钥（Public Key）：(e, n) = (65537, 3233)（可公开）；
   • 私钥（Private Key）：(d, n) = (2753, 3233)（必须保密）。

关键注意：

• 实际应用中，p 和 q 需用 “密码学安全的随机数生成器” 生成（如 Go 的crypto/rand、Java 的SecureRandom），避免使用小质数或可预测的质数；
• 密钥长度：1024 位已逐步淘汰（存在被破解风险），2048 位是当前主流（安全性足够，计算速度适中），4096 位安全性更高但运算较慢，无需过度追求长度。

2. 第二步：加密过程（用公钥加密）

发送方获取接收方的公钥（e, n），对明文 m（需满足 m < n，否则需分段加密）进行加密。

加密公式：

密文c = m^e mod n（m 的 e 次方，对 n 取余）

示例：

明文 m=65（对应 ASCII 码的 'A'），用公钥 (65537, 3233) 加密：

c = 65^65537 mod 3233 = 2790（实际计算需用 “快速幂模算法”，避免直接计算大数次方）。

关键注意：

• 明文 m 必须小于 n，否则需分段加密（如 n=2048 位，明文按 2000 位分段）；
• 快速幂模算法：将时间复杂度从 O (e) 降至 O (log e)，是 RSA 高效运算的核心，编程语言均有内置实现。

3. 第三步：解密过程（用私钥解密）

接收方用自己的私钥（d, n）解密密文 c，还原明文 m。

解密公式：

明文m = c^d mod n（c 的 d 次方，对 n 取余）

示例：

密文 c=2790，用私钥 (2753, 3233) 解密：

m = 2790^2753 mod 3233 = 65（成功还原明文 'A'）。

核心原理（数学证明简化）：

根据模逆元定义，e×d = k×φ(n)+1（k 为整数），因此：

c^d mod n = (m^e mod n)^d mod n = m^(e×d) mod n = m^(k×φ(n)+1) mod n；根据欧拉定理，当 m 与 n 互质时，m^φ(n) mod n=1，因此：

m^(k×φ(n)+1) mod n = (m^φ(n))k × m mod n = 1^k × m mod n = m。

四、RSA 的安全性：为什么难破解？

RSA 的安全核心是 “大整数分解难题”—— 要破解私钥 d，必须先获取 φ(n)，而 φ(n)=(p-1)×(q-1)，因此必须先分解公开参数 n=p×q。

1. 破解难度分析：

• 若 n 是 2048 位大整数（由两个 1024 位质数相乘得到），目前最先进的计算机（包括量子计算机雏形）也无法在合理时间内完成分解；
• 若 n 是 1024 位及以下，已存在被破解的案例，因此实际应用需至少使用 2048 位密钥。

2. 常见攻击方式及防御手段

攻击方式	原理	防御手段
暴力破解	枚举可能的 p 和 q，尝试分解 n	使用 2048 位以上 n，选择随机大质数 p 和 q
中间人攻击	拦截公钥传输，替换为攻击者的公钥，窃取加密数据	结合数字证书（如 CA 证书）验证公钥合法性，避免接收未知来源的公钥
侧信道攻击	利用加密 / 解密时的时间、功耗、电磁辐射等信息推测私钥	使用恒定时间算法实现加密解密，避免分支预测泄露信息（编程语言官方库已优化）
小指数攻击	e 选择过小（如 e=3），导致明文可通过数学推导破解	直接使用行业标准 e=65537
padding oracle 攻击	利用解密时的填充错误提示，逐步推测明文	使用安全的填充模式（如 OAEP），避免返回具体的填充错误信息

3. 安全使用原则：

• 不手动实现密钥生成、加密解密逻辑，优先使用编程语言官方密码学库（如 Go 的crypto/rsa、Java 的java.security）；
• 私钥需加密存储（如用 AES 加密后存入文件 / 数据库），避免明文泄露；
• 定期更换密钥（如 1-2 年），降低密钥长期使用的风险。

五、RSA 的实际应用场景（通用场景）

1. HTTPS 协议：服务器用私钥签名证书，客户端用公钥验证证书合法性；客户端用服务器公钥加密 “预主密钥”，服务器用私钥解密，后续用对称加密传输数据（混合加密模式）；
2. SSH 登录：客户端用服务器公钥加密登录信息，服务器用私钥解密，确保登录过程安全；
3. 数字签名：文档作者用私钥对文档哈希值签名，接收方用公钥验证签名，确认文档未被篡改且来自合法作者（如电子合同、软件安装包校验）；
4. 敏感数据加密存储：用公钥加密敏感数据（如用户密码、API 密钥），存储到数据库，仅持有私钥的服务能解密；
5. 密钥交换：两个通信方用 RSA 交换对称加密密钥（如 AES 密钥），后续用对称加密传输大量数据（兼顾安全性和效率）。

版权所有

许可证：署名 4.0 国际 (CC-BY-4.0)