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陷门使得它构建数字签名变得很容易。
总结。
总结。
