为什么在 Diffie-Hellman 密钥交换中使用素数？

Question

Diffie-Hellman 密钥交换算法使用诸如2^8 mod nwheren是素数之类的操作。

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

Answer 1

质数不会分解为更小的因子，这使得破解代码或散列比使用 12 更困难，12 分解为 /2 或 /3 或 /4 或 /6。素数7虽然小于12，但只有7的因数，因此攻击向量较少。这过于简单化了，但希望能有所帮助。

这是一个具体的例子：

2^x 模 12

对于任何大于 1 的 x，它只有 2 个可能的值：4 或 8。由于这用于以类似的方式生成共享密钥，因此最终会得到相同的两种可能性。换句话说，一旦您知道基数和模数分别为 2 和 12（任何监听对话的计算机都能够接收到），您就会自动知道共享秘密加密密钥只能是两种可能性之一。只需两个简单的操作即可确定哪个解密消息。现在让我们看一下主要模组：

2^x 模 13

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

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

2^x mod 15 有 4

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

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

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