math - RSA - p 和 q 的位长

Question

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

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

感谢您的澄清

抢

Answer 1

对于 32 位模数，这个问题有点学术性:您选择 p 的主要目的是和 q是使乘积难以分解，但找到小于 2^32 的数的质因数分解太简单了，不用担心 p 的大小和 q在这种情况下。请注意，只要 p 数学运算就可以正常工作。和 q是不同的素数。

对于更现实的东西，例如 1024 位模数，那么是的，您可以非常安全地选择两个 512 位素数 p和 q随机:即选择p和 q从 [2^511, 2^512] 范围内的所有素数的集合中统一.有一个“strong primes”的概念'，这是旨在避免特定可能的已知攻击的素数——例如，您会看到建议 p和 q应该选择这样p-1和 q-1有大因子，以防止使用 Pollard's 'p-1' algorithm 进行简单的因式分解.但是，这些建议并不真正适用于大型模数和最先进的分解算法( GNFS 、 ECM )。理论上还有其他可能的情况可以进行简单的因式分解，但实际上它们不太可能从 p 的随机选择中出现。和 q他们不值得担心。

总结:只需选择两个位长相等的随机素数，就大功告成了。

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

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

不要刻意选择p和 q以便它们彼此靠近:如果 p和 q彼此真正接近(例如，相距小于 10^10)，那么它们的乘积 pq很容易被 Fermat's method 分解.但是如果你选择随机素数 p和 q在 [2^511, 2^512] 范围内，这不会以任何现实的概率发生。

随机选择素数时，一个诱人的策略是在 [2^511, 2^512] 范围内选择一个随机(奇数)整数。然后增加它直到找到第一个素数。但请注意，这并没有在所有质数中给出统一的选择:在大间隙之后出现的质数比其他质数更有可能出现。一个更好的策略是继续选择随机奇数并保留第一个是质数(或者更有可能是许多随机选择的碱基的强可能质数，您可以在实践中确定它是质数)。

确保你手头有一个非常好的随机数加密源来生成素数。