RSA 算法介绍 – wiki大全

作者： /

RSA 算法介绍：现代密码学的基石

RSA 算法是 Rivest、Shamir 和 Adleman 三位科学家于 1977 年共同提出的一种公钥密码体制。它不仅是现代密码学中最重要、应用最广泛的算法之一，更是数字签名、密钥交换和数据加密等多种安全机制的核心。理解 RSA，就是理解了公钥密码学的基础原理。

一、公钥密码学的概念

在深入 RSA 之前，我们首先要理解“公钥密码学”（或称“非对称加密”）的概念。

传统的对称加密（如 AES）使用相同的密钥进行加密和解密。这意味着通信双方必须共享同一个秘密密钥，这在密钥分发时带来了挑战（如何安全地将密钥传递给对方？）。

公钥密码学解决了这个问题。它为每位用户生成一对密钥：
1. 公钥 (Public Key)：可以公开给任何人。
2. 私钥 (Private Key)：必须严格保密，只有所有者知道。

这对密钥具有以下特性：
* 用公钥加密的数据，只能用对应的私钥解密。
* 用私钥加密的数据（用于数字签名），只能用对应的公钥解密。

RSA 算法正是构建在这一伟大思想之上。

二、RSA 算法的数学基础

RSA 的安全性主要基于一个重要的数论难题：大整数分解的困难性。即给定一个非常大的合数（两个大素数的乘积），很难在合理的时间内将其分解成两个素因子。

RSA 算法涉及到的主要数学概念包括：
* 素数 (Prime Numbers)：只能被 1 和自身整除的正整数（如 2, 3, 5, 7…）。
* 互质关系 (Coprime)：如果两个整数的最大公约数是 1，则称它们互质。
* 模运算 (Modulo Operation)：取余数操作。
* 欧拉函数 φ(n) (Euler’s Totient Function)：小于或等于 n 的正整数中与 n 互质的数的数目。如果 n 是两个素数 p 和 q 的乘积，那么 φ(n) = (p-1)(q-1)。
* 模反元素 (Modular Multiplicative Inverse)：如果 (a * x) mod n = 1，那么 x 是 a 模 n 的模反元素。

三、RSA 算法的详细步骤

RSA 算法分为三个主要部分：密钥生成、加密和解密。

1. 密钥生成 (Key Generation)

这是 RSA 算法最核心的部分，每位用户需要独立生成自己的公钥和私钥对。

  1. 选择两个大素数 (p 和 q)：

    • 随机选择两个非常大且不同的素数 p 和 q。为了保证安全性，这两个素数通常需要有数百位二进制（例如，各 1024 比特）。
    • 选择时应避免 p 和 q 过于接近，否则容易被分解。

  2. 计算模数 n (Modulus n)：

    • 计算 n = p * q。
    • n 是公钥和私钥的一部分，其长度决定了 RSA 的强度（例如，2048 位或 4096 位）。

  3. 计算欧拉函数 φ(n) (Euler’s Totient Function)：

    • 计算 φ(n) = (p – 1) * (q – 1)。
    • φ(n) 在后续步骤中用于生成私钥，但不会作为公钥的一部分公开。

  4. 选择公钥指数 e (Public Exponent e)：

    • 选择一个整数 e，使其满足 1 < e < φ(n)，并且 e 与 φ(n) 互质。
    • 通常选择较小的素数，如 3, 17 或 65537。选择 65537 是为了提高加密和验证的速度，因为其二进制表示中有较少的 1。

  5. 计算私钥指数 d (Private Exponent d)：

    • 计算 d，使其满足 (d * e) mod φ(n) = 1。
    • 换句话说，d 是 e 模 φ(n) 的模反元素。可以使用扩展欧几里得算法来计算 d。

至此，密钥生成完成：
* 公钥 (Public Key)：由 (n, e) 组成，可以公之于众。
* 私钥 (Private Key)：由 (n, d) 组成，必须严格保密。
* （有时私钥也会包含 p, q, φ(n) 等信息，以方便加速解密过程，但这只是实现细节）。

2. 加密 (Encryption)

假设发送方 A 想要向接收方 B 发送消息 M，并且只有 B 能够解密。A 需要使用 B 的公钥 (n_B, e_B) 进行加密。

  1. 将明文消息 M 转换为整数：

    • M 必须是一个小于 n_B 的整数。如果消息过长，需要分块处理。
    • 实际应用中，通常是对消息的哈希值或对称密钥进行 RSA 加密，而不是直接加密原始消息。

  2. 计算密文 C：

    • 使用 B 的公钥 (n_B, e_B) 计算密文 C：
      C = M^e_B mod n_B

  3. 发送密文：

    • 发送方 A 将密文 C 发送给接收方 B。

3. 解密 (Decryption)

接收方 B 收到密文 C 后，使用自己的私钥 (n_B, d_B) 进行解密。

  1. 计算明文 M：

    • 使用 B 的私钥 (n_B, d_B) 计算原始明文 M：
      M = C^d_B mod n_B

  2. 将整数 M 转换回原始消息格式。

四、数字签名 (Digital Signatures)

除了加密，RSA 还可以用于创建数字签名，以验证消息的完整性和发送者的身份（不可否认性）。

  1. 签名过程：

    • 发送方 A 对消息 M 计算哈希值 H = Hash(M)。
    • A 使用自己的私钥 (n_A, d_A) 对哈希值 H 进行“加密”（实际上是签名）：
      S = H^d_A mod n_A
    • A 将消息 M 和数字签名 S 一起发送给接收方 B。

  2. 验证过程：

    • 接收方 B 收到消息 M 和签名 S。
    • B 使用发送方 A 的公钥 (n_A, e_A) 对签名 S 进行“解密”（实际上是验证）：
      H' = S^e_A mod n_A
    • B 独立计算收到的消息 M 的哈希值 H = Hash(M)。
    • B 比较 H’ 和 H。如果 H’ = H，则签名有效，表示消息 M 未被篡改，且确实是由拥有 A 私钥的人发送的。

五、RSA 的安全性与应用

安全性：
RSA 的安全性依赖于大整数分解的难度。目前，还没有有效的算法能够快速分解极大的合数。随着计算能力的提升，推荐的 RSA 密钥长度也在不断增加，目前 2048 位或 4096 位的 RSA 密钥被认为是安全的。量子计算的出现对 RSA 构成潜在威胁，因为它可能能够高效地分解大整数，但目前尚未商业化应用。

应用场景：
RSA 算法因其公钥特性，在现代网络安全中扮演着不可替代的角色：
* HTTPS/SSL/TLS：用于在客户端和服务器之间建立加密连接时，交换对称加密密钥。
* 数字证书：用于验证网站、软件和其他实体的身份。
* 电子邮件加密：如 PGP (Pretty Good Privacy) 中使用 RSA 加密会话密钥。
* VPN：用于安全通信。
* 代码签名：验证软件的完整性和来源。

六、总结

RSA 算法是公钥密码学领域的一项里程碑式发明，它巧妙地利用了数论中的非对称特性，实现了在不共享秘密密钥的情况下进行安全通信和身份验证。尽管其计算开销相对较大，不适合直接加密大量数据，但通过与对称加密算法的结合（用 RSA 交换对称密钥，然后用对称密钥加密数据），它构成了当今互联网安全基础设施的基石。理解 RSA 不仅是学习密码学的重要一步，也是理解现代信息安全运作方式的关键。

滚动至顶部