1.4 ElGamal公钥加密方案
ElGamal加密算法由Taher ElGamal于1985年提出，它是一个基于Diffie-Hellman密钥交换的非对称加密算法，方案描述如下。
1.4.1 方案描述
●SysGen：输入安全参数λ，系统参数生成算法生成循环群(G,p,g)，p为群G的阶，g为群G的生成元，输出系统参数SP=(G,p,g)。
●KeyGen：输入系统参数SP，私钥生成算法选取随机数α∈Zp，计算g1=gα，输出公钥pk=g1，私钥sk=α。
●Encrypt：输入待加密的明文数据m∈G，公钥pk，系统参数SP，加密算法选取随机数r∈Zp，计算C1=gr，C2=
·m，输出密文CT=（C1，C2）。
●Decrypt：输入密文CT，私钥sk，系统参数SP，解密算法计算C2·
=
·（gr）-α=m获取明文数据。
1.4.2 安全性分析
ElGamal加密算法的安全性基于判定性Diffie-Hellman（Decisional Diffie-Hellman，DDH）问题的难解性，我们首先给出DDH困难问题的定义。
DDH问题：设G为循环群，p为群G的阶，g为群G的生成元，已知（g，ga，gb，Z），判断Z是否等于gab。
定理1.2 如果DDH问题是难解的，那么ElGamal加密方案是IND-CPA安全的。
证明：假设在IND-CPA安全模型中，存在一个敌手A能以不可忽略的优势ε攻破ElGamal加密方案，那么可以构造一个模拟算法B通过与A交互，以不可忽略的优势给出DDH问题的解。设B以循环群（G，p，g）上的DDH问题实例（g，ga，gb，Z）作为输入。
系统建立：令SP=（G，p，g），B设置公钥为g1=ga，其中a未知，公钥可以从给定问题实例中得到。
挑战：A输出两个不同的挑战明文数据m0，m1∈G。B随机选取比特c∈{0,1}，计算挑战密文CT*=
=（gb，Z·mc）并发送给敌手，其中gb和Z来自问题实例。设r=b，若Z=gab，则
因此，若Z=gab，CT*为消息mc正确的挑战密文。
猜测：A输出对c的猜测，若c′=c，B输出True，表示Z=gab，否则输出False，表示Z≠gab。
由于证明中用到的a和b都是随机数，因此模拟和真实攻击环境是同分布、不可区分的。模拟过程没有出现终止情况，所以模拟成功的概率为1。下面分析A攻破挑战密文的概率。若Z=gab，方案的模拟与真实攻击环境不可区分，因此根据假设，敌手正确猜到加密消息的概率为1/2+ε/2。若Z≠gab，那么Z是随机的，与C1*无关，则CT*是一次一密加密。因此，敌手正确猜测到加密消息的概率为1/2。综上所述，B解决DDH问题的概率为
