public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1

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

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

RSA ( Rivest-Shamir-Adleman ) Example p = 47 and q = 71, n = p q = 3337 (p 1) (q 1) = 46 70 = 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 = 6882326879666683 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 = 688 79 mod 3337 = 1570 c = 1570 2756 2091 2276 2423 158 To decrypt, m 1 = c d 1 mod n = 1570 1019 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 ) 106 10, Quadratic Sieve (1994 ) RSA-129, 129 10, 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, 130 10, Number Field Sieve, 500 mips-year 4

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

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 ) = ( 1 0 1 0 ). i e i z 3 1 1 2 3 mod 15 = 3 2 0 3 2 mod 15 = 9 1 1 9 2 3 mod 15 = 3 0 0 3 2 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

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

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

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

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

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

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

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

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 2. 2 3x1 + 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 = 9 3 + 9 mod 23 25 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

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

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 + 6. (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

1 mips 1 40,000. 1 mips 1 (40,000)(60 60 24 365) 2 40. t Pollard rho,. 1,000 mips 10,000 t = 2 160 96,000 year p(bits) t (bits) mips year n (bits) mips year 163 160 2 80 9.6 10 11 191 186 2 93 7.9 10 15 239 234 2 117 1.6 10 23 359 354 2 177 1.5 10 41 431 426 2 213 1.0 10 52 512 3 10 4 768 2 10 8 1024 3 10 11 1280 1 10 14 1536 3 10 16 2048 3 10 20 ECC, RSA, DSA 1.2 1 Key Size 0.8 (Bits) 0.6 0.4 0.2 0 6000 5000 4000 ECC 3000 RSA &DSA 2000 1000 0 10000 100000000 1E+12 1E+20 1E+36 Time to Break Key (mips-years) 17