/ ( ) 1 1.1 323 206 23 ( 23 529 529 323 206 ) 23 1.2 33

1.3 323 61 61 3721 3721 323 168 168 323 23 61 61 23 1403 323 111 111 168 206 323 47 111 323 47 2 23 2 2.1 34

2 2.2 2 a, b N a b N a b (mod N) mod N 32 2 30 15 2 32 2 (mod 15) (1) 32 2 15 21 6 15 15 21 6 15 21 6 (mod 15) (2) 323 206 X 2 206 (mod 323) a 1 b 1 (mod N), a 2 b 2 (mod N) a 1 + a 2 b 1 + b 2 (mod N) a 1 a 2 b 1 b 2 (mod N) (1) (2) 32 + 21 2 + 6 (mod 15) 32 21 2 6 (mod 15) c N ( 1) ca cb (mod N) a b (mod N) 35

N c c N (1) 2 16 1 (mod 15) (2) 3 7 2 (mod 15) 7 2 (mod 5) 2 15 3 15 2.3 2 X 2 206 206 100 = 10 2 400 = 20 2 10 X 20. 10 20 10+20 2 = 15 15 2 = 225 206 X 15 10 X 15. 10 15 10+15 2 = 12.5 12.5 2 = 156.25 206 X 12.5 12.5 X 15. X X = 14.35270009 N = 323 X 2 206 (mod 323) N = 323 x = 0 x 1 1 N = 323 0 N a X 2 a (mod N) X N a ( ) 36

N N 4 1 N ( N N N ) N ( N ) N N 3 P V P V x w w (P, V ) L (L ) x w ( ) P w V P P V ( ) P w V V P P V ( ) V P x ( ) V P 3 [4] 3 w V P w 3 37

3.1 X 2 a (mod N) X = w 1 [3] P X 2 a (mod N) (a, N) X = w V (a, N) P V V V [ ] 1. ( 1 ) P 0 (N 1) r r N c = r 2 mod N P c V 2. ( ) V e 0 1 P 3. ( 2 ) P e 0 c r y (y = r) e 1 r w N y (y = rw mod N) P y V 4. ( ) V c e y y 2 ca e (mod N). 1: 1 e = 0 a 0 1 V ) y 2 c (mod N) y = r c r e = 1 y 2 ca (mod N) y w y rw w a P a w V P ( ) ( ) P V P 1 c P V 38

V e e = 0 e = 1 y ( V e = 0 e = 1 ) 2 y y 0, y 1 y 0, y 1 P y 2 0 c (mod N) y 2 1 ca (mod N) (2 c ) (y 1 /y 0 ) 2 a (mod N) 1 w = y 1 /y 0 X 2 a (mod N) y 0, y 1 P y 1 /y 0 P w P 1 P w V r y r c c r V y r w P w V y r w w V P x ( ) S( ) S: 1. ( ) X 2 a (mod N) (a, N) 2. ( ) e 0 1 3. ( ) y e c c = y 2 /a e mod N 4. ( ) S (a, N) V V c ( ) e e e 1 y 0 ( c) N y 0 ( c) N N y 0 ( c) N 39

5. ( ) V r S V e e y c (c = y 2 /a e mod N y 2 ca e (mod N) ) e S V c r P w ( ) ( ) e e 0,1 2 2 e ( c y e V c V e ) S w V V c y ( ) w w (a, N) S 3.2 3.2.1 p 2 g, h g x h (mod p) x ( ) p h g ( ) p = 43 4 x 35 (mod 43) x x = 0 4 x mod 43 4 0 mod 43 = 1, 4 1 mod 43 = 4, 4 2 mod 43 = 16, 4 3 mod 43 = 21, 4 4 mod 43 = 41, 4 5 mod 43 = 35, x = 5 x p p 2 len(p)1/3 len(p) p p 40

