エルガマル（ElGamal）暗号についての簡単な備忘録

エルガマル暗号とは

離散対数問題の困難性をもとにした公開鍵暗号方式の一種です。Tsher ElGamalによって発表されました。この暗号方式はランダムに生成される数(乱数)、3つの公開鍵、1つの秘密鍵によって成立しています。

秘密鍵と公開鍵について

ここで使用する秘密鍵と公開鍵は次のような条件を満たしているものとします。

v = a^s\:(mod\: p)

暗号化

※これは送信者が行う処理

1. 乱数rを生成する。ただし自然数。
2. 受信者の公開鍵p, a, vを用いて次の2つの数を生成し、送信する。

c_1 = a^r \:(mod\: p)\\
c_2 = wv^r \:(mod\: p)

復号

※これは受信者が行う処理

1. 秘密鍵sを用いて次のようにして平文wを生成する。

w = (c_1^s)^{-1}c_2 \:(mod\: p)