暗号技術の発展 - lab.iisec.ac.jplab.iisec.ac.jp/~arita/pdf/x08.pdf · SBox S i: {0,1}6 →...

’08年度特別講義X

暗号技術の発展

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

‘08.09.01有田正剛

1

暗号k k :鍵k1,k2 : 鍵E : 暗号化アルゴリズムD : 復号アルゴリズム

k1 m k2

送信者 c 受信者

c ← Ek1(m) m ← Dk2(c)

m

Eve

? 2

目次目次

1. 古典暗号ブ ク暗号2. ブロック暗号

3. 公開鍵暗号4. IDベース暗号

3

1 古典暗号1. 古典暗号

– コンピュータのない時代の暗号

4

換字暗号方式

鍵• 鍵π : アルファベット{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}EK(x) = (x + K) mod 26 “cryptography”

• 復号 // y ∈ {0,1, ・・・25}D (y) (y K) mod 26

yp g p y

DK(y) = (y ‐ K) mod 26 K=3

“FUBWRJUDSKB”

6

転置暗号方式

• 鍵m : 正の整数

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

• 暗号化暗号化Eπ(x1, ・・・, xm) =  (xπ(1), ・・・, xπ(m))

• 復号Dπ(y1, ・・・, ym) = (yπ^{‐1}(1), ・・・, yπ^{‐1}(m))

7

転置暗号の例鍵

“cryptography”

C R Y P

O GT O G R

A P H Y

“CTAROPYGHPRY”

8

2 ブロ ク暗号2. ブロック暗号

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

9

ブロック暗号

• ブロック暗号 =  効率的に計算可能なE : {0 1}l x {0 1}n → {0 1}nE : {0,1}l x {0,1}n → {0,1}n

ただし、各第一引数kについて Ek(・)は置換（全単射）

• 鍵:  k ←$ {0,1}l

暗号化: c ← Ek(m)       (m ∈ {0,1}n)復号: m← E ‐1(c) (c∈ {0 1}n)復号: m ← Ek 1(c)         (c ∈ {0,1}n)

•理想は各Ek(・)がランダム置換入力が1ビットでも変化するとその影響は全ての出力ビットに理想は各 k( )がランダム置換 その影響は全ての出力ビットに及ぶ。

ランダム置換と区別がつかないような、ランダム置換と区別がつかないような、効率的な疑似ランダム置換をどのように作ればよいか？

換字と転置を繰り返す10

DES

• E: {0, 1}56  x  {0,1}64 → {0,1}64

• Ek(m): // m ∈ {0,1}64

(k1 ・・・ k16)← KeySchedule(k) // ki ∈ {0 1}48(k1, ,k16) ← KeySchedule(k)       // ki ∈ {0,1}m ← IP(m)L0∥R0 ← m // |L0|=|R0|=320 0 0 0for r = 1 to 16 do

Lr ← Rr‐1; Rr ← f(kr , Rr‐1) + Lr‐1← IP 1(L ∥R )c ← IP‐1(L16∥R16)

return c

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

11

k1L0 R0

f

k2L1 R1

f

L1 R1

k33

f

L2 R2

12

L3 R3

攪拌関数 ff(J, R): // |J| = 48, |R| = 32

R ← E(R); R ← R + JR ∥R ∥・・・∥R ← R R JR1∥R2∥・・・∥R8 ← Rfor r = 1 to 8 do

Ri ← Si(Ri)∥ ∥ ∥

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

R J

R ← R1∥R2∥・・・∥R8R ← P(R)return R

E

48ビット

48ビット中間データ

S1 S2 S3 S4 S5 S6 S7 S8

P

32ビット

32ビット出力13

SBoxSi : {0,1}6 → {0,1}4 ;  一種の換字暗号 (i=1,・・・6)

b1b6 b2b3b4b5

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

S1

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 1311 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ビットが変わる。

ビ ビR0の1ビットが変化→ R1の2ビットが変化→ R2の4ビットが変化→・・・ “アバランシュ効果”

14

S1

EP[Vaudenay05]Figure2.4 より

S2

S3

S4

f(J R)

S5R

f(J,R)

S6

S7

S8 15

DESの問題点

