Document

ElGamal暗号
• １９８２年にElGamalによって提示
• 離散対数問題に基づく初めての公開鍵暗号
有限巡回群
G  {１ , a, a ,, a
2
n2
,a
n 1
}
G：aによって生成される有限巡回群
a：Gの生成元
p：素数
pを法とするaのべき乗は有限巡回群
例．p＝7を法としたとき、a＝3のべき乗を計算
することにより、有限巡回群であることを示す。
30 mod 7  1
36 mod 7  1
3 mod 7  3
3 mod 7  3
32 mod 7  2
38 mod 7  2
33 mod 7  6
39 mod 7  6
1
34 mod 7  4
35 mod 7  5
１
7

５
３
４
２
６
離散対数問題
p：素数
a：pを法とする生成元
b：b≠0
a  b (mod p)
x
整数 x を求める。
aとbがわかっていても，xを求めることは不可
能に近い。
例． p= 20000003 を法としてa=2,b=3とすると
3 = 2x mod 20000003
x =10502638
暗号方式
≪状況設定≫
〈共通鍵〉 { p , g }
〈秘密鍵〉 {s}
〈公開鍵〉 { y}
例．
p : (大きな )素数
g : mod pにおける生成元
s:0  s  p
y : y  g mod p
s
〈共通鍵〉 p  11, g  2
〈秘密鍵〉
s6
〈公開鍵〉
y  2 mod 11  9
6
≪暗号化≫
共通鍵（ g，p ）
公開鍵（ y ）
平文
暗号文
m
c1 : c1  g k mod p
{c1 , c2 }
c2 : c2  m  y mod p
乱数k
(mod (p-1))
例．アリス
メッセージm=10
乱数k=8
k
ボブ
c1  28 mod 11
3
c2  10  98 mod 11
8
暗号文
(c1 , c2 )  (3,8)
≪復号化≫
共通鍵（
秘密鍵（
p
s
）
）
s
1
復号文 m : m  c2  c mod p
暗号文
{c1 , c2 }
m
復号文m＝平文m
例．アリス
ボブ
暗号文(c1 , c2 )  (3 , 8)
m  8  36 mod 11
 10
復号文m＝10は、メッセージm となる。
ElGamal暗号の安全性
 離散対数問題の難しさ
解読するとしたら、
1秒に108回演算を行う能力を有するマシンを使用
鍵サイズ
512ﾋﾞｯﾄ
768ﾋﾞｯﾄ
1024ﾋﾞｯﾄ
300年
200万年
30億年

Download Report