# 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 '19 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 '19 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 '19 at 22:14
• (Also, in principle you should also verify that 1237 and 2347 are prime.) Jan 6 '19 at 22:16
• Odd, I get $d = 386621$; that certainly works as a decryption exponent. Your textbook might be wrong... Jan 7 '19 at 2:24