ぎ• 鍵長 l = 56 は小さすぎる。

ブ も ぎ• ブロック長 n = 64 も短すぎる。

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

16

AES• E: {0, 1}128  x  {0,1}128 → {0,1}128

• Ek(m):         // m ∈ {0,1}128

(k0,・・・,k10) ← expand(k)       // ki ∈ {0,1}128

← + ks ←m + k0for 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 + kr

return ss: 128ビット = 16バイト

• ソフトウェアでも高速処理可能 s0 s4 s8 s12s1 s5 s9 s13s2 s6 s10 s14s3 s7 s11 s15

17

GF(28)バイトは加減乗除が

有限体 GF(28)• 集合として G(28) = {0,1}8

• (a7 a6 a5 a4 a3 a2 a1 a0) + (b7 b6 b5 b4 b3 b2 b1 b0)

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

(a7,a6,a5,a4,a3,a2,a1,a0) + (b7,b6,b5,b4,b3,b2,b1,b0)= (a7+b7,a6+b6,a5+b5,a4+b4,a3+b3,a2+b2,a1+b1,a0+b0)    ( + は XOR )

• (a7,a6,a5,a4,a3,a2,a1,a0) ・ (b7,b6,b5,b4,b3,b2,b1,b0)= (c c c c c c c c )= (c7,c6,c5,c4,c3,c2,c1,c0)

ここで7 6 5 4 3 2c7x7+c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0 

= (a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0 ) ・ (b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 )mod (x8=x4+x3+x+1)

例えば

x7 ・(x2 + 1) = x9 + x7 = x・(x4+x3+x+1) + x7

= x7 + x5 + x4 + x2 + x

例えば (10000000)+(00000101) = (100000101)

 x + x + x + x + x

∴ (10000000)・(00000101) = (101110110)18

S1. 各siの、GF(28)の要素としての、逆数 si‐1 をとる。（ただし、0‐1=0とおく。）2. 各si‐1 に（ある）アファイン変換を施す。

s0 s4 s8 s12 s0‐1 s4‐1 s8‐1 s12‐1

1 1 1 1s1 s5 s9 s13

s2 s6 s10 s14

s1‐1 s5‐1 s9‐1 s13‐1

s2‐1 s6‐1 s10‐1 s14‐1逆数

s3 s7 s11 s15 s3‐1 s7‐1 s11‐1 s15‐1

s0’ s4 ’ s8 ’ s12 ’アファイン変換

s1 ’ s5 ’ s9 ’ s13 ’

s2 ’ s6 ’ s10 ’ s14 ’

19

s3 ’ s7 ’ s11 ’ s15 ’

shift‐rows とmix‐colshift 横方向に転置

s0 s4 s8 s12s0 s4 s8 s12

shift‐rows :  横方向に転置

0

s1 s5 s9 s13

s2 s6 s10 s14

s5 s9 s13 s1

s10 s14 s2 s6

1

2

s3 s7 s11 s15s15 s3 s7 s113

mix‐cols： 縦方向に（換字しながら）転置

s0 s4 s8 s12

s1 s5 s9 s13

s0’ s4’ s8’ s12’

s1’ s5’ s9’ s13’

02 03 01 01

01 02 03 01x

s2 s6 s10 s14

s3 s7 s11 s15

s2’ s6’ s10’ s14’

s3’ s7’ s11’ s15’

01 02 02 03

03 01 01 02

x

20

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

