Public key encryption algorithms Requirements: ( need K,(and K:(such that K。(K(m)=m 2)given public key B it should be impossible to compute private key RSA: Rivest, shamir Adelson algorithm 361.F2003
Comp 361, Fall 2003 7: Network Security 16 Public key encryption algorithms need K ( ) and K ( ) such that B B . . given public key K , it should be impossible to compute private key K B B Requirements: 1 2 RSA: Rivest, Shamir, Adelson algorithm + - K (K (m)) = m B B - + + -
RSA: Choosing keys 1. Choose two large prime numbers P, q (e.g., 1024 bits each) 2. Compute n= pq, z=(p-1)(q-1) 3. Choose e( with en)that has no common factors with z(e, z are relatively prime") 4. Choose d such that ed-1 is exactly divisible by z (in other words: ed mod =1) 5. Public key is(n,e). Private key is (n, d) B 361.F2003
Comp 361, Fall 2003 7: Network Security 17 RSA: Choosing keys 1. Choose two large prime numbers p, q. (e.g., 1024 bits each) 2. Compute n = pq, z = (p-1)(q-1) 3. Choose e (with e<n) that has no common factors with z. (e, z are “relatively prime”). 4. Choose d such that ed-1 is exactly divisible by z. (in other words: ed mod z = 1 ). 5. Public key is (n,e). Private key is (n,d). K B + K B -
RSA: Encryption, decryption 0. Given(n,e)and(n, d)as computed above 1. To encrypt bit pattern, m, compute c=m mod n( i.e., remainder when m is divided by n 2. To decrypt received bit pattern, c, compute m=cd mod n(i.e, remainder when ca is divided by n) Magic happens/ m =(m mod n)mod n 361.F2003
Comp 361, Fall 2003 7: Network Security 18 RSA: Encryption, decryption 0. Given (n,e) and (n,d) as computed above 1. To encrypt bit pattern, m, compute c = m mod n e (i.e., remainder when m is divided by n) e 2. To decrypt received bit pattern, c, compute m = c mod n d (i.e., remainder when c is divided by n) d m = (m mod n) e mod n Magic d happens! c
RSA example Bob chooses p=5, =7. Then n=35, z=24 e=5(so e, z relatively prime) d=29 (so ed-1 exactly divisible by z enc rypt: le letter 已 m C= m mod n 121524832 17 decrypt c d m=cmod n letter 174819685721067509150914118201697 12 361.F2003
Comp 361, Fall 2003 7: Network Security 19 RSA example: Bob chooses p=5, q=7. Then n=35, z=24. e=5 (so e, z relatively prime). d=29 (so ed-1 exactly divisible by z. letter m m e c = m mod n e l 12 1524832 17 c m = c mod n d 17 481968572106750915091411825223071697 12 c d letter l encrypt: decrypt:
RSA: Why is that m =(me mod n)dmod n Useful number theory result: If p,q prime and n= pq, then y mod(p-1)-1) xX moa n三X mod n (m mod nmod n =m mod n ed mod (p-1)(-1) mod n (using number theory result above) m mod n (since we chose ed to be divisible by (p-1)(q-1) with remainder 1) m 361.F2003
Comp 361, Fall 2003 7: Network Security 20 RSA: Why is that m = (m mod n) e mod n d (m mod n) e mod n = m mod n d ed Useful number theory result: If p,q prime and n = pq, then: x mod n = x mod n y y mod (p-1)(q-1) = m mod n ed mod (p-1)(q-1) = m mod n 1 = m (using number theory result above) (since we chose ed to be divisible by (p-1)(q-1) with remainder 1 )