08/05/17 IISEC オープンキャンパス模擬授業 (08/06/18 改訂 ) 暗号理論への招待 擬似乱数の話 情報セキュリティ大学院大学有田正剛 0
はじめに 暗号理論の対象 擬似乱数 擬似ランダム関数 一方向性関数 共通鍵暗号 公開鍵暗号 MAC デジタル署名 暗号プロトコル ( 鍵共有 コミットメント ) セキュアシステム / サービス ( 電子投票 オークション ) 暗号理論の目標 システム / サービスを安全なものにコンパイル ( 自動変換 ) すること 安全 = 悪意ある環境でも正しく動作すること 正当な利用者に対する完全性 悪意ある利用者に対する頑強性 悪意あるシステムに対する健全性 1
約束ごと すべての情報はビット列で表す 整数 17 2 進表現 10001 IISEC ISO/IEC 8859 1 01001001, 01001001, 01010011, 01000101, 01000011 音楽データ MP3 画像データ JPEG {0,1} n : n ビットの文字列全体 {0,1}* : 全ての有限長の文字列全体 すべての関数 / アルゴリズムはビット列操作とみなす 101 100 101 100 + ( 排他的論理和 ) 0 + 0 = 0, 1 + 0 = 1 1001 /* 5 + 4 = 9 */ 001 0 + 1 = 1, 1+ 1 = 0 2
ワンタイムパッド メッセージ m=(m 1,m 2,m 3, ) と同じ長さのランダムなビット列 k を選ぶ ビット列 k は送信者と受信者の間だけの秘密とする k k 送信者 ( 暗号化 ) 受信者 ( 復号 ) (k 1, k 2, k 3, ) = k (k 1, k 2, k 3, ) = k k i k i m i m i c i (m + k) + k = m Eve? どのような Eve にも m i はわからない 3
ワンタイムパッドの実行例 m=(01001001, 01001001, 01010011, 01000101, 01000011) /* IISEC */ k = (00100001, 11101010, 01000101, 11001111, 10000011) /* ランダムに生成 */ 暗号化 m=(01001001, 01001001, 01010011, 01000101, 01000011) k = (00100001, 11101010, 01000101, 11001111, 10000011) c = (01101000, 10100011, 00010110, 10001010, 11000000) c = (01101000, 10100011, 00010110, 10001010, 11000000) Eve? 復号 c = (01101000, 10100011, 00010110, 10001010, 11000000) k = (00100001, 11101010, 01000101, 11001111, 10000011) m=(01001001, 01001001, 01010011, 01000101, 01000011) 4
擬似乱数生成器 擬似乱数生成器 G: {0,1} n {0,1} n+w n nビット乱数 擬似乱数生成器 G w (n+w) ビット擬似乱数
ストリーム暗号 メッセージm=(m 0,m 1,m 2, ) より ( ずっと ) 短い鍵 k をランダムに選ぶ 擬似乱数生成器 G( ) を用意する k k 暗号化 復号 k 0, k 1, k 2, G(k) k 0, k 1, k 2, G(k) k i k i m i m i ci i 本当にこれで安全なのか? 6
暗号理論における安全性の捉え方 安全であるとは理想的に安全であることと識別できないこと 1. 理想を明確に 2. ただし システムは完全に理想的でなくてもよい 現実的な敵 ( 効率的な敵 ) に理想との差を識別されなければよい ( 計算論的安全性 ) 3. しかし どの様なタイプの敵に識別されたくないのかは明確にする 敵の計算能力 敵が入手しうる情報 敵が取りうる立場 オラクル と 識別者 を用いてモデル化 7
オラクルと識別者を用いた安全性定義 ( の形 ) オラクル which? System 0 : 理想のシステム 問い合わせ 答え System 1 : 現実のシステム 識別者 b ( = 0 or 1) 定義 System 1 が安全 どのような効率的な識別者もオラクルの実体が System 0 なのか System 1なのか わからない どのような効率的な識別者に対しても Pr[ オラクルの実体 = System b ] 1/2 が無視できるほど小さい 8
擬似乱数生成器の安全性定義 擬似乱数生成器 G: {0,1} n {0,1} n+w G x z w オラクル ε z which? h? 定義 System 0 ( 理想 ) : z を {0,1} n+w からランダムに選択 System 1 ( 現実 ): x を {0,1} n からランダムに選択 z = G(x) 識別者 Gが安全な擬似乱数生成器 どのような効率的な識別者に対しても Pr[ オラクルの実体 = System b] 1/2 が無視できるほど小さい b ( = 0 or 1) 9
定理 安全な擬似乱数生成器を用いれば G: {0,1} n {0,1} n+w が安全な擬似乱数生成器ならば Gを用いたストリーム暗号は効率的なEveに対して安全である ( ただし メッセージ長はn+w 以下とする ) なぜならば もしもGを用いたストリーム暗号を破る効率的なEveがいたとすると Eveを用いてGを破る効率的な識別者 Dを構成できるから 識別者 D Eve z c = m + z オラクル z( {0,1} n+w ) m を解読できたら : 疑似 else: 真 or 疑似 ( ランダムに選択 ) 10
安全な擬似乱数生成器を作るには? まず w=1 とする : 関数 G: {0,1} n {0,1} n+1 System 1 System 0 x $ {0,1} n, z = G(x) z $ {0,1} n+1 (y,σ) = z (y {0,1} n, σ {0,1} ) y とσ はx を通して従属 y とσ は完全に独立 違いを見分けられないためには G は y とσ の関連を隠さなければならない 11
関数 G: {0,1} 5 {0,1} 6 : G(x 0,x 1,x 2,x 3,x 4 ) = (x 0,x 1,x 2,x 3,x 4, x 2 ) System 1 System 0 00100 1 11011 0 01101 1 00010 1 01111 1 01000 0 10010 0 00110 0 11011 0 01111 1 どちらが System 1? 12
ハードコア述語 関数 f: {0,1} n {0,1} n : 効率的に計算可能述語 h: {0,1} n {0,1} : f x y h σ オラクル x $ {0,1} n y = f(x), σ = h(x) return y ε y インバータ 定義述語 σ が関数 f のハードコア述語 y=f(x) はσ=h(x) を隠す どのような効率的なインバータに対しても Pr[ σ^ = σ ] 1/2 が無視できるほど小さい σ^ 13
定理 ハードコア述語があれば 述語 h: {0,1} n {0,1} {, } が関数 f:{0,1} n {0,1} {, } n のハードコア述語ならば G(x) = (f(x),h(x)) は安全な擬似乱数生成器である x f(x) h(x) G(x) 14
なぜならば ハードコア述語 hの性質より どんな識別者 Dも y=f(x) yf(x) からσ=h(x) を予測できないから じっさい 擬似乱数生成器 G=(f, (, h) を破る識別者 Dが存在したとすると Dを用いてハードコア述語 hのインバータ I を構成できる : なぜならば インバータ I 識別者 D ε y r $ {0,1} ε z = (y, r) オラクル x $ {0,1} n y = f(x) (σ=h(x)) 疑似 : r 真 : 1 r σ^ 15
ハードコア述語を作るには? 1. 何らかの難問を用いて 一方向性関数 f: {0,1} n {0,1} n ( の候補 ) を作る (y=f(x) を知っても x は分からない ) 2. y=f(x) が完全に隠す xのビット x i を見つける 3. h(x) = x i とする x f h y=f(x) x i ランダムに選択された x について y(=f(x)) を知っても Pr[h(x)=1] = 1/2 16
たとえば N = pq : 大きな2つの素数の積 e: φ(n)=(p 1)(q 1) と互いに素な整数 y = RSA en e,n( (x) = x e mod N (x {0,1,,,N 1}) は一方向性関数と信じられている RSA 仮定 さらに h(x) = LSb(x) (= x の最下位ビット ) は RSA e,n (x) のハードコア述語 ( つまり y を知ってもxが偶数か奇数かまるで分らない 数 ) a mod N: 整数 a を整数 N でわった余り 17
N=0 RSA 関数と RSA 仮定 N 1 1 N = pq y = RSA e,n (x) = x e mod N x から y = x e mod N となるyを求めるのは容易 y から y = x e mod N となる x を求めるのは困難 y (=x e mod N) x x から出発して何周してy になったのか? 偶数回それとも奇数回? 18
y = RSA e,n (x) = x e mod N N が素数のときは Nが素数 pのときは y から y = x e mod p となる x を求めるのは容易 φ(p) = p 1 d = e 1 mod (p 1), x = y d mod p N = pq のときは φ(n) =? 19
安全な擬似乱数生成器の例 系 RSA 仮定のもとで 以下の G( ) は安全な擬似乱数生成器である x $ {0,1,...,N 1} 1} G(x) = (x e mod N, LSb(x)) w ビット延長したいときは G w (x) = (x e^w mod N, LSb(x e^(w 1) mod N), LSb(x e^(w 2) mod N),, LSb(x)) 20
数値例 p = 17, q = 23 N = p * q = 391, φ(n)=16*22 = 352 e = 123 y = RSA 391 = 123 123,391 (x) x mod 391 ( x {0,1,...,390} ) k = 56 $ {0, 1,..., 390} y = k = 56 k 0 = 0 y = 56 123 mod 391 = 130 k 1 = 0 y = 130 123 mod 391 = 97 k 2 = 1 y = 97 123 mod 391 = 159 k 3 = 1 y = 159 123 mod 391 = 226 k 4 = 0 y = 226 123 mod 391 = 283 k 5 = 1 y = 283 123 mod 391 = 250 k 6 = 0 y = 250 123 mod 391 = 244 k 7 = 0 y = 244 123 mod 391 = 379 k 8 = 1 y = 379 123 mod 391 = 385 k 9 = 1 y = 385 123 mod 391 = 148 k 10 = 0 y = 148 123 mod 391 = 176 k 11 = 0 y = 176 123 mod 391 = 5 k 12 = 1 k56 k=56 を知っていれば確定的 知らなければランダム! 21
RSA 関数を用いたストリーム暗号 i= 0 y = k k ( $ {0,1,,N 1} ) [ ランダムビットの生成 ] while ( i< w ) { k i = LSb(y) y = y e mod N i= i+ 1 } RSA 仮定のもとで 効率的なEveに対して安全 (m i は知られない ) しかし 遅すぎて実用は ( 到底 ) 無理 m i k i c i 22
k ストリーム暗号 RC 4 [ 初期化 ] S 0 = 0, S 1 = 1,..., S 255 = 255 K 0, K 1,..., K 255 : 鍵 kを繰り返し用いて埋める j = 0 for i = 0 to 255: j = (j + S i + K i ) mod 256 swap S i and S j i = j = 0 [ ランダムバイトの生成 ] while (true) { i= (i+1) mod 256 j = (j+s i ) mod 256 swap S i and S j t = (S i + S j ) mod 256 K = S t } 1987 by Ron Rivest for RSA Data Security, Inc. 高速 安全性の保証は経験的 K: S i, S j から作られる i : すべての Sbox S i を用いる j : ランダムなSbox S j を用いるこれにより Kの周期を長くしている K M i i Ci 23
おわりに ストリーム暗号の セマンティック ギャップ 安全性は証明できるが 遅くて現実には使い難い 高速だが 安全性の保証は経験的 このようなギャップは暗号理論 / 技術の様々な局面にあり 暗号理論 / 技術はまだまだ発展途上 一筋縄ではいかない 色々な個性の研究者 技術者が必要 24
記号 {0,1} n : n ビットの文字列全体 {0,1}* : 全ての有限長の文字列全体 k $ {0,1} n : n ビットの文字列 k をランダムに選択 z = x + y : z は x と y との桁ごとの排他的論理和 0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1 y A(x) : 入力 x でアルゴリズム A を実行し 出力 y を得た Pr[E] : Eがおきる確率 Pr[E C] : 条件 C のもとで E がおきる確率 a mod N: 整数 a を整数 N でわった余り 25
参考文献 B. Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, 1996. J. Katz, Y. Lindell, "Introduction to Modern Cryptography: Principles And Protocols", Chapman & Hall/Crc, 2007. D.R.Stinson, "Crptography", 2nd edition, CHAPMAN & HALL/CRC, 2002. 26