鍵共有グラフを用いた 絶対に安全な鍵共有 西関研究室 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連結でない例 10 任意の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 定理２の十分性 42 定理２の十分性 43 定理２の十分性 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 2024 ExpyDoc
