鍵共有グラフを用いた 絶対に安全な鍵共有 西関研究室 7669 印藤 嘉浩 研究内容 • 秘密の漏えいを防ぐためさまざまな暗号が用いられている. • コンピュータの進歩に伴い計算速度は年々速くなっている. • 無限の計算能力をもつ盗聴者Eve がいると仮定し,計算量的 安全性に基づく暗号が使えない環境を考える. • 情報理論的に安全であり,無限の計算能力をもつ盗聴者Eve でさえ解読不可能であるone-time pad暗号と鍵共有グラフを 利用して秘密を共有する方法を考える. 2 仮定 • • • • プレーヤー と盗聴者Eve いくつかのプレーヤーの対が秘密鍵を事前に共有 簡単化のために秘密鍵と共有したい秘密は1ビット 鍵共有グラフ [2] Eve 3 仮定 • 秘密鍵を共有している2人のプレーヤーだけがその値を知っ ており,他のプレーヤーと盗聴者Eveはその値を知らない. • 全てのプレーヤーと盗聴者Eveは鍵共有グラフの形を知って いる. • プレーヤー間の通信は公衆通信網を用いる. →プレーヤー間の全ての通信は盗聴者Eveに盗み聞きされる. • 盗聴者Eveは無限の計算能力を持っている. →計算量的安全性に基づく暗号は使用できない. • 全てのプレーヤーは,信頼でき,プロトコルに従った動きをす る. 4 Eve 5 絶対に安全に • メッセージを共有したいプレーヤーだけがメッ セージを共有でき,盗聴者Eveや他のプレー ヤーはメッセージに関する情報を全然得るこ とができないとき,絶対に安全にメッセージを 共有できるという. Eve 6 指定された2人のプレーヤーだけ での絶対に安全なメッセージ共有 7 Eve 8 指定された2人のプレーヤーだけ での絶対に安全なメッセージ共有 9 任意の2人のプレーヤーだけ での絶対に安全なメッセージ共有 2連結である例 2連結でない例 10 任意の2人のプレーヤーだけ での絶対に安全なメッセージ共有 2連結である例 2連結でない例 11 指定された3人のプレーヤーだけでの 絶対に安全なメッセージ共有 12 まとめ • 2人のプレーヤーが絶対に安全にメッセージを共有させるこ とができるプロトコルが存在するための必要十分条件を示し, 証明した. • 3人のプレーヤーが絶対に安全にメッセージを共有させるこ とができるプロトコルが存在するための十分条件を示し,証 明した. • 今後は,3人のプレーヤーが絶対に安全にメッセージを共有 させることができるプロトコルが存在するための必要十分条 件を求める. 13 参考文献 • [1] T. Mizuki, S. Nakayama and H. Sone, “An application of stnumbering to secret key agreement,” Int. J. Foundations of Computer Science, to appear. • [2] T. Mizuki, T. Sato and H. Sone, “A one-round secure message broadcasting protocol through a key sharing tree,” Inf. Proc. Let., 109, pp. 842-845, 2009. • [3]C. Shannon, “Communication theory of secrecy systems,” Bell System Technical Journal, Vol. 28, pp. 656-715, 1949. 14 以下予備スライド 15 既存研究 • フラッディングプロトコルを用いたメッセージ共有 – フラッディングプロトコル • ネットワーク上に接続された送信可能なすべての端末に対して, 多数のパケットやフレームをほぼ同時に洪水(flooding)のように 送出したり,受信する方法. • ある1人のプレーヤーが鍵共有グラフ内の全てのプレーヤーに メッセージを伝える方法 Eve 16 プロトコルの実行(1) • がメッセージ を全てのプレーヤーに送りたいとする. • に隣接する と にメッセージとそれぞれと共有した秘密鍵との排 他的論理和を伝える. • と は受け取った値と と共有した秘密鍵との排他的論理和を計算 することでメッセージを得る. Eve 17 プロトコルの実行(2) • 今,メッセージを得た は隣接する セージを暗号化して伝える. と に, は隣接する にメッ • 受け取ったそれぞれのプレーヤーは,復号化をしてメッセージを得る. Eve 18 プロトコルの実行(3) • • の隣接する は隣接する はすでにメッセージを得ているので, は何もしない. と にメッセージを暗号化して伝える. • 受け取ったそれぞれのプレーヤーは,復号化をしてメッセージを得る. Eve 19 プロトコルの実行(4) • の隣接する はすでにメッセージを得ているので, 暗号化して送る. • 受け取った にメッセージを は復号化をしてメッセージを得る. Eve 20 プロトコルの実行 • 終了 Eve • フラッディングプロトコルは鍵共有グラフ内の全てのプレーヤーにメッ セージを送る方法 →全てのプレーヤーではなくグラフ内の何人かだけに送るにはどうする かを考えた. 21 既存研究 • 秘密鍵がEveに知られている可能性を考えた研究 – 各々辺には,Eveに秘密鍵が知られている確率が与えら れている. Eveは,鍵 をちょう ど0.9の確率で知って いて,ちょうど0.1の確 率で知らない. Eve 0.8 0.1 0.9 0.2 0.2 0.3 • このときどんな2人のプレーヤー でも最も安全に(Eveがメッセージ を得ることができる確率が最も低い) メッセージを共有するためのプロトコルを 与えた研究 0.8 0.4 0.1 0.7 0.9 0.7 22 計算量的安全性 • 暗号を解読するためのアルゴリズムの計算量が膨 大であり,現実的な時間で解読することができない ことに着目した安全性の概念 • RSA 暗号で用いられているのは素因数分解問題 →無限の計算能力をもつEveは解読可能 • 問題点 – 無限の計算能力をもつ盗聴者Eveには安全性を 保つことができない – 新しい解読方法が見つかると解読にかかる計算 量が減少 23 情報理論的安全性 • 情報理論に基づいて暗号文や公開されている情報 から得られる解読するための情報の情報量に着目 した安全性の概念 • C. Shannonがone-time pad暗号は解読不可能であ ることを数学的に証明 [3]. • 情報理論的安全性は,計算量的安全性より強い安 全性を有する. 24 無条件安全性 25 無条件安全性 26 内素な道 内素である , P_ P 内素でない 27 Eve 28 メッセージ伝達方法 • 2人の間に道 が存在する場合 29 指定された2人のプレーヤーだけ での絶対に安全なメッセージ共有 30 定理1の十分性の証明(1) • • • に辺 が存在する場合 は と暗号化して, に送る. は を計算して を復号化する. ( は共有したいメッセージ) 31 定理1の十分性の証明(1) • に辺 が存在する場合 • Eve:one-time pad暗号を用いているので解読 できない. • 他のプレーヤー: one-time pad暗号を用いて いるので解読できない. 32 定理1の十分性の証明(2) • と 間に内素な2本の道が存在する場合 33 定理1の十分性の証明(2) • と 間に内素な2本の道が存在する場合 • 道 上のプレーヤー: • 道 上のプレーヤー: → を得るが, を得るが, を得ることはできない. を得ることはできない. を計算することができない. • Eveや他のプレーヤー:one-time pad暗号を用いているので 解読できない. 34 定理1の必要性の証明(1) • と – 間に道が存在しない場合 と が異なる連結成分に含まれている 35 定理1の必要性の証明(2) • に辺 がなく, と 存在する場合 間に道が1本だけ 36 無条件安全性 37 無条件安全性 38 定理1の必要性の証明(3) • 補題1,補題2より定理1の必要性が証明された. 39 任意の2人のプレーヤーだけ での絶対に安全なメッセージ共有 • 2連結:カット点のない連結グラフ. • カット点 :連結グラフ から点 を除去すると 連結でなくなるとき. 40 指定された3人のプレーヤーだけでの 絶対に安全なメッセージ共有 41 定理2の十分性 42 定理2の十分性 43 定理2の十分性 44 定理1の必要性の準備 45 定義:鍵情報 1 0 0 1 1 0 1 1 0 46 定義:乱数集合 1 0 0 1 1 0 1 1 0 47 定義:会話 • プロトコルを実行したときにブロードキャストさ れた暗号文を並べたもの 48 定義:プロトコルポイント 49 以下暗号系 スライド 50 素因数分解問題 • 合成数を素数の積に分解する問題,小さな合 成数に対しては,短時間で素因数分解実施 可能であるが,大きな数については現実的な 時間内に計算を終えることは困難. 51 離散対数問題 52 定義 • 平文: – 暗号化する前の文章 • 暗号化: 平文 暗号化 – 平文を暗号文にするアルゴリズム 暗号文 • 暗号文: – 暗号化したメッセージ 平文 復号化 • 復号化: – 暗号文を平文にするアルゴリズム 暗号文 53 暗号の種類(1) • 公開鍵暗号 – 暗号化と復号化で使われる鍵が異なる暗号方式 – 暗号化に使う鍵:公開鍵 公開鍵 – 復号化に使う鍵:秘密鍵 – 例:RSA暗号 平文 暗号化 暗号文 • 公開鍵≠秘密鍵 秘密鍵 – 数学的関係 平文 復号化 暗号文 54 暗号の種類(2) • 共通鍵暗号 – 暗号化と復号化で使われる鍵が同じである暗号 方式 – 例:DES,AES 秘密鍵 – one-time pad暗号 平文 暗号化 暗号文 秘密鍵 平文 復号化 暗号文 55 one-time pad (使い捨てパッド)暗号 • 排他的論理和の性質を利用した共通鍵暗号 • 無限の計算能力をもった盗聴者Eveであって も解読が不可能 – 絶対に安全な暗号 • 平文と秘密鍵のビット長が同じ暗号 56 one-time pad 暗号 暗号化 復号化 • 相手に送りたい: m=10011100 • 事前に共有した秘密鍵: k=01001110 • 暗号文: c=11010010 を受け取る • 事前に共有した秘密鍵: k=01001110 • 暗号文: c=11010010 を送る • 平文: m=10011100 を得る 57 one-time pad暗号は解読できない • 平文:10011100 • 秘密鍵:01001110 • 暗号文: 11010010 – Eveが分かるのは暗号文11010010のみ – Eveは鍵を00000000から順に11111111まで試し ていく – あるとき01001110で復号化し10011100を得たと する.しかし,それが本当の平文であるかをEve は確認することができない. 58 one-time pad暗号を使う理由 • one-time pad暗号は,情報理論的安全性を有し,無限の計 算能力をもつEveにさえ解読不可能な暗号 59 復号化≠解読 • 解読 – 受信者以外の第三者が暗号文から平文を得よう とすること • 復号化 – 受信者が復号化の鍵で暗号文を平文にすること 60 ブルート・フォース・アタック • Brute force attack 総当たり攻撃 – 鍵になりうる候補の中から本当の鍵を順番にす べて試す方法である. – one-time pad暗号を解読することはできない 61 RSA • 開発者の名前Ron Rivest, Adi Shamir, Leonard Adleman の頭文字をとってつけられた公開鍵 暗号のひとつ • 計算量的安全性を有する暗号 62 RSA 暗号化と復号化 63
© Copyright 2025 ExpyDoc