p x ( p ) 3.2.2 g x h (mod p) x = w 2 [6] P g x h (mod p) (p, g, h, q) x = w ( q g q 1 (mod p) q q g g ) V (p, g, h, q) 1. ( 1 ) P 0 (q 1) r g p r c = g r mod p P c V 2. ( ) V e 0 (q 1) P 3. ( 2 ) P e r w y = (r + ew) mod q P y V 4. ( ) V c e y g y ch e (mod p). 2: 2 ( 1) e 1 q 1 41

P w y g y = g r+ew = g r (g w ) e ch e (mod p) V ( ) P V c ( )2 e 0, e 1 y 0, y 1 g y 0 ch e 0, g y 1 ch e 1 (mod p) g y 0 y 1 h e 0 e 1 (mod p). P w = (y 0 y 1 )/(e 0 e 1 ) V e ( P w ) V V P {(c, e, y) : r $ {0,..., q 1}, e $ {0,..., q 1}, c = g r mod p, y = (r + ew) mod q} w {(c, e, y) : e $ {0,..., q 1}, y $ {0,..., q 1}, c = g y h e mod p} V P w 3.3 F F s r LOOP: 1. m 42

2. s r s m F : (s, m ) F (s, r, m). 3. m 4. s s LOOP (m, m ) (s, m ) = F (s, r, m) s, s, r F F F ( ) ( ) F 4 4.1 M 1. pk Bob 2. pk Bob M C 3. C ( ) 4. sk Bob C M 43

pk Bob C sk Bob C M pk Bob sk Bob pk Bob sk Bob C pk Bob sk Bob 4.1.1 ( ) 3 ES = (Gen, Enc, Dec) Gen(k) k pk sk ( k ) Enc(pk, m) m pk c Dec(sk, c) sk c m ) (pk, sk) Gen(k), c Enc(pk, m) Dec(sk, c) = m ) sk pk c m 44

4.2 [2] Gen(k) 2 p, q (1 ) g g q 1 (mod p) q k ( p, q, g ) 0 (q 1) x g p x y = g x mod p (p, q, g, x) sk (p, q, g, y) pk Enc(pk, m) pk p, q, g, y 0 (q 1) r g p r c 1 = g r mod p ( )y p r m c 2 = my r mod p c 1 c 2 c = (c 1, c 2 ) c Dec(sk, c) sk p, q, g, x c c 1, c 2 c 1 x c 2 m = c 2 /c x 1 mod p m p, q, g 0 (p 1) ( m 0 (p 1) g ( α g α mod p) ) k = 3 ( k 160 ) 2 p = 43, q = 7 g = 4 4 7 1 (mod 43) q k = 3 0 q 1 = 6 x = 3 y = g x mod p = 4 3 mod 43 = 21 (p = 43, q = 7, g = 4, x = 3) sk (p = 43, q = 7, g = 4, y = 21) pk m = 11 pk p = 43, q = 7, g = 4, y = 21 0 q 1 = 6 r = 2 c 1 = g r mod p = 4 2 mod 43 = 16 c 2 = my r mod p = 11 21 2 mod 43 = 35 m = 11 c = (16, 35) Dec(sk, c) sk p = 43, q = 7, g = 4, x = 3 c c 1 = 16, c 2 = 35 45

c 2 /c x 1 mod p = 35/163 mod 43 = 11 pk = (p, q, g, y) sk = (p, q, g, x) y g x (mod p) pk = (p, q, g, y) m c = (c 1, c 2 ) r c 1 = g r, c 2 = my r c 2 /c x 1 (my r )/(g r ) x (mod p) (m(g x ) r )/(g r ) x (mod p) m (mod p). c m ( sk ) A pk = (p, q, g, y) c = (c 1, c 2 ) c 1, c 2 r c 1 = g r, c 2 = my r c 2 A m y r A g, y, c 1 = g r y r A c 1 = g r r y y r 2 g, y, c 1 = g r y r r m m m 4.3 4.3.1 CPA 4.1.1 pk c m ES = (Gen, Enc, Dec) A CPA CPA : k 1. (.) k Gen (pk, sk) 46