E = {Ek}k∈K : 置換族Ek: {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 ← Ek(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は差分解読や線形解読に対して（証明可能）安全。

22

差分解読オラクル

識別者 ク を差分識別者 限定オラクル

System 0:  H(・) System 1:  Ek (・)

u

識別者のクラスを差分識別者に限定

差分識別者a,b

パラメータ: a,b∈ {0,1}n v, { , }

以下を(ある回数)繰り返す:u ←$ {0,1}n

オラクルに u を尋ねて v1 を得る。オラクルに u+aを尋ねて v2 を得る。if v2 = v1 + b

よいa,bをみつけることが暗号解析者の腕の見せどころ

output 1 and haltelse

continueブロック暗号E = {Ek}が差分解読に対して安全

output 0

ブ ック暗号E   {Ek} が差分解読に対して安全⇔

どのような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:  Ek (・)

線形識別者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 ・ bc ← 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] –

240 or  1

| Pr[線形識別者a,b,A 1 | System0] Pr[線形識別者a,b,A =1 | System1] | 

が無視できるほど小さい。

識別利得 ⇒ 鍵の情報

E = {Ek}k∈{0,1}^l : ラウンド数 rのブロック暗号E‐ = {E‐k}k∈{0,1}^l : Eから 終ラウンドを除いたブロック暗号、ラウンド数 r‐1

ある a,bがあって、 E‐に対する識別者a,bの識別利得が大きいとする。次のようにして、 終ラウンド鍵krを求めることができる。r

1. Ekの(平文、暗号文)対を集める:(Xi (Yi L Yi R))(Xi, (Yi,L, Yi,R))

2. K ← krのランダムな推測値Zi L = f(K, Yi L) + Yi Ri,L f(K, Yi,L) Yi,RZi,R = Yi,L /*  Kが正しければ、 (Xi, Zi)はE‐の(平文、暗号文)対 */

Zi = (Zi L, Zi R) を Xiに対する応答として、識別者a b を実行し、i ( i,L, i,R) i a,bその識別利得K を求める。

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

25

k

XL XR

k1fEE‐‐

k2L1 R1

f

L1 R1

f

L2 R2

K

26

YL YR

3 公開鍵暗号3. 公開鍵暗号

–計算の非対称性の発見

27

公開鍵暗号

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

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

• 鍵生成アルゴリズムG:   (pk, sk)  ←  G(k)• 暗号化アルゴリズムE： c ← Epk(m)• 復号アルゴリズムD：m ← Dsk(c)

m

ただしm = Dsk(Epk(m)))．pk, c からmを求めることは困難(一方向性）

pk 

S

m sk 

p

c

Rc ← Epk(m)

m ← Dsk(c)

m  28

たとえば・・・

N = pq ： 大きな2つの素数の積pqe: φ(N)=(p‐1)(q‐1)と互いに素な整数

( ) ( { })y = RSAe,N(x) = xe mod N          (x ∈ {0,1,・・・,N‐1})

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

すなわち、y,e,Nを与えられても y = RSAe,N(x) となる x は求められない。

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

29

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

RSA 関数とRSA仮定N=0

1N‐1

N1

• xから

• N = pqy = RSAe,N(x) = xe mod N

• x からy = xe mod N となるyを

求めるのは容易

• y からy = xe mod N となる x を求めるのは困難

xy

求めるのは困難

y(=xe mod N)

x から出発して何周して にな たのか？

30

何周してy になったのか？偶数回それとも奇数回？

Nが素数のときは・・・( ) d

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

y = RSAe,N(x) = xe mod N

Nが素数pのときは、y から y   RSAe,p(x) となる x を求めるのは容易。

φ(p) = p – 1, d = e‐1 mod (p‐1)RSAd p = RSAe p

‐1RSAd,p  RSAe,p

• N = pqのときもRSAd N = RSAe N‐1  ( d = e‐1 mod φ(N) )。N   pqのときもRSAd,N  RSAe,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：Epk(m) = me mod N           // = RSAe,N(m)p ,

•復号アルゴリズム D：Dsk(c) = cd mod N             // = RSAd N(c)sk( ) // d,N( )

• RSAd N = RSAe N‐1 [ オイラーの定理 ]d,N e,N [オイラ の定理 ]

• RSA仮定： RSAe,N は一方向関数32

素数を法としたべき乗数

p: 素数q: p‐1 を割る素数q pg : mod p で位数がqの整数

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

{1, g mod p, g2 mod p, …., gq‐1 mod p}<p, q, g> 指定

全て異なる巨大な数の（算法つき）集合(gq mod p = 1)

43 7 4

例例

<p=43, q=7, g=4>g0 mod p = 1,  g mod p = 4g2 mod p = 16,  g3 mod p = 21g4 mod p = 41,  g5 mod p = 35        g6 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で位数がqg : mod p で位数がq

<p, q, g>に対してp, q, g に対して

CDH仮定

a, b  ←$ {1,2,・・・,q}どんな効率的なアルゴリズムも、ga mod p と gb mod p を与えられて、gab mod p を求めることはできない。与えられて、g mod pを求める とはできない。

• <p=43, q=7, g=4>g3 mod p 21 g5 mod p 35 g15 mod p 4

？？

34

g3 mod p = 21,  g5 mod p = 35  g15 mod p = 4

DDH仮定<p, q, g>に対して

b $ { }

DDH仮定

a, b, c  ←$ {1,2,・・・,q}どんな効率的なアルゴリズムも、ga mod p と gb mod p を与えられても、gab mod p と gc mod p を区別できない。

すなわち

ga mod p と gb mod p を教わっても gab 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, gq = 1 mod px ←$ {1, ・・・,q‐1}, y ← gx mod ppk {p g q y} sk {p g q x}pk = {p,g,q,y},  sk = {p,g,q,x}

•暗号化アルゴリズム Epk(m)：$ { }r ←$ {1, ・・・,q‐1}

c = (gr mod p, myr mod p)  

•復号アルゴリズム Dsk(c1,c2)：c2 / c1x mod p

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

36

エルガマル暗号のからくり( r r)

yr = gxry = gxc = (gr, myr)  

y g

EDec

r

Enc

rgx

gr

xCDH仮定

gr

gx

37

RSA暗号に対する攻撃

“賛成” pk={n,e} 

m ∈ {“賛成”，“反対”}

S

sk={n,d} 

RRc = “賛成”e mod n

c

“賛成”← cd mod npk={n e}

A

pk={n,e} 

“賛成”

c1 = “賛成”e mod nc2 = “反対”e mod n c = c ならば“賛成”

RSA暗号はな

賛成

c = c1 ならば 賛成

else “反対”IND‐CPAでない。

“賛成” 38

識別不可能性 （IND‐CPA)(G, E, D): 公開鍵暗号

