密码学中的 Diffie-Hellman 问题有几种变体：计算问题 (CDH) 和决策问题 (DDH)。这篇文章将解释两者，并举例说明前者如何困难而后者如何简单。
设 g 为群的生成元。当我们将群运算想象为乘法时，这意味着群中的每个元素都是 g的幂。
为了计算 g ab 我们需要知道 a 或 b，但我们没有给出。求解任一指数都是离散对数问题，这对于某些组来说是不切实际的。
可以想象，有一种方法可以在不解决离散对数问题的情况下解决CDH，但是，此时，对CDH最有效的攻击是计算离散对数。
假设 Alice 和 Bob 都同意生成器 g，并分别选择私钥 a 和 b 。Alice 发送 Bob g a ，Bob 发送 Alice g b。这不会泄露他们的私钥，因为离散对数问题（据信是）很难。现在，双方都计算 g ab 并将其用作共享密钥。Alice 通过 g b的a 次方 计算g ab，Bob 通过 g a的b 次方 计算g ab。
如果有人拦截了 Alice 和 Bob 之间的交换，他们将拥有 g a和 g b 并想要计算 g ab。这就是CDH。
当处理以大素数 p为模的整数时，如果 p -1 具有大因子，例如当 p – 1 = 2 q 对于素数 q时，CDH 会很困难。如果 p -1 只有很小的因子，即如果 p -1 是“平滑的”，那么离散对数问题可以通过 Silver-Pohlig-Hellman 算法来处理 [1]。如果 p 很大并且 p -1 具有很大的质因数，据我们目前所知，CDH 是困难的。
显然，DDH 比 CDH 弱，因为如果我们能够解决 CDH，我们就可以确定地知道 DDH 问题的答案。尽管如此，DDH 问题被认为对某些群体来说是困难的，例如某些椭圆曲线，但对其他群体来说则不然，如下所示。
由于一半的正整数 mod p 是平方，因此我们可以通过上面的奇偶校验参数在一半的情况下确定地回答 DDH 问题。如果我们的平价论证没有结论，我们就必须猜测。所以，总的来说，我们能够以 0.75 的概率正确回答 DDH 问题。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/18517.html