2. (A.) pk A( ) A 2 (m 0, m 1 ) b 0 1 m b pk Enc ( )c A 3. (.) A ˆb ˆb = b A A A pk 2 m 0, m 1 (m 0, m 1 ) m b c A c m 0 m 1 ˆb ˆb = b A A A 1/2 CPA c m b 1/2 b CPA ES CPA A CPA 1/2 ) 4.3.2 CPA DH CPA DH p, q g g q 1 (mod p) g a mod p g b mod p g ab mod p DH DH DH p 0 q 1 a, b DH DH DH g a mod p g b mod p g c mod p c ab (mod q) DH DH DH 2.1 DH p 0 q 1 a, b, c g a mod p g b mod p z = g ab mod p z = g c mod p 47

z z 1/2 z = g ab mod p z = g c mod p z 1/2 1 DH CPA CPA A DH D DH DH CPA CPA A CPA 1/2 A DH D D 0 q 1 a, r, c (g a mod p, g r mod p, z) z 1/2 z = g ar mod p z = g c mod p D z 1/2 mod p D: (g a, g r, z) 1. (.) A pk = (p, q, g, g a ) g a D 1 2. (.) A (m 0, m 1 ) b 0 1 π = (g r, zm b ) A g r D 2 z 3 3. (.) A ˆb ˆb = b z = g ar z = g c D z z = g ar 1/2 A π π = (g r, zm b ) = (g r, g ar m b ) = (g r, (g a ) r m b ) pk = (p, q, g, g a ) m b z = g ar D A CPA A CPA 1/2 A b (ˆb = b) D z = g ar 1/2 z z = g ar D z p 0 1/2 D z z = g c 1/2 π = (g r, zm b ) = (g r, g c m b ) b c 48

b = 0 b = 1 π 2 g c m b m b g ( α g α ) m b = g α c α g c m b = g c+α {g 0, g 1,..., g q 1 } b c m b g c b π b A b (ˆb = b) 1/2 b c A ˆb b D z = g c p 1 1/2 D 1/2p 0 + 1/2p 1 = 1/2p 0 + 1/4 p 0 1/2 1/2 D DH 4.3.3 CPA 1. 10 m = 10 c = (g r mod p, 10 y r mod p) (p, q, g, y(= g x )) 1 2. A c = (c 1, c 2 ) c 2 100 c 2 = 100 c 2 mod p c = (c 1, c 2 ) A (c 1 ) 3. A c = (c 1, c 2 ) c 2/c x 1 = (100 10 y r )/(g r ) x mod p = 1000. A 1000 A 4. A 1000 100 10 c = (c 1, c 2 ) A 4.3.4 CCA 4.3.3 CCA 49

CCA ES = (Gen, Enc, Dec) A CCA : k 1. (.) k Gen (pk, sk) 2. (A.) pk A( ) A A (.) A c c c sk Dec m A A (.) A 2 (m 0, m 1 ) b 0 1 m b pk Enc c A 3. (.) A ˆb ˆb = b A A A (m 0, m 1 ) m b c m 0, m 1 ˆb CPA CCA A A CCA A m 0, m 1 c c A m b ES CCA A CCA 1/2 ) CCA CCA A A: pk = (p, q, g, y) 1. (.) m 0, m 1 (m 0, m 1 ) c = (c 1, c 2 ) 50

2. (.) c 2 g c 2 = c 2g mod p c = (c 1, c 2 ) m 3. (.) m m 0 g mod p 0 1 A 4.3.3 A 4.4 [5, 8] c 1 = g r r r r σ c = (g r, my r, σ) e 2 H H H Gen(k) 2 p, q (1 ) g g q 1 (mod p) q k ( p, q, g ) H : {0, 1} {0, 1,..., q 1} 0 (q 1) x g p x y = g x mod p (p, q, g, x) sk (p, q, g, y) pk Enc(pk, m) pk p, q, g, y 0 (q 1) r pk m (c 1 = g r, c 2 = my r ) r c 1 σ 0 (q 1) s u = g s mod p e H (c 1, c 2, u) e = H(c 1, c 2, u) z r z = s+er σ = (u, z) (c 1, c 2 ) σ c = (c 1, c 2, σ) Dec(sk, c) sk p, q, g, x c c 1, c 2, σ = (u, z) 2 H : {0, 1} {0, 1} h H H(x) = H(y) x, y (x y) 51

