x - 情報セキュリティ大学院大学 情報セキュリティ研究科

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