html5高端酒水饮料企业网站模版,软文推广案例大全,阜宁城乡建设局网站,晚上必看的正能量视频下载密码学中的 Diffie-Hellman 问题有几种变体#xff1a;计算问题 (CDH) 和决策问题 (DDH)。这篇文章将解释两者#xff0c;并举例说明前者如何困难而后者如何简单。
迪菲-赫尔曼问题 Diffie-Hellman 问题是针对阿贝尔群制定的。我们想到的主要群是非零整数以大素数 p为模的乘…密码学中的 Diffie-Hellman 问题有几种变体计算问题 (CDH) 和决策问题 (DDH)。这篇文章将解释两者并举例说明前者如何困难而后者如何简单。
迪菲-赫尔曼问题 Diffie-Hellman 问题是针对阿贝尔群制定的。我们想到的主要群是非零整数以大素数 p为模的乘法群。但我们从更普遍的角度开始因为迪菲-赫尔曼问题对于某些群体来说比其他群体更难正如我们将在下面看到的。
设 g 为群的生成元。当我们将群运算想象为乘法时这意味着群中的每个元素都是 g的幂。
计算迪菲-赫尔曼问题 设 a 和 b 是两个整数。给定 g a 和 g bCDH 问题是计算 g ab。请注意指数是 ab 而不是 a b。后者很简单只需将 g a和 g b相乘即可。
为了计算 g ab 我们需要知道 a 或 b但我们没有给出。求解任一指数都是离散对数问题这对于某些组来说是不切实际的。
可以想象有一种方法可以在不解决离散对数问题的情况下解决CDH但是此时对CDH最有效的攻击是计算离散对数。
迪菲-赫尔曼密钥交换 Diffie-Hellman 密钥交换取决于 CDH 是一个难题的假设。
假设 Alice 和 Bob 都同意生成器 g并分别选择私钥 a 和 b 。Alice 发送 Bob g a Bob 发送 Alice g b。这不会泄露他们的私钥因为离散对数问题据信是很难。现在双方都计算 g ab 并将其用作共享密钥。Alice 通过 g b的a 次方 计算g abBob 通过 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 问题也从 g a 和 g b的知识开始。但是它不是要求计算 g ab而是询问 对于随机选择的 c 是否可以以 优于 0.5 的概率区分g ab 和 g c 。
显然DDH 比 CDH 弱因为如果我们能够解决 CDH我们就可以确定地知道 DDH 问题的答案。尽管如此DDH 问题被认为对某些群体来说是困难的例如某些椭圆曲线但对其他群体来说则不然如下所示。
乘法群 Mod p的 DDH 假设我们正在处理以素数p为模的非零整数乘法群 。使用勒让德符号即使对于非常大的数字也可以进行计算您可以确定 g a 是否是平方 mod p当且仅当 a 为偶数时才会发生这种情况。因此通过计算g a mod p的勒让德符号 我们知道a的奇偶性 。同理我们可以求出b的奇偶性 。因此我们知道 ab的奇偶性。如果 ab 是奇数但 g c 是平方 mod p我们知道 DDH 问题的答案是否定的。类似地如果 ab 是偶数但 g c 不是平方 mod p我们也知道 DDH 问题的答案是否定的。
由于一半的正整数 mod p 是平方因此我们可以通过上面的奇偶校验参数在一半的情况下确定地回答 DDH 问题。如果我们的平价论证没有结论我们就必须猜测。所以总的来说我们能够以 0.75 的概率正确回答 DDH 问题。
