ElGamal暗号
鍵生成
大きな素数$ pと$ Z^\ast_pの原始元$ gを選ぶ $ x \in Z_{p-1}をランダムに選び、$ y=g^x\bmod pを計算する
$ xは$ \{2,\cdots p-2\}のいずれか
公開鍵として$ P_K=(p,g,y)
秘密鍵として$ S_K=x
$ pは大きな素数でないと攻撃できてしまう。1024bit以上が望ましい
暗号化
公開鍵$ P_Kと、平文$ m\in Z_pを入力とし、暗号文$ C=(c_1,c_2)を以下のようにして決める
$ c_1\equiv g^r\bmod p, $ c_2\equiv my^r\bmod p
↑$ m*y^rね
$ r\in Z_{p-1}はランダム
なので、暗号化するたびに違う暗号文になる
ここの$ rが離散対数問題に基づいて、攻撃者は求められないはず！ 求められたら終わる
復号
秘密鍵$ xと暗号文$ Cを用いて以下のようにして平文$ mを複合する
$ m\equiv c_2c_1^{p-1-x}\bmod p
↑$ c_2*c_1^{p-1-x}ね
原理
$ c_2c_1^{p-1-x}\equiv my^{r}\times g^{r(p-1-x)}\equiv mg^{rx}g^{-rx}g^{r(p-1)}\equiv mg^{r(p-1)} \bmod p
参考