RSA 加密算法详解：原理、实现与应用

RSA 是 1977 年由 Ron Rivest、Adi Shamir 和 Leonard Adleman 三位数学家共同提出的公钥密码算法，是迄今为止理论上最为成熟完善的非对称加密算法。RSA 基于大整数素数分解的数学难题，其安全性依赖于大数分解的计算困难性。作为公钥密码学的基石，RSA 被广泛应用于数字签名、密钥交换、安全通信等领域。本文将从数学原理出发，深入剖析 RSA 算法的核心机制。

一、RSA 概述

RSA 是第一个既能用于数据加密也能用于数字签名的算法，它的命名来源于三位发明者的姓氏首字母。

核心特点

RSA 作为非对称加密算法的代表，具有以下显著特点：1）公钥加密，私钥解密；2）私钥签名，公钥验签；3）密钥分发简单，无需安全通道；4）安全性基于数学难题。

二、数学原理

RSA 算法的安全性建立在数论中几个经典难题之上，理解这些数学基础是掌握 RSA 的关键。

2.1 大素数分解问题

大素数分解问题是 RSA 安全性的核心。该问题可以表述为：给定两个大素数 p 和 q，计算它们的乘积 n = p × q 是很容易的；但反过来，已知 n 求 p 和 q 则被认为是非常困难的。这就是所谓的「单向函数」特性。目前最快的大数分解算法（如数域筛法）的时间复杂度仍然是亚指数级的，对于足够大的素数（如 2048 位以上），在合理时间内分解是不可行的。

2.2 欧拉函数

欧拉函数 φ(n) 表示小于 n 且与 n 互质的正整数的个数。对于素数 p，φ(p) = p - 1。对于两个不同素数的乘积 n = p × q，有 φ(n) = φ(p) × φ(q) = (p-1)(q-1)。这个性质在 RSA 密钥生成中起着至关重要的作用。

2.3 模幂运算

模幂运算是 RSA 加密和解密的核心操作，即计算 a^b mod n。直接计算 a^b 会产生天文数字，但通过模运算的性质和快速幂算法（平方-乘算法），可以高效地计算结果。模幂运算的性质保证了 RSA 的加密和解密操作在计算上是可行的。

2.4 费马-欧拉定理

费马小定理是欧拉定理的特例，它指出：如果 p 是素数，a 是不被 p 整除的整数，则 a^(p-1) ≡ 1 (mod p)。欧拉定理将其推广为：若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n)。这个定理是 RSA 加密解密正确性的数学基础。

三、密钥生成过程

RSA 密钥生成是整个算法的起点，其过程涉及素数生成、参数计算等步骤。

生成步骤

1. 选择大素数：随机选择两个不同的大素数 p 和 q，它们的位数相近但不相等
2. 计算模数 n：计算 n = p × q，n 的二进制位数即为密钥长度（如 2048 位）
3. 计算欧拉函数：计算 φ(n) = (p-1)(q-1)
4. 选择公钥指数 e：选择一个整数 e，满足 1 < e < φ(n)，且 e 与 φ(n) 互质。通常选择 e = 65537 (0x10001)
5. 计算私钥指数 d：计算 d，使得 d × e ≡ 1 (mod φ(n))，即 d 是 e 模 φ(n) 的乘法逆元

最终，公钥为 (e, n)，私钥为 (d, n)。p 和 q 必须销毁或严格保密。

简单示例

为了便于理解，我们用小数字演示 RSA 密钥生成（实际应用中使用数百位的大素数）：

// RSA 密钥生成示例（使用小数字，仅用于演示）
// 1. 选择两个素数
const p = 61;
const q = 53;

// 2. 计算 n = p * q
const n = p * q; // n = 3233

// 3. 计算 φ(n) = (p-1)(q-1)
const phi = (p - 1) * (q - 1); // phi = 60 * 52 = 3120

// 4. 选择公钥指数 e（通常为 65537，这里用小数值）
const e = 17; // 1 < 17 < 3120，且 17 与 3120 互质

