斯坦福大学密码学-基于Diffie-Hellman 的公钥加密 12

ppt链接：

EIGamal 公钥加密系统

回顾。

公钥加密的应用。

Bob用Alice的公钥加密完 K_F 后，Alice就可以用自己的私钥解出对称密钥，读取文件。

密钥契约。

Bob在公司用自己的公钥和契约的公钥加密了 K_F ,然后Bob突然离职了，公司需要读取Bob的文件，于是公司会联系契约服务，契约服务用私钥解出对称密钥，读取文件。注意：契约服务是完全离线的，知道公司需要它。

两种构造公钥加密机制的方式。

回顾：DH密钥交换协议。

EIGamal 。

这是一个随机加密算法，Bob每加密一条信息，他都要选择一个新的随机b，然后使用这个新的随机数b加密信息。

构造。

加密和解密。

EIGamal 性能。

加密需要两个指数运算，而解密只需要一个指数运算。但是解密 u 是变化的。如果加密速度慢的话，可以提前计算重复平方根需要的数，这样可以提高加密的速度。

EIGamal 加密系统的安全性

CDH假设分析EIGamal系统的安全性并不理想。

HDH(Hash D-H假设)。

如果哈希D-H实际上很难解决，那么CDH也将是难的。因为HDH是一个更强的假设。可能会有CDH困难的集合，但HDH不困难，所以说HDH是一个更强的假设。

HDH足以证明EIGamal系统的安全性。

例题。

即使CDH可能在群G上是困难的，但是如果选择了一个不好的哈希函数，那么HDH在这个 (G,H) 上也不成立。

EIGamal系统在HDH假设下是语义安全的。

证明：

选择密文攻击安全。IDH 交互DH假设。

在以上奇怪的假设下，保障了CCA安全。

具有更好的选择密文安全分析的EIGamal变形

想在CDH基础上证明EIGamal的CCA安全性。1.使用双性线群这种特殊的结构。2.改变EIGamal系统结构。

孪生EIGamal。

孪生EIGamal是CCA安全的。

能否回避哈希函数是理想的假设？需要继续阅读了。。。。。。

文献推荐。

一个统一的定理

RSA和DH这两类机制遵循着一个统一的原理，单向函数。不能证明单向函数的是否存在。只是假设它们存在。

单向函数。

单向函数举例1。

使用伪随机发生器构造单向函数。

证明：逆否命题。

A是一个求f的逆的有效算法，需要构建一个算法B破解PRG。B有集合Y中的某个元素y，算法B试着输入y运行算法A，如果y是PRG的输出，那么A会输出种子，即以不可忽略的概率，输出X中的一个元素。再次应用F，应该等于y。输出0。否则，输出1。

如果是伪随机发生器的输出y，则算法B不可忽略的概率输出0。如果是真随机发生器，随即发生器输出的字符串不由发生器任何种子生成，则很大概率输出1。

所以，如果A可以求f的逆，那么B可以破解PRG。所以，如果B是安全的PRG，那么A不可以求f的逆。

单向函数举例2。

离散对数是一个单向函数。

单向函数举例3。

RSA单向函数。

RSA陷门使得它构建数字签名变得很容易。

总结。

总结。