A In a publickey system using RSA you intercept the cipherte

A. In a public-key system using RSA, you intercept the ciphertext C = 57 sent to a user whose public key is e = 17, n = 77. What is the plaintext M? Show your calculations.

Solution

We know that the ciphertext C = 57, and the public key PU = {e, n} = {17, 77}.

Based on Euler’s Totient function, f(n) is defined as the number of positive integers less than n and relatively prime to n

Now, we guess two prime numbers p and q. Let p be 7 and q be 11. All the following conditions will be satisfied based on the guess:

We calculate d in the next step. Based on RSA key generation algorithm,

d e^-1 mod f(n) which is equivalent to ed 1 mod f(n)

We have e = 17, f(n) = 60. So, 17d mod 60 =1, so d = 53 [calculated using calculator ]

Now, we find the private key PR = {d, n} = {53, 77}.

Based on RSA decryption algorithm,

M = C^d mod n

    = 57⁵³ mod 77

    = 8

We also can verify the correctness by the RSA encryption algorithm as the following:

            C = M^e mod n = 8¹⁷ mod 77 = 57

Therefore, we conclude that the plaintext M is 8.


Thanks, let me know if there is any concern.