public key private key Encryption Algorithm Decryption Algorithm 1

Size: px

Start display at page:

Download "public key private key Encryption Algorithm Decryption Algorithm 1"

일국 도
5 years ago
Views:

1 public key private key Encryption Algorithm Decryption Algorithm 1

2 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given y, x = f 1 (y) is difficult Integer Multiplication vs. Factorization - a b y is easy, where a and b are primes. - y a and b is difficult Modular Exponentiation vs. Discrete Logarithm - f(x) = a x mod n y is easy, Exponential Function - y x = log a y mod (n 1) Trapdoor One-Way Function One-Way Function, where some trapdoor information makes the function invertible Power Function, y = f(x) = x a mod n, where a and n are given - f 1 (y) = x is also power function, where x = (x a ) b mod n a b mod φ(n) = 1 - If n = p q, where p and q are large primes, f(x) is trapdoor function. - Euler, x φ(n) mod n = 1, where φ(n) = (p-1) (q-1) 2

3 m E ke (m) = c is easy, but c D kd (m) = m is difficult without knowing D kd. E ke is a Trapdoor one-way Function D kd is a Trapdoor Information D kd (E ke (m)) = m E ke (D kd (m)) = m D kd (E ke (m)) = E ke (D kd (m)) = m Domain of E and D should be large to avoid Dictionary Attack RSA ( Rivest-Shamir-Adleman ) System choose 2 primes p and q and compute n = p q, φ(n) = (p-1) (q-1), where p, q are 100-digit numbers choose e [1, φ(n)-1] such that (e, φ(n)) = 1 and d [1, φ(n)-1] such that e d modφ(n) = 1 (e,n) : public-key (d,n) : private-key RSA Encryption and Decryption m,c {1,2,...,n-1} Encryption : c = m e mod n Decryption : m = c d mod n = m ed mod n, where e d modφ(n) = 1 3

4 RSA ( Rivest-Shamir-Adleman ) Example p = 47 and q = 71, n = p q = 3337 (p 1) (q 1) = = 3220, GCD ( e, (p 1) (q 1)) = 1 Choose e at random to be 79 d = 79 1 mod 3220 = 1019 To encrypt message m = m 1 = 688 m 2 = 232 m 3 = 687 m 4 = 966 m 5 = 668 m 6 = 003 c 1 = m e 1 mod n = mod 3337 = 1570 c = To decrypt, m 1 = c d 1 mod n = mod 3337 = 688 Security of RSA Factorization of n = p q - n and e are known; e d mod(p 1) (q 1) = 1 Number Field Sieve, Quadratic Sieve, Elliptic Curve Method (1983 ) 69 10, Quadratic Sieve (1989 ) , Quadratic Sieve (1994 ) RSA-129, , Quadratic Sieve, 5000 mips-year n = 114,381,625,757,888,867,669,235,779,976,146,612,010,218,296, 721,242,362,562,561,842,935,706,935,245,733,897,830,597,123, 563,958,705,058,989,075,147,599,290,026,879,543,541 (1996 ) RSA-130, , Number Field Sieve, 500 mips-year 4

5 Security of RSA ➀ ➁ ➂ Security of RSA Ciphertext-only Attack Solving c = m e mod n is equivalent to taking roots modulo a composite number with unknown factorization, which is as difficult as the discrete logarithm. Iterative Attack Given (N,e, c), c 1 = c e mod N,..., c i = c i-1 e mod N If there is c j in c 1,c 2,...,c i,... such that c j = c, m is the same as c j-1 since c j-1 e mod N = c j = c. Adaptively Chosen-Ciphertext Attack c = m e mod n, x (0, n 1) c = cx e mod n m = (c ) d mod n = c d (x e ) d mod n = m x mod n m x 1 mod n = m 5

6 Repeated Square-and-Multiply - z 1; for i = k 1 downto 0 { z z 2 mod n; if e i = 1 then z z m mod n; } return ( z ); [ ] e = 10, n = 15 m = 3 c = m e mod n = 9. e = 10 2 ( e 3 e 2 e 1 e 0 ) = ( ). i e i z mod 15 = mod 15 = mod 15 = mod 15 = 9 Primality Testing Sieve of ERATOSTHENES Every positive integer > 1 has a prime divisor. If n is a composite, n has a prime factor not exceeding n. To determine if n is a prime, check n for divisibility by all primes not exceeding n. e.g. if n = 20 is a composite, it must have a prime factor less than n = 4. Since n = 20 has a prime factor 2, it is not a prime. 6