// 5. 计算私钥 d = e^(-1) mod phi
// 使用扩展欧几里得算法计算
function modInverse(a, m) {
  let m0 = m;
  let y = 0, x = 1;
  if (m === 1) return 0;
  while (a > 1) {
    let q = Math.floor(a / m);
    let t = m;
    m = a % m;
    a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}

const d = modInverse(e, phi); // d = 2753

console.log('公钥 (e, n):', e, n);  // (17, 3233)
console.log('私钥 (d, n):', d, n);  // (2753, 3233)

// 加密: c = m^e mod n
// 解密: m = c^d mod n
const plaintext = 65; // 'A' 的 ASCII 码
const ciphertext = BigInt(plaintext) ** BigInt(e) % BigInt(n);
console.log('明文:', plaintext);
console.log('密文:', ciphertext.toString());

const decrypted = BigInt(ciphertext) ** BigInt(d) % BigInt(n);
console.log('解密后:', decrypted.toString());

四、加密解密原理

RSA 的加密和解密操作都基于模幂运算，其正确性由欧拉定理保证。

4.1 加密过程

发送方使用接收方的公钥 (e, n) 对明文 m 进行加密。明文 m 必须满足 0 ≤ m < n。加密公式为：c = m^e mod n，其中 c 为密文。

4.2 解密过程

接收方使用自己的私钥 (d, n) 对密文 c 进行解密。解密公式为：m = c^d mod n。根据欧拉定理，可以证明该解密过程能够正确还原明文。

4.3 正确性证明

RSA 解密正确性的核心证明：因为 c = m^e mod n，所以 c^d = m^(ed) mod n。又因为 ed ≡ 1 (mod φ(n))，所以 ed = kφ(n) + 1。因此 m^(ed) = m^(kφ(n)+1) = m × (m^φ(n))^k。根据欧拉定理，m^φ(n) ≡ 1 (mod n)，所以 (m^φ(n))^k ≡ 1^k = 1 (mod n)。因此 m^(ed) ≡ m × 1 = m (mod n)，即 c^d ≡ m (mod n)。

RSA 加密解密（Node.js 示例）

const crypto = require('crypto');

// 生成 RSA 密钥对
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
  publicExponent: 65537,
  publicKeyEncoding: {
    type: 'spki',
    format: 'pem'
  },
  privateKeyEncoding: {
    type: 'pkcs8',
    format: 'pem'
  }
});

console.log('公钥:', publicKey);
console.log('私钥:', privateKey);

// 加密数据
const plaintext = 'Hello, RSA!';
const encrypted = crypto.publicEncrypt(
  {
    key: publicKey,
    padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
    oaepHash: 'sha256'
  },
  Buffer.from(plaintext)
);

console.log('密文:', encrypted.toString('base64'));

// 解密数据
const decrypted = crypto.privateDecrypt(
  {
    key: privateKey,
    padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
    oaepHash: 'sha256'
  },
  encrypted
);

console.log('解密后:', decrypted.toString());

五、数字签名

RSA 不仅可用于加密，还可用于数字签名，这是其最重要的应用之一。

5.1 签名原理

数字签名的过程与加密相反：签名者使用自己的私钥对消息摘要进行签名，验证者使用签名者的公钥进行验证。签名公式为：s = m^d mod n，其中 m 是消息摘要，s 是签名。验签公式为：m' = s^e mod n。如果 m' = m，则签名有效。

5.2 签名流程

1. 消息摘要：使用哈希算法（如 SHA-256）对原始消息计算摘要
2. 私钥签名：使用签名者的私钥对摘要进行签名运算
3. 发送消息：将原始消息和签名一起发送给接收方
4. 验签：接收方使用公钥验证签名的有效性
5. 摘要比对：比对恢复的摘要与计算的摘要是否一致

5.3 安全性保障

数字签名提供了三重安全保障：1）身份认证：确认消息确实来自声称的发送者；2）完整性：确保消息在传输过程中未被篡改；3）不可否认性：发送者无法否认发送过该消息。

RSA 数字签名（Node.js 示例）

const crypto = require('crypto');

// 生成 RSA 密钥对
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
  publicExponent: 65537,
  publicKeyEncoding: { type: 'spki', format: 'pem' },
  privateKeyEncoding: { type: 'pkcs8', format: 'pem' }
});

// 原始消息
const message = 'This is an important document.';

