如何正式地说素数$p$的整数模$p$给出了比复合$n$更“随机”的结果？

Question

我正在为非专家做一个关于密码学的演讲。我演示的主要算法是Diffie密钥交换。它对素数p使用模算法。在我的演示中，我希望能够解释为什么模操作使用素数而不是复合数。我见过那种“手挥手”的解释文件。我所见过的最好的解释--尽管是手波--来自奎拉：

但是当数据不是随机的，那么奇怪的事情就会发生。例如，假设数值数据总是10的倍数。如果我们使用mod 4，我们发现：10 \bmod 4 = 2 20 \bmod 4 = 0 30 \bmod 4 = 2 40 \bmod 4 = 0 50 \bmod 4 = 2，所以从模(0,1,2,3)的3可能值中只有0和2会发生碰撞，这是很糟糕的。如果我们使用像7：10 \bmod 7 = 3 20 \bmod 7 = 6 30 \bmod 7 = 2 40 \bmod 7 = 4 50 \bmod 7 = 1这样的素数

我的问题是:我们能不能比这个更精确？有什么数学定理可以说明为什么会出现这种模式吗？

Answer 1

我们能比这个更精确吗？

实际上，结果值的“随机性”并不是DH的复合模块的阻塞问题。

更严重的是，如果您知道模n=pq的因式分解，那么然后解题g^x\bmod n#qcStackCode#本质上等同于解决g^x\bmod p#qcStackCode#和g^x\bmod q#qcStackCode#和n本身解决问题要容易得多(使用GNFS)。之后，您可以廉价地将解决方案与阴极射线管重新组合。

特别要注意的是，对于DH使用一个2048位的安全素数会产生一个安全的(未经身份验证的)密钥交换(需要进行关于2^{112}的努力来打破它)，而如果您要使用例如平衡因子来解决两个1024位的离散日志实例，这两个实例都需要2^{80}工作(因此总共需要2^{81} )。这被认为是可行的，如果你有适当的资金数额(如国家-州一级)。显然，如果你使用不平衡的因素，攻击的运行时间被更大的因素所支配，在这一点上，你可能只是取消了较小的因素，并为自己节省了计算时间(用于正常的交换)。

如果你不知道因式分解，事情会变得更加困难，但不确定性也会变得更加困难。您必须相信，生成复合模量的人实际上不知道这些因素(因此能够更容易地破坏安全性)。此外，它还允许参数替换攻击，这反过来又允许这样的攻击。这不是理论上的攻击。事实上，有了这样一个参数替换攻击，您就可以偷偷地进入一个由4x512位素数组成的值，没有人可以(很容易)考虑这个(很容易)，但是使用经过一周的预计算，每一个具有这个模数的离散日志实例都可以在几秒钟内得到解决。。

所以TL;DR:通过使用复合模块，您只会感到头痛，速度和安全性都不高。

如果上面的内容太复杂，请尝试以下操作：

我们在Diffie-Hellman中使用素数，因为它没有速度，也没有不使用它们的安全优势。实际上恰恰相反，如果我们使用复合材料，我们可以沿着因式分解分解相关的离散对数硬问题，并行地解决这两个子问题。更糟糕的是，由于求解算法的复杂度随着问题的大小而快速增长，每个实例都显着地更容易解决。如果我们不知道因式分解，我们将不得不相信模数生成器不会利用上面针对我们的弱点，攻击者可能会用他们的参数替换我们的参数，从而使他们可以后门访问数据。