為什麼 Diffie-Hellman 的模數必須是素數？

我讀了很多關於 Diffie-Hellman 的文章，但有一件事我不明白：為什麼模 p 必須是素數？如果它不是素數怎麼辦？

回答 Martin 和 Vadim 的評論：

讓 $ n:=p $ 你想找到 $ x $ 和 $ g^{x} \equiv y \bmod pq $

計算兩個更簡單的 DL 問題：

$ {x_p} $ 和 $ g^{x_p} \equiv y \bmod p $

$ {x_q} $ 和 $ g^{x_q} \equiv y \bmod q $

注意

$ x_p \equiv x \bmod p-1 $

$ x_q \equiv x \bmod q-1 $

使用中國剩餘定理，您可以計算 $ x’ $ 從 $ x_p $ 和 $ x_q $ 和

$ x’ \equiv x \bmod lcm(p-1, q-1) $

這與 Diffie-Hellman 假設有關。DH 密鑰交換在計算 DH 假設成立的組中是安全的。最簡單的群之一是以大素數為模的乘法群。

然而，這不是必須的。假設因式分解很困難，至少一些具有未知因子的複合整數會產生安全的 Diffie-Hellman 模數。

引用自：https://crypto.stackexchange.com/questions/30328