Question

a) In a public-key system using RSA, n=77 and its public key is e=23. What is the private key d? Show your steps of calculation.

b) Let M=3. Compute its cipher text under the above RSA. Please use the divide conquer algorithm to compute the exponential function for the cipher text.

Answer 1

Solution:

(a)

Given,

=>RSA algorithm

=>n = 77, e = 23

Explanation:

Calculating values of p and q:

=>We know that n = p*q

=>77 = p*q

=>p = 11 and q = 7

Calculating value of phi(n) (Euler totient function):

=>phi(n) = (p-1)*(q-1)

=>phi(n) = (11-1)*(7-1)

=>phi(n) = 10*6

=>phi(n) = 60

Calculating value of d:

=>We know that edmodphi(n) = 1

=>23*d mod 60 = 1

=>d = 47 as 23*47 mod 60 = 1

=>Hence private key(d)= 47

(b)

Given,

=>M = 3

Explanation:

Calculating value of ciphertext(C):

=>C = M^e mod n

=>C = 3^23 mod 77

(3^5 mod 77 = 12, 3^3 mod 77 = 27)

=>C = (3^5 mod 77)*(3^5 mod 77)*(3^5 mod 77)*(3^5 mod 77)*(3^3 mod 77)

=>C = 12*12*12*12*27 mod 77

(12^4 mod 77 = 23)

=>C = (12^4 mod 77)*(27 mod 77)

=>C = 23*27 mod 77

=>C = 5

=>Hence ciphertex(C) = 5

I have explained each and every part with the help of statements attached to the answer above.