ElGamal加密算法

乐乐天

ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
* r2 p- w: r. v# f密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
! o4 J/ f. p$ u8 S- q0 k% b9 h6 dElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算
, n; J9 ~: p ~7 r- q% u
a = g^k ( mod p )
+ o6 s9 J' d# ?' [- T0 b6 j( `再用扩展 Euclidean 算法对下面方程求解b：
% n- ?9 k) x" w0 a4 t1 J7 }" l; U
M = xa + kb ( mod p - 1 )

签名就是( a, b )。随机数k须丢弃。
& V0 {5 R# c( ~! W G验证时要验证下式：

y^a * a^b ( mod p ) = g^M ( mod p )
) `7 H6 U' {; R& h! N, f8 v
同时一定要检验是否满足1<= a < p。否则签名容易伪造。
ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算
( c8 S/ o; G( l8 B
( k. N0 _! Y7 c- qa = g^k ( mod p )
. L7 ~: B8 {8 C4 bb = y^k M ( mod p )
) x* p/ e8 Q1 z/ M5 }9 v5 a/ E
& `9 ]# B. c: E* b& H/ I
( a, b )为密文，是明文的两倍长。解密时计算
_" p5 M3 s' b
M = b / a^x ( mod p )
+ n* G6 h# b) o( u
　　ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
2 r- T5 N& T+ N6 ^* |" |3 y; T因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

5 P) m: f/ ~0 G　　美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
8 {4 j- u9 Y8 N6 N, ^+ G3 F; S; Z变而来。