RSA:Creating public/private key pair 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). KB Security:8-21
RSA: Creating public/private key pair Security: 8- 21 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). KB + KB -
RSA:encryption,decryption 0.given(n,e)and (n,d)as computed above 1.to encrypt message m(<n),compute c=memod n 2.to decrypt received bit pattern,c,compute m=cdmod n magic happens!m =(memod n)mod n Security:8-22
RSA: encryption, decryption Security: 8- 22 0. given (n,e) and (n,d) as computed above 1. to encrypt message m (<n), compute c = m mod n e 2. to decrypt received bit pattern, c, compute m = c dmod n m = (m mod n) e mod n magic happens! d c
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). encrypting 8-bit messages. bit pattern m m c=memod n, encrypt: 00001000 12 24832 17 decrypt: m=cdmod n, 17 481968572106750915091411825223071697 12 Security:8-23
RSA example: Security: 8- 23 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). bit pattern m m e c = m mod n e 0000l000 12 24832 17 encrypt: encrypting 8-bit messages. c m = c mod n d 17 481968572106750915091411825223071697 12 c d decrypt:
Why does RSA work? must show that cd mod n=m,where c=me mod n fact:for any x and y xy mod n=xly modz)mod n where n=pq and z=(p-1)(q-1) ■thus, cd mod n=(me mod n)d mod n med mod n =m(ed mod z)mod n- =m1 mod n m Security:8-24
Why does RSA work? Security: 8- 24 ▪ must show that cd mod n = m, where c = me mod n ▪ fact: for any x and y: xy mod n = x(y mod z) mod n • where n= pq and z = (p-1)(q-1) ▪ thus, c d mod n = (me mod n)d mod n = med mod n = m(ed mod z) mod n = m1 mod n = m
RSA:another important property The following property will be very useful later: KBK。m)=m=K含Kgm) use public key use private key first,followed first,followed by private key by public key result is the same! Security:8-25
RSA: another important property Security: 8- 25 The following property will be very useful later: K (K (m)) = m B B - + K (K (m)) B B + - = use public key first, followed by private key use private key first, followed by public key result is the same!