Microsoft PowerPoint - 暗号技術の発展.pptx

’08年度特別講義X

暗号技術の発展

古典暗号からIDベース暗号まで

‘08.09.01

有田 正剛

1

暗号

k k : 鍵 k₁,k₂ : 鍵 E : 暗号化アルゴリズム D : 復号アルゴリズム k₁ m k₂ 送信者 _c 受信者 c ← E_k1(m) m ← Dk2(c) m Eve ? 2

目次

目次

1. 古典暗号

ブ

ク暗号

2. ブロック暗号

3. 公開鍵暗号

4. IDベース暗号

3

1 古典暗号

1. 古典暗号

換字暗号方式

鍵

• 鍵

π : アルファベット{A, B, C, ・・・, Z}の並べ替え

例えば π(A) = V, π(B) = S, π(C) = G, ・・・, π(Z)=U

例えば π(A)   V, π(B)   S, π(C)   G, 

, π(Z) U

• 暗号化

// x ∈ {A, B, C, ・・・, Z}

E

_π

(x) = π(x)   

• 復号

// y ∈ {A B C ・・・ Z}

• 復号

// y ∈ {A, B, C, ・・・, Z}

D

_π

(y) = π

‐1

_(y)

5

シフト暗号

鍵

• 鍵

K ∈ {0, 1, 2, ・・・, 25}

• 暗号化

// x ∈ {0,1, ・・・25}

E

_K

(x) = (x + K) mod 26

_{“cryptography”}

• 復号

// y ∈ {0,1, ・・・25}

D (y) (y K) mod 26

yp g p y

D

_K

(y) = (y ‐ K) mod 26

_K=3 “FUBWRJUDSKB”

転置暗号方式

• 鍵

m : 正の整数

{1 2

}の並べ替え（転置）

π : {1, 2, ・・・,m}の並べ替え（転置）

• 暗号化

暗号化

E

_π

(x

₁

, ・・・, x

_m

) =  (x

_π(1)

, ・・・, x

_π(m)

)

• 復号

D

_π

(y

₁

, ・・・, y

_m

) = (y

_π^{‐1}(1)

, ・・・, y

_π^{‐1}(m)

)

転置暗号の例

鍵 “cryptography” C R Y P O G T O G R A P H Y “CTAROPYGHPRY”

2 ブロ ク暗号

2. ブロック暗号

– コンピュータを駆使して換字に転置

ブロック暗号

• ブロック暗号

=  効率的に計算可能な

E : {0 1}

l

_{x {0 1}}

n

_{→ {0 1}}

n

E : {0,1}

l

_x {0,1}

n

_→ {0,1}

n

ただし、各第一引数kについて E

_k

(・)は置換（全単射）

• 鍵:  k ←

$

_{0,1}

l

暗号化: c ← E

_k

(m)       

