EIGamal密码*：由EIGamal提出，是一种基于离散对数问题的双钥密码*，既可用于加密，又可以用于签名。

密钥对生成步骤：

1.取大素数p和g<p（g最好是p的素根）

2.选一整数x<p，（p，g，x）是私钥

3.计算y=g^x （mod p），（p，g，y）作为公钥

加密和解密步骤

要加密M，选取一个随机数k，（k，p-1）=1即k与p-1互素

加密:  a=g^k （mod p）

　　　b=My^_k （mod p）

　　　C=a||b（||表示连接）

解密：M=ba^-x （mod p）

证明：ba^-x（mod q）Ξ My^kg^-xk Ξ Mg^xkg^-xk Ξ M

EIGamal的一些特征：

1.加密过程中引入随机数

2.密文是明文的两倍

EIGamal的安全性基础：

还记得对称加密的密钥传送必须通过安全通道问题，有这样一种交换会话密钥的方案：

Diffie-Hellman密钥交换----于1976年提出的第一个公钥案

允许两个用户安全地建立一个秘密信息，用于后续的通讯过程

算法的安全性依赖于：有限域上计算离散对数的难度。

p，g可以让第三方知道，A和B先约定共同的p和g，A自己决定一个X_a，B自己决定一个X_b，通过计算Y=g^x （mod p）算出各自的Y_a和Y_b，交换Y_a和Yb，再计算各自K=Y^x  （mod p），发现K的值是相同的，值为K=g^{x_ax_{b （mod p）}} ，这时K就可以作为共享密钥，用于后续的通讯。

DH方案的第三者攻击方法：

问题在于A和B在不安全的信道上通信，无法确定另一方到底是谁。

改进方案：

K是A，B之间的认证秘密信息