σ e H (c 1, c 2, u) e = H(c 1, c 2, u) (u, e, z) u = g z c e 1 mod p c = (c 1, c 2 ) sk m = c 2 /c x 1 mod p m p, q, g 0 (p 1) ( m 0 (p 1) g ( α g α mod p) ) 4.4.1 A A c = (g r, c 2, σ) A c = (g r, c 2, σ) 1 g r c = (g r, c 2, σ ) A c σ 1 g r r σ A 1 g r r σ A c = (g r, c 2, σ) g r c = (g r, c 2, σ ) r σ r σ σ c 2 c 2 c 2 c 2 A (g r, c 2 ) H e = H(g r, c 2, u) e = H(gr, c 2, u) z z σ = (u, z) e = H(c 1, c 2, u) c 2 e = H(c 1, u) A subtle A c = (g r, c 2, σ) g r c = (g r, c 2, σ ) A 52

2 (Schnorr, Jakobsson 00[7]) CCA v H(u) v H(u) u v h {H : {0, 1} {0, 1} h } H u H u H(u) h g a 1 1 ga i i (g 1,..., g i ), (a 1,..., a i ) h (g 1,..., g i ), (a 1,..., a i ) g a 1 1... ga i i 4.5 c = (g r, my r, σ) r σ DH (c 1 = g x, z = h x x) [1] 53

Gen(k) 2 p, q (1 ) g g q 1 (mod p) q k ( p, q, g ) 2 H : {0, 1} {g i mod p i = 0, 1,..., q 1} G : {0, 1} {0, 1,..., q 1} 0 (q 1) a g p a b = g a mod p (p, q, g, a) sk (p, q, g, b) pk Enc(pk, m) pk p, q, g, b 0 (q 1) x pk m (c 1 = g x, c 2 = mb x ) DH c 1 x σ 0 (q 1) k u = g k mod p, h = H(u, c 1 ) z = h x, v = h k c G (c 1, c 2, h, z, u, v) c = G(c 1, c 2, h, z, u, v) s x s = k + cx σ = (z, s, u, v) (c 1, c 2 ) σ c = (c 1, c 2, σ) Dec(sk, c) sk p, q, g, a c c 1, c 2, σ = (z, s, u, z) σ c G (c 1, c 2, h, z, u, v) c = G(c 1, c 2, h, z, u, v) (u, v, c, s) DH u g s c c 1, v hs z c (mod p) c = (c 1, c 2 ) sk m = c 2 /c a 1 mod p 3 ( 09 [9]) DH CCA [1] B. Chevallier-Mames, An Efficient CDH-based Signature Scheme With a Tight Security Reduction, CRYPT 2005, pp. 1-27, 2005. [2] T. ElGamal, A Public-key Cryptosystem and a Signature Scheme Basedon Discrete Logarithms, CRYPTO 84, LNCS 196, pp.10-18, Springer-Verlag, 1985 [3] Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Proc. Of Crypto 86, LNCS 263. [4] O. Goldreich, Foundations of Cryptography: Volume 1 - Basic Tools, Cambridge University Press, 2001. [5] M. Jakobsson, A Practical Mix, Eurocrypt 98, LNCS 1403, pp. 448-461, 1998. [6] C. P. Schnorr, Efficient signature genoration by smart cards, Journal of Cryptology, 4(3), pp. 161-174, 1991. [7] C. P. Schnorr and M. Jakobosson, Security of Signed ElGamal Encryption, ASIACRYPT 2000, LNCS 1976, pp. 73-89, 2000. 54

[8] Y. Tsiounis and M. Yung, On the Security of ElGamal Based Encryption, PKS 98, LNCS 1431, pp. 117-134, 1998. [9],,, Signed, 2009, SCIS 2009, 2B2-1, 2009/1. 55