cryptography - 为什么在 Diffie-Hellman key 交换中使用素数？

Question

Diffie-Hellman key 交换算法使用类似 2^8 mod n 的操作哪里n是素数。

使用质数而不是其他数字的原因是什么？

Answer 1

质数不会分解成更小的因子，这使得破解代码或散列比使用 12 更难，比如使用/2 或/3 或/4 或/6 分解。质数 7 小于 12，但只有 7 的因数，因此攻击向量较少。这是一个极端的过度简化，但希望能有所帮助。

下面是一个具体的例子:

2^x 模 12

对于任何大于 1 的 x，这只有 2 个可能的值:4 或 8。由于它用于以类似的方式生成共享 key ，因此您最终会得到相同的两种可能性。换句话说，一旦您知道 base 和 mod 是 2 和 12(任何监听对话的计算机都可以接收到)，您就会自动知道共享 secret 加密 key 只能是两种可能性中的一种。只需要两个简单的操作就可以确定哪个解密了消息。现在让我们看看一个主要的 mod:

2^x 模 13

这有 12 种不同的可能性，x>1。它还可以生成 12 个不同的可能共享 key 。因此，与 mod 12 示例相比，基于该质数模数解密消息需要 6 倍的计算能力。

2^x mod 14 有 4 种可能性。

2^x mod 15 有 4

2^x mod 16 在 x=3 后完全崩溃为 1 种可能性(这就是为什么选择符合 DH 要求的基数很重要)

2^x mod 17 有……你猜对了，16 种可能性!素数不是很酷吗？ :)

因此，是的，模数的可分解性与加密消息的可破解性有关。