a. use the Euclidean algorithm to calculate d (Step 4, of Bob\'s RSA key choise
ID: 3621890 • Letter: A
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 27Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.