Question

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

key of this user?

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

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

Kindly revert for any queries

Thanks.