namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

暗号理論 [番外編] ~ ElGamal暗号 ~

ElGamal暗号とは

ElGamal暗号とは, 1984年にエルガマルによって提案された暗号です. ElGamal暗号は, 離散対数問題の計算困難性を安全性の担保として利用している暗号化手法になります.

事前知識

別の記事で, Diffie-Hellman鍵共有プロトコルの話をしました. Diffie-Hellman鍵共有プロトコルも, 離散対数問題の計算困難性を利用したプロトコルであるので, 一度そちらの記事を読んでいただいた方がスムーズに理解できると思います.

tomonori4565.hatenablog.com

追加で, オイラーの定理というものを紹介します.  a, mは互いに素である自然数とすると, 以下が成り立ちます.


 a^{\varphi(m)} \equiv 1 \ \ (mod \ \ m)

ここで,  \varphiとはオイラー関数というもので,  \varphi(m) mを超えない正の整数のうちで mと互いに素であるものの個数を指します. 例えば,  \varphi(8) = 4となります(8と互いに素な正の整数は1,3,5,7の4つであるため).

ElGamal暗号の仕組み

鍵生成アルゴリズム

f:id:tomonori4565:20181016163057p:plain

(1) kビットのランダムな素数 pと原始元 g \ \ (1 < g < p)を選択する.
(2)  0 \leq x \leq p-2となる整数 xをランダムに選択する.
(3)  y = g^x \ mod \ pを計算する.
(4)  pk = (p, g, y)を公開鍵として公開し,  sk = x秘密鍵として保管する.

暗号化アルゴリズム

f:id:tomonori4565:20181016163112p:plain

平文 m \ (0 < m < p), 公開鍵 pkを入力とします.

(1)  0 \leq r \leq p-2となる整数 rをランダムに選択する.
(2)  c_1 = g^r \ mod \ p \ とc_2 = my^r \ mod \ pを計算する.
(3)  c = (c_1, c_2)を暗号文として出力する.

復号化アルゴリズム

f:id:tomonori4565:20181016163122p:plain

暗号文 c, 公開鍵 pk, 秘密鍵 skを入力とします.

(1)  m' = c_2c_1^{p-1-x} \ mod \ p を計算して,  m'を出力する.

ElGamal暗号の正当性

ElGamal暗号において, 正当性をチェックしてみましょう.


 m'
 =  c_2c_1^{p-1-x} \ mod \ p
 = my^r \cdot g^{r(p-1-x)} \ mod \ p
 = mg^{rx} \cdot g^{r(p-1-x)} \ mod \ p
 = mg^{r(p-1)} \ mod \ p
 = m \cdot 1^r \ mod \ p \ (\because フェルマーの小定理より)
  = m \ mod \ p

したがって,  m' = mとなることがわかりました.

ElGamal暗号の安全性

盗聴者には pk, cが観測可能になります.しかし, y=g^x \ mod \ p \ (y,g,pは既知)から xを求めることは,離散対数問題の計算困難性から難しいとされています.したがって,秘密鍵が漏れない限りElGamal暗号は安全であると言われています.