公開鍵暗号 (一般)ElGamal暗号の勉強

公開鍵暗号の1つであるElGamal暗号について.
ElGamal暗号 - Wikipedia

一般ElGamal暗号については後述する. 詳しく知りたい人は 暗号技術のすべて を買おう. 余談だが私はほしい物リストに入れてたら誰かが買ってくれた. 誰なのかは未だわからない.

Key Generation

セキュリティパラメータをk [bits]とする.

• k [bits] の素数p を選択する
• Z_pから元を2つ選びg, xとし h = g^x mod p を計算する

公開鍵 : (g, h, p)
秘密鍵 : x

Encrypt

平文mを受け取る暗号化関数は以下のように定義される.
Z_pから元を1つ選択しrとする.

Enc(m) := (c1, c2) = (g^r mod p , m*h^r mod p)

(c1, c2) を暗号文とする.

Decrypt

暗号文c1, c2を受け取る復号関数は以下のように定義される.

Dec(c1, c2) := c2 * (c1^x)^-1 mod p

Dec(c1, c2) = m になることを確認しよう.

まずはc1から

c1^x = g^rx

次にc2

c2 = m * h^r
= m * (g^x)^r
= m * g^rx

最後に

c2 * (c1^x)^-1 mod p
= m * g^rx * (g^rx)^-1 mod p
= m

平文が復号できた.

乗法準同型

ElGamal暗号は乗法準同型を持っていて, 平文mを暗号化した(c1, c2)のc2をt倍して復号すると平文mをt倍したものが得られる.

たとえば3倍する場合だと次のようになる.

c1, c2 = Enc(m)
Dec(c1, 3 * c2) = 3 * m

確認しよう.
c2をt倍して復号する. c2' = t*c2

Dec(c1, c2') = c2' * (c1^x)^-1 mod p
= c2' * (c1^x)^-1 mod p
= t * m * g^rx * (g^rx)^-1 mod p
= t * m mod p

復号オラクルが使用できる場合, 選択暗号文攻撃に弱い.

一応検証コードを置いておく.

test_elgamal

実は選択暗号文攻撃以外にも, 鍵生成を失敗すると攻撃者に暗号文を解読されてしまう可能性がある. 次の説でElGamal暗号の安全性について話をする.
Wikipediaではちゃんとセキュリティを考慮した鍵生成の解説がなされている.

安全性

結論を先に言うと, ElGamal暗号で重要なのは素数pの選択である.

Z_*pの位数は p-1 であり, Z_*pの元gが作る部分群の位数は p-1 以下になるのだが, ラグランジュの定理により, gによる部分群の位数は p-1 を割り切る数字となる.

p-1 は偶数なので, 位数が2である群と (p-1)/2 が位数の部分群が少なくとも存在する.
他にも約数を持つ場合, gによる部分群の位数が小さくなる.

また, φ(p) = p-1 が複数の小さな素数の積で表すことができるとき, Pohlig–Hellman algorithmによって解読が簡単化される. Pohlig–Hellman algorithm - Wikipedia

これを回避するために, 最初の素数選択では安全な素数(safe prime)を使うことが推奨されている.

safe primeとはある素数pに対して, 2p + 1 も素数である時の2p + 1のことである.
たとえば, 3は素数であり 2*3 + 1 = 7も素数なので7はsafe primeといえる.
言い換えると (p-1)/2 が素数であるp.

q = 2*p + 1; (p ,q はそれぞれ素数) としてElGamal暗号を考える.

このとき

φ(q) = 2*p + 1 - 1 = 2*p

であり, φ(q)の約数は2と大きな素数pに限定される.

φ(q)が2*pではPohlig–Hellman algorithmは効果を発揮できないため弱点を克服できた.

次は部分群の位数が素数になるようにしよう.
pが素数のとき g^x ≡ 1 (mod p) の最小のxがp-1であればgは原始元となる. 原始元とはもとの群と部分群の位数が同じになるような元である(素体を扱っているので原始元と呼んでいる. 生成元でもよい).

|{g, g², g³, ..., 1}| = p-1
のとき g は原始元

適当な原始元を選択し, 次のような式を考える.

α = g^(q-1)/p mod q

q = 2*p + 1 であれば

α = g^{(2p + 1 -1)/p} mod q
α = g² mod q

Z_*qの原始元gを2乗したαを使って部分群を生成すると位数が素数になる.
これはαのp乗が1になれば確認できる.

α^p = (g^(q-1)/p)^p mod q
α^p = g^q-1 mod q
= 1

Z_*qの原始元gによって作られる部分群の位数はq-1になるが, g²によって作られる部分群の位数はpでありこれは素数である.

まとめ

一般ElGamalに関する記述が見当たらない. 安全性のあたりから曖昧な記憶を頼りに書いてしまったのでまたちゃんと勉強して書き直す.