7 Probabilistic Primality Testing Miller_Rabin(n, k) Algorithm 1 find r and s such that n 1 = 2 s r ; for i = 1 to k do { 2 choose a random integer a, 1 a n 2 3 y a r mod n; 4 if y 1 and y n 1 then { 5 j 1; while ( j s 1 and y n 1 ) do { 6 y y 2 mod n; 7 j j+1; } 8 if y n 1 then return( composite ); } } 9 return( prime ); n > 2 r n 1 = 2 s r., gcd(a, n) = 1 a a r mod n = 1 0 j s 1 j a 2 j r mod n = 1. n 2 a n 1 a a r mod n = 1 0 j s 1 j a 2 j r mod n = 1 n (strong pseudoprime), a n (strong liar). Probabilistic Primality Testing Miller_Rabin(n, k) Algorithm Miller_Rabin(n, k) = composite n., n. Miller_Rabin(n, k) = prime 2. n n. a n. n 2 a n 1 1/4 a (composite) n Miller Rabin 1/4., n a Miller Rabin n., k Miller Rabin n 1 (1/4) k. 7

8 Speed of RSA (1995) 1 Mbps with 512-bit modulus Hardware, DES 1000 Software with 8-bit public-key on SPARC II 512-bit 768-bit 1024-bit Encrypt 0.03sec 0.05sec 0.08sec Decrypt 0.16sec 0.48sec 0.93sec Standard and Patent RSA Data Security Inc., (Sep. 20, 2000) in USA French and Australian Banks ISO de facto standard p Z p * g y Z p * y = g x mod p 1 x p 2 x = log g y mod (p 1). Algorithms [1] Compute g 0, g 1, g 2, until y = g x mod n so that x can be obtained [2] Shanks Algorithm [3] Pohlig-Hellman Algorithm [4] Index-Calculus Algorithm 8

9 Shanks Algorithm p, Z p * g, g t = p-1, s = t y = g x mod p 1 x p 2 x = log g y mod (p 1) x = i s + j, where i, j [0, s) y = g x = g is g j =g is+j y(g -s ) i = g j (0, g 0 ) (1, g 1 ) : (j, g j ) : (s 1, g s 1 ) yg 0 yg s 1 : yg s i : yg s (s 1) x = i s + j System (i) p (ii) Z p * g (iii) x [ 1, p 2 ], y = g x mod p. k e { y, g, p }, k d { x }. x [1, p 2] ( Randomized Encryption ) E ke ( m ) = c = { c 1, c 2 } = { g x mod p, y x m mod p } D kd ( c ) = c 2 c 1 x mod p = m 9

10 Diffie-Hellman System (i) p (ii) Z p * g x A Alice ya = g x A mod p y B = g x B mod p x B Bob k = (y B ) x A mod p =g x B x A mod p k = (y A ) x B mod p =g x A x B mod p (real number) (elliptic curve) a b y 2 = x 3 + ax + b (x, y). Java Animation : ecc-java1.htm 10

11 Addition of point P and point Q Addition of P and P By definition, P + (-P) = O. As a result of this equation, P + O = P in the elliptic curve group. O = the additive identity of the elliptic curve group; All elliptic curves have an additive identity. 11

12 Doubling the point P P = (x, y) If y 0, then P. the law for doubling a point on an elliptic curve group : P + P = 2P = R Doubling the point P if y = 0 By definition, 2P = O for such a point P. To find 3P in this situation, one can add 2P + P. Then, P + O = P Thus 3P = P. 3P = P, 4P = O, 5P = P, 6P = O, 7P = P, 12

13 y P Q R x S = P + Q, O P P + O = P. (identity). P P + Q = O Q Q = P R S R + ( S). P P x P (x, y) P (x, y)., P Q P + Q = Q + P., P, Q R P + ( Q + R ) = ( P + Q ) + R. Elliptic Curve ( ) (x 1, y 1 ), (x 2, y 2 ), (x 3, y 3 ) P, Q, S = P + Q. P + Q = S (x 3, y 3 ) x 1, y 1, x 2, y 2. y = αx + β P Q, α = (y 2 y 1 ) / (x 2 x 1 ), β = y 1 αx 1., (αx + β) 2 = x 3 + ax + b P Q (x, αx + β). y 3 x 3 (αx + β) 2 + ax + b (root). (x 1, αx 1 + β) (x 2, αx 2 + β) P Q x 1 x 2 3. x 1 + x 2 + x 3 = α 2 P Q R S = P + Q x x 3 = α 2 x 1 x 2 P + Q (x 3, y 3 ) y2 y1 2 y2 y1 x3 = ( ) x1 x2 y3 = y1 + ( )( x1 x3) x2 x x 1 2 x1 13

