Inside PK Cryptography:Math and Implementation

Inside PK Cryptography:Math and Implementation : Inside PK Cryptography: Math and Implementation Sriram Srinivasan (“Ram”) sriram@malhar.net

Agenda : 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

Security Issues : 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.

Public Key Cryptography : Public Key Cryptography Consider a pair of magic pens. Write with one, use the other to decode. Symmetric: either can be used to encode You want to send a message to me 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.

Mathematics : Mathematics

Fundamental Theorem of Arithmetic : 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

Fundamental Theorem proof : 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

Fundamental Theorem proof : 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

GCD (Greatest Common Divisor) : 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

Euclid’s algorithm : r r1 r r = a % b Euclid’s algorithm a b b r % r1 = 0. \ gcd (a,b) = r1 r1 = b % r 1 2 3

Euclid’s algorithm proof : Proof that r1 divides a and b Euclid’s algorithm proof r1 | r b = r1 + r r1 | b a = qb + r r1 | b r1 | r r1 | a

Euclid’s algorithm proof (contd) : 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

Linear Combination : 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.

GCD & Linear combination (contd.) : 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

GCD & Linear combination (contd.) : GCD & Linear combination (contd.) Let c | a, c | b, c > 0 a = cm, b = cn d = ax1 + by1 = c(mx1 + ny1) Þ c | d Þ d is the gcd Second part of proof Any other divisor is smaller than d

Summary 1 : 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

Modular/Clock Arithmetic : 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

Modular Arithmetic : Modular Arithmetic a º b (mod n), c º d (mod n) Addition a + c º b + d (mod n) Multiplication ac º bd (mod n) a - b = jn c - d = kn a + c - (b + d) = (j + k) n

Modular Arithmetic (contd.) : Modular Arithmetic (contd.) Power a º b (mod n) Þ ak º bk (mod n) Going n times around the clock a + kn º b (mod n) Using induction, If ak º bk (mod n), a . ak º b . bk (mod n), by multiplication rule \ ak+1 º bk+1 (mod n)

Chinese Remainder Theorem : 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

GCD and modulus : 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

Multiplicative Inverse : 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)

Summary 2 : Summary 2 Modular arithmetic Addition, multiplication, power, inverse Chinese Remainder Theorem 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)

Euler’s Totient function : 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

Totient lemma #2: product : 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)

Totient lemma #3: power : 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

Totient lemma #4: product : 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+1 (n-1)m+2 (n-1)m+3 (n-1)m+r nm

Totient lemma #4 (contd.) : Totient lemma #4 (contd.) 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 Step 1: Eliminate columns

Totient lemma #4 (contd.) : 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

Totient lemma #5 : 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)

Totient lemma #5 (contd.) : 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

Euler’s Theorem : 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)

Fermat’s little theorem : Fermat’s little theorem Special case of Euler’s theorem. If gcd(a,p) = 1 and p is prime, ap-1 º 1 (mod p) We now have all the essential number theory. Whew! Because f(p) = p - 1

RSA Algorithm : 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” encrypted ciphertext, c = me (mod n) Bob decrypts using his own private key To decrypt, compute cd (mod n). Result is m

RSA Key Generation : 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

RSA Key Generation : 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 pair: e, n Keeps private key: d, n p = 3, q = 11 Þ n = 33 f(n) = (3 - 1)(11 - 1) = 20 e = 7 7d = 1 (mod 20) Þ d = (1 + 20k)/7 Þ d = 3 Public key = (7, 33) Private key = (3, 33)

RSA algorithm : RSA algorithm Treat each letter or block as m (m < n) n = 33, e = 7, d = 3 Encryption: for each m compute c=me (mod n) Decryption: for each c, compute cd (mod n) “RSA” Þ {18, 19, 1} 63 % 33 Þ {18 133 % 33 Þ {18, 19 13 % 33 Þ {18, 19, 1} 187 % 33 Þ {6 197 % 33 Þ {6, 13 17 % 33 Þ {6, 13, 1}

RSA proof : 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)

RSA proof (contd.) : 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)

RSA proof (contd.) : 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

RSA Implementation : Creating a big random prime n = pq f(n) = (p - 1) (q - 1) RSA Implementation SecureRandom r = new SecureRandom(); BigInteger p = new BigInteger(nbits, 100, r); n = p.multiply(q); phi = p.subtract(BigInteger.ONE) .multiply(q.subtract(BigInteger.ONE));

RSA Implementation : Select e coprime to f(n) Select d, such that ed º 1 (mod f(n)) RSA Implementation e = new BigInteger("3"); while(phi.gcd(e).intValue() > 1) e = e.add(new BigInteger("2")); d = e.modInverse(phi);

RSA Implementation : Encrypt/decrypt RSA Implementation BigInteger encrypt (BigInteger message) { return message.modPow(e, n); } BigInteger decrypt (BigInteger message) { return message.modPow(d, n); }

Digital Signature : 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

RSA Deployment : 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

Examples of RSA Attacks : Examples of RSA Attacks Exploiting algorithm parameter values Low e or d values Exploiting implementation Measuring time and power consumption of smart cards Exploiting random errors in hardware Exploiting error messages Social Engineering: Blinding attack

Ellis / Diffie-Hellman Key Exchange : 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

Ellis / Diffie-Hellman Key Exchange (contd) : 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.

References : 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