RSA为什么需要p和q为质数？

#1 楼

但是，即使对于使用已知因数分解算法的计算机，也很难分解大整数。


不是绝对的。如果分解大整数仅由小的因子组成，则是微不足道的。

一个相当幼稚的分解N的算法如下：

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

使用此算法，$ 340 $ $ 282 $ $ 366 $ $ 920 $ 938 $ $ 463 $ $ 463 $ $ 374 $ $ 607 $ $ 431 $ $ 768 $ $ 211 $ $ 456 $可以在最里面的时候精确地进行$ 128 $迭代。 （该数字当然是$ 2 ^ {128} $）

复合数的质数越多，则这些因数必须越小。例如，$ 919 \ cdot 677 = 622 $ $ 163 $。使用朴素算法时，这需要$ 157 + 1 = 158 $次迭代。大小大致相同的数字由三个因素组成，$ 73 \ cdot 89 \ cdot 97 = 630 $ $ 209 $，仅需$ 25 + 2 = 27 $次迭代即可。

同样，1000-由两个大致相等大小的因子组成的数字将需要大约$ 10 ^ {497} $次迭代才能分解。由100个均等大小的因子组成的1000位数字将需要大约$ 434 $ $ 294 $ $ 481 + 99 \约10 ^ {9} $次迭代。而由1000个大致相等的因子组成的1000位数字将需要大约$ 4 + 999 \约10 ^ {3} $次迭代。

因此，要使分解尽可能困难，您需要主因子要尽可能大，这意味着您希望N具有尽可能少的因子。对于$ p $和$ q $素数，$ N $具有两个因素。在$ p $和$ q $组合的情况下，$ N $至少具有四个因素，甚至可能更多。

请注意，这远不能完全解答RSA为什么（我们认为）安全的原因，但我希望它能给出一个更直观/基于示例的想法，说明为什么$ p $和$ q $应该是质数。

还应注意$ p $和$ q $的大小应相似。如果一个比另一个大得多，分解就变得容易了。例如，如果$ p = 43 $，那么朴素的算法将只进行$ 14 $的迭代。

（在阅读注释（感谢Taemyr和Daz C）之后，我纠正了答案中的一些错误。要点不受影响。）

#2 楼

我们通常选择$ p $和$ q $质数的主要原因是：对于给定的$ N = p \，q $大小，这会使$ N $难以分解，因此采用RSA更安全。尽管有效的分解因数算法无法通过试验划分找到因数，但是查找非常小的素因数仍然比查找大因数要容易得多。如果我们随机选择$ p $和/或$ q $而不考虑它们的因式分解，它们往往会具有可能从$ N $中撤出的因素。
如果$ p $和$ q $不是质数，我们需要找到它们的因式分解来计算RSA私有函数；或/和从公共指数$ e $计算RSA私有指数$ d $（反之亦然），因为我们需要知道$ N $的因式分解才能计算$ \ varphi（N）$或$ \ lambda（N ）$;这将是非常困难的（通常比分解$ N $容易，但对于许多实际目的而言仍然太难了）。生成素数要比通常分解因数相等的整数（通常要大两倍）要容易得多。

有RSA（Multiprime RSA）的变体，其中$ N $是两个以上素数的乘积；可以看作$ p $或/和$ q $不是素数。尽管有事实1，这还是有一些兴趣。

#3 楼

对于两个素数$ p $和$ q $，RSA模通常采用$ N = pq $的形式。 $ p $和$ q $的大小（大约）相同也很重要。主要原因是RSA的安全性与分解问题有关。要分解的最困难的数字是大小相似的两个素数的乘积。


注意。基本上有两类方法可以解决因式分解问题：


诸如数字字段筛（NFS）之类的方法，其复杂度取决于$ N $的大小。为了防止这些方法，RSA模数$ N $应该至少具有2048位。
诸如椭圆曲线法（ECM）之类的方法，其复杂度取决于最小的素数因子$ N $。为了防止这些方法，RSA模数$ N $的所有主要因子的大小至少应为256位。

