5

我只是想了解 RSA 的密钥生成部分，更具体地说，是选择 p 和 q 素数。给定模数 n 的目标位长度，我应该在什么范围内生成 p 和 q？

模数 n 是 p 和 q 的乘积，其中 p 和 q 都是素数。我读过 p 和 q 应该相对接近，并且在 sqrt(n) 附近。例如，如果目标位长度是 32 位（我意识到非常小），那么是否遵循 p 和 q 应该是最大 16 位的随机素数？

感谢您的任何澄清

抢

4

1 回答 1

16

对于 32 位模数，这个问题有点学术性：您选择的主要目标p是q使乘积难以因式分解，但是找到小于 的数的素数分解2^32非常容易，因此不必担心在这种情况下p。q请注意，只要p和q是不同的素数，数学就可以正常工作。

对于更现实的东西，比如 1024 位模数，那么是的，你可以非常安全地随机选择两个 512 位素数p：q也就是说，从范围内的所有素数集中均匀地选择p和。有一个“强素数”的概念，它是旨在避免特定可能的已知攻击的素数——例如，您会看到建议并且应该选择这样并且具有较大的因数，以防止使用Pollard 的简单因式分解。 p-1'算法。然而，这些建议并不真正适用于大模数和最先进的分解算法（GNFS、ECMq[2^511, 2^512]pqp-1q-1）。还有其他可能的情况在理论上可以提供简单的因式分解，但它们在实践中不太可能从随机选择中出现p，q因此不值得担心。

摘要：只需选择两个位长相等的随机素数，就完成了。

一些额外的评论和需要考虑的事情：

  1. 当然，如果您确实选择了两个 512 位素数，您最终会得到一个1023 位或一个 1024 位模数；这可能不值得担心，但如果你真的很想得到一个 1024 位模数，你可以限制范围p甚至q更远，比如[1.5 * 2^511, 2^512]，或者只是扔掉任何 1023 位模数，然后再试一次。

  2. 不要刻意选择pandq使它们彼此靠近：如果p和q确实彼此靠近（例如，小于10^10分开，例如），那么它们的乘积很容易被费马方法pq分解。但是，如果您选择随机素数并且在 range 内，这不会以任何现实概率发生。pq[2^511, 2^512]

  3. 当随机选择一个素数时，一个诱人的策略是在范围内选择一个随机（奇数）整数，[2^511, 2^512]然后递增它直到找到第一个素数。但请注意，这并不能在所有素数中给出统一的选择：在大间隙之后出现的素数比其他素数更有可能出现。一个更好的策略是继续选择随机奇数并保留第一个素数（或者更有可能，对于这么多随机选择的基数来说是一个强可能素数，你可以在实践中确定它是素数）。

  4. 确保您手头有一个非常好的随机数加密源，用于生成素数。

于 2012-08-30T11:23:40.543 回答