Block cipher

18 12 9 1 2 1.1............................... 2 1.2.................. 2 1.3................................. 4 1.4 Block cipher............................. 4 1.5 Stream cipher............................ 5 1.6.......................... 5 2 6 2.1 Diffie-Hellman........................ 6 2.2............................... 8 2.3...................... 8 2.4 DLP........................... 10 2.5........................ 10 2.6 ElGamal....................... 11 2.7 RSA........................... 11 2.8............................. 12 2.9............................... 13 2.10................................. 17 Douglas R. Stinson Cryptography: Theory and Practice CRC Press, 1995. 1

1 1.1 (Alice) (Bob) (Oscar) Oscar 1.2 2 1.1. ASCII A 01000001, B 01000010,... 2 8 8 (2 8 0 255) 1.2. ( ) 26 0 25 K 26 26 K 1.3. K=3 iloveyou 8, 11, 14, 21, 4, 24, 14, 20 11, 14, 17, 24, 7, 1, 17, 23 loryhbrx 1.4. 2

1. P: (plaintext) 2. C: (ciphertext) 3. K: (key) 4. e : K P C: (encryption function) 5. d : K C P: (decryption function) x P, k K, d(k, e(k, x)) = x. k x k e(k, x) d(k, ) d(k, e(k, x)) = x k 1.5. K = C = P = Z/26 := {0, 1,..., 25} mod 26 e(k, x) = x + k, d(k, y) = y k 1.6. d(k, ) d(k, ) : C P, y d(k, y) (break the cipher) K e(k, x) k K d(k, ) P k P 26 K k K e(k, ) : P C 3

e C e success, balloon c,s,l,o ii,aa q u k P C P P 2 128 2 256 1.3 P, C, K, e, d Oscar Oscar Alice Bob k K Oscar k Oscar Oscar (known plaintext attack) Oscar k Oscar Oscar Alice Oscar (chosen plaintext attack) 1.4 Block cipher P C P P = C 256 e(k, ) : P C 4

256 256 e(k, ) C 256 AES 2 256 26 1.5 Stream cipher k k 1, k 2,..., k n P n Alice Bob k K k 1, k 2,..., k n Alice i P e(k i, ) Bob Bob d(k i, ) SNOW2.0 F 2 16 e(k i, ) k i F 2 k i x 1,..., x i 1 1.6 Shannon e : K P C x P e(, x) : K C P n Alice K n (k 1, k 2,..., k n ) Bob x 1, x 2,..., x n e(k 1, x 1 ), e(k 2, x 2 ),..., e(k n, x n ) k 1,..., k n (one-time pad) k i P n 5

2 2.1 Diffie-Hellman DH Alice Bob Oscar Alice Bob Oscar k Alice S s A S Alice Bob Oscar s A Bob Oscar Bob s B s A s B Alice Bob Oscar s A Bob Oscar Alice Oscar Alice Bob f s A f(s A ) Bob Alice s B f(s A ) g(s B ) Bob Alice s A, g(s B ) 6

Bob f(s A ), s B Oscar f(s A ), g(s B ) f, g Alice, Bob f g f(s A ) s A Oscar Oscar Alice s A g(s B ) f(s A ) s B f(s A ) g(s B ) Alice Bob Diffie-Hellman S T S T T,, s, t s t s 1 (s 2 t) = s 2 (s 1 t) S, T t T Alice s A S Bob s B S Alice s A t Bob Bob s B t Alice Alice s B (s A t) Bob s A (s B t) Oscar s A t, s B t s A s B t t s t r NP=P (discrete log problem, DLP) G S = N, T = G, N G G, (n, g) g n (g, g n ) n DLP (Z/p), F pn, DLP 7

DLP Alice (g r A ) Bob Bob (g r B ) Alice Alice (g r A ) r B Bob (g r B ) r A (g, g r A, g r B ) g r Ar B DH intruder in the middle Oscar Alice Bob Alice Bob Bob Alice Alice Alice Bob Bob 2.2 G g n g n n O(log n) n = 13 = (1101) 2 1, 11, 110, 1101 4 ( 2 ) g, g 11 = g 10 g, g 110 = (g 11 ) 10, g 1101 = (g 110 ) 10 g 2 (binary method) 2.3 DH G, g G g G g < g > G G G = Z/N (N ) Z/N Z/N O((log N)) Z/N g, z Z/N z = rg r z rg mod N 8

r z = rg + bn r b x, y, z ax + by = z a, b a, b a x + b y = z (a a )x + (b b )y = 0 d := gcd(x, y), x = x 0 d, y = y 0 d (a a )x 0 = (b b)y 0 x 0 y 0 x 0 y 0 m a a = my 0, b b = mx 0 (m Z) d z d z ax + by = d a, b z/d a, b d ax + by qx + y y x r x + qr x r x, y d O(log α N) α (1 + 5)/2 O(log 2 N) = O(log 2 (α) log α (N)) = O(log α N) 9

O(log N) Z/N DLP φ : Z/N = G, n g n DH 1, r A, r B r A r B φ DLP DH 2.4 DLP n S n n DLP g, y S n y = g r r g {1, 2,..., n} y g i n i y = g r i r i r r i mod n i r 2.5 Alice Bob k e k d e : K e P C d : K d C P e(k e, ) d(k d, ) = id P (k e, k d ) K e K d 10

