Presentation is loading. Please wait.

Presentation is loading. Please wait.

情報セキュリティ 第3回 現代暗号の基礎数理. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号.

Similar presentations


Presentation on theme: "情報セキュリティ 第3回 現代暗号の基礎数理. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号."— Presentation transcript:

1 情報セキュリティ 第3回 現代暗号の基礎数理

2 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号 一方向ハッシュ関数 メッセージ認証コード デジタル署名

3 情報理論的安全性 その1 暗号化アルゴリズム E 平文 m と鍵 k とアルゴリズム E から暗号文 c=E(k,m) が決まる。 確率変数 m, k, c 平文 m は集合 M={m 1,m 2,..} の中の 1 つであり、 どの平文かは確率分布で決まる。但し、任意 の平文 m i ∈ M に対し、 Pr(m=m i )>0 を満たす。 鍵 k は、集合 K={k 1,k 2,..} の中の 1 つであり、どの 鍵かは確率分布で決まる。 暗号文 c は、 c=E(k,m) から定まる集合 C={c 1,c 2,..} の中の 1 つである。 暗号化 E 確率分布に従って発 生 暗号文 c 平文 m 鍵k鍵k 平文と鍵の確率 分布に依存して 決まる m=m 1 (緑) m=m 2 (赤) m=m 3 (青 ) Pr(m)1/3 集合 M={m 1,m 2,m 3 } 平文 m の確率分布 確率 0 はダメ 確率分布に従っ て発生 k=k 1 k=k 2 k=k 3 Pr(k)1/3 集合 K={k 1,k 2,k 3 } 鍵 K’ の確率分布 「確率変数 m 」とは、平 文が集合 M の中のどれか の値を一つ取るため「変 数」(定数でない)であ り、どれを取るかは確率 によって決まるから、 「確率変数」という。 全く使わ れない平 文 m i は無 い

4 情報理論的安全性 その 2 情報理論的に安全とは 任意の m i ∈ M と c j ∈ C に対し、 Pr(m i |c j )=Pr(m i ) 条件付確率の定義: Pr(m i |c j ) = Pr(m i,c j ) / Pr(c j ) 暗号化 E 敵 Pr(m|c) Pr(m) 暗号文 c 平文 m = 鍵k鍵k 暗号文 c から何も 情報が得られない Pr(m|c)=Pr(m) 平文 暗号 文 赤 青 緑 E(m,k 1 ) 平文 暗号 文 赤 青 緑 平文 暗号 文 赤 青 緑 E(m,k 2 ) E(m,k 3 ) c1c1 c2c2 c3c3 m=m 1 (緑) m=m 2 (赤) m=m 3 (青 ) Pr(m)1/3 k=k 1 k=k 2 k=k 3 Pr(k)1/3 Pr(m|c)≠Pr(m) 平文 暗号 文 赤 青 緑 E(m,k 1 ) 平文 暗号 文 赤 青 緑 平文 暗号 文 赤 青 緑 E(m,k 2 ) E(m,k 3 ) c1c1 c2c2 c3c3 暗号文が赤( c 1 ) の場合、平文が 赤である確率が 高い。 平文 m=m 1 ( 赤 ) 鍵 k 1 で決 まる置換 感覚的に分 かりずらい 具体的なイ メージで説 明 暗号文 c j が与えられた場合、 c j の平文が m i である確率

5 安全性 情報理論的に安全ならば、 |K| ≧ |M| ( |K| は集合 K の要素 数) 暗号文 c から平文 m へ一意に復号 出来るためには、異なる平文 m に対し異なる鍵 k が必要になる。 任意の暗号文 c j ∈ C に対し、集合 M の全ての平文が c j に対する平文で ある可能性を持つ。なぜならば、 任意の m i ∈ M と c j ∈ C に対し、 Pr(m i |c j )=Pr(m i ) かつ、 Pr(m i )>0 以上から、鍵の数 |K| を平文の数 |M| よりも少なくすることは出来 ない。 計算量理論的に安全 情報理論的に安全でなくても、 計算時間が大きい(例えば10 億年)ならば安全と考える。 擬似ランダム置換族は計算量理 論的安全性の基本構成要素であ る。 m1m2::mim1m2::mi ::cj::::cj:: m1m2::mim1m2::mi 暗号化 E k 復号 D k k1k1 k1k1 暗号文 c j に対して、全ての平 文が c j に対する平文の候補で ある m1m2::mim1m2::mi ::cj::::cj:: m1m2::mim1m2::mi k1k1 k2k2 二つの異なる平文を同じ鍵で 同じ暗号文にすると、どちら に復号していいかわからない k1k1 k2k2 ? 同じ鍵 はダメ kiki kiki 平文の集合 M={ 緑、赤、青 } の例では、 |M|=|K|=3