// 签名
const sign = crypto.createSign('SHA256');
sign.update(message);
const signature = sign.sign(privateKey, 'base64');

console.log('原始消息:', message);
console.log('签名:', signature);

// 验签
const verify = crypto.createVerify('SHA256');
verify.update(message);
const isValid = verify.verify(publicKey, signature, 'base64');

console.log('签名是否有效:', isValid);

// 尝试篡改消息
const tamperedMessage = 'This is a tampered document.';
const verifyTampered = crypto.createVerify('SHA256');
verifyTampered.update(tamperedMessage);
const isTamperedValid = verifyTampered.verify(publicKey, signature, 'base64');

console.log('篡改后签名是否有效:', isTamperedValid);

六、应用场景

6.1 TLS/SSL 安全通信

在 HTTPS 协议中，RSA 曾是最主要的密钥交换算法。服务器将公钥放在数字证书中，客户端使用公钥加密随机生成的会话密钥，只有拥有私钥的服务器才能解密，从而建立安全的加密通道。虽然现代 TLS 更倾向于使用 ECDHE 进行前向保密，但 RSA 仍广泛用于服务器身份验证。

6.2 邮件加密与签名

在 S/MIME 和 PGP/GPG 等邮件安全标准中，RSA 用于加密邮件内容和数字签名。发送方使用接收方的公钥加密邮件，确保只有接收方能够解密阅读；同时使用自己的私钥签名，让接收方能够验证邮件来源和完整性。

6.3 代码签名

软件开发者使用 RSA 私钥对发布的软件进行数字签名，用户可以通过公钥验证软件确实来自可信的开发者，且未被篡改。这在防止恶意软件植入和供应链攻击方面起着重要作用。

6.4 区块链与加密货币

虽然大多数现代区块链使用 ECDSA（椭圆曲线数字签名算法），但 RSA 的签名原理与区块链的地址生成和交易签名机制一脉相承。RSA 的公私钥体系为区块链的去中心化身份认证提供了理论基础。

6.5 身份认证与访问控制

在智能卡、USB Key、双因素认证等场景中，RSA 用于身份认证。用户设备中存储私钥，服务器保存公钥，通过挑战-应答机制验证用户身份，无需传输密码，大大提高了安全性。

七、安全性分析

RSA 的安全性依赖于大数分解的困难性，但这并不意味着 RSA 是绝对安全的。

7.1 密钥长度与安全性

RSA 的安全性与密钥长度直接相关。随着计算能力的提升和分解算法的改进，所需的密钥长度也在不断增加：

7.2 常见攻击方式

• 暴力分解攻击：尝试所有可能的素数因子。对于 2048 位以上的密钥，这种方法在计算上不可行
• 计时攻击：通过测量解密运算的时间差异来推断私钥信息。可通过使用恒定时间运算来防御
• 选择密文攻击：攻击者选择特定密文让目标解密，从中获取信息。OAEP 填充方案可有效防御
• 故障注入攻击：通过硬件故障诱导计算错误，从而泄露私钥信息

7.3 填充方案的重要性

直接使用裸 RSA（教科书式 RSA）是不安全的，必须使用安全的填充方案：

RSA-OAEP 加密示例

// 使用 Web Crypto API 进行 RSA-OAEP 加密
async function encryptWithRSA_OAEP(publicKeyPem, plaintext) {
  // 将 PEM 格式的公钥导入
  const publicKey = await window.crypto.subtle.importKey(
    'spki',
    pemToArrayBuffer(publicKeyPem),
    {
      name: 'RSA-OAEP',
      hash: 'SHA-256'
    },
    false,
    ['encrypt']
  );

  // 加密
  const encoder = new TextEncoder();
  const data = encoder.encode(plaintext);
  const encrypted = await window.crypto.subtle.encrypt(
    { name: 'RSA-OAEP' },
    publicKey,
    data
  );

  return arrayBufferToBase64(encrypted);
}

