Dan Boneh密码学笔记12

12.Public key encryption from Diffie-Hellman

1.The ElGamal Public-key System

2.ElGamal Security

3.ElGamal Variants With Better Security

4.A Unifying Theme

5.Farewell (for now)

1.The ElGamal Public-key System

上节基于陷门函数RSA的公钥加密系统

这节基于diffie-hellman协议的公钥加密系统

elgamal加密被用于一个邮件加密系统GPG，GNU隐私卫士

共享密钥是KAB

攻击者可以看到A和B，但是还不知道生成元g，它要计算g^ab是困难的。

从大A提取小a，是一个离散对数问题，还原私钥是困难的。

将Diffie-hellman协议转换成一个实际的公钥系统

现在这两步是分开进行的 ，不一定同时发生。

生词密钥对，公钥是A，私钥是a

信息m是Bob要发给Alice的 ，对称加密密钥k

Bob每加密一次信息，需要选择一个新的随机b

u是Bob的公钥作为密文被发送，但是攻击者不会知道v，h是Alice的公钥，通过求二元组（u,v）的哈希值，最后Bob输出自己的公钥u和加密信息m后的密文c。

看似加密用时是解密的两倍，因为有两个指数运算。但其实并不是这样的。

g、h是固定的，所以可以先计算重复平方法的值。离线完成。而u是变化的。如果可以存储由公钥推导出的重复平方表，这叫做窗口化的指数计算。事实上，加密快于解密。

如果所有的加密者只是加密单个接收方，可以使用这些预计算的表很快完成计算。如果加密者对每个信息都要加密给不同的接收方，例如每次发送电子邮件给不同的接收方，事实上加密要比解密慢一倍。

如果很在意性能，RSA更快。

2.ElGamal Security

elgamal公钥加密系统的安全性

CDH，computationalDiffie hellman，CDH假设

事实上这个假设对于分析elgamal系统的安全性并不理想

接着引入一个稍微更强一点的假设，叫做哈希DF

Hash diffie-hellman假设，HDH假设

哈希推出的密钥与R真随机的密钥不可区分

HDH实际上比CDH假设要强

证明，逆否命题，如果CDH是容易的，则意味着有了g^a,g^b可以计算g^ab,因为我知道哈希函数H，给我左边的或者右边的样本，我可以轻松地分辨其来源。如果来自左边，我一旦自己计算g^ab,就可以测试组里的最后一个元素事都就是g^a和g^ab的哈希值，如果是，我就知道这个样本来自左边。如果不是，我就知道是取自右边的。这给了我很高的优势来区分这两个分布。CDH容易的话，可以容易得区分。这就是说，如果HDH很难解决，那么CDH也将是很难的。

如果是真随机的，R的第一位是0的概率是1/2，而左边的第一位总是0，因此，看到0，我就说分布来自左边。这会给我1/2的优势以区分这两个分布。因此，HDH假设在这里不成立。

证明elgamal在HDH假设下是语义安全的。

如果用真随机完全独立的密钥k来替换这哈希函数的结果，根据HDH假设，攻击者无法区分这两个游戏。

因为右边两个也是不可区分的。所以左边两个也不可区分。所以得证是语义安全的。

证明elgamal系统对抗CCA的安全性

IDH，interactiveDH交互的，也就是这个案例中的DH

ro表示是在随机神谕的前提下

3.ElGamal Variants With Better Security

elgamal的变种。更好的CCA安全的分析。

过去十年主要结果的综述，特别是应用到elgamal系统的方面

这个安全定理：IDH假设下，elgamal是CCA安全的。

如何证明在CDH假设下，是CCA安全的？

法1，证明CDH假设是困难的。但可以证明CDH与IDH等价。可以组建这样的群，叫做双线性群。（双线性群上的二元运算是（0，2）型张量），在这些群里，elgamal系统是CCA安全的，严格地基于CDH假设得证。

双线性群是由椭圆曲线构建的。更多的代数结构可以使得我们证明IDH和CDH的等价性。

法2，不使用椭圆曲线，修改elgamal系统。证明直接使用CDH对任意群CDH都是困难的。不用假设群上的任何附加结构。叫做孪生twin elgamal。

孪生twin elgamal

在生成密钥对阶段，随机选择两个指数a1和a2

自己看图，就这么简单的改动…..

这个简单的改变允许我们根据CDH假设来证明CCA安全了

下个问题，我们能否回避这个哈希函数是理想的假设即假设哈希函数是随机神谕。这是个很大的研究方向。

法1，使用了特殊的群，双线性群。

法2 ，更强的假设，判定decisionDH假设。可以构建一个elgamal变种系统叫做cramer-shoup系统。是CCA安全的，且无需随机神谕。

第一篇，讨论了大量的DH相关假设。特别研究了判定DH。

第二篇，讨论了构建CCA安全的系统根据判定DH和类似假设。

第三篇，从双线性群构建CCA安全性，基于身份的加密，几乎没有开销。

第四篇，twin DH

第五篇，给出一般的框架用来构建CCA安全的系统。使用所谓的易解哈希证明（extractable hash proofs）。

4.A Unifying Theme

综合RSA和DH，

这两类机制遵循着一个更一般的原理，单向函数。

正向计算容易，反向计算难。

若P=NP，则公钥密码学将有根基危机。

我们不能证明单向函数的存在性。只是假设它们存在。

如何破解这个PRG呢？

y是发生器的输出，A会输出种子，因为它能求伪随机数发生器的逆。

这就是我们区分出PRG的方法

如果A可以求F的逆，那么B也可以破解发生器。因为这个发生器是安全的，所以A不可能求F的逆。因此F是一个单向函数。

第二个例子是我们称离散对数是单向函数，如果群G上的离散对数问题是困难的，那么事实上函数f是单向的。f的单向性就是离散对数假设。

不需要知道x和y的值。这是一个群同态。elgamal属于部分同态加密。

这个单向函数的加性，使得公钥密码学成为可能。

例子3，RSA单向函数，这个性质也比较有意思。乘法性质。

f有一个trapdoor，有一个私钥可以让拿给我们突然间就能计算这个函数的逆了，不过没有这个私钥时，这个函数是单向的。这个具有陷门的性质，使得公钥密码学成为可能。使得RSA特别适合数字签名。

同态性质

5.Farewell (for now)

第一季六周的课程回顾

第一季完结撒花！

每集我学习用时是课程时长的两到三倍，刚开始的时候学起来比较困难，到后面就越来越顺了，也习惯了这位老师的英语发音，养成了不错的学习习惯。当然，约到后面的内容其实比前面是困难一些的。这个老师讲的太好了！！！尤其是数论那节，我本科学习信息安全数学基础学的一脸懵逼，但是他只用一节课就把这个课程需要用到的数论知识讲完了，讲的也算非常清楚了。

即使每节课都做到这样耗时间得学习，依然只能掌握80%的内容。接下来要做的是，在开学后的课程上严格要求自己。认认真真把这位老师的课本探究透彻。把每节课提到的论文都认真读读。把对应的数学证明都亲自证明一遍。把信安数学基础再补补。

下一篇，课程汇总，思维导图。