# Verifying valid public key and finding private key? [duplicate]

A naive user of RSA has announced the public key $$n = 2903239, e = 5$$. Eve has worked out that $$n = 1237×2347$$. Verify that the public key is valid and explain why the private key is $$d = 2319725$$. [Calculators are not required.]

This question comes from a mock exam that I am trying to solve for tomorrow.

I attach my working out:

$$n = p\;q = (1237)(2347) = 2903239$$

$$\varphi(n) = (1237-1)(2347-1) = 1236(2346) = 2899656$$

$$d\;e \bmod \varphi(n) = 1$$

$$e = 5$$

$$5\;d \bmod 2899656 = 1$$

Applying the Euclidean algorithm:

$$5\;x + 2899656\;y = 1$$

$$2899656 = 5(579931)+1$$

• The public key part: $$(e,n) = (5, 2903239)$$
• The private key part: $$(d,n) = (2319725,1)$$

I do not understand how the private key is calculated, nor how to do this with a calculator. Any help would be welcome.

EDIT: $$\varphi (n) = (1237-1)(2347-1)= 2899656 \neq 2903239$$

de mod (phi(n)) = 1

5d mod 2903239 = 1

5x + 2903239y = 1

2903239 = 5(580647)+4

5 = 4(1) + 1

1 = 5 - 4(1)

1 = 5 - (2903239 - 5(580647)

1 = 5 - 2903239 + 5(580647)

1 = 5(580648) - 1(2903239)

I am still unsure of how to obtain the private key value from this.

2903239 - 5860648 = 2322591

This value is not the same as the desired value of d, d = 2319725.

• Look for extended Euclidean algorithm or see Modular Multiplicative Inverse or search for ext GCD examples. If you don't do it now, you won't in the exam. Jan 6, 2019 at 20:26
• take $\mod 2903239$ you will get $1 \equiv 5 \cdot 580648 \bmod 2903239$. don't you see the inverse of $5$ now? But there is a calculation error right. Jan 6, 2019 at 22:11
• Note that you don't need to obtain the private key, since it is given. You only need to verify that the given key is correct. Jan 6, 2019 at 22:14
• (Also, in principle you should also verify that 1237 and 2347 are prime.) Jan 6, 2019 at 22:16
• Odd, I get $d = 386621$; that certainly works as a decryption exponent. Your textbook might be wrong... Jan 7, 2019 at 2:24