RSA:getting ready message:just a bit pattern bit pattern can be uniquely represented by an integer number thus,encrypting a message is equivalent to encrypting a number example: m=10010001.This message is uniquely represented by the decimal number 145. to encrypt m,we encrypt the corresponding number, which gives a new number(the ciphertext). Security 8-21
RSA: getting ready ▪ message: just a bit pattern ▪ bit pattern can be uniquely represented by an integer number ▪ thus, encrypting a message is equivalent to encrypting a number example: ▪ m= 10010001 . This message is uniquely represented by the decimal number 145. ▪ to encrypt m, we encrypt the corresponding number, which gives a new number (the ciphertext). Security 8-21
RSA:Creating public/private key pair I.choose two large prime numbers p,q. (e.g.,1024 bits each) 2.compute n pq,z =(p-1)(q-l) 3.choose e (with e<n)that has no common factors with z (e,z are "relatively prime"). 4.choose d such that ed-I is exactly divisible by z. (in other words:ed mod z =) 5.public key is (n,e).private key is (nd). Ke Security 8-22
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). K B + K B - Security 8-22
RSA:encryption,decryption 0.given(n,e)and(n,d)as computed above l.to encrypt message m(<n),compute c=me mod n 2.to decrypt received bit pattern,c,compute m =cdmod n magic m =(me mod n)dmod n happens! c Security 8-23
RSA: encryption, decryption 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 mod n d m = (m mod n) e mod n magic d happens! c Security 8-23
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 encrypt: m m c=memod n 0000I000 12 24832 17 decrypt: m=cdmod n 17 481968572106750915091411825223071697 →12 Security 8-24
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). 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: Security 8-24
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 x(ymod 2)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 ml mod n =m Security 8-25
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 = 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 Security 8-25