オラクル

System 0 : [初期化]  (pk,sk) ← G[(m0,m1)に対して] c*← Epk(m0)[(m0,m1)に対して]  c  ← Epk(m0)

System 1 : 初期化[初期化]  (pk,sk) ← G

[(m0,m1)に対して]  c* ← Epk(m1)pk m0,m1 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} 

( )

Rc = (gr, 10yr)

c=(c1,c2)

pk={p g q y}1000 ← c2 /c1x mod n

A

pk={p,g,q,y} 

「本当に1000個も注文するの？」

c2’ = c2 x 100「本当に1000個も注文するの？」

c’=(c1,c2’)エルガマル暗号は

m = 1000/100 = 10エルガマル暗号はIND‐CCAでない。(DDH仮定のもとでIND‐CPA)40

識別不可能性 （IND‐CCA)(G, E, D): 公開鍵暗号

オラクル

System 0 : [初期化]  (pk,sk) ← G[(m0,m1)に対して]  c* ← Epk(m0)に対して[c に対して] m ← Dsk(c)    (c ≠ c*)

System 1 : [初期化] (pk sk)← G

pk m0,m1

c*c m c m

[初期化]  (pk,sk) ← G[(m0,m1)に対して]  c* ← Epk(m1)[c に対して] m ← Dsk(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}hH: {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

42

OAEP+f : {0,1}k → {0,1}k : 置換, g = f ‐1

k0+k1<k, 2‐k0,2‐k1: negligible, n = k‐k0‐k1G : {0 1}k0 → {0 1}n H’ : {0 1}n+k0 → {0 1}k1 H : {0 1} n+k1 → {0 1}k0G : {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}ny g

EE

x ∈ {0,1} f

w = g(y)DecDec

r ←$ {0,1}k0

s = (G(r) + x) ∥ H’(r∥ x)H( )

EncEnc s ∥ t = w

r = H(s) + tt = H(s) + rw = s ∥ ty = f(w)

x = G(r) + s[0..(n‐1)]c = s[n..(n+k1‐1)]

∥？

c = H’(r∥ x)：x

elsej t

？

reject

f がone‐wayならばOAEP+(f)はランダムオラクルモデルのもとでIND‐CCA 43

OAEP+の暗号文

x rx r暗号文の正当性をチェックするための冗長な情報

x + G(r) H’(r∥x) H(s) + r( ) ( ∥ ) ( )

s

f

r やsを知らずにな をy 正当な暗号文を

作ることはできない。

44

FO変換π = (K, E, D), H = {Hn}nπ’ = (K’, E’, D’) = FOH(π):

K’(1k) :(pk, sk) ← K(1k), H ←$ Hk

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

E’(pk’,m):r←$ R

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

m~ = m∥rc = Epk(m~; H(m~))

∧ γ⇒ π’ : IND‐CCA

D’(sk’,c):m~ = Dsk(c)∥ ~

γ(x,y) =def Pr[ γ←$ R : y = Epk(x;r)]

m∥r  = m~

c =? Epk(m~; H(m~)) :m

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

else⊥ 45

4 IDベ ス暗号4. IDベース暗号

46

IDベース暗号

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

E = (Setup, Extract, Enc, Dec)

(params master key) ← Setup(k)

鍵配布センター

• dID ← Extractparams(master‐key, ID)• c← Encparams (ID, m)• m ← Decparams (dID, c)

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

IDdID ← Extractparams (master‐key, ID)params ( ID, )

params ID  m 

ID params

送信者

paramsdIDparams

送信者

受信者 (ID)c ← Encparams(ID, m)c

m ← Decparams(dID, c)

m  47

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

S 0

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

System 0 : [初期化]  (params,master‐key) ← Setup[(m0,m1, ID*):]  c* ← Encparams(ID*, m0)[ID ] d← E t t ( t k ID) (ID ≠ ID*)

オラクル

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

System 1 : [初期化] ( t k )← S tparams

m0,m1,ID*

c*ID d ID d

[初期化]  (params,master‐key) ← Setup[(m0,m1, ID*):]  c* ← Encparams(ID*, m1)[ID:]   d ← Extractparams(master‐key, ID)    (ID ≠ ID*)

識別者

定義EがIND‐ID‐CPA安全

(*) (*)

識別者

0 or 1

が C 安全⇔どのような現実的な識別者Dに対しても

| Pr[D=1 | System0] – Pr[D=1 | System1] | 

48

0 or  1 | [ | y ] [ | y ] |が無視できるほど小さい。

Bilinear maps

G1, G2: 素数位数q の群

e : G1 x G1 → G2 が bilinear mapとは1 (Bilinear) e(aP bQ) = e(PQ)ab (∀PQ∈G ∀a b∈ Z)1. (Bilinear)    e(aP, bQ) = e(P,Q) (∀P,Q∈G1,∀a,b∈ Z)2. (非退化)     e(P,P) ≠ 1                         (∀P(≠0)∈G1)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):QID = H1(ID)

