Question

Let the two primes p = 41 and q = 17 be given as set-up parameters for RSA. 1) Which of the parameters e1 = 32, e2 = 49 is a valid RSA exponent (i.e., is a valid public key, e1 or e2)? Justify your choice. 2) Compute the corresponding private key Kpr = (p, q, d). Use the extended Euclidean algorithm for the inversion and point out every calculation step.

Answer 1

Solution :

It is given in the question that :

Two prime numbers : p = 41

                                    q = 17

Therefore, n = p x q

                     = 41 x 17

                    = 697

Now we know that :

$\phi (n) = (p-1)\times (q-1)$

$\phi (n) = (41-1)\times (17-1)$

       = 40 x 16

      = 640

a). For the public key $\text{e gcd(e, }\phi(n))=1$

Now the $\text{gcd}(e_1,\phi(n))=1$ implies $\text{gcd}(32,640)=1$

But this is false as the $\text{gcd}(32,640)! = 1$

Therefore the public key will prefer $e_2$ , that is 49.

b). We have to find the private key d. So we know that

    $e \times d = 1 \text{ mod } \phi(n)$

    $49 \times d = 1 \text{ mod } 640$  

Therefore the value of d = 209

c). The encryption of the message M, we will use the relation:

$C=M^e \text{ mod } n$ ;  here "C" is cipher text

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

Therefore, $C=26^{49} \text{ mod }697$

                     = 468

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

d). For the decryption of message C,

    $M=C^d \text{ mod }n$ (here C = cipher text, M = plain text)

    Given $C=513$. And the value of d is 209 and n is 697

    Therefore, $M=513^{209}\text{ mod } 697$

                            $=326$

Therefore, the plain text for cipher text 513 is 326.