鍵共有法 廣瀬勝一 廣瀬 鍵共有法 1 / 18 話題 鍵事前配布法 (key pre-distribution scheme) • Blom 法 • Diffie-Hellman 法 オンライン鍵共有法 (on-line key establishment protocol) • Diffie-Hellman プロトコル • 認証付 Diffie-Hellman プロトコル 廣瀬 鍵共有法 2 / 18 Blom の鍵事前配布法 Blom, 1985 年 信頼できるセンタ (TA) の存在を仮定する k 人以下の利用者の結託に対して無条件に安全 利用者を U1 , U2 , . . . , Un とする • p は素数で n ≤ p • 配布される鍵は Zp の要素 • 各利用者 Ui は ri ∈ Zp を割り当てられる． i ̸= j のとき ri ̸= rj ．Ui の ID を ri として利用できる． • p と r1 , . . . , rn は公開される． 廣瀬 鍵共有法 3 / 18 Blom の鍵事前配布法 TA によるセットアップ 1 0 ≤ i ≤ k, 0 ≤ j ≤ k について ai,j ∈ Zp を無作為に選ぶ． • すべての i, j について ai,j = aj,i を満たすように選ぶ． • ai,j は TA のみが知る秘密情報 多項式 f (x, y) を以下のように定める． f (x, y) = k ∑ k ∑ ai,j xi y j mod p i=0 j=0 2 多項式 fUs (x) = f (x, rs ) mod p を計算し，安全な通信路を用いて Us に送る． 廣瀬 鍵共有法 4 / 18 Blom の鍵事前配布法 鍵共有 Us は Ut との間の秘密鍵 Ks,t を以下のように計算する． Ks,t = fUs (rt ) mod p ここで Ks,t = fUs (rt ) mod p = f (rt , rs ) mod p である．一方，Ut が計算する Us との間の秘密鍵 Kt,s は Kt,s = fUt (rs ) mod p = f (rs , rt ) mod p である．次に述べるとおり Ks,t = Kt,s である． 廣瀬 鍵共有法 5 / 18 Blom の鍵事前配布法 f (x, y) = k ∑ k ∑ ai,j xi y j i=0 j=0 = k ∑ k ∑ aj,i y j xi (ai,j = aj,i より) i=0 j=0 = = k ∑ k ∑ v=0 u=0 k k ∑ ∑ au,v y u xv ((i, j) → (v, u)) au,v y u xv (加算の順序を変更) u=0 v=0 = f (y, x) 廣瀬 鍵共有法 6 / 18 例（k = 1 のとき） TA は a0,0 , a0,1 , a1,0 , a1,1 ∈ Zp を無作為に選ぶ．ただし a0,1 = a1,0 ． • 簡単のため a0 = a0,0 , a1 = a0,1 = a1,0 , a2 = a1,1 と書く． • a0 , a1 , a2 は TA のみが知る秘密情報． f (x, y) = a0 + a1 (x + y) + a2 x y mod p Us は TA から以下の多項式を受け取る． fUs (x) = (a0 + a1 rs ) + (a1 + a2 rs ) x mod p Us と Ut の共有する秘密鍵は Ks,t = fUs (rt ) mod p = fUt (rs ) mod p = a0 + a1 (rs + rt ) + a2 rs rt mod p 廣瀬 鍵共有法 7 / 18 例（k = 1 のときの方式の安全性） 単一の第三者 Uu は，秘密鍵 Ks,t の情報を一切得ることが出来ない． Ks,t = a0 + a1 (rs + rt ) + a2 rs rt def fUu (x) = (a0 + a1 ru ) + (a1 + a2 ru ) x = cu,0 + cu,1 x このとき a0 a0 Ks,t 1 rs + rt rs rt def cu,0 = 1 ru 0 a1 = M a1 cu,1 0 1 ru a2 a2 ru ̸= rs , rt なので，det(M ) = (ru − rs )(ru − rt ) ̸= 0 したがって，(a0 , a1 , a2 ) と Ks,t とは 1 対 1 対応 廣瀬 鍵共有法 8 / 18 例（k = 1 のときの方式の結託に対する非安全性） Us と Ut が結託して互いの秘密情報を教えあったと仮定すると def fUs (x) = (a0 + a1 rs ) + (a1 + a2 rs ) x = cs,0 + cs,1 x def fUt (x) = (a0 + a1 rt ) + (a1 + a2 rt ) x = ct,0 + ct,1 x したがって，Us と Ut は， a0 + a1 rs = cs,0 a1 + a2 rs = cs,1 a0 + a1 rt = ct,0 a1 + a2 rt = ct,1 により a0 , a1 , a2 を計算できる． 廣瀬 鍵共有法 9 / 18 Diffie-Hellman 鍵事前配布法 Diffie & Hellman, 1976 年 盗聴のある安全でない通信路を介して秘密鍵を共有する方式 • Diffie-Hellman 問題を解くことが現実的に不可能であれば安全 • 信頼できるセンタを必要としない Diffie-Hellman 問題 (DHP) p は素数 g は乗法群 Z∗p の位数 q の元 α = g x mod p．ただし x ∈ Zq β = g y mod p．ただし y ∈ Zq DHP 入力 出力 p, q, g, α, β g x y mod p 仮定 x, y が無作為に選択されるならば DHP を解くことは困難 廣瀬 鍵共有法 10 / 18 Diffie-Hellman 鍵事前配布法 p は素数 g は乗法群 Z∗p の位数 q の元 Alice Bob 秘密鍵 sA ∈ Zq sB ∈ Zq 公開鍵 vA = g sA mod p vB = g sB mod p Alice と Bob とが共有する秘密鍵 K = g sA sB mod p = vB sA mod p = vA sB mod p 廣瀬 鍵共有法 11 / 18 オンライン Diffie-Hellman プロトコル p は素数 g は乗法群 Z∗p の位数 q の元 Alice rA ∈ Zq Bob rB ∈ Zq uA uA = g rA mod p uB = g rB mod p uB Alice と Bob とが共有する秘密鍵（セッション鍵と呼ばれる） K = g rA rB mod p = uB rA mod p = uA rB mod p 廣瀬 鍵共有法 12 / 18 オンライン Diffie-Hellman プロトコルの安全性 DHP が解けなければ，オンライン DH プロトコルは受動的な攻撃者に対 して安全である． しかし，能動的な攻撃者に対しては安全ではない． 受動的な攻撃者はやり取りされるメッセージの盗聴のみを行う． 能動的な攻撃者はメッセージの改竄なども行う． 廣瀬 鍵共有法 13 / 18 オンライン DH プロトコルへの man-in-the-middle 攻撃 Eve を能動的な攻撃者とする． Eve は以下のようにして，Alice，Bob のそれぞれとセッション鍵を共有 できる． Alice rA ∈ Zq uA = g rA mod p Eve uA uE rE ∈ Zq uE = g rE mod p Bob uE uB rB ∈ Zq uB = g rB mod p KAE = g rA rE mod p KBE = g rB rE mod p 廣瀬 鍵共有法 14 / 18 認証つき DH プロトコル Alice Bob rA ∈ Zq uA = g rA mod p rB ∈ Zq IDA, s, uA IDB, s, uB, β VerB(β, (IDB , IDA, s, uB, uA)) = true? IDA, s, α ) α = SignA(IDA, IDB, s, uA, uB) uB = g rB mod p β = SignB(IDB, IDA, s, uB , uA) VerA(α, (IDA, IDB, s, uA, uB)) = true? • IDA , IDB はそれぞれ Alice, Bob の ID を表す． • s はセッション ID である． 廣瀬 鍵共有法 15 / 18 似ているが安全でないプロトコル Alice Bob rA ∈ Zq uA = g rA mod p rB ∈ Zq IDA, s, uA IDB, s, uB, β uB = g rB mod p β = SignB(uB, uA) VerB(β, (uB , uA)) = true? α = SignA(uA, uB) IDA, s, α ) VerA(α, (uA, uB)) = true? 異なる点 署名されるメッセージに ID が含まれていない． 廣瀬 鍵共有法 16 / 18 攻撃 Alice Eve Bob rA ∈ Zq uA = g rA mod p rB ∈ Zq IDA, s, uA IDE, s, uA uB = g rB mod p β = SignB(uB, uA) IDB, s, uB, β VerB(β, (uB , uA)) = true? γ = SignE(uA, uB) α = SignA(uA, uB) IDA, s, α ) IDE, s, γ VerE(γ, (uA, uB)) = true? • Alice と Bob のみがセッション鍵 KAB = g rA rB mod p を知っている． • Alice は Bob と KAB を共有したと信じている． • Bob は Eve と KAB を共有したと信じている． 廣瀬 鍵共有法 17 / 18 演習問題 1 k = 2 の場合の Blom 方式を示し，任意の二人の利用者が秘密鍵を共 有できることを確認せよ． 2 Diffie-Hellman 問題を利用して，3 人以上の利用者がセッション鍵を 共有する方法を考えよ． 廣瀬 鍵共有法 18 / 18
© Copyright 2024 ExpyDoc
![[ HAMMER MOD with Taifun GT ] CLONE SET 使用説明書](http://s3.expydoc.com/store/data/007323535_1-68122d95f85d4a86c536d92286d4704f-250x500.png)
