algorithm - 生成 Diffie-hellman 参数(生成器)

Question

我正在尝试实现 diffie-hellman key 交换。假设我找到了一个大素数 p - 我怎样才能找到生成器 g？

受我必须使用的多精度库的限制，只有几个基本操作(+、*、-、/、pow、modExp、modMult、mod、gcd、isPrime、genRandomPrime、genRandomBits 等)是可用。

寻找一个安全的素数 q 是否可行，以便每个 n 的 gcd(n,q) == 1 应该是一个生成器，对吧？

Answer 1

你基本上回答了你的问题。刚刚测试gcd(n,q)==1没有必要，因为 q是质数。这意味着任何数字 n , 这样 n < q与 q 没有公因数和 gcd(n,q)将始终输出 1。

您可以检查q=2p + 1 是否是质数。如果是这样，则 ord(Zq) = q-1 = (2p+1)-1 = 2p。由于 ord(x) | ord(Zq) 对于 Zq ord(x)=2 或 ord(x)=p 中的每个 x 或 ord(x)=2p。因此，您只需要检查从 {2,...,q-1} 中随机选择的元素 x 是否为 2 阶。如果不是，则它为 p 或 2p 阶，您可以使用它作为发电机。