ElGamal暗号
鍵生成
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
参考