RSA加密算法的加密过程

我将为您详细讲解RSA加密算法的加密过程。RSA是1977年由Ron Rivest、Adi Shamir和Leonard Adleman提出的非对称加密算法，其安全性基于大整数分解的困难性。

一、RSA加密前置知识

在理解加密过程前，需要掌握几个关键概念：

1. 非对称加密：使用公钥加密、私钥解密，公钥可公开，私钥需保密
2. 模运算：即求余运算，如 13 mod 5 = 3
3. 欧拉函数φ(n)：表示小于n且与n互质的正整数个数

二、RSA密钥生成（加密的前提）

加密前必须先生成密钥对，过程如下：

1. 选择两个大质数

   • 随机选择两个大质数p和q（通常为1024位或更长）
   • 示例：p = 61, q = 53（为简化说明使用小质数）

2. 计算模数n

   • n = p × q
   • 示例：n = 61 × 53 = 3233

3. 计算欧拉函数φ(n)

   • φ(n) = (p-1) × (q-1)
   • 示例：φ(3233) = 60 × 52 = 3120

4. 选择公钥指数e

   • e需满足：1 < e < φ(n) 且 e与φ(n)互质
   • 通常选择e = 65537（0x10001），这是安全且高效的选择
   • 示例：选择e = 17

5. 计算私钥指数d

   • d是e关于模φ(n)的模逆元，即满足：d × e ≡ 1 mod φ(n)
   • 示例：d = 2753（因为2753 × 17 = 46801，46801 mod 3120 = 1）

至此得到：

• 公钥：(e, n) = (17, 3233)
• 私钥：(d, n) = (2753, 3233)

三、RSA加密过程详解

假设要加密的明文消息为M，加密过程如下：

1. 明文准备

   • 将明文转换为整数M，满足 0 ≤ M < n
   • 如果明文较长，需要分块处理
   • 示例：要加密消息"M = 65"

2. 加密计算

   • 使用公钥(e, n)进行加密
   • 密文C = M^e mod n
   • 即：明文的e次方除以n的余数

3. 计算示例

   • 已知：M = 65, e = 17, n = 3233
   • 计算：C = 65¹⁷ mod 3233

   逐步计算：

   • 65² = 4225 → 4225 mod 3233 = 992
   • 65⁴ = (65²)² = 992² = 984064 → 984064 mod 3233 = 2050
   • 65⁸ = (65⁴)² = 2050² = 4202500 → 4202500 mod 3233 = 2337
   • 65¹⁶ = (65⁸)² = 2337² = 5461569 → 5461569 mod 3233 = 1739
   • 65¹⁷ = 65¹⁶ × 65 = 1739 × 65 = 113035 → 113035 mod 3233 = 2790

   最终得到密文：C = 2790

四、RSA解密的数学验证

为验证加密正确性，我们进行解密：

• 使用私钥(d, n) = (2753, 3233)
• 解密计算：M' = C^d mod n = 2790²⁷⁵³ mod 3233
• 通过模幂运算可得：M' = 65，与原始明文一致

五、RSA加密的重要特性

1. 确定性加密：相同明文和公钥总是产生相同密文
2. 乘法同态：Enc(M₁) × Enc(M₂) = Enc(M₁ × M₂) mod n
3. 安全性依赖：大整数分解问题的困难性

六、实际应用中的注意事项

1. 填充方案：实际使用中需要添加随机填充（如OAEP）防止攻击
2. 密钥长度：当前推荐使用至少2048位的n
3. 性能考虑：RSA加密较慢，通常用于加密对称密钥

通过以上步骤，我们完整地理解了RSA加密算法的数学原理和具体计算过程。这种基于数论难题的设计使其成为目前最广泛使用的公钥加密算法之一。