Public key cryptography K* Bob's public B key @学K、 Bob's private B key plaintext encryption ciphertext decryption plaintext message,m algorithm Kg(m) algorithm message m=K。(Kgm） 8:Network Security 8-16
8: Network Security 8-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 Kg(-)and Kp()such that K。(K(m》=m given public key Kg,it should be impossible to compute private key Kg RSA:Rivest,Shamir,Adelson algorithm 8:Network Security 8-17
8: Network Security 8-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,g. (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). 8:Network Security 8-18
8: Network Security 8-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=me mod n (ie.remainder when me is divided by n) 2.To decrypt received bit pattern,c,compute m=cdmod n (i.e.,remainder when cd is divided by n) Magic happens! m=(memod n)dmod n C 8:Network Security 8-19
8: Network Security 8-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,g=7.Then n=35,z=24. e=5 (so e,z relatively prime). d=29(so ed-1 exactly divisible by z. letter m me c=memod n encrypt: 12 1524832 17 decrypt: g m=comod n letter 17 481968572106750915091411825223071697 12 8:Network Security 8-20
8: Network Security 8-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: