0
$\begingroup$

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.

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