public-key-encryption - 整数分解和密码学

Question

我知道公钥密码学使用质数，
还知道两个大(例如 100 位)质数 (P, Q) 用作私钥，
乘积是公钥 N = P * Q，
并且使用素数是因为 N 的因式分解来获得 P 、 Q 太困难并且需要很多时间，
我没问题，但我很困惑
为什么不直接对 P , Q 使用任何普通的大非质数
所以 N 的因式分解仍然很困难
因为会因为现在，不仅有 2 个可能的因素，而且可能更多。

谢谢....

Answer 1

我不是加密专家。

why not just use any ordinary large non-prime numbers for P , Q

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

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

N = P * Q

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

然而!
如果 P 和 Q 都共享因子 2

N/4 = P/2 * Q/2

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

这意味着我可以找到 P,Q S.T. 的标量倍数 P', Q'。 P',Q' < P,Q

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

您必须搜索更小的空间，直到您暴力破解 key 。