4.6 EIGamal算法

ElGamal算法既可以用于加密，也可以用于签名，其安全性依赖于有限域上计算离散对数的难度。要产生一对密钥，首先选择一素数p，整数模p的一个原根g，随机选取x，g和x都小于p，然后计算：

y=gx mod p

公开密钥是y，g，p，其中g，p可以为一组用户共享，私有密钥是x。

将明文信息M表示成{0，1，…，p-1}范围内的数，加密时，秘密选择随机数k，计算：

a = gk mod p

b = ykM mod p

（a，b）作为密文。注意，密文长度是明文的两倍，信息有扩张。

解密时，计算：

M=b/ax mod p

ax≡ gkx mod p，b/ax≡ykM/ax≡gxkM/gxk≡M mod p

下面的例子说明ElGamal算法的加解密过程。

① 生成密钥：使用者Alice选取素数p =19及Z19*的生成元g =2，Alice选取私钥x =10并计算：

gx mod p=210mod19=17

A的公钥是p=19，g=2，gx=17

② 加密：为加密消息m = 16，Bob选取一个随机整数k = 9并计算：

a =29 mod 19 =18

b =16×179mod19=16

Bob发送a，b给Alice

③ 解密：Alice计算：

a-x≡18p-1-x≡188≡1（mod19）

M≡b/ax≡ba-x≡16×1≡16（mod19）

攻击ElGamal加密算法等价于解离散对数问题，要使用不同的随机数k加密不同的信息。假设用同一个k加密两个消息m1，m2，所得到的密文分别为（a1，b1）（a2，b2），则b1/b2=m1/m2，故当m1已知，m2可以很容易地计算出来。