RSA加密算法

一、RSA算法概述

RSA（Rivest-Shamir-Adleman）是首个实用的非对称加密算法，基于 大数分解难题 的非对称加密，核心是生成公钥（加密）和私钥（解密）的数学关系。
主要步骤如下：

1. 密钥生成
2. 加密过程
3. 解密过程

图1：RSA算法示意图

---

二、数学基础

• 模运算：若 a ≡ b mod n，则 a 和 b 在模 n 下同余
• 欧拉定理：若 a 与 n 互质（即 gcd(a, n) = 1）， a^T(n) ≡ 1 mod n

其中，T(n) 是欧拉函数，表示小于 n 且与 n 互质的正整数的个数。

• 欧拉函数：若 n = p × q，且 p 和 q 为质数，则：T(n)=(p−1)(q−1)

三、RSA算法详细步骤

1. 密钥生成

步骤分解

1. 选择大质数

   • 随机选取两个不相等的大质数 p 和 q（实际使用至少1024位）
   • 示例：p = 61，q = 53。

2. 计算模数n

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

3. 计算欧拉函数值T(n)

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

4. 选择公钥指数

   选择一个整数e，满足：

   • 1 < e < T
   • e 与 T互质
     可得公钥对 KU = (n,e)
     示例：选 e = 17。公钥：(n, e) = (3233, 17)

5. 计算私钥指数

   • d 是 e 关于模T(n)的模反元素，即 （d × e）% n = 1，可通过扩展欧几里得算法求解。
     可得私钥对 KR = (n,d)
     示例：d = 2753（17 × 2753 = 46801 ≡ 1 mod 3120）,私钥：(n, d) = (3233, 2753)

最终密钥

• 公钥：KU = (n,e)
• 私钥：KR = (n,d)

2. 加密过程

对明文 M（需满足 M < n），计算密文 C = M^e mod n
示例：明文 M = 65，则 C = 65¹⁷ mod 3233 = 2790

3. 解密过程

对密文C，计算明文 M = C^d mod n
示例：M = 2790²⁷⁵³ mod 3233 = 65

优缺点

特性	对称加密
安全性高（依赖数学难题）	计算慢，适合小数据
支持加密和数字签名	密钥长（2048位以上）
标准化程度高（广泛应用）	量子计算机威胁显著

应用场景

1. HTTPS/TLS：

• 用于协商对称密钥（如AES密钥），后续通信使用对称加密。

2. 数字签名：

• 私钥签名：签名 = H(M)^d mod n（H为哈希函数）。
• 公钥验证：检查 签名^e mod n 是否等于 H(M)。
• 软件发布（验证作者身份）、电子邮件（PGP）、区块链交易签名。

3. 加密小数据：

• 加密对称密钥、密码传输等。

示例代码（Python）

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 生成密钥对
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

# 加密
cipher = PKCS1_OAEP.new(RSA.import_key(public_key))
ciphertext = cipher.encrypt(b"Hello, RSA!")

# 解密
cipher = PKCS1_OAEP.new(RSA.import_key(private_key))
plaintext = cipher.decrypt(ciphertext)
print(plaintext.decode())  # 输出: Hello, RSA!

RSA作为非对称加密的基石，尽管面临量子计算的挑战，但在可预见的未来仍将是数字安全的核心工具之一。实际应用中，常与对称加密（如AES）结合，形成兼顾安全与效率的混合加密系统。