1.4 ElGamal公鑰加密方案

ElGamal加密算法由Taher ElGamal于1985年提出，它是一個(gè)基于Diffie-Hellman密鑰交換的非對(duì)稱加密算法，方案描述如下。

1.4.1 方案描述

1.4.2 安全性分析

ElGamal加密算法的安全性基于判定性Diffie-Hellman（Decisional Diffie-Hellman，DDH）問(wèn)題的難解性，我們首先給出DDH困難問(wèn)題的定義。

DDH問(wèn)題：設(shè)G為循環(huán)群，p為群G的階，g為群G的生成元，已知（g，ga，gb，Z），判斷Z是否等于gab。

定理1.2 如果DDH問(wèn)題是難解的，那么ElGamal加密方案是IND-CPA安全的。

證明：假設(shè)在IND-CPA安全模型中，存在一個(gè)敵手A能以不可忽略的優(yōu)勢(shì)ε攻破ElGamal加密方案，那么可以構(gòu)造一個(gè)模擬算法B通過(guò)與A交互，以不可忽略的優(yōu)勢(shì)給出DDH問(wèn)題的解。設(shè)B以循環(huán)群（G，p，g）上的DDH問(wèn)題實(shí)例（g，ga，gb，Z）作為輸入。

系統(tǒng)建立：令SP=（G，p，g），B設(shè)置公鑰為g₁=ga，其中a未知，公鑰可以從給定問(wèn)題實(shí)例中得到。

挑戰(zhàn)：A輸出兩個(gè)不同的挑戰(zhàn)明文數(shù)據(jù)m₀，m₁∈G。B隨機(jī)選取比特c∈{0,1}，計(jì)算挑戰(zhàn)密文CT*==（gb，Z·m_c）并發(fā)送給敵手，其中gb和Z來(lái)自問(wèn)題實(shí)例。設(shè)r=b，若Z=gab，則

因此，若Z=gab，CT*為消息m_c正確的挑戰(zhàn)密文。

猜測(cè)：A輸出對(duì)c的猜測(cè)，若c′=c，B輸出True，表示Z=gab，否則輸出False，表示Z≠gab。

由于證明中用到的a和b都是隨機(jī)數(shù)，因此模擬和真實(shí)攻擊環(huán)境是同分布、不可區(qū)分的。模擬過(guò)程沒(méi)有出現(xiàn)終止情況，所以模擬成功的概率為1。下面分析A攻破挑戰(zhàn)密文的概率。若Z=gab，方案的模擬與真實(shí)攻擊環(huán)境不可區(qū)分，因此根據(jù)假設(shè)，敵手正確猜到加密消息的概率為1/2+ε/2。若Z≠gab，那么Z是隨機(jī)的，與C₁*無(wú)關(guān)，則CT*是一次一密加密。因此，敵手正確猜測(cè)到加密消息的概率為1/2。綜上所述，B解決DDH問(wèn)題的概率為