ElGamal密码

ElGamal也是一种基于离散对数的公钥体制，与Diffie-Hellman密钥体制密切相关。ElGamal密码体系用于数字签名标准（DSS）和S/MIME电子邮件标准等一些技术标准中。

算法描述：

　　1、用户A选择一个素数q及q的某本原根α，并产生一随机数X_A，1 < X_A < q - 1。计算Y_A = α^X_A mod q。A的私钥为X_A，公钥为{q , α , Y_A}

　　2、用户B要和用户A通信，使用A的公钥加密信息。加密过程如下：

　　　　a) 使用分组密码序列的方式发送消息，每块分组表示成一个整数M, 1 ≤ M ≤ q - 1

　　　　b) 选择一个随机整数β，使得1 ≤ β ≤ q - 1。每块分组的k值不相同

　　　　c) 计算一次密钥K = (Y_A)^β mod q

　　　　d) 将M加密成明文对(C₁,C₂),其中

　　　　　　C₁ = α^β mod q C₂ = KM mod q

　　用户A恢复明文

　　　　a) 通过计算K = (C₁)^X_A mod q恢复密钥K

　　　　b) 计算M = (C₂K^-1) mod q

之所以每块分组的k都必须不同是因为若有多块分组k相同，则攻击者可以根据某块已知明文推算出其他的未知明文。

　　　　C_1.1 = α^k mod q C_2.1 = KM₁ mod q

　　　　C_1.2 = α^k mod q C_2.2 = KM₂ mod q

　　于是

　　　　如果M₁已知，则可以很容易计算出M₂：

　　　　M₂ = (C_2.1)^-1C_2.2M₁ mod q

巴特西