Report

Inside PK Cryptography: Math and Implementation Sriram Srinivasan (“Ram”) [email protected] Agenda Introduction to PK Cryptography Essential Number Theory Fundamental Number Theorem GCD, Euclid’s algorithm Linear combinations Modular Arithmetic Euler’s Totient Function Java implementation of RSA Sriram Srinivasan 2/47 Security Issues Authentication, Authorization, and Encryption, Non-repudiation Shared Secrets (e.g passwords, Enigma) Something shared, something (else) secret Concept by Ellis, Cocks and Williams Popularly attributed to Diffie and Hellman Algorithm by Rivest, Shamir and Adelman Used everywhere: https, SSL, email, certificates. Sriram Srinivasan 3/47 Public Key Cryptography Consider a pair of magic pens. You want to send a message to me Write with one, use the other to decode. Symmetric: either can be used to encode You borrow one of my pens and write with it. I decode it with my other pen. Avoids problems of shared secrets Same tools for authentication, encryption and non-repudiation. Sriram Srinivasan 4/47 Mathematics Fundamental Theorem of Arithmetic All numbers are expressible as a unique product of primes 10 = 2 * 5, 60 = 2 * 2 * 3 * 5 Proof in two parts 1. All numbers are expressible as products of primes 2. There is only one such product sequence per number Sriram Srinivasan 6/47 Fundamental Theorem proof First part of proof All numbers are products of primes Let S = {x | x is not expressible as a product of primes} Let c = min{S}. c cannot be prime Let c = c1 . c2 c1, c2 < c c1, c2 S (because c is min{S}) \ c1, c2 are products of primes c is too \ S is an empty set Sriram Srinivasan 7/47 Fundamental Theorem proof Second part of proof The product of primes is unique Let n = p1p2p3p4… = q1q2q3q4… Cancel common primes. Now unique primes on both sides Now, p1 | p1p2p3p4 p1 | q1q2q3q4… p1 | one of q1, q2, q3, q4… p1 = qi which is a contradiction Sriram Srinivasan 8/47 GCD (Greatest Common Divisor) gcd(a,b) = the greatest of the divisors of a,b Many ways to compute gcd Extract common prime factors Express a, b as products of primes Extract common prime factors gcd(18, 66) = gcd(2*3*3, 2*3*11) = 2*3 = 6 Factoring is hard. Not practical Euclid’s algorithm Sriram Srinivasan 9/47 Euclid’s algorithm a 1 b r=a%b b 2 3 r r r1 r1 = b % r r % r1 = 0. \ gcd (a,b) = r1 Sriram Srinivasan 10/47 Euclid’s algorithm proof Proof that r1 divides a and b r1 | r b = r1 + r a = qb + r r1 | b r1 | r r1 | b r1 | a Sriram Srinivasan 11/47 Euclid’s algorithm proof (contd) Proof that r1 is the greatest divisor Say, c | a and c | b c | qb + r c|r c | q’b + r1 c | r1 Sriram Srinivasan 12/47 Linear Combination ax + by = “linear combination” of a and b 12x + 20y = {…, -12,-8,-4,0,4,8,12, … } The minimum positive linear combination of a & b = gcd(a,b) Proof in two steps: 1. If d = min(ax+by) and d > 0, then d | a, d | b 2. d is the greatest divisor. Sriram Srinivasan 13/47 GCD & Linear combination (contd.) Let S = {z = ax + by | z > 0 } Let d = min{S} = ax1 + by1 Let a = qd + r. 0 <= r < d r = a - qd = a - q(ax1 + by1) r = a(1 - qx1) + (-qy1)b If r > 0, r S But r < d, which is a contradiction, because d = min{S} \r=0 d | a Sriram Srinivasan 14/47 GCD & Linear combination (contd.) Second part of proof Any other divisor is smaller than d Let c | a, c | b, c > 0 a = cm, b = cn d = ax1 + by1 = c(mx1 + ny1) c | d d is the gcd Sriram Srinivasan 15/47 Summary 1 All numbers are expressible as unique products of prime numbers GCD calculated using Euclid’s algorithm gcd(a,b) = 1 a & b are mutually prime gcd(a,b) equals the minimum positive ax+by linear combination Sriram Srinivasan 16/47 Modular/Clock Arithmetic 1:00 and 13:00 hours are the same 1:00 and 25:00 hours are the same 1 13 (mod 12) a b (mod n) n is the modulus a is “congruent” to b, modulo n a - b is divisible by n a%n=b%n Sriram Srinivasan 17/47 Modular Arithmetic a b (mod n), c d (mod n) Addition a - b = jn c - d = kn a + c - (b + d) = (j + k) n a + c b + d (mod n) Multiplication ac bd (mod n) Sriram Srinivasan 18/47 Modular Arithmetic (contd.) Power a b (mod n) ak bk (mod n) Using induction, If ak bk (mod n), a . ak b . bk (mod n), by multiplication rule \ ak+1 bk+1 (mod n) Going n times around the clock a + kn b (mod n) Sriram Srinivasan 19/47 Chinese Remainder Theorem m a (mod p), m a (mod q) m a (mod pq) (p,q are primes) m-a = cp. Now, m-a is expressible as p1. p2 .p3 . . . If m - a is divisible by both p and q, p and q must be one of p1 , p2 , p3 m - a is divisible by pq Sriram Srinivasan 20/47 GCD and modulus If gcd(a,n) = 1, and a = b (mod n), then gcd(b,n) = 1 a b (mod n) a = b + kn gcd(a,n) = 1 ax1 + ny1 = 1, for some x1 and y1 (b + kn)x1 + ny1 = 1 bx1 + n(kx1 + y1) = bx1 + ny2 = 1 gcd(b,n) = 1 Sriram Srinivasan 21/47 Multiplicative Inverse If a, b have no common factors, there exists ai such that a.ai 1 (mod b) ai is called the “multiplicative inverse” gcd(a,b) = 1 = ax1+ by1, for some x1 and y1 ax1 = 1 – by1 ax1 = 1 + by2 (making y2 = -y1) ax1 - 1 = by2 ax1 1 (mod b) (x1 is the multiplicative inverse) Sriram Srinivasan 22/47 Summary 2 Modular arithmetic Chinese Remainder Theorem Addition, multiplication, power, inverse If m a (mod p) and m a (mod q), then m a (mod pq) Relationship between gcd and modular arithmetic gcd(a,b) = 1 aai 1 (mod b) Sriram Srinivasan 23/47 Euler’s Totient function f(n) = Totient(n) = Count of integers n coprime to n f(10) = 4 (1, 3, 7, 9 are coprime to 10) f(7) = 6 (1, 2, 3, 4, 5, 6 coprime to 10) f(p) = p - 1, if p is a prime Sriram Srinivasan 24/47 Totient lemma #2: product f(pq) = (p - 1)(q - 1) = f(p) . f(q) if p and q are prime Which numbers pq share factors with pq? 1.p, 2.p, 3.p, … (q-1)p and 1.q, 2.q, 3.q, … (p-1)q and pq The rest are coprime to pq. Count them. f(pq) = pq - (p - 1) - (q - 1) - 1 = (p - 1)(q - 1) Sriram Srinivasan 25/47 Totient lemma #3: power f(pk) = pk - pk-1 , if p is prime and k > 0 Only numbers that are a multiple of p have a common factor with pk : 1.p, 2.p, 3.p, … pk-1 . p and The rest don’t share any factors, so are coprime \ f(pk) = pk - pk-1 Sriram Srinivasan 26/47 Totient lemma #4: product f(mn) = f(m) . f(n) if m and n are coprime ( gcd(m,n) = 1) Organize into a matrix of m columns, n rows 1 2 3 … r … m m+1 m+2 m+3 m+r … 2m 2m+1 2m+2 2m+3 2m+r … 3m (n-1)m+3 (n-1)m+r nm … (n-1)m+1 (n-1)m+2 Sriram Srinivasan 27/47 Totient lemma #4 (contd.) Step 1: Eliminate columns If gcd(m,r) = 1, gcd(m,km+r) = 1 All cells under that rth column have no common factors with m Others have a common factor with mn, so can be eliminated f(m) columns survive Sriram Srinivasan 28/47 Totient lemma #4 (contd.) Step 2: Examine cells in remaining columns No two cells in a column are congruent mod n Because if im + r jm + r (mod n), im + r - jm - r = kn n |(i - j), which is not possible because i - j < n Because there are n (non-congruent) cells in each column, label them as 0, 1, 2, … n-1 in some order. f(n) cells in each column coprime to n f(n) f(m) cells left that are coprime to both m and n Sriram Srinivasan 29/47 Totient lemma #5 If gcd(c,n) = 1 and x1,x2,x3 … xf(n) are coprime to n, then cx1,cx2,… cxf(n) are congruent to x1,x2,x3… in some order. 1, 3, 5, 7 are coprime to 8. Multiply each with c=15, (also coprime to 8) {15, 45, 75, 105} {7, 5, 3, 1} (mod 8) Sriram Srinivasan 30/47 Totient lemma #5 (contd.) cxi is not cxj (mod n). Because if cxi cxj (mod n) c(xi - xj) = kn . But gcd(c,n) = 1 n | (xi - xj), which is impossible because xi - xj < n Remember the old identity: gcd(a,n) =1 and a b (mod n) gcd(b,n) = 1 Let cxi b (mod n) gcd(cxi, n) = 1 gcd(b,n) = 1 \ b must be one of xj Sriram Srinivasan 31/47 Euler’s Theorem If gcd(a,n) = 1, af(n) 1 (mod n) Consider x1, x2, … xf(n) < n and coprime to n Since a is also coprime to n, from previous result ax1 xi (mod n), ax2 xj (mod n), … etc. af(n) x1x2x3…xf(n) x1x2x3…xf(n) (mod n) af(n) x x (mod n) where x = x1x2x3…xf(n) n | x(af(n) - 1) But n doesn’t divide x n | (af(n) - 1) af(n) 1 (mod n) Sriram Srinivasan 32/47 Fermat’s little theorem Special case of Euler’s theorem. If gcd(a,p) = 1 and p is prime, ap-1 1 (mod p) Because f(p) = p - 1 We now have all the essential number theory. Whew! Sriram Srinivasan 33/47 RSA Algorithm Bob generates public and private keys public key : encrypting key e and modulus n private key: decrypting key d and modulus n Alice wants to send Bob a message m m treated as a number Alice encrypts m using Bob’s “public pen” e encrypted ciphertext, c = m (mod n) Bob decrypts using his own private key To decrypt, compute cd (mod n). Result is m Sriram Srinivasan 34/47 RSA Key Generation Bob selects primes p, q computes n = pq f(n) = f(p) f(q) = (p - 1) (q - 1) Select e, such that gcd(e, f(n)) = 1 Compute the decrypting key, d, where ed 1 (mod f(n)) Bob publishes public key info: e, n Keeps private key: d, n Important: m < n Sriram Srinivasan 35/47 RSA Key Generation Bob selects n = pq p = 3, q = 11 primes p, nq =computes 33 f(n) = f(p) f(q) =- (p (3 - 1)(11 1) -= 1) 20(q - 1) Select e = 7 e, such that gcd(e, f(n)) = 1 Compute the20) decrypting d, where 7d = 1 (mod d = (1 key, + 20k)/7 edd=13(mod f(n)) Bob publishes Public key = (7,public 33) key pair: e, n Privateprivate key = (3, 33) Keeps key: d, n Sriram Srinivasan 36/47 RSA algorithm Treat eachletter block “RSA” {18,or19, 1} as m (m < n) n = 33, e = 7, d = 3 77 Encryption: each 18 119 %%33 33 for {6, {6 13m1} 13, compute c=me (mod n) 6333% 113 %%33 33 33 for {18, {18 19 Decryption: each19, c, 1} compute cd (mod n) Sriram Srinivasan 37/47 RSA proof Prove c = me (mod n) cd(mod n) = m Review: a b (mod n) ak bk (mod n) a<n a = a (mod n) gcd(a,n) = 1 af(n) 1 (mod n) a (mod p) a (mod q) m = a (mod pq) f(pq) = f(p)f(q) ed 1 (mod f(n) ) ed = 1 + k f(n) Sriram Srinivasan 38/47 RSA proof (contd.) c = me (mod n) c me (mod n) cd med (mod n) Consider, med (mod p) and med (mod q) If p | m, med (mod p) = 0 = m (mod p) If not, med (mod p) m1+kf(n) (mod p) m. mkf(p) f(q) (mod p) m. (mf(p)) kf(q) (mod p) m. (1) kf(q) (mod p) (by euler) m (mod p) Sriram Srinivasan 39/47 RSA proof (contd.) So, in both cases, med m (mod p) Similarly, med m (mod q) \ med m (mod pq) (chinese remainder theorem) m (mod n) \ med (mod n) = m Sriram Srinivasan 40/47 RSA Implementation Creating a big random prime SecureRandom r = new SecureRandom(); BigInteger p = new BigInteger(nbits, 100, r); n = pq n = p.multiply(q); f(n) = (p - 1) (q - 1) phi = p.subtract(BigInteger.ONE) .multiply(q.subtract(BigInteger.ONE)); Sriram Srinivasan 41/47 RSA Implementation Select e coprime to f(n) e = new BigInteger("3"); while(phi.gcd(e).intValue() > 1) e = e.add(new BigInteger("2")); Select d, such that ed 1 (mod f(n)) d = e.modInverse(phi); Sriram Srinivasan 42/47 RSA Implementation Encrypt/decrypt BigInteger encrypt (BigInteger message) { return message.modPow(e, n); } BigInteger decrypt (BigInteger message) { return message.modPow(d, n); } Sriram Srinivasan 43/47 Digital Signature med (mod n) = mde (mod n) Bob encrypts his name using private key Alice, the recipient, decrypts it using Bob’s public key Sriram Srinivasan 44/47 RSA Deployment If msg m > n, m chop it up in blocks < n p and q are usually 512 bits, e = 65537. Ensure p - 1 doesn’t have small prime factors. Ensure d is large Pad m with random bits Never reuse n Sign documents very carefully Sriram Srinivasan 45/47 Examples of RSA Attacks Exploiting algorithm parameter values Exploiting implementation Low e or d values Measuring time and power consumption of smart cards Exploiting random errors in hardware Exploiting error messages Social Engineering: Blinding attack Sriram Srinivasan 46/47 Ellis / Diffie-Hellman Key Exchange RSA is slow in practice Encrypt AES’s keys using RSA Alice and Bob agree publicly on a prime p, and some integer, c < p. gcd(p,c) = 1 Alice chooses a privately, and Bob chooses b. a, b < p Sriram Srinivasan 47/47 Ellis / Diffie-Hellman Key Exchange (contd) Alice computes A=ca (mod p). Bob computes B=cb (mod p) They exchange these numbers. Alice computes Ba. Bob computes Ab Both of them compute cab (mod p) Both use this number as a key for AES. Sriram Srinivasan 48/47 References “Cryptological Mathematics”, Robert Lewand “Twenty Years of Attacks on the RSA Cryptosystem”, Dan Boneh http://crypto.stanford.edu/~dabo pajhome.org.uk/crypt/index.html “Concrete Mathematics”, Donald Knuth et al. "The Code Book", Simon Singh Sriram Srinivasan 49/47