Public Key cryptography symmetric key crypto public key cryptography o requires sender, 口 radica| y different receiver know approach [Diffie shared secret key HelIman76, RSA781 O Q: how to agree on g sender receiver do key in first place not share secret key (particularly if D encryption key public never " met (known to all) O decryption key private(known only to receiver 7: Network Security
7: Network Security 11 Public Key Cryptography symmetric key crypto requires sender, receiver know shared secret key Q: how to agree on key in first place (particularly if never “met”)? public key cryptography radically different approach [DiffieHellman76, RSA78] sender, receiver do not share secret key encryption key public (known to all) decryption key private (known only to receiver)
Public key cryptography Public e in Ke Private decryption Plaintext Plaintext message, m message, m Encryption Decryption m=dlegmlk aigorithm algorithm Ciphertext 7: Network Security 12
7: Network Security 12 Public key cryptography Figure 7.7 goes here
Public key encryption algorithms Two inter-related requirements: B(>and need do B)such that de (m))=m 2) need public and private keys for banded( RSA: Rivest, shamir Adelson algorithm 7: Network Security 13
7: Network Security 13 Public key encryption algorithms need d ( ) and e ( ) such that d (e (m)) = m B B B B . . need public and private keys for d ( ) and e ( ) . . B B Two inter-related requirements: 1 2 RSA: Rivest, Shamir, Adelson algorithm
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) 7: Network Security 14
7: Network Security 14 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)
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=co mod n (i.e., remainder when co is divided by y Magic happens/ m=(m mod n)mod n 7: Network Security 15
7: Network Security 15 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!