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). Network Security 8-21
Network 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)
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). Network Security 8-22
Network 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 -
RSA:encryption,decryption 0.given (n,e)and (n,d)as computed above 1.to encrypt message m(<n),compute c=mod n 2.to decrypt received bit pattern,c,compute m=e mod n magic m (me mod n)dmod n happens! C Network Security 8-23
Network 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
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 me c=memod n encrypt: 00001000 12 24832 17 decrypt: m=cdmod n 17 481968572106750915091411825223071697 12 Network Security 8-24
Network 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:
Why does RSA work? must show that cd mod n m where c me mod n fact:for any x and y:xYmod n x(y mod z)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 Network Security 8-25
Network 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, cd mod n = (me mod n)d mod n = med mod n = m(ed mod z) mod n = m1 mod n = m