ElGamal簽名演算法

密鑰產生

• 確定一個大素數p
• 取p的一個本原根g
• 在Z_p域上選擇一個亂數x
• y = g^x%p
• (y, g, p)為公鑰，x為私鑰

簽名演算法

設待簽名的訊息為m

• C₁=g^k%p
• C₂=(H(m)-x*C_1) * k^-1%(p-1)
• 輸出簽名(C₁,C₂)和訊息m

驗證演算法

• y C 1 ? C 1 C 2 = H ( m ) y^{C_1}*C_1^{C_2}=H(m) yC1??C1C2??=H(m)

正確性證明

ElGamal加密演算法

簡單介紹

• EIGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼

• EIGamal是建立在離散對數的困難問題上的一種公鑰體制密碼

密鑰產生

• 選一個素數p，以及小于p的兩個亂數g和x
• 計算 y = g x y = g^x y=gx%p
• 公鑰為(y, g, p)，私鑰為x

演算法加密程序

M為明文

• 選取一個與p-1互素的整數k
• C 1 = g k C_1=g^k C1?=gk%p
• C 2 = y k M C_2=y^kM C2?=ykM%p
• ( C 1 , C 2 ) (C_1,C_2) (C1?,C2?)即為密文

演算法解密程序

解密方法： C 2 C 1 x \frac{C_2}{C_1^x} C1x?C2??%p

證明：

EIGamal 密碼體制安全性

由于私鑰x是通信雙方共享的，別人不知道

所以，當加密完了以后的密文(y, g, p)被別人盜取后，想獲取明文M,只能通過 C 2 = y k M C_2=y^kM C2?=ykM%p來獲得，這里面只有k和M是不知道的，所以只要獲得了k就能獲得M，而想獲得k，只有通過 C 1 = g k C_1=g^k C1?=gk%p來獲取，這里面雖然只有k是未知數，但是求離散對數的程序是很困難的，尤其是對p很大的情，所以EIGamal密碼體制很安全

舉個例子

• 取p=11, g=5, x=2
• 則 y = g ^x%p = 3
• 取 k 為 7， m為10
• 則C₁ = g^k%p = 3
• C₂ = y^k*m % p = 2
• 則C₁^x%p= 9
• 9在模11下的逆元為5
• 所以 C 2 C 1 x = 2 ? 5 \frac{C_2}{C_1 ^x}=2 * 5 C1x?C2??=2?5%10 =10，所以解密成功

ElGamal簽名演算法

密鑰產生

• 確定一個大素數p
• 取p的一個本原根g
• 在Z_p域上選擇一個亂數x
• y = g^x%p
• (y, g, p)為公鑰，x為私鑰

簽名演算法

設待簽名的訊息為m

• 取一個與p-1互質的k

• C₁=g^k%p

• C₂=(H(m)-x*C₁) * k^-1%(p-1)

• 輸出簽名(C₁,C₂)和訊息m

驗證演算法

• y C 1 ? C 1 C 2 = g H ( m ) y^{C_1}*C_1^{C_2}=g^{H(m)} yC1??C1C2??=gH(m)%p

正確性證明

舉個例子

• p = 11
• g = 2,(注意必須取p的一個生成元)
• x = 6
• 計算y = g^x%p = 9
• 取 k = 7
• 計算C₁=g^k%p = 7
• 利用擴展歐幾里得計算k在模p-1意義下的逆元k^-1= 3
• 假設需要驗證的訊息m經過哈希后的結果是H = 10
• 則計算C₂ = ((H - x * C1) * k_-1 ) % (p-1) = 4
• 驗證：計算 y C 1 ? C 1 C 2 y^{C_{1}} * C_{1}^{C_2} yC1??C1C2??%p = 1
• 計算H^g%p=1
• 所以驗證成功