DLP,CDH和DDH问题解释
The Discrete Logarithm Problem(DLP)土豆英语怎么说
让G
为⼀个阿贝尔群(交换群).⾸先我们把G中的⼆元操作写成乘法*.对任何g∈G 和任何整数a>1令ga表⽰g∗g∗g...∗g，其中g出现了a
次.离散对数问题就是(DLP);
给定G,g
和h=ga，寻找a
.
这⾥a
国内热点新闻就叫做h的以g
为低的离散对数.
⼀个离散对数问题是难的吗?有时候是，有时候不是.作为反例，令G
为加法下的整数.所以现在可以把群运算相加,⽽不是相乘.因此相同的步骤过后，使⽤相同的元素g，现在写成了g+g+...+g，这就是说现在这个表达式的和就是h，即h=ag.因此对a来说，仅仅需要⽤h除以g就可以计算出来.例如'找出以3为低18的离散对数'.我们仅仅需要⽤18除以3就可以得到a的值.我能够改变这个群运算变成模N的运算.这个问题不会更难.因为我们只需要去解ag=h(mod N)，这个我们可以⽤多项式算法扩展欧⼏⾥得先算出g−1(mod N)，然后a=(g−1mod N)∗h mod N格桑花种植方法>不学无术的成语故事
飞花令诗句
.这不是⼀个好的安全密码原语.
另⼀⽅⾯，有限域内素数阶乘法下的群(在去掉0之后)即椭圆曲线群都被认为是难的.因为我们还不知道多项式时间的算法来在这些群中找到离散对数.举⼀个具体的例⼦，假设我问你'整数模7的乘法群中找到以3为低5的离散对数'.这意味着找到⼀个整数a，使得3a=5 mod 7
.现在我们暴⼒枚举⼀下:
33=(32)×3≡2×3=6≡5(mod7)
32=9≡2≡5(mod7)
33=(32)×3≡2×3=6≡5(mod7)
34=(33)×3≡6×3=18≡4≡5(mod7)
35=(34)×3≡4×3=12≡5(mod7)
因此a=5
.这样我们通过反复乘3得到了这种跳来跳去的⽅法最终获得了结果，这个会让你对DLP困难性有⼀个直观的认知.如果我们的模数远远⼤于 7，有成千上万的⼆进制位，甚⾄⼀台电脑要花费很多时间才能解决这个问题.尽管有次指数级的算法，但是没有证明不存在多项式时间内解决DLP 的⽅法.
The Computational Diffie-Hellman Problem(CDH)
⼀个和DLP问题相关的问题是由Whit Diffie和Martin Hellman提出的两⽅协商密钥在公共信道上不会被窃取的问题:
Alice和Bob共同确定使⽤的循环群G
，和⽣成器q
Alice选择⼀个随机的密钥整数a
,
Bob选择了⼀个随机的整数b
Alice计算ga
海南路线在公共信道上发送给Bob，同时Bob也计算出gb
在公共信道上发送给Alice.
Alice和Bob都计算gab=(ga)b=(gb)a
通过知道他们⾃⼰的随机的整数，这个⽣成的就是他们协商的密钥.
现在gab
是⼀个密钥能被⽤于Alice和Bob之间的对称加密.但是有⼀些⼈窃听了他们之间的交换获得了G,g,ga,gb
.因此密钥取决于的这个问题，就叫做 计算DH问题(CDH).
给定G,g,ga,gb
，找出gab首肯的意思
CDH是和DLP相关的，但是哪个更难呢?如果我能有效率的解决DLP，那么我就可以找出a
，然后轻松的计算出gab
就像Bob做的那样，因此我们就解决了CDH.所以我们说能解决DLP那么⼀定能解决CDH，这就是说DLP⾄少和CDH⼀样难.
The Decisional Diffie-Hellman Problem (DDH)
这是另⼀个离散对数的问题,⽤于证明难以区分的属性.假如说Alice和Bob执⾏如上所述的Diffie-Hellman密钥协议，那么G,g,ga,gb
都是公共的,gab是密钥.直观上,DDH问题就是是否对⼿能够从随机的G中的元素区分出Alice和Bob的密钥gab
.正是来说:
给定G,g,ga,gb
和Tx使得T0是G中随机的⼀个元素,T1=gab同时x
终于我明白
被随机均匀的从{0,1}中选择，找出x.
如果对⼿能够解决DDH(输出正确的x的概率⼤于1/2).那么就是说G,ga,gb
⼀定泄露了⼀些关于gab的信息，使得攻击者能把它从随机的元素中分辨出来，尽管不能直接计算出来.⽽且很明显，如果对⼿能解决CDH问题，那么它可以有效率的解决DDH，因为它已经可以得到gab
的值.这意味着,CDH⾄少和DDH⼀样难.
这就是我们这篇中讨论的三个问题，我们给出了⼀个简明的证明对他们的困难性进⾏排序:DLP最难，然后是CDH，最后是DDH.就像我们看到的那样,DLP有时候是简单的，会让CDH和DDH都变简单.因此群G
和⽣成器g的选择在做密码学的时候是⼗分重要的!