14 P + Q P = Q α P y 2 = x 3 + ax + b 2yy = 3x 2 + a P = (x 1, y 1 ) α = (3x 12 + a) / 2y 1. P + Q = S (x 3, y 3 ) x 1, y 1, x 2, y x1 + a 2 x3 = ( ) 2x1 2 y1 2 3x ( 1 + a y3 = y1 + )( x1 x3) 2y1 P y R x S = P + P p GF(p) (elliptic curve) a, b GF(p) y 2 mod p = x 3 + ax + b mod p (x, y) O., x, y GF(p) a = 1 and b = 0, y 2 = x 3 + x. (9,5) because : y 2 mod p = x 3 + x mod p 5 2 mod 23 = mod mod 23 = 738 mod 23 2 = 2 The 23 points which satisfy this equation are: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17) Java Animation : ecc-java2.htm 14

15 GF(p), where p is a prime( ) P (order) t : tp = 0 t GF(p) Q, t P, Q = xp x [0, t 1] P, 2P = P + P, 3P = P + P + P, y 2 mod 23 = x 3 + 9x + 17 mod 23, What is the discrete logarithm x of Q = (4,5) to the base P = (16,5)? Q = xp P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5) Since 9P = (4,5) = Q, the discrete logarithm of Q to the base P is x = 9. 2P = P + P 100P = 2( 2( P + 2( 2( 2( P + 2P ) ) ) ) ) 15

16 What is the discrete logarithm of Q(-0.35,2.39) to the base P(-1.65,-2.79) in the elliptic curve group y 2 = x 3-5x + 4 over real numbers? Java Animation : ecc-java3.htm ElGamal : { g, p, y = g x mod p } { G, p, Y = xg } : { x } { x } : [ c 1, c 2 ] = [ g x mod p, y x m mod p ] [ C 1, C 2 ] = [ xg, xy + M ] : c 2 c x 1 mod p C 2 xc 1 [ ] p = 11, a =1, b = 6 GF(p) y 2 = x 3 + x (2, 4) (2, 7) (3, 5) (3, 6) (5, 2) (5, 9) (7, 2) (7, 9) (8, 3) (8, 8) (10, 2) (10, 9) x = 7, G = (2, 7), Y = 7(2, 7) = (7, 2), x = 3 M = (10, 9) C 1 = 3(2, 7) = (8, 3), C 2 = 3(7, 2) + (10, 9) = (10, 2). 16

17 1 mips 1 40, mips 1 (40,000)( ) t Pollard rho,. 1,000 mips 10,000 t = ,000 year p(bits) t (bits) mips year n (bits) mips year ECC, RSA, DSA Key Size 0.8 (Bits) ECC 3000 RSA &DSA E+12 1E+20 1E+36 Time to Break Key (mips-years) 17

Ⅰ. 들어가는 말 2005년 6월에 발생한 인터넷뱅킹 해킹 사건이 2005년 가장 기억에 남는 정보보호 뉴 스로 선정되었다고 한다. 해킹 등으로 인해 개인의 PC가 악의적인 해커에 의해 장악이 된 경우에는 어떤 보안시스템도 제 기능을 다하지 못함에도 불구하고, 해킹 사

Ⅰ. 들어가는 말 2005년 6월에 발생한 인터넷뱅킹 해킹 사건이 2005년 가장 기억에 남는 정보보호 뉴 스로 선정되었다고 한다. 해킹 등으로 인해 개인의 PC가 악의적인 해커에 의해 장악이 된 경우에는 어떤 보안시스템도 제 기능을 다하지 못함에도 불구하고, 해킹 사 공인인증체계에서 이용되는 보안 알고리즘의 안전성 전자인증센터 과장 이한욱(tubby@kftc.or.kr) I. 들어가는 말 84 II. 보안 알고리즘 종류 85 1. 대칭키 알고리즘 85 2. 알고리즘 87 3. 해쉬 알고리즘 91 III. 공인인증체계에서 보안 알고리즘 활용 93 IV. 보안 알고리즘 공격방법 95 1. 대칭키 알고리즘 공격방법 95 2.