密码学/RSA

RSA 是一种非对称的公钥密码学算法，广泛应用于电子商务。该算法由罗恩·里维斯特、阿迪·萨莫尔和伦纳德·阿德曼在 1977 年描述；RSA 这三个字母分别代表他们姓氏的首字母。

克利福德·考克斯，一位在英国政府通信总部工作的英国数学家，在 1973 年的一份内部文件中描述了等效系统。然而，由于其最高机密分类，他的发现直到 1997 年才公布。

RSA 系统的安全性依赖于 对非常大的整数进行因式分解 的难度。该领域的新型快速算法可能会使 RSA 不安全，但这通常被认为不太可能发生。

该算法于 1983 年在美国由麻省理工学院获得专利。专利于 2000 年 9 月 21 日到期。由于该算法在专利申请之前已经公布，因此它无法在其他国家获得专利。

操作

密钥生成

假设用户 Alice 希望允许 Bob 通过不安全的传输介质向她发送私密消息。她需要执行以下步骤来生成一个公钥和一个私钥

1. 随机选择两个大的质数 p ≠ q，并且彼此独立。计算 N = p q。
2. 选择一个整数 1 < e < N，该整数与 (p-1)(q-1) 互质。
3. 计算 d 使得 d e ≡ 1 (mod (p-1)(q-1))。
4. 销毁所有关于 p 和 q 的记录。

• (步骤 2 和 3 可以使用扩展欧几里得算法执行；请参阅模运算。此外，可以使用丢番图方程 $ed-k\phi (n)=1$ 来求解 e 或 d 的值。)

N 和 e 是公钥，而 N 和 d 是私钥。请注意，只有 d 是秘密，因为 N 是公开的。Alice 将公钥发送给 Bob，并保密私钥。

您可以使用 OpenSSL 和一些 Unix 工具来生成和检查真实的 RSA 密钥对。（密码学/使用 OpenSSL 生成密钥对）。

加密消息

假设 Bob 希望向 Alice 发送消息 m。他知道 Alice 公开的 N 和 e。他使用一些预先商定的可逆协议将 m 转换为一个数字 n < N。例如，明文消息中的每个字符都可以转换为其 ASCII 码，并将这些码连接成一个数字。如果需要，他可以将 m 分成几段，并分别加密每段。然后，他计算密文 c

$c\equiv n^{e}\ (\mathrm {mod} \ N)$

这可以通过 平方求幂 的方法快速完成。然后 Bob 将 c 传输给 Alice。

解密消息

Alice 从 Bob 处收到 c，并知道她的私钥 d。她可以通过以下程序从 c 中恢复 n

$c^{d}\equiv n\ (\mathrm {mod} \ N)$

然后，Alice 可以提取 n，因为 n < N。有了 n，她就可以恢复原始消息 m。

解密过程有效是因为

$c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)$

并且 ed ≡ 1 (mod p-1) 以及 ed ≡ 1 (mod q-1)。费马小定理得出

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ p)$     以及     $n^{e\cdot d}\equiv n\ (\mathrm {mod} \ q)$

这意味着（因为 p 和 q 是不同的质数）

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ pq)$

签名消息

RSA 也可以用于签名消息。假设 Alice 希望向 Bob 发送签名消息。她生成消息的哈希值，用她的私钥加密它，并将它作为“签名”附加到消息中。该签名只能用她的公钥解密。当 Bob 收到签名消息时，他用 Alice 的公钥解密签名，并将生成的哈希值与消息的实际哈希值进行比较。如果两者一致，他知道消息的作者拥有 Alice 的私钥，并且消息自签名后未被篡改。

安全

假设窃听者 Eve 拦截了公钥 N 和 e，以及密文 c。但是，她无法直接获得 Alice 保密的 d。Eve 从 c 中推断出 n 的最明显方法是将 N 分解成 p 和 q，以便计算 (p-1)(q-1)，从而从 e 中确定 d。目前尚未发现经典计算机上用于分解大整数的多项式时间方法，但也没有证明不存在此类方法。有关此问题的讨论，请参见整数分解。

尚未证明分解 N 是从 c 推断出 n 的唯一方法，但尚未发现更简单的方法（至少公开知识中没有）。

因此，通常假定如果 N 足够大，Eve 就会在实践中失败。

如果 N 为 256 位或更短，可以使用现有的免费软件在个人计算机上用几小时时间分解。如果 N 为 512 位或更短，截至 1999 年，它可以被数百台计算机分解。目前建议 N 的长度至少为 1024 位。

