密码学/ElGamal

ElGamal 是基于离散对数问题的最简单的密码系统之一。离散对数问题的快速提醒 - 给定 $g,h\in G$，使得 $h=g^{x}$，找到 $x$。当处理有限集时，这是一个难题。ElGamal 有一组公共参数，可以被系统中的许多用户共享。这些被称为域参数。这些参数是

- $p$ - a large prime of around 1024 bits (currently) such that $p-1$ is divisible by another prime $q$ of around 160 bits.
- $g$ - an element of the finite field $F_{p}^{*}$ with order divisible by $q$, that is $g^{(p-1)/q}(modp)\neq 1$.

域参数创建一个公共组 $G$，具有素数阶 $q$ 和一个生成器 $g$。换句话说，我们创建了一个庞大但有限的群，以及对该群进行排序的方法（生成器），我们知道它将包含素数个元素。这些是我们追求的属性。这些参数是公开的，系统的安全性取决于公钥和私钥对，我们将在下一步生成它们。

私钥 $x$ 是一个随机选择的整数。公钥是 $h=g^{x}(modp)$。

为了加密消息 $m$，我们生成一个随机的短暂密钥 $k$，并计算：$c_{1}=g^{k}c_{2}=m*h^{k}$

这给了我们密文 $c=(c_{1},c_{2})$。

为了解密密文，我们计算：${\frac {c_{2}}{c_{1}^{x}}}={\frac {m*h^{k}}{g^{x*k}}}={\frac {m*g^{x*k}}{g^{x*k}}}=m$

正如您从解密方法中看到的，消息 0 会加密成它本身，因此不是一个好的消息选择。除此之外，由于使用短暂密钥 $k$，每次都会改变，您可以看到相同的消息 $m$ 会加密成许多不同的密文。

由于密文表示为与消息长度相同的 2 个整数，因此我们最终得到密文的大小是它们加密的消息的两倍。