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? (hint: you can look at the prime number table and find out q and p pretty easily)

Answer 1

Answer: 1256.

Explanation: To find the private key in an RSA system, we need to calculate the value of d, which is the modular multiplicative inverse of e modulo (p-1)(q-1), where p and q are the prime factors of n. We can find p and q by factoring n, which in this case is:

n = 3599 = 59 x 61

Therefore, p = 59 and q = 61. We can then calculate (p-1)(q-1) = 58 x 60 = 3480.

To find d, we need to calculate the value of d such that:

d * e ≡ 1 (mod 3480)

In other words, we need to find the value of d that satisfies the above congruence equation. One way to do this is to use the extended Euclidean algorithm.

Using the extended Euclidean algorithm, we can find that:

3480 = 31 x 112 + 8

31 = 3 x 8 + 7

8 = 1 x 7 + 1

Working backwards, we can express 1 as a linear combination of 3480 and 31:

1 = 8 - 7 x 1

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

1 = 4 x 8 - 31 x 1

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

1 = 4 x 3480 - 1256 x 31

Therefore, d = 1256. The private key for this RSA system is (n, d) = (3599, 1256)