a. use the Euclidean algorithm to calculate d (Step 4, of Bob\'s RSA key choise

Question

 

a. use the Euclidean algorithm to calculate d (Step 4, of Bob's RSA key choise algorithm from below)

 

b. encode the text T = 8 using the public key (n,e)

 

c. decode your answer to your encoding result to retrieve your message 8. See alice-send-message-to-bob(x) in steps 7 and 8 on the below

 

-----------------------------------------------------------------------------------------------------

 

Bobs RSA Key Choice Algorithm

 

(1) Choose 2 large prime number p and q

 

(2) n = p * q

 

(3) choose e != 1 so that e is relatively prime to (p-1)(q-1)

 

(4) compute d = e^-1 mod (p-1)(q-1)

 

(5) publish e and n

 

(6) keep d secret

 

 

 

Alice-send-message to box (x)

 

(1) alice does the following

 

(2) read the public directory for bob's keys e and n

 

(3) compute y = x^e mod n

 

(4) send y to bob

 

(5) bob recieves the foloowing:

 

(6) recieve y from alice

 

(7) computer z=y^d mod n, using secret key d

 

(8) read z

Explanation / Answer

Dear, 1.a. use the Euclidean algorithm to calculate d (Step 4, of Bob's RSA key choise algorithm from below) Step 1: Choose two random large prime numbers p and q, For maximum security, choose p and q of about equal length, Step 2: Compute the product n = p•q Step 3: Choose a random integer e < (p-1)(q-1) The numbers e and (p-1)(q-1) must be relatively prime, i.e. they should not share common prime factors. Step 4: Compute the unique inverse d = e-1 mod (p-1)(q-1) The equation d•e mod (p-1)(q-1) = 1 can be solved using the Euclidian algorithm. p = 5, q = 8: n = p•q = 40 the public exponent e must be relatively prime to (p-1)•(q-1), i.e. it cannot contain any factors of 4 and 7 = 2.2.7 all possible choices for the exponents e and d e d ed edmod28 5 17 85 1 9 25 225 1 11 23 253 1 13 15 195 1 15 13 195 1 17 5 85 1 19 23 11 253 1 25 9 225 1 27

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---