gatebook

Question

Suppose that in RSA encryption, the public encryption key is the pair (e n)= (3, 55) and the private decryption key is the pair (d,n)=55, where d

(A) 13

(B) 27

(C) 37

(D) 39

Answer 1

public key = (3,55) and private key = (d,55)

According to given data n=55

now n can also be given by n=p*q where p and q are prime numbers

since n=55 so p=11 and q=5 or p=5 and q=11

z= (p-1)*(q-1) = 10*4 = 40

e*d mod z =1

3*d mod 40 =1

now 3*d can be 1 or 41 or 81 or 121 or so on

if 3*d =81 then d= 81/3 = 27

If u go option then also only 27 satisfy the modulo property

Hence answer should be B) 27

Answer 2

Let us we have given public keys =(e,n)=(3,55)

so e=3 and n=55

Privates keys as =(d,n)=(d,55)

¢(n)=¢(p) x ¢(q)

where p and q are two distinct prime number and here n=55= 11 x 5 so p=11 and q=5

¢(55)=¢(11) x ¢(5)

¢(55)=(11-1) x (5-1)=40

Since we know e=3

Therefore to find out d(one of the private key pair):

d x e= 1 mod ¢(55)

d x 3 = 1 mod40

Choose from the option is the best way to solve such problem in gate.

Therefore d=27 is going to satisfy.

Therefore best option will be d=27