4

我知道公钥密码学使用素数，也知道使用两个大（例如100位）素数（P，Q）作为私钥，乘积是公钥N = P * Q，并使用素数是因为 N 的因式分解来获得 P ， Q 非常困难并且需要很多时间，我可以接受，但我很困惑为什么不使用任何普通的大非素数来 P ， Q 等等分解N 仍然很困难，因为现在，不仅有 2 个可能的因素，而且还有更多。

谢谢....

4

3 回答 3

2

我不是加密专家。

为什么不对 P ， Q 使用任何普通的大非素数

因为会有更多的因素。整数分解是对公钥加密的一种攻击。这种攻击利用了这种关系。

人们可以更容易地找到具有更多共同因素的关系和可能的值。它归结为代数。

N = P * Q

如果 P 和 Q 都是素数，则 N 有 4 个因数 {NPQ 1}

然而！如果 P 和 Q 都共享一个因子 2

N / 4 = P / 2 * Q / 2

如果 N 本来可以是 0..2^4096，那么现在是 0..2^4094，因为 2 是一个因素，另一个大数也是一个因素。

这意味着我可以找到 P,Q ST P',Q' < P,Q 的标量倍数 P', Q'

我自己并不完全理解这个概念，但我相信这表明了我的目标。

您必须搜索较小的空间，直到您暴力破解密钥。

于 2010-12-19T01:12:43.220 回答
2

完全有可能使用模数 N 的 RSA，该模数 N 由两个以上的质因数 P 和 Q 组成，但必须注意两点：

  1. 您必须知道所有这些因素的确切值，否则您将无法在生成密钥时从公钥中导出私钥。二素数 RSA 的等式是 1 = D*E (mod LCM(P-1,Q-1))。如果您确实知道这些主要因素，则可以执行计算。如果您不知道您无法执行此计算的主要因素，顺便说一句，这就是为什么公开公钥 E，N 是安全的 - 如果您只有以下信息，您就无法导出私钥 D很容易从公钥导出，除非您能够分解 N。

  2. RSA 的安全性实际上受到 RSA 模数 N 的第二大素因数的大小的限制。在现代计算机上，只需尝试一下，就可以在几分之一秒内找到小于 2^32 的小素因数将模数 N 除以每个这样的素数，并检查余数是否为零（意味着 N 可被该数整除）或不是（意味着该数不是 N 的因数）。如果 N 仅由这样小的素因数乘以单个大素因数 Q 组成，那么找到 Q 也是微不足道的，只需将 N 除以所有小因数即可得到 N' 并测试 N' 的素数。如果 N' 是素数，则它是最后一个素数因子 Q。

于 2012-02-08T14:59:04.830 回答
0

我不是真正的密码学专家（所以如果我错了，请在评论中告诉我，我会立即删除这个答案），但我认为这是因为如果你只使用随机大数，你可能会很容易地因式分解（即，您不必达到非常大的质数来获得它们的质因数）。所以只使用了非常大的保证素数。

于 2010-12-19T01:00:38.787 回答