ElGamal暗号
Gの元mを平文として受け取る。
rを { 0 , . . . , q − 1 } {\displaystyle \{0,...,q-1\}} からランダムに選ぶ。
c 1 = g r {\displaystyle c_{1}=g^{r}} , c 2 = m ⋅ h r {\displaystyle c_{2}=m\cdot h^{r}} を計算する。
( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} を暗号文とする。
受け取った暗号文を ( c 1 , c 2 ) ∈ G × G {\displaystyle (c_{1},c_{2})\in G\times G} とする。
m = c 2 ⋅ ( c 1 x ) − 1 {\displaystyle m=c_{2}\cdot ({c_{1}}^{x})^{-1}} とする。
実際、もし ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} が正しい方法で生成された暗号文であれば、 m ′ = c 2 ⋅ ( c 1 x ) − 1 = m ⋅ ( g x ) r ⋅ ( ( g r ) x ) − 1 = m {\displaystyle m'=c_{2}\cdot ({c_{1}}^{x})^{-1}=m\cdot (g^{x})^{r}\cdot ((g^{r})^{x})^{-1}=m} を満たす。