(m ∈ {0,1}

n

₎

復号: m ← E

‐1

_(c)

_{(c ∈ {0 1}}

n

₎

復号: m ← E

_k 1

_(c)         

_{(c ∈ {0,1}}

n

₎

• 理想は各

理想は各

E

_kk

(・)がランダム置換

( )がランダム置換

入力が1ビットでも変化すると_{その影響は全ての出力ビットにその影響は全ての出力ビットに} 及ぶ。 ランダム置換と区別がつかないような、 ランダム置換と区別がつかないような、 効率的な疑似ランダム置換を どのように作ればよいか？

換字と転置を繰り返す

DES

•

E: {0, 1}

56 

_x  {0,1}

64

_→ {0,1}

64

•

E

_k

(m):

// m ∈ {0,1}

64

(k

₁

・・・ k

₁₆

) ← KeySchedule(k)

// k

_i

∈ {0 1}

48

(k

₁

,

,k

₁₆

) ← KeySchedule(k)       

// k

_i

∈ {0,1}

m ← IP(m)

L

₀₀

∥R

₀₀

← m

// |L

₀₀

|=|R

₀₀

|=32

for r = 1 to 16 do

L

_r

← R

_r‐1

; R

_r

← f(k

_r

, R

_r‐1

) + L

_r‐1

← IP

1

_{(L ∥R )}

c ← IP

‐1

_(L

16

∥R

16

)

return c

※ f がどんな関数であっても E (・) は必ず置換となる ※ f がどんな関数であっても E_k( ) は必ず置換となる 11

k₁ L₀ R₀ f k₂ L₁ R₁ f L₁ R₁ k₃₃ f L₂ R₂ L₃ R₃

攪拌関数 f

f(J, R):

// |J| = 48, |R| = 32

R ← E(R); R ← R + J

R ∥R ∥・・・∥R ← R

R J

R

₁

∥R

₂

∥・・・∥R

₈

← R

for r = 1 to 8 do

R

_i

← S

_i

(R

_i

)

∥ ∥

∥

32ビット入力 48ビット部分鍵 R J

R ← R

₁

∥R

₂

∥・・・∥R

₈

R ← P(R)

return R

E 48ビット 48ビット中間データ S₁ S₂ S₃ S₄ S₅ S₆ S₇ S₈ P 32ビット 32ビット出力 13

SBox

S_i : {0,1}6 _→ {0,1}4 _{;  一種の換字暗号 (i=1,・・・6)} b₁b₆ b₂b₃b₄b₅ i { , } { , } ; 種 換 暗 ( , ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 0 2 3 0 6 2 9 3 8 S₁ 01 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 10 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 1. 各Sボックスは4対1関数 2. 各行は0から15を1回ずつとる 入力 ビ トを変えると出力 少なくとも ビ トが変わる 3. 入力の1ビットを変えると出力の少なくとも2ビットが変わる。 ビ ビ R₀の1ビットが変化 → R₁の2ビットが変化 → R₂の4ビットが変化→・・・ “アバランシュ効果”

S₁ E P [Vaudenay05] Figure2.4 より S₂ S₃ S₄ f(J R) S₅ R f(J,R) S₆ S₇ S_{8 15}

DESの問題点

ぎ

• 鍵長

l = 56 は小さすぎる。

ブ

も

ぎ

• ブロック長

n = 64 も短すぎる。

ボ

実装

向き

•

Sボックスの実装はソフトウェアに不向き

AES

•

E: {0, 1}

128 

_x  {0,1}

128

_→ {0,1}

128

•

E

_k

(m):         

// m ∈ {0,1}

128

(k

₀

,・・・,k

₁₀

) ← expand(k)       

// k

_i

∈ {0,1}

128

←

+ k

s ← m + k

₀

for r = 1 to 10 do

s ← S(s)

s ← S(s)

s ← shift‐rows(s)

if r ≦ 9 then s ← mix‐cols(s)

s ← s + k

_r

return s

_{s: 128ビット = 16バイト}

•

ソフトウェアでも高速処理可能

s0 s4 s8 s12 s₁ s₅ s₉ s₁₃ s₂ s₆ s₁₀ s₁₄ s₃ s₇ s₁₁ s₁₅ 17

GF(2

8

)

バイトは加減乗除が

有限体 GF(2

8

₎

• 集合として

G(2

8

_) = {0,1}

8

•

(a

₇

a

₆

a

₅

a

₄

a

₃

a

₂

a

₁

a

₀

) + (b

₇

b

₆

b

₅

b

₄

b

₃

b

₂

b

₁

b

₀

)

バイトは加減乗除が できる

(a

₇

,a

₆

,a

₅

,a

₄

,a

₃

,a

₂

,a

₁

,a

₀

) + (b

₇

,b

₆

,b

₅

,b

₄

,b

₃

,b

₂

,b

₁

,b

₀

)

= (a

₇

+b

₇

,a

₆

+b

₆

,a

₅

+b

₅

,a

₄

+b

₄

,a

₃

+b

₃

,a

₂

+b

₂

,a

₁

+b

₁

,a

₀

+b

₀

)    ( + は XOR )

•

(a

₇

,a

₆

,a

₅

,a

₄

,a

₃

,a

₂

,a

₁

,a

₀

) ・ (b

₇

,b

₆

,b

₅

,b

₄

,b

₃

,b

₂

,b

₁

,b

₀

)

= (c c c c c c c c )

= (c

₇

,c

₆

,c

₅

,c

₄

,c

₃

,c

₂

,c

₁

,c

₀

)

ここで

7 6 5 4 3 2

c

₇

x

7

_+c

6

x

6

+c

5

x

5

+c

4

x

4

+c

3

x

3

+c

2

x

2

+c

1

x+c

0 

= (a

₇

x

7

_+a

6

x

6

+a

5

x

5

+a

4

x

4

+a

3

x

3

+a

2

x

2

+a

1

x+a

0 

) ・ (b

7

x

7

+b

6

x

6

+b

5

x

5

+b

4

x

4

+b

3

x

3

+b

2

x

2

+b

1

x+b

0 

)

mod (x

8

_=x

4

_+x

3

_+x+1)

例えば x7 _・(x2 _+ 1) = x9 _+ x7 _= x・(x4_+x3_+x+1) + x7 = x7 _{+ x}5 _{+ x}4 _{+ x}2 _{+ x} 例えば _{(10000000)+(00000101) = (100000101)}  x + x + x + x + x ∴ (10000000)・(00000101) = (101110110)

S

1. 各s_iの、GF(28_{)の要素としての、逆数 s} i‐1をとる。（ただし、0‐1=0とおく。） 2. 各s_i‐1 _{に（ある）アファイン変換を施す。} s₀ s₄ s₈ s₁₂ s0‐1 s4‐1 s8‐1 s12‐1 1 1 1 1 s₁ s₅ s₉ s₁₃ s₂ s₆ s₁₀ s₁₄ s₁‐1 _s 5‐1 s9‐1 s13‐1 s₂‐1 _s 6‐1 s10‐1 s14‐1 逆数 s₃ s₇ s₁₁ s₁₅ s3‐1 s7‐1 s11‐1 s15‐1 s₀’ _s 4’ s8’ s12’ アファイン変換 s₁’ _s 5’ s9’ s13’ s₂’ _s 6’ s10’ s14’ 19 s₃’ _s 7’ s11’ s15’

shift‐rows と mix‐cols

hift 横方向に転置 s₀ s₄ s₈ s₁₂ s₀ s₄ s₈ s₁₂ shift‐rows :  横方向に転置 0 s₁ s₅ s₉ s₁₃ s₂ s₆ s₁₀ s₁₄ s₅ s₉ s₁₃ s₁ s₁₀ s₁₄ s₂ s₆ 1 2 s₃ s₇ s₁₁ s₁₅ s₁₅ s₃ s₇ s₁₁ 3 mix‐cols： 縦方向に（換字しながら）転置 s₀ s₄ s₈ s₁₂ s₁ s₅ s₉ s₁₃ s₀’ s₄’ s₈’ s₁₂’ s₁’ s₅’ s₉’ s₁₃’ 02 03 01 01 01 02 03 01 x s₂ s₆ s₁₀ s₁₄ s₃ s₇ s₁₁ s₁₅ s₂’ s₆’ s₁₀’ s₁₄’ s₃’ s₇’ s₁₁’ s₁₅’ 01 02 02 03 03 01 01 02 x

擬似ランダム置換の安全性定義

E = {E_k}_k∈K : 置換族 E_k: {0,1}n _→ {0,1}n_{;効率的に計算可能} オラクル System 0 (理想) :  [初期化] H ← 真のランダム置換 [u に対して] v ← H(u) [u に対して]  v ← H(u) System 1 (現実) :  初期化 u v [初期化] k ← K_{[u に対して]  v ← E} k(u) 識別者 定義 Eが安全な擬似ランダム置換（族） ⇔ 0 or 1 ⇔ どのような現実的な識別者Dに対しても | Pr[D=1 | System0] – Pr[D=1 | System1] |  が無視できるほど小さい 21 0 or  1 が無視できるほど小さい。

DESやAESは疑似ランダム置換か？

DESやAESは疑似ランダム置換か？

•

AESも擬似ランダム置換であると証明されているわけではな

い

い。

• 識別者のクラスを限定すると：

識別者のクラスを限定すると：

–

DESには線形解読が（理論的には）有効。

差

解読

線

解読

能 安全

–

AESは差分解読や線形解読に対して（証明可能）安全。

差分解読

オラクル 識別者 ク を差分識別者 限定 オラクル System 0:  H(・)  System 1:  E_k(・) u 識別者のクラスを差分識別者に限定

差分識別者a,b

パラメータ: a,b ∈ {0,1}_{, { , }}n v 以下を(ある回数)繰り返す: u ←$ _{0,1}n オラクルに u を尋ねて v₁ を得る。 オラクルに u+a を尋ねて v₂ を得る。 if v₂ = v₁ + b よいa,bをみつけることが 暗号解析者の腕の見せどころ output 1 and halt else continue ブロック暗号E = {E_k} が差分解読に対して安全 output 0 ブ ック暗号E   {E_k} が差分解読に対して安全 ⇔ どのようなa,bに対する差分識別者_a,bに対しても | Pr[差分識別者_{a b}=1 | System0] – 23 | [ _a,b | y ] Pr[差分識別者_a,b=1 | System1] |  が無視できるほど小さい。 0 or  1

線形解読

オラクル 識別者 ク を線 識別者 限定 オラクル u 識別者のクラスを線形識別者に限定 System 0:  H(・)  System 1:  E_k(・)

線形識別者

_a,b,A パラメータ: a,b ∈ {0,1}_{, { , }}n v A ⊆ {0, 1, 2, …} c ← 0 以下を(ある回数)繰り返す: u ←$ _{0,1}n オラクルに u を尋ねて v を得る。 よいa,b,Aをみつけることが 暗号解析者の腕の見せどころ if u ・ a  =  v ・ b c ← c + 1 if A 1 l 0 ブロック暗号E = {E } が線形解読に対して安全

if c ∈ A, output 1 else output 0 ブロック暗号E = {Ek} が線形解読に対して安全

⇔ どのようなa,b,Aに対する線形識別者_a,b,Aに対しても | Pr[線形識別者 _{b A}=1 | System0] – 0 or  1 | Pr[線形識別者_a,b,A 1 | System0]  Pr[線形識別者_a,b,A=1 | System1] |  が無視できるほど小さい。

識別利得 ⇒ 鍵の情報

E = {E_k}_k∈{0,1}^l : ラウンド数 rのブロック暗号 E‐ _= {E‐ k}k∈{0,1}^l : Eから最終ラウンドを除いたブロック暗号、ラウンド数 r‐1 ある a,bがあって、 E‐_{に対する識別者} a,bの識別利得が大きいとする。 次のようにして、最終ラウンド鍵k_rrを求めることができる。 1. E_kの(平文、暗号文)対を集める: (X_i (Y_{i L} Y_{i R})) (X_i, (Y_i,L, Y_i,R))

2. K ← k_rのランダムな推測値 Z_{i Li,L} = f(K, Yf(K, Y_{i Li,L}) + Y) Y_{i Ri,R}

Z_i,R = Y_i,L /*  Kが正しければ、 (X_i, Z_i)はE‐_{の(平文、暗号文)対 */}

Z_ii= (Z( _{i Li,L}, Z, _{i Ri,R})) を X_iiに対する応答として、識別者_{a ba,b} を実行し、 その識別利得_K を求める。

3. 識別利得_Kの大きな K を k_r の推測値として出力。

k X_L X_R k₁ f EE‐‐ k₂ L₁ R₁ f L₁ R₁ f L₂ R₂ K Y_L Y_R

3 公開鍵暗号

3. 公開鍵暗号

– 計算の非対称性の発見

公開鍵暗号

• 鍵生成アルゴリズムG: (pk sk) ← G(k)

アルゴリズムの3つ組(G,E,D)

• 鍵生成アルゴリズムG:   (pk, sk)  ←  G(k)

• 暗号化アルゴリズムE： c ← E

_pk

(m)

• 復号アルゴリズムD： m ← D

_sk

(c)

m ただし m = D_sk(E_pk(m)))． pk, c から mを求めることは困難(一方向性） pk  S m  sk  p c R c ← E_pk(m) m ← Dsk(c) m 

たとえば・・・

N = pq ： 大きな2つの素数の積

pq

e: φ(N)=(p‐1)(q‐1)と互いに素 な整数

( )

(

{

})

y = RSA

_e,N

(x) = x

e

_{mod N      (x ∈ {0,1,・・・,N‐1})}

は一方向関数と信じられている（RSA仮定）

は

_{方向関数と信じられている（RSA仮定）。}

すなわち、

y,e,N を与えられても y = RSA

_e,N

(x) となる x は求められない。

d N 整数 を整数Nでわ た余り

29 a mod N: 整数aを整数Nでわった余り。

RSA 関数とRSA仮定

N=0 1 N‐1

N

1

•

x から

•

N = pq

y = RSA_e,N(x) = xe _mod N

•

x から

y = x

e

_{mod N となるyを}

求めるのは容易

•

y から

y = x

e

_{mod N となる x を}

求めるのは困難

x y

求めるのは困難

y (=xe _mod N)

x から出発して

何周して にな たのか？

何周してy になったのか？

偶数回それとも奇数回？

Nが素数のときは・・・

( )

d

•

Nが素数pのときは、y から y = RSA (x) となる x を求

y = RSA

_e,N

(x) = x

e

_mod N

Nが素数pのときは、y から y   RSA

_e,p

(x) となる x を求

めるのは容易。

φ(p) = p – 1, d = e

‐1

_mod (p‐1)

RSA

_{d p}

= RSA

_{e p}‐1

RSA

_d,p

 RSA

_e,p

•

N = pq のときもRSA

_{N   pq のときもRSA}

_{d N}

= RSA

_{e N}‐1 

_{( d = e}

‐1

_{mod φ(N) )。}

d,N

 RSA

e,N

( d   e mod φ(N) )。

ところが、

φ(N) = ?

φ(N)   ?

が分からない。（p, qを知っていれば分かる。）

が分からない。（p, qを知っていれば分かる。）

31

RSA暗号

•鍵生成アルゴリズム G:

多項式時間アルゴリズムの3つ組(G,E,D)

•鍵生成アルゴリズム G:   

p, q ←  異なるランダムな素数；

N = p q；

e: φ(N) (p 1)(q 1)と互いに素な整数;

e: φ(N)=(p‐1)(q‐1)と互いに素な整数;

d 

← e‐1 _mod φ(N)

pk = {N,e},  sk = {N,d}

•暗号化アルゴリズム E：

E

_pk

(m) = m

e

_{mod N       // = RSA}

e,N

(m)

p ,

•復号アルゴリズム D：

D

_sk

(c) = c

d

_{mod N       // = RSA}

d N

(c)

sk

( )

//

d,N

( )

• RSA

_{d N}

= RSA

_{e N}‐1

_{[ オイラーの定理 ]}

d,N e,N

[ オイラ の定理 ]

素数を法としたべき乗数

p: 素数

q: p‐1 を割る素数

q p

g : mod p で位数がqの整数

全て異なる巨大な数の（算法つき）集合

{1, g mod p, g

2

_{mod p, …., g}

q‐1

_mod p}

<p, q, g>

指定

全て異なる巨大な数の（算法つき）集合

(g

q

_{mod p = 1)}

43

7

4

例

例

<p=43, q=7, g=4>

g

0

_{mod p = 1,  g mod p = 4}

g

2

_{mod p = 16,  g}

3

_{mod p = 21}

g

4

_{mod p = 41,  g}

5

_{mod p = 35}        

g

6

_{mod p = 11}

33

<p=43, q=7, g=4>

{1,4,16,21,41,35,11}

CDH仮定

p: 素数

q: p‐1 を割る素数

g : mod p で位数がq

g : mod p で位数がq

<p, q, g>に対して

p, q, g に対して

CDH仮定

a, b  ←

$

_{{1,2,・・・,q}}

どんな効率的なアルゴリズムも、g

a

_{mod p と g}

b

_mod p を

与えられて、g

ab

_{mod p を求めることはできない。}

与えられて、g mod p を求める とはできない。

• <p=43, q=7, g=4>

g

3

_{mod p 21 g}

5

_{mod p 35}

？

？

_g

15

_{mod p 4}

DDH仮定

<p, q, g>に対して

b

$

_{

_}

DDH仮定

a, b, c  ←

$

_{{1,2,・・・,q}}

どんな効率的なアルゴリズムも、g

a

_{mod p と g}

b

_mod p を

与えられても、g

ab

_{mod p と g}

c

_{mod p を区別できない。}

すなわち

g

a

_{mod p と g}

b

_{mod p を教わっても g}

ab

_{mod p はまったく分からない。}

（情けない話ではある）

すなわち、

（情けな 話ではある）

• <p=43, q=7, g=4>

35

<p 43, q 7, g 4>

(21, 35, 4)  OR (21, 35, 11)  どちらが正しい?

エルガマル暗号

•鍵生成アルゴリズム G:

多項式時間アルゴリズムの3つ組(G,E,D)

•鍵生成アルゴリズム G:   

p, q, g ← 素数p,qと整数g、ただし q | p‐1, g

q

_= 1 mod p

x ←

$

_{{1, ・・・,q‐1}, y} 

_← gx _mod p

pk {p g q y} sk {p g q x}

pk = {p,g,q,y},  sk = {p,g,q,x}

•暗号化アルゴリズム E

_pk

(m)：

$

_{

_}

r ←

$

_{{1, ・・・,q‐1}}

c = (g

r

_{mod p, m y}

r

_mod p)  

•復号アルゴリズム D

_sk

(c

₁

,c

₂

)：

c

₂

/ c

₁x

_mod p

• DDH仮定のもとでIND‐CPA安全

エルガマル暗号のからくり

(

r r

₎

y

r

_= g

xr

y = g

x

c = (g

r

_{, m y}

r

₎  

y

g

E Dec

r

Enc

r

g

x

g

r

x

CDH仮定

g

r

g

x

37

RSA暗号に対する攻撃

“賛成” pk={n,e}  m ∈ {“賛成”，“反対”} S sk={n,d}  R R c = “賛成”e _mod n c “賛成” ← cd _mod n pk={n e} A pk={n,e}  “賛成” c₁ = “賛成”e _mod n c₂ = “反対”e _mod n  c = c ならば“賛成” RSA暗号は_な 賛成 c = c₁ ならば 賛成 else “反対” IND‐CPAでない。 “賛成” 38

識別不可能性 （IND‐CPA)

(G, E, D): 公開鍵暗号 オラクル System 0 :  [初期化]  (pk,sk) ← G [(m₀,m₁) に対して] c* ← E_pk(m₀) [(m₀,m₁) に対して]  c  ← E_pk(m₀) System 1 :  初期化 [初期化]  (pk,sk) ← G [(m₀,m₁) に対して]  c* ← E_pk(m₁) pk m₀,m₁ c* 識別者 定義 EがIND‐CPA安全 0 or 1 が _C 安全 ⇔ どのような現実的な識別者Dに対しても | Pr[D=1 | System0] – Pr[D=1 | System1] |  39 0 or  1 | [ | y ] [ | y ] | が無視できるほど小さい。

エルガマル暗号に対する攻撃

m=10  pk={p,g,q,y}  m ∈ {(ある商品に対する）注文個数} S sk={p,g,q,x}  ( ) R c = (gr_, 10yr₎ c=(c₁,c₂) pk={p g q y} 1000 ← c2 /c1 x _mod n A pk={p,g,q,y}  「本当に1000個も注文するの？」 c₂’ = c₂ x 100 「本当に1000個も注文するの？」 c’=(c₁,c₂’) エルガマル暗号は m = 1000/100 = 10 エルガマル暗号は IND‐CCAでない。 (DDH仮定のもとでIND‐CPA)40

識別不可能性 （IND‐CCA)

(G, E, D): 公開鍵暗号 オラクル System 0 :  [初期化]  (pk,sk) ← G [(m₀,m₁) に対して]  c* ← E_pk(m₀) に対して [c に対して] m ← D_sk(c)    (c ≠ c*) System 1 :  [初期化] (pk sk) ← G pk m₀, m₁ c* c m c m [初期化]  (pk,sk) ← G [(m₀,m₁) に対して]  c* ← E_pk(m₁) [c に対して] m ← D_sk(c)    (c ≠ c*) 識別者 定義 EがIND‐CCA安全 (*) (*) 識別者 0 or 1 が _{CC 安全} ⇔ どのような現実的な識別者Dに対しても | Pr[D=1 | System0] – Pr[D=1 | System1] |  41 0 or  1 | [ | y ] [ | y ] | が無視できるほど小さい。

ハッシュ関数

効率的な（圧縮）関数

H: {0 1}* → {0 1}

h

H: {0,1}* → {0,1}

h

Hが衝突困難：

Hが衝突困難：

どのような現実的なアルゴリズムも

H(x)=H(y)となるx, y (x≠y) を見つけることはできない。

ランダムオラクルモデル:

プログラム中のすべてのz ← H(x) を

ダムオ ク

問 合わせに置き換える

ランダムオラクルへの問い合わせに置き換える。

H ←$ _{{ H: {0 1}* → {0 1}}h _} プログラム ... z ← H(x) H ← { H: {0,1}  → {0,1} } z = H(x) x プログラム ... z ( )

OAEP+

f : {0,1}k _→ {0,1}k _{: 置換, g = f} ‐1 k₀+k₁<k, 2‐k0_,2‐k1_{: negligible, n = k‐k} 0‐k1 G : {0 1}k0 _{→ {0 1}}n _{H’ : {0 1}}n+k0 _{→ {0 1}}k1 _{H : {0 1}} n+k1 _{→ {0 1}}k0 G : {0,1}k0 _→ {0,1}n_{, H  : {0,1}}n k0 _→ {0,1}k1_{, H : {0,1}} n k1 _→ {0,1}k0 x ∈ {0 1}n y g EE x ∈ {0,1} _f w = g(y) Dec Dec r ←$ _{0,1}k0 s = (G(r) + x) ∥ H’(r ∥ x) H( ) Enc Enc _{s ∥ t = w} r = H(s) + t t = H(s) + r w = s ∥ t y = f(w) x = G(r) + s[0..(n‐1)] c = s[n..(n+k₁‐1)] ∥ ？ c = H’(r ∥ x)： x else j t ？ reject f がone‐wayならばOAEP+(f)はランダムオラクルモデルのもとでIND‐CCA 43

OAEP+の暗号文

x r x r 暗号文の正当性をチェックするための 冗長な情報 x + G(r)( ) H’(r∥x)( ∥ ) H(s) + r( ) s f r やsを知らずに な を y 正当な暗号文を 作ることはできない。

FO変換

π = (K, E, D), 

H = {H

_n

}

_n

π’ = (K’, E’, D’) = FO

_H

(π):

K’(1

k

_) :

(pk, sk) ← K(1

k

_), H ←

$

H

k

pk’ = (pk, H), sk’ = sk

p

(p , ),

E’(pk’,m):

r ←

$

_R

ランダムオラクルモデルのもとで π: IND‐CPA ∧ γ‐uniform

r ← R

m

~

_= m∥r

c = E

_pk

(m

~

_; H(m

~

₎₎

∧ γ ⇒ π’ : IND‐CCA

D’(sk’,c):

m

~

_= D

sk

(c)

∥

~

γ(x,y) =def _Pr[ γ←$ _{R : y = E}

pk(x;r)]

m∥r  = m

~

c =

?

_E

pk

(m

~

; H(m

~

)) :

m

π is γ‐uniform if ∀x,y, γ(x,y) ≦ γ

else

⊥

45

4 IDベ ス暗号

4. IDベース暗号

IDベース暗号

• (params, master‐key)  ←  Setup(k)

E = (Setup, Extract, Enc, Dec)

(params master key) ← Setup(k)

鍵配布センター

• d

_ID

← Extract

_params

(master‐key, ID)

• c← Enc

_params

(ID, m)

• m ← Dec

_params

(d

_ID

, c)

(params, master‐key)  ←  Setup(k) ID

d_ID← Extract_params(master‐key, ID)

params

(

ID

, )

params ID  m  ID params 送信者 params d_ID params 送信者 受信者 (ID) c ← Enc_params(ID, m)

c

m ← Dec_params(d_ID, c)

識別不可能性 （IND‐ID‐CPA)

S 0

(Setup, Extract, Enc, Dec):  IDベース暗号

System 0 : 

[初期化]  (params,master‐key) ← Setup [(m₀,m_1, ID*):]  c* ← Enc_params(ID*, m₀)

[ID ] d ← E t t ( t k ID) (ID ≠ ID*)

オラクル

[ID:]   d ← Extract_params(master‐key, ID)    (ID ≠ ID*) System 1 :  [初期化] ( t k ) ← S t params m₀, m₁, ID*c* ID d ID d [初期化]  (params,master‐key) ← Setup [(m₀,m_1, ID*):]  c* ← Enc_params(ID*, m₁)

[ID:]   d ← Extract_params(master‐key, ID)    (ID ≠ ID*)

識別者 定義 EがIND‐ID‐CPA安全 (*) (*) 識別者 0 or 1 が _C 安全 ⇔ どのような現実的な識別者Dに対しても | Pr[D=1 | System0] – Pr[D=1 | System1] |  0 or  1 | [ | y ] [ | y ] | が無視できるほど小さい。

Bilinear maps

G

₁

, G

₂

: 素数位数q の群

e : G

₁

x G

₁

→ G

₂

が bilinear map とは

1 (Bilinear) e(aP bQ) = e(P Q)

ab

_{(∀P Q∈G ∀a b∈ Z)}

1. (Bilinear)    e(aP, bQ) = e(P,Q)

(∀P,Q∈G

₁

, ∀a,b∈ Z)

2. (非退化)     e(P,P) ≠ 1       (∀P(≠0)∈G

₁

)

3. (計算可能)   e(P,Q)は効率的に計算可能。(∀P,Q∈G)

楕円曲線上の Weil paring を用いて実現。

楕円曲線上の Weil paring を用いて実現。

49

BF暗号

[BF01]

bili

版のエルガマル暗号

BF = (Setup, Extract, Encrypt, Decrypt):

bilinear map版のエルガマル暗号

Encrypt(params, ID, m): Q_ID = H₁(ID)

Setup(k):

<q, G

₁

, G

₂

, e> ←

G(k)

_Q ID  H1(ID) r ←$ _Z q* g_ID= e(Q_ID, P_pub) c = < rP, m + H₂(g_IDr_)>

q,

₁

,

₂

,

G( )

P ←

$

_G

1

, s ←

$

Z

q

*, P

pub

= s P

Choose

H

₁

: {0 1}* → G

₁

*

c rP, m H2(gID ) Decrypt(params, c=<U,V>, d_ID): m = V + H₂(e(d_ID, U))

H

₁

: {0,1}  → G

₁

H

₂

: G

₂

→ {0,1}

n

params = <q,G

₁

,G

₂

,e,n,P,P

_pub

,H

₁

,H

₂

>

master key = s

2( ( ID ))

master‐key = s

Extract(ID, params, s):

Q

H (ID) (

G *)

Q

_ID

= H

₁

(ID) (∈G

₁

*)

d

_ID

= s Q

_{ID ランダムオラクルモデルにおいて} BF暗号はGに対するBDH仮定のもとでG IND‐ID‐CPA安全。

BDH仮定

G₁, G₂: 素数位数q  e : G₁ x G₁ → G₂； bilinear map  P ∈ G₁* P ∈ G₁

<e, q, P>に対して

, q,

に対して

BDH仮定

a, b, c  ←

$

_{{1,2,・・・,q}}

どんな効率的なアルゴリズムも、aP, bP, cPを

与えられて、e(P,P)

abc

_{を求めることはできない。}

与えられて、e(P,P)

を求める とはできない。

51

BF暗号のからくり

c = < U, m + H

₂

(g

_IDr

_)>

g

_ID

r

_= e(P,P)

ksr

P

_pub

= sP

U = rP

c

U,

₂

(g

_ID

)

g

_ID

e( , )

E Dec

U = rP

Q

_ID

= kP

k P ( d )

Enc

r

kP

ksP (=d

_ID

)

rP

BDH仮定

sP

rP

kP

自由度 ザ

sP

自由度k ↔ ユーザID

今後の暗号について

• ランダムオラクルモデルからの脱却

b l

の意味

•

bilinear map の意味

• 各種多機能暗号

• 各種多機能暗号

– 閾値復号、放送暗号、属性ベース暗号など

– 暗号プロトコルの構成部品としての機能

• より高度または繊細な安全性

フ ワ ドセキ リテ

アダプテ ブセキ リテ

– フォワードセキュリティ、アダプティブセキュリティ

– 量子計算機への対応

53

記号

• {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

0   0   1   1   0, 0   1   1   0   1

• y ← A(x) : 入力xでアルゴリズムAを実行し、出力y を得た。

• Pr[E] : Eがおきる確率

Pr[E | C] : 条件Cのもとで Eがおきる確率

Pr[E | C] : 条件Cのもとで、Eがおきる確率

•

a mod N: 整数aを整数Nでわった余り。

a mod N: 整数aを整数Nでわった余り。

参考文献

A t S l “P bli K C t h ” S d Editi S i 1996 主なもの

• Arto Salomma, “Public‐Key Cryptography”, Second Edition, Springer,  1996 • [Vaudenay05] Serge Vaudenay,  “A Classical Introduction to Cryptography:  Applications for Communications Security” Springer 2005

Applications for Communications Security ,  Springer, 2005

• J Katz Y Lindell "Introduction to Modern Cryptography: • J. Katz, Y. Lindell,  Introduction to Modern Cryptography: 

Principles And Protocols", Chapman & Hall/Crc, 2007. 

• [BF01] D Boneh M Franklin “Identity‐Based Encryption from the Weil Pairing”[BF01] D.Boneh, M.Franklin,  Identity Based Encryption from the Weil Pairing , CRYPTO 01, LNCS 2139, pp. 213‐229.