6 識別不可能性 選択平文攻撃 神様は {0,1} n 上のランダム置換族 P n とその部分集合 A n を知ってい る。 神様に m ∈ {0,1} n を質問すると、 c=π(m) (暗号文)を教えてくれ る。 識別アルゴリズム D の識別利得 Adv(D)=|P random - P A | P random とは: P n から選ばれた π が D =1 を出力 する(置換がある性質を持つ) 確率。 P A とは: A n (暗号アルゴリズムの置換集 合)の中の置換が D=1 を出力す る確率。 擬似ランダム置換族 質問回数をある値に制限した時、 どんな D に対しても、 Adv(D)<ε ( ε は非常に小さい値を表す)と なるとき、 A n は擬似ランダム置 換族と呼ぶ。 神様への質問回数は現実的な値 に制限する。例えば、 2 50 (=10 15 ) 回。 AnAn PnPn D =1 PA=PA= 交わりの面積 |A n | P random = D =1 の面積 |P n | D は A n の識別に有効 識別アルゴリズ ム D が 1 を出力す る置換族 ランダム置換族 0001 0110 100011 {0,1} 2 の置換 π 暗号アルゴリ ズムの置換族 暗号アルゴリ ズムは置換族 A n であるが、 A n を特定する のに時間がか かる

7 Feistel 型構造 ( DES 暗 号 ) ラウンド関数 F i は {0,1} n から {0,1} n への任意の関 数。 Feistel 型構造は逆関数 が存在する(上への 1 対 1 )ので {0,1} 2n 上の 置換。 Feistel 型構造への入力 を (L 0,R 0 ) とする。但し、 L 0 ∈ {0,1} n 、 R 0 ∈ {0,1} n 。 i=1,..,u に対して、 L i =R i-1 、 R i =L i-1 F i (R i-1 ) 。 DES 暗号は 16 段の Feistel 型構造である。 F1F1 F2F2 FuFu L0L0 R0R0 L1L1 R1R1 L2L2 R2R2 LuLu RuRu : FuFu F1F1 RuRu LuLu R u-1 L u-1 R u-2 L u-2 R0R0 L0L0 : F u-1 u 段構造 逆関数 1段1段 2段2段 u段u段 R u F u (L u ) =L u-1 F u (R u-1 ) F u (R u-1 ) =L u-1 RuRu F u (L u ) 暗号化 復号 平文は 2n ビッ ト 暗号文 ラウンド関 数

8 2 段 Feistel は擬似ランダム置換族でな い F1F1 F2F2 0n0n 0n0n 1n1n 0n0n a=0 n F 1 (0 n ) b F1F1 F2F2 a’=1 n F 1 (0 n ) b’ 入力 =(0 n,0 n ) の場合 入力 =(1 n,0 n ) の場合 2 段 Feistel 型構造の置換集合 ψ ( F 1,F 2 ) 識別アルゴリズム D: if (a a’=1 n ) then D=1 else D=0 但し、 a=0 n F 1 (0 n ) 、 a’=1 n F 1 (0 n ) P ψ ( F1, F2) =Pr(D=1)=1 証明: a a’=0 n F 1 (0 n ) 1 n F 1 (0 n )=1 n D の識別利得 Adv(D) = |P random - P ψ ( F1, F2) | > 1-1/2 n-1 0 n =00….0 n 十分大きい F 1 と F 2 は独 立な擬似 ランダム 関数 P 2n D =1 ψ ( F 1,F 2 ) P random =N 3 /N 2 N 3 と N 2 は「復習 3」で求める 攻撃のた めに選択 した平文 暗号文 敵は D=1 となる置換だ けを解読の対象に出来 る

9 強擬似ランダム 3段 Feistel 型構造は擬似ランダム置換である が強擬似ランダム置換でない。 4段 Feistel 型構造は強擬似ランダム置換 強擬似ランダム置換族とは: 長さ 2n のランダム置換族 P 2n の部分集合 A 2n が、選択暗号文攻撃において P 2n と A 2n の識 別が困難ならば、 A 2n は「強擬似ランダム 置換族」と呼ばれる。 暗号化 E 敵 平文 暗号文 平文 復 号 D 鍵K鍵K 暗号文 選択暗号文攻撃 段数が増えれば 攻撃に強くなる


Download ppt "情報セキュリティ 第3回 現代暗号の基礎数理. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号."

Similar presentations


Ads by Google