ElGamal的安全性

ElGamal密码体制基于离散对数问题。

离散对数问题

离散对数问题(DLP)

已知一个乘法群\((G,\cdot)\),一个\(n\)阶元素\(\alpha \in G\)和元素\(\beta \in G\),计算\(a=\log_{\alpha}\beta\)

计算Diffie-Hellman问题(CDH)

已知一个乘法群\((G,\cdot)\),一个\(n\)阶元素\(g\in G\)和两个元素\(g^a,g^b\in G\),其中\(a,b\)未知,计算\(g^{ab}\in G\)

  • 在一个公共信道上,Alice和Bob确定了一个公用的循环群\(G\)和生成器

  • Alice选择一个随机数\(a\),Bob选择一个随机数\(b\)

  • Alice计算\(g^a\)在公共信道上传输给Bob,同时Bob计算\(g^b\)在公共信道上传输给Alice

  • Alice分别计算\((g^a)^b\)\((g^b)^a\),得到他们协商的密钥

如果有敌手窃听了他们交换使用的\(G,g,g^a,g^b\),需要计算出\(a\)\(b\)即能解决DLP问题,才能获得\(g^{ab}\),也就是说CDH问题基于DLP问题。

判定Diffie-Hellman问题(DDH)

已知一个乘法群\((G,\cdot)\),一个\(n\)阶元素\(g\in G\)和元素\(g^a,g^b,g^c\in G\),其中\(a,b,c\)未知,判定\(g^{ab}=g^c\)是否成立。

Diffie-Hellman问题中,\(G,g,g^a,g^b\)是公开的,\(g^{ab}\)是私钥,DDH问题用于证明难以区分的属性,也就是敌手不能从\(G\)中区分出密钥\(g^{ab}\)

给定\(G,g,g^a,g^b,T_b\),设\(T_0\)\(G\)中随机的一个元素,\(T_1=g^{ab}\)\(b\leftarrow \{0,1\}\),如果敌手以大于\(\frac{1}{2}\)的概率得到正确的\(b\),也就是说敌手能够解决CDH问题,也就是说DDH问题基于CDH问题

综上,困难性:DLP>CDH>DDH

ElGamal的安全性规约证明

设敌手攻击ElGamal加密方案成功的概率为\(\frac{1}{2} + \sigma\),当\(z\)取随机数时,\(\tilde{\Pi}\)不是一个加密方案,不能解密,敌手有\(\frac{1}{2}\)的概率猜中。

\[\begin{aligned} &Pr[D(G,g,g^x,g^y,g^{xy})=1] = Pr[PubK^{eav}_{A,\Pi}=1] = \dfrac{1}{2} + \sigma\\ &Pr[D(G,g,g^x,g^y,g^z)=1] = Pr[PubK^{eav}_{A,\tilde{\Pi}}=1] = \dfrac{1}{2}\\ &Pr[D(G,g,g^x,g^y,g^{xy})=1] – Pr[D(G,g,g^x,g^y,g^z)=1] = \sigma\\ \end{aligned} \]

因此,ElGamal加密方案安全等价于DDH问题。

原文地址:http://www.cnblogs.com/euler0525/p/16921585.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性