ElGamal暗号 - crypto-writeup-public

通常は巡回群 $G$ として、乗法群 $Z_q$ が用いられる。

巡回群の位数と互いに素な値はその乗法巡回群の生成元となるから、 $g$ は適当な素数を選ぶ

$r \in {0..q-1}$ をランダムに選んで、 $c_1 = g^r, c_2 = mh^r$ を計算し、 $(c_1, c_2)$

$(c_1^x)^{-1}c_2 = (g^{rx})^{-1}mh^r = (h^r)^{-1}mh^r = m$

とはちょっと違うけど、 $(c_1, c_2)$ に対して $(c_1, 2c_2)$ とするだけで平文 $m$ が $2m$ になる

普通に乗法準同型性もあって、 $m$ を暗号化して $(c_1, c_2)$ 、 $m'$ を暗号化して $(c_1', c_2')$ がある時、 $(c_1c_1', c_2c_2')$ を計算すると、復号結果は $mm'$ になる

$(h^rh^{r'})^{-1}mm'h^rh^{r'} = mm'$