Public key cryptography Bob's public k ≥K- Bob's private b ke plaintext encryption ciphertext decryption_plaintext message, algorithm kr(m) algorithm message m=K(Kr(m)) B Network Security 7-16
Network Security 7-16 Public key cryptography plaintext message, m encryption ciphertext algorithm decryption algorithm Bob’s public key plaintext message K (m) B + K B + Bob’s private key K B - m = K (K (m)) B + B -
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 Network Security 7-17
Network Security 7-17 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 Network Security 7-18
Network Security 7-18 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 =cu mod n i.e., remainder when cu is divided by y Magic happens/ m =(m mod n)mod n C Network Security 7-19
Network Security 7-19 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 Network Security 7-20
Network Security 7-20 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: