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

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

情報理論的安全性 その１ 暗号化アルゴリズム 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 は無 い

情報理論的安全性 その ２ 情報理論的に安全とは 任意の 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 である確率

安全性 情報理論的に安全ならば、 |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| よりも少なくすることは出来 ない。 計算量理論的に安全 情報理論的に安全でなくても、 計算時間が大きい（例えば１０ 億年）ならば安全と考える。 擬似ランダム置換族は計算量理 論的安全性の基本構成要素であ る。 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

識別不可能性 選択平文攻撃 神様は {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 = Ｄ =1 の面積 |P n | D は A n の識別に有効 識別アルゴリズ ム D が 1 を出力す る置換族 ランダム置換族 {0,1} 2 の置換 π 暗号アルゴリ ズムの置換族 暗号アルゴリ ズムは置換族 A n であるが、 A n を特定する のに時間がか かる

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 段構造 逆関数 １段１段 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 ビッ ト 暗号文 ラウンド関 数

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 は「復習 ３」で求める 攻撃のた めに選択 した平文 暗号文 敵は D=1 となる置換だ けを解読の対象に出来 る

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