Question

In an rsa system the public key of a given user is e= 31, n=3599. What is the private key of this used

Answer 1

Answer :-

n = 3599 , e = 31

n = p x q  here p and q are prime numbers

 

∴ 3599=59 x 61 -- Here 59 , 61 are prime numbers

Now, ed=1 mod ϕ(n)

here, ϕ(n) is Euler's tortient function .

ϕ(n) = (p−1) x (q−1)

ϕ(n) = 58 x 60

ϕ(n) =  3480

Now 31 x d = 1 mod (3480)

3480 * X + 31∗Y = 1

Step1:  Eucledian Algorithm

 

3480 = 112 * (31) + 8

8 = 1 * (7) + 1

Step 2 : Back Substitution  

1 = 8 - 1 (7)

1 = 8 - 1( 31 - 3(8) )

1 = 4 (8) -  1 (31)

1 = 4 ( 3480 - 112 (31)  ) -  1 (31)

1 = 4 (3480) -  449 (31)

Since 449 is a negative number subtract from tortient function

Hence d=3480−449

           d=3031