Question

please help me to solve (c and d) knowing that d=209

Let the two primes p = 41 and q = 17 be given as set-up parameters for RSA. a. Which of the parameters e_1 = 32, e_2 = 49 is a valid RSA exponent? Justify your choice b. Compute the corresponding private key Kpr = (p, q, d). Use the extended Euclidean algorithm for the inversion and point out every calculation step. c. Using the encryption key, encrypt the message M = 26. d. Using the private key and the Chinese remainder theory (CRT) decrypt the cipher C = 513. Show all your calculation steps.

Answer 1

Given p = 41 and q = 17 from these p and q

we will get n = p * q hence n = 41 * 17 = 697

Now $\Phi (n) = (p-1) * (q-1)$

Hence $\Phi (n) = (41-1) * (17-1) = 40 *16 = 640$

a)

       We know that for public key e, gcd( e ,$\Phi (n)$ ) = 1

       Now gcd( e₁ ,$\Phi (n)$ ) = 1 implies gcd (32,640) = 1

       this is false as gcd (32,640) != 1

       Hence for public key we will prefer e2 which is 49.

b)

      Now to find private key d we have the below relation

            e * d = 1 mod $\Phi (n)$

            49 * d = 1 mod 640

      Hence the value of d is 209.

c)

    For Encryption of Message M we will use the relation

   C = M^e mod n   (where C is the cipher text)

Given M = 26 and we know that e = 49 and n = 697

Hence C = 26⁴⁹ mod 697

   = 468

   Hence the cipher text for the plain text 26 is 468.

d)

   For Decryption of Message C we will use the relation

   M = C^d mod n   (where C is the cipher text and M is plain text)

Given C = 513 and we know that d = 209 and n = 697

   Hence M = 513²⁰⁹ mod 697

   = 326

   Hence the plain text for the cipher text 513 is 326.