3.2.2
ElGamal算法

ElGamal算法的过程分为三个步骤：第一步，Bob基于某个数学难题构造私钥和公钥参数，并将公钥公布，私钥自存；第二步，Alice根据公钥生成密文，并将密文发送给Bob；第三步，Bob利用私钥对密文解密。

大家会发现上述过程和RSA并无二致，因为这正是非对称加密的一般框架。但是，ElGamal算法和RSA算法到底有哪些区别呢？简要地说，区别主要有以下两个方面。第一，算法基于的数学难题不同，RSA的基础是大整数的素数分解，而ElGamal算法是基于离散对数问题构建的。第二，加密和解密的计算过程也不同，在ElGamal算法中Alice除了用公钥对明文进行加密之外，还利用自己秘密生成的一个随机数生成一个随机密码，并将该随机密码和密文一起发给Bob，Bob利用私钥、随机密码和密文恢复明文。下面对这两个方面进行详细的介绍。

Bob生成密钥参数的操作有以下几步：

• Step 1：找到一个大素数 p 。
• Step 2：基于 p ，满足一定条件的整数 α ，以及另一个整数 t ；其中 t 需要满足2≤ t ≤ p -2。
• Step 3：计算 β = α ^t mod p 。

上述过程中，参数{ α , β , p }为公钥， t 为私钥。

Alice利用公钥参数加密的步骤如下：

• Step 1：选择秘密的随机数 i ，满足2≤ i ≤ p -2。
• Step 2：计算随机密码 k _a = α ⁱ mod p 。
• Step 3：用公钥对明文 m 进行加密得到密文 s ，即 s = m × β ⁱ mod p 。
• Step 4：将随机密码 k _a 和密文 s 都发送给Bob。

Bob利用私钥参数进行解密的过程较简单，其计算方法如下：

m = s ×[( k _a ) ^t ] ^-1 mod p

从表面的数学形式来看，上述过程非常容易推导，其核心是 β = α ^t mod p 。但实际上，上述过程中参数{ α , β , p }以及 i 的选择都有一定的限制条件，其背后有着比较丰富的数论原理。下面我们试图以比较简明的语言来解释ElGamal算法涉及的数论知识。

通常情况下，上述ElGamal算法的运算都发生在一个特殊的整数集合 中。 表示所有小于 p 且和 p 最小公约数为1的整数所构成的集合。

我们需要了解，集合 有以下两个重要的性质。

• 该集合中任意一个元素都有乘法逆，即对任意 都有 。这确保了加密和解密算法中的求逆运算有效。
• 该集合中可以找到 α ，使得集合中任何一个元素都可以用 α 的幂来表示。这种情况下，称 α 为该集合的生成元。这个性质就使得以 α 为根来构造离散对数问题比较简单。

在数论中，有经典算法可以帮助我们根据 p 和 快速找到适合的 α 。除此之外，算法中的乘法、求幂和求逆都是比较简单的操作。

至此，我们便可更加形象地理解ElGamal算法的原理了。简单地说，由于 的特殊构造，集合中所有元素都可以表示为 α 的幂，当然 β 也可以表示成 α 的 t 次幂。由于 β 很大，以 α 底来求解其对数很难，因此只有Bob知道私钥 t ，其他人只知道公钥{ α , β , p }。剩下的过程非常简单：Alice利用 β ⁱ 对明文进行加权，而Bob用[( k ^a ) ^t ] ^-1 去除加权效果。因为：

在后续讨论中可以看到，ElGamal利用的离散对数问题也是数学难题，利用穷举或通用算法破解离散对数的计算复杂度非常高。并且，和RSA算法相比，ElGamal具有概率的特征，由于Alice选择随机密码 i 时有不确定性，对于相同的明文 m ₁ 和 m ₂ ，加密的密文是不同的。由于 i 也是在一个很大的集合中随机选择的，这显著增加了穷举型破解方式的计算复杂度。 XXzZQn6dfl4B78CE+drt3hh4wFuuSOt/ne99DvlRL9JFhLl0iXs1aN42JGD92nYN