#4 楼

$ \ varphi（n）$是一个乘法函数：它由公式

$$ \ varphi（n）= n \ prod_ {p \ mid n} \ frac {p-1}计算{p} $$

或类似的名称。这基本上是已知的唯一计算方法，当$ n $不小的时候仍然可行。

因此，如果$ N $是您要用于RSA的模数，则需要知道它的质数因式分解，以便您可以计算$ \ varphi（N）$。而且您不希望其他人知道它的素因数分解，否则他们可以计算$ \ varphi（N）$。

此外，RSA关心的只是它有一些$ N $和$ \ varphi（N）$。我们谈论$ p $和$ q $的唯一原因是选择$ N = pq $，因为这是满足上一段的最佳方法。

#5 楼

我有同样的问题，所以我降落在这里。 RSA具有两个关键属性


映射$ m \到m ^ e（mod \ N）$是双射
逆映射$（m ^ e）^ d \ equiv m \（mod \ N）$很容易计算（当然是给定$ p $和$ q $）

从我的阅读中，可以证明（RSA的这两个属性） ）假定$ p $和$ q $质数。因此，我研究了一些违反此属性的示例，但我认为它存在一个更严重的问题。

尽管所有答案都集中于实践方面，但对于我认为，加密方计算它选择的一个较大的复合数的$ totient $，让$ p $和$ q $进行复合有一个根本的问题，即加密将失去其双射性质（解密变得模棱两可）。

例如，如果我们让$ p = 8 $和$ q = 9 $，则$ N = 72 $。 $ \ phi（72）= 24 $。可能的$ e $是$ 5 $。使用此公钥$（N，e）=（72，5）$，就不会有双射。考虑消息$ m = 4 $，加密后，消息变为$ 16 $，而消息$ m = 22 $也变为$ 16 $。 （$ m = 58，\ 40 $加密后也变成$ 16 $）。

我没有这方面的证明，并且对这种理论也很陌生。我将不胜感激任何建议和改进。

#6 楼

有多种原因，RSA使用模数为$ PQ $的Modulo乘法组。由于组的性质，该组不包含1到$ PQ $之间的所有自然数，而是仅包含与$ PQ $互质的数。巧合的是，元素的数量恰好是$（P-1）（Q-1）$。
那是当$ P $和$ Q $是素数时。如果您假设P不是素数，而是半素数，因此$ P = AB $且$ A $和$ B $是素数，则$ PQ $组中的元素数不再是$（P-1）（ Q-1）$，而是$（A-1）（B-1）（Q-1）$。因此，如果您在扩展的欧几里德算法期间在哪里使用$（P-1）（Q-1）$，您将找不到正确的解密密钥（可以使用$（A-1）（B-1）（ Q-1）$）。
这是第一个原因，第二个原因是，通过使用3个质数而不是2个，还有3个额外的密钥可以部分解密。
通过将EEA应用于相同的加密密钥和$（A-1）（B-1）$，$（A-1）（Q-1）$和$（B-1）（Q-1）$，您可以获得可以解密的密钥使用E与$ ABQ $模进行加密的消息。不能保证解密，但有可能。另外，这3个密钥还可以通过使用$ AB $，$ BQ $或$ AQ $模来解密无法使用$ ABQ $模解密的某些消息，具体取决于所使用的3个额外密钥中的哪一个。
几乎全部3个质数必须与传统RSA质数一样长（如果不是，则比$ Q $更容易找到$ A $和$ B $，如果您知道$ A $和$ B，则找到$ Q $并不重要。 $），因为两个密钥都包含$ PQ $，所以密钥长度为$ len（P）len（Q）+ len（E）$（大约为$ len（Q）^ 2）$。如果使用3个素数，则它们的密钥长度现在为$ len（A）len（B）len（Q）+ len（E）$（大约$ len（Q）^ 3 $）。
这三个原因使使用3个质数是不切实际的，必须专门实现非质数处理，从而导致密钥更长的整体算法较弱。
所有这些问题只有在使用更多质数的情况下才会复杂化。 >