Alice k e k d k e k d Bob Alice Bob e(k e, ) Oscar Alice d(k d, ) k e k d k e d(k d, ) Alice Bob Bob k e k d k e 2.6 ElGamal G g G P := G, C := G G, K e = G, K d := Z Alice k e := g a k d := a Bob e(k e, x) = (g r, xk r e) (= (g r, xg ar )) r Bob e Alice d(k d, (y, z)) = zy k d (= (zy a )) 2.7 RSA RSA 1977 Alice G m Alice a ab 1 mod m b P = C = G K e = K d = Z/φ(n) Alice G k e := a k d := b 11

e(x, a) := x a d(y, b) := y b (x a ) b = x ab = x 1 ab 1 mod m m m Oscar a b G RSA n G := (Z/n) φ(n) φ(n) n φ(n) Alice p, q n = pq φ(n) = (p 1)(q 1) n n = pq φ(n) p + q = n φ(n) + 1 pq = n p, q ( 2 500 ) 2.8 RSA Alice private 12

Oscar 2 500 2 n 1 (Mersenne Prime ) 2 500 2 501 1 2.9 N N 2 500 Fermat 2.1. (Fermat ) n a (Z/n) a n 1 = 1 mod n. (Z/n) n 1 Fermat 1. a Z/n, a 0 2. a n 1 mod n 3. 1 n 1 n n a n 2.2. a (Z/n) {0} Fermat n Carmichael 10000 Carmichael 561, 1105, 1729, 2465, 2821, 6601, 8911 Carmichael Fermat Miller-Rabin 13

Miller-Rabin 2.3. n 3 a (Z/n) {0} n 1 2 n 1 = 2 r d, d a d = 1 a 2kd = 1 0 k < r. a 2rd = 1 a 2kd 1 0 k < r a d = 1 (a 2kd ) 2 = 1 x 2 1 = 0 1, 1 n 3 k a 2kd = 1 Miller Rabin n 3 1. n 1 = 2 r d, d: 2. a Z/n, a 0 3. a d, a 2d, a 4d,... a 2r 1d 1 1 n 4. n n a (witness) Carmichael Fermat Miller-Rabin Fermat 2.4. n (Z/n) Miller-Rabin 1/4 n a (Z/n) Miller-Rabin 3/4 n 1/4 n 100 Miller-Rabin 4 100 = 2 200 10 30 100 Miller-Rabin n 2.4 3 14

2.5. p (Z/p e ) (p 1)p e 1 2.6. 3 G > H > N H/N G/N G/H = (G/N)/(H/N). ( 2.4 ) n = p e 1 1 p e s s (Z/n) = (Z/(p e 1 1 )) (Z/(p e s s )) a (a 1,..., a s ) a (Z/n) a d = 1 k a 2kd = 1 a ( a) d = 1 k 0 a a 0 k r 1 K L := {a (Z/n) a 2Kd = ±1} K {a : } L a a d = 1 a 2kd = 1 (0 k < r) [(Z/n) : L] 4 L := {a = (a 1,..., a s ) a 2K d i = ±1( i)} < (Z/n) L > L f := ( ) 2Kd : (Z/n) (Z/n) L = f 1 ({(1, 1,..., 1), ( 1, 1,..., 1)}), 15

L = f 1 ({(±1, ±1,..., ±1)}), ±1 K a 2Kd = 1 a f : L {(1, 1,..., 1), ( 1, 1,..., 1)} a a = (a 1,..., a s ) a i 1 a a 2 Kd = (±1,..., ±1) 2.6 f : L ({(±1, ±1,..., ±1)}) L /L = (L/ ker f)/(l / ker f) = {(±1, ±1,..., ±1)})/({(1, 1,..., 1), ( 1, 1,..., 1)}). s 3 2 s 1 4 s = 1 n = p e 2.5 (Z/(p e )) (p 1)p e 1 L 2 K+1 d p e 1 p 1 1/p e 1 1/4 p = 3, e = 2 (Z/9) = {1, 2, 4, 5, 7, 8} 2,4,5,7 1/4 s = 2 n = p e 1 1 p e 2 2 [L : L] = 2 [(Z/n) : L ] 2 (Z/n) = L L 2 K d ±1 a 2K+1d = 1 2 K+1 d n 1 n Carmichael 2.7. n Carmichael 1. n Z/n = Z/(p e 1 1 ) Z/(p es s ) (p i 1)p e i 1 i n 1 1 (p i 1)p ei 1 n 1 p i e i = 1 n = pq p 1 pq 1 mod (p 1) pq 1 q 1 p 1 q 1 q 1 p 1 p = q 16

2.10 Alice x P Alice identify 2.8. (signature scheme) P A K s : K v : s : K s P A: v : K v P A {T, F }: k s K s, k v K v v(k v, x, a) = T a = s(k s, x) Alice k s k v k v k s x Alice x s(k s, x) (x, s(k s, x)) Alice Bob (x, a) Alice k v v(k v, x, a) T (True) a Alice Oscar Alice k s k v Alice k s Alice Oscar Alice x Alice Bob Alice (x, a) Bob e(k e,b, (x, a)) Bob Bob (x, a) Alice k v Alice Alice Bob Alice Oscar e(k e,b, (x, a)) Bob Bob Alice 17

Alice Bob RSA n = pq P = A = Z/n k s, k v Z/φ(n), k s k v = 1 s(k s, x) := x k s, v(k v, x, a) := a kv = x RSA Alice k s k d,a k v k e,a Alice x a a = x k d,a Bob ( ) k e,b Bob Bob ( ) (x, a) x a k e,a Alice 18