async function decryptWithRSA_OAEP(privateKeyPem, ciphertextBase64) {
  // 将 PEM 格式的私钥导入
  const privateKey = await window.crypto.subtle.importKey(
    'pkcs8',
    pemToArrayBuffer(privateKeyPem),
    {
      name: 'RSA-OAEP',
      hash: 'SHA-256'
    },
    false,
    ['decrypt']
  );

  // 解密
  const encryptedData = base64ToArrayBuffer(ciphertextBase64);
  const decrypted = await window.crypto.subtle.decrypt(
    { name: 'RSA-OAEP' },
    privateKey,
    encryptedData
  );

  const decoder = new TextDecoder();
  return decoder.decode(decrypted);
}

八、与 ECC/SM2 对比

随着椭圆曲线密码学的发展，ECC 和 SM2 正在越来越多的场景中替代 RSA。

算法对比

对比总结

从对比可以看出：1）ECC/SM2 在相同安全级别下密钥更短，计算更快；2）RSA 的优势在于理解简单、实现成熟、兼容性好；3）对于资源受限的设备（如物联网设备），ECC 是更好的选择；4）RSA 仍然广泛应用于遗留系统和对兼容性要求高的场景。

九、实践建议

9.1 密钥长度选择

选择合适的密钥长度是保障 RSA 安全的第一步：

• 短期安全（1-2 年）：2048 位密钥
• 中期安全（3-5 年）：3072 位密钥
• 长期安全（10 年以上）：4096 位密钥
• 高安全需求：考虑使用 ECC 替代 RSA

9.2 填充方案选择

• 加密使用 OAEP 填充，配合 SHA-256 或更高版本哈希
• 签名使用 PSS 填充，配合 SHA-256 或更高版本哈希
• 避免使用 PKCS#1 v1.5 填充方案
• 不要使用裸 RSA（教科书式 RSA）

9.3 实现注意事项

• 使用经过充分验证的密码学库，不要自行实现 RSA
• 确保素数生成的随机性和质量
• 使用恒定时间运算，防御计时攻击
• 妥善保管私钥，考虑使用硬件安全模块（HSM）
• 定期轮换密钥，建立密钥管理体系

Web Crypto API 实现 RSA

// 使用 Web Crypto API 生成 RSA 密钥对并进行签名
async function generateRSAKeyPair() {
  const keyPair = await window.crypto.subtle.generateKey(
    {
      name: 'RSASSA-PKCS1-v1_5',
      modulusLength: 2048,
      publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // 65537
      hash: { name: 'SHA-256' }
    },
    true,
    ['sign', 'verify']
  );

  // 导出公钥
  const publicKey = await window.crypto.subtle.exportKey(
    'spki',
    keyPair.publicKey
  );

  // 导出私钥
  const privateKey = await window.crypto.subtle.exportKey(
    'pkcs8',
    keyPair.privateKey
  );

  return {
    publicKey: arrayBufferToBase64(publicKey),
    privateKey: arrayBufferToBase64(privateKey)
  };
}

async function rsaSign(privateKeyData, message) {
  const privateKey = await window.crypto.subtle.importKey(
    'pkcs8',
    base64ToArrayBuffer(privateKeyData),
    {
      name: 'RSASSA-PKCS1-v1_5',
      hash: { name: 'SHA-256' }
    },
    false,
    ['sign']
  );

  const encoder = new TextEncoder();
  const data = encoder.encode(message);
  
  const signature = await window.crypto.subtle.sign(
    { name: 'RSASSA-PKCS1-v1_5' },
    privateKey,
    data
  );

  return arrayBufferToBase64(signature);
}

十、土豆丝在线工具

如果你想实际体验 RSA 加密解密和数字签名的效果，可以使用我们的在线工具：

十一、总结

RSA 作为公钥密码学的开山之作，其理论基础坚实，应用场景广泛。从数学原理上看，RSA 基于大数分解的困难性，利用模幂运算实现加密解密和数字签名；从应用角度看，RSA 支撑了现代互联网的安全基础设施，从 HTTPS 到数字证书，从邮件加密到代码签名，处处可见其身影。

然而，随着计算技术的发展和量子计算的威胁，RSA 也面临着新的挑战。椭圆曲线密码学（ECC）在同等安全级别下具有更短的密钥和更高的效率，正在逐步成为 RSA 的替代方案。但在可预见的未来，RSA 仍将在众多场景中继续发挥重要作用。理解 RSA 的原理，对于深入掌握现代密码学至关重要。