Setup(k):<q, G1, G2, e> ← G(k) QID  H1(ID)

r ←$ Zq*gID = e(QID, Ppub)c = < rP, m + H2(gIDr)>

q, 1, 2, G( )P ←$ G1, s ←$ Zq*, Ppub = s PChoose

H1 : {0 1}*→ G1* c rP, m H2(gID )

Decrypt(params, c=<U,V>, dID):m = V + H2(e(dID, U))

H1 : {0,1}  → G1H2 : G2 → {0,1}n

params = <q,G1,G2,e,n,P,Ppub,H1,H2>master key = s 2( ( ID ))master‐key = s

Extract(ID, params, s):Q H (ID) ( G *)QID = H1(ID) (∈G1*)dID = s QID ランダムオラクルモデルにおいて

BF暗号はGに対するBDH仮定のもとでGIND‐ID‐CPA安全。

50

BDH仮定

G1, G2: 素数位数q e : G1 x G1 → G2； bilinear map P∈ G1*P ∈ G1

<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 + H2(gIDr)>

gIDr = e(P,P)ksrPpub = sPU = rP

c U, 2(gID )

gID e( , )

EDec

U = rPQID = kP

k P ( d )

Enc

rkP

ksP (=dID)rPBDH仮定

sP

rPkP

自由度 ザ

52sP 自由度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 = 10   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でわった余り。

54

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 2005Applications 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.

55