密碼學/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 個整數，因此我們最終得到密文的大小是它們加密的訊息的兩倍。