Diffie-Hellman密钥交换和离散对数

Question

我有一个一般性的问题，这里举个例子： 假设Alice和Bob选择了素数593和公共值g=9。 Alice选择数字530。 Bob选择数字147。

Alice计算：x=g^a mod p=574 Bob计算：y=g^b mod p=527 他们的共享密钥是156。

现在Eve正在尝试破解密钥并找到a。她有一个破解函数，并找到了c，使得g^c mod p=x。 在我们的例子中，c=234，但这不是Alice选择的原始a，所以她仍然没有成功。我的问题是：她是否有办法使用这些信息找出Alice的原始a-即Eve拥有c、g、p和x，并且她知道g^c mod p=x。

（也许通过反函数，我不知道...） 谢谢。

- CnR

---

如果您使用错误的密钥，仍然可以“解密”密文，但最终得到的是垃圾数据而不是原始明文。 - Marc B

这个问题似乎不适合讨论，因为它涉及基础加密知识，没有特定的编程内容。 - Maarten Bodewes

@MarcB 你的意思是Eve无法获取原始a吗？ - CnR

Answer 1

是的。如果

g^a mod p = g^x mod p

那么

g^ab mod p = g^xb mod p

特别地,

(g^b mod p)^a mod p= (g^b mod p)^x mod p

因此，你可以在所有实际情况下假装Alice的私钥是x。这就是为什么g成为群生成器很重要的原因，以便没有这样的“兄弟”私钥。

她不可能知道“原始”的a，但她确实知道它是与x相差o(g)倍数的（通常）小数字集合之一。它是哪一个并不重要。

在这种特殊情况下，发生的情况是g的阶数为296而不是592。因此，Alice选择的实际秘密密钥-530，有一个“兄弟”：

c = 530 + 296 mod 592 = 234

- santosh.ankr

---

如果我理解正确的话，她可以破解Bob和Alice的共享密钥，对吗？ - CnR