7回目

情報セキュリティ
第７回
ＤＨの鍵配送
脅威と暗号技術
セキュリティに対する脅威
盗聴
（秘密が漏れる）
脅かされる特性
暗号技術
共通鍵暗号
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
ＤＨ（Ｄｉｆｆｉｅ-Ｈｅｌｌｍａｎ）の鍵配送法

鍵配送方法



共通鍵を暗
号化して送る
公開鍵暗号系を使う方法
DHの鍵配送法を使う方法
ＤＨの鍵配送法




送信者はaをランダムに選
び yA(=ga mod p)と素数p
と原始元gを公開する。
受信者はbをランダムに選
びyB(=gb mod p)と素数p
と原始元gを公開する。
送信者はaと受信者の公
開情報yBを使って共通鍵
K=(yB )aを計算する。
受信者はbと送信者の公
開情報yAを使って、共通
鍵K=(yA )bを計算する。
公開鍵暗号系を使う方法
受信者
送信者
共
通
鍵
K
暗
号
化
公開鍵PＫ
暗号文c
復
号
共
通
鍵
K
秘密鍵SＫ
DHの鍵配送法を使う方法
送信者の
公開情報
受信者の
公開情報
素数p, 原始元g
yA(=ga mod p)
素数p, 原始元g
yB(=gb mod p)
送信者の
秘密情報
受信者の
秘密情報
a, K=(yB)a mod p
b, K=(yA)b mod p
共通鍵 K=gba mod p
共通鍵 K=gab mod p
「ＤＨ問題の難しさ」
≦「離散対数問題の難しさ」
 DH問題とは，公開情報（p,g,yA,yB）から鍵K（=gab mod p）を求める問題。
 離散対数問題とは，公開情報（p,g,yA,yB）からyA=ga mod pとyB=gb mod p
を満たす離散対数aとbを求める問題。
 離散対数問題が解ければ、DH問題は解ける。
 理由： aとbが得られれば鍵K（=gab mod p）を求めることが出来るから。
 従って、離散対数問題の方が難しい。このことを次のように書く：
「DH問題の難しさ」≦「離散対数問題の難しさ」
 ＤＨ仮説：ｐが大きいならばＤＨ問題を解く効率的なアルゴリズムはない。
問題を解く
アルゴリズム
入力
p,g,yA,yB
ＤＨ問題
アルゴ
リズム
出力
K = gab mod p
離散対数問題
p,g,yA,yB
アルゴ
リズム
a （yA=ga mod p）
b （yB=gb mod p）
「ＤＨ問題の難しさ」
＝「ＥｌＧａｍａｌ暗号の難しさ」
ＥｌＧａｍａｌ暗号を解くＡ
Pk=(p,g,gx)
C=(gr,mgxr)
公開情報
ＤＨ問題を解くB
(p,g,ga,gb)
m
A
公開鍵
暗号文
Aを使って
ＤＨ問題を解くB
(p,g,ga,gb)
共通鍵
m
R/m ≡ gab
gab
「DH問題の難しさ」≦「ElGamal暗号の難しさ」
gab
Bを使って
ElGamalを解くA
(p,g,gx,gr)
Rをランダム
に選ぶ
A
素数pに対し、
GF(p)は「体」
Pk=(p,g,gx)
C=(gr,mgxr)
Pk=(p,g,ga)
C=(gb,R)
B
B
gxr
mgxr/gxr ≡ m
平文
m
「DH問題の難しさ」≧「ElGamal暗号の難しさ」
「DH問題の難しさ」=「ElGamal暗号の難しさ」
高速べき乗法（多項式時間で解ける）
 ｙ=ax mod n を高速に計算する方法
べき乗計算はElGamalやRSAで現れる
 通常の方法
 x-1（≒2k、kはxのビット数）回の掛算： ax=a×a×…×a
乗算6回≒23回
 （例）７乗： a7=a×a×a×a×a×a×a
xk-1, xk-2 ,.., x0 は0又は1
 高速ベキ乗法
 xの２進数表示： x=(xk-1, xk-2, … , x0)2
x =0ならば掛算が不
2
k-1
要なので回数は減る
=x0+2x1+2 x2+…+2 xk-1
2
k-1
 k-1回の掛算： ax=ax0×a2x1×a2 x2×…×a2 xk-1
2(k-1)回
2
k-1
k-2
k-2
 k-1回の掛算： a2 =a×a, a2 =a2×a2,…,a2 =a2 ×a2
2
2
乗算4回
 （例）７乗： a2, (a2) , a7=a×a2×a2
i
通常の方法
高速べき乗法
2k
2(k-1)
計算回数
「指数関数」
K=1024ビットでは、約10306回
kはxのビット数
「多項式」
K=1024ビットでは2046回
公開鍵暗号の歴史
 １９７６年DiffieとHellmanは公開鍵暗号のアイディアを発表。
 １９７７年MerkleとHellmanはナップサック暗号を作成。
 １９７８年ＲｉｖｅｓｔとＳｈａｍｉｒとAdlemanはRSAを発表。




RSAは現在、公開鍵暗号のデファクト標準である。
１９８３年ＲＳＡ社はＲＳＡアルゴリズムを特許化。
１９９９年DiffieとHellmanとMerkleがＩＥＥＥ小林宏治記念賞を
受賞。
２０００年ＲｉｖｅｓｔとＳｈａｍｉｒとAdlemanがＩＥＥＥ小林宏治記念
賞を受賞。
２００２年ＲｉｖｅｓｔとＳｈａｍｉｒとAdlemanがTuring賞を受賞。

Download Report