1993 年，Peter Shor 证明了量子计算机原则上可以以多项式时间执行分解。如果（或当）量子计算机成为一种实用技术时，Shor 算法将使 RSA 及其相关算法过时。

如果发现高效的经典分解代码或构建了实用的量子计算机，则使用更大的密钥长度可以提供一种权宜措施。但是，RSA 中的任何此类安全漏洞显然是追溯性的。窃听者可以记录公钥和使用该公钥生成的任何密文（只需记录到该公钥所有者的流量即可轻松找到），然后只需等待此类突破。然后将该密文解密为明文消息。因此，使用 RSA 或任何具有类似漏洞的密码交换长期秘密从本质上讲是不安全的。

实际考虑因素

密钥生成

找到大的素数 p 和 q 通常是通过使用概率素性测试对正确大小的随机数进行测试来完成的，这种测试可以快速排除大多数非素数。如果这种测试发现了一个“可能的素数”，那么应该使用确定性测试来验证该数确实是素数。

p 和 q 不应该“太接近”，以免费马分解对 N 成功。此外，如果 p-1 或 q-1 只有小的素数因子，则 N 可以快速分解，因此应丢弃这些 p 或 q 值。

不应采用任何向攻击者提供有关素数信息的素数搜索方法。特别是，需要使用一个良好的随机数生成器作为起始值。请注意，这里要求既是“随机”又是“不可预测”。这些不是相同的标准；一个数字可能是通过随机过程选择的（即结果没有模式），但如果它以任何方式（甚至部分可预测）是可预测的，则使用的方法将导致安全性的丧失。例如，兰德公司在 1950 年代出版的随机数表可能非常随机，但它已经出版，因此也可以作为攻击者的工具。如果攻击者可以猜出 p 或 q 的一半数字，他们可以快速计算出另一半（由 Coppersmith 在 1997 年证明）。

密钥 d 必须足够大。Wiener 在 1990 年证明，如果 p 在 q 和 2q 之间（这是相当典型的）并且 d < N^1/4/3，那么 d 可以从 N 和 e 中有效地计算出来。加密密钥 e = 2 也不应该使用。

速度

RSA 比 DES 和其他对称密码系统慢得多。在实践中，Bob 通常会使用对称算法加密秘密消息，使用 RSA 加密（相对较短的）对称密钥，并将 RSA 加密的对称密钥和对称加密的消息都传输给 Alice。

此过程引发了额外的安全问题。例如，使用强大的随机数生成器生成对称密钥至关重要，因为否则 Eve 可以通过猜测对称密钥来绕过 RSA。

密钥分发

与所有密码一样，RSA 公钥的分发方式很重要。密钥分发必须确保防范中间人攻击。假设 Eve 能够以某种方式向 Bob 提供任意密钥，并让他相信这些密钥属于 Alice。假设 Eve 还能够拦截 Alice 和 Bob 之间的传输。Eve 向 Bob 发送她自己的公钥，Bob 认为这是 Alice 的公钥。然后，Eve 可以拦截 Bob 发送的任何密文，使用她自己的私钥解密，保留消息副本，使用 Alice 的公钥加密消息，并将新的密文发送给 Alice。原则上，Alice 和 Bob 都无法检测到 Eve 的存在。针对此类攻击的防御措施通常基于数字证书或公钥基础设施的其他组件。

计时攻击

Kocher 在 1995 年描述了一种巧妙的、出乎意料的针对 RSA 的新攻击：如果攻击者 Eve 知道 Alice 的硬件并且能够测量多个已知密文的解密时间，她可以快速推断出解密密钥 d。为了阻止这种攻击，解密代码应以恒定时间解密。这被称为RSA 盲化。

自适应选择密文攻击

1998 年，Daniel Bleichenbacher 描述了第一次针对使用 PKCS #1 v1 冗余函数的 RSA 加密消息的实用自适应选择密文攻击（冗余函数向 RSA 加密消息添加结构，因此可以确定解密的消息是否有效）。由于 PKCS #1 方案存在缺陷，Bleichenbacher 能够对安全套接字层协议的 RSA 实现发起实际攻击，并可能泄露会话密钥。由于这项工作，密码学家现在建议使用可证明安全的冗余检查，例如最佳非对称加密填充，RSA 实验室发布了不受这些攻击影响的 PKCS #1 新版本。