0

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.

kelalaka
  • 45,607
  • 9
  • 104
  • 179
princetongirl818
  • 163
  • 5
  • Look for [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) or see [Modular Multiplicative Inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) or search for `ext GCD examples`. If you don't do it now, you won't in the exam. – kelalaka Jan 06 '19 at 20:26
  • Please see edit. I have reviewed that example. – princetongirl818 Jan 06 '19 at 22:08
  • 1
    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. – kelalaka Jan 06 '19 at 22:11
  • 1
    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. – fkraiem Jan 06 '19 at 22:14
  • 1
    (Also, in principle you should also verify that 1237 and 2347 are prime.) – fkraiem Jan 06 '19 at 22:16
  • I don't really know how to progress having applied the extended euclidean algorithm :/ – princetongirl818 Jan 06 '19 at 22:18
  • The inverse of $5$ for $\bmod \varphi$ not $\bmod n$. Did you look at the duplicate link? in Edit part it is taken as 2903239 but should be 2899656 – kelalaka Jan 06 '19 at 22:21
  • 2
    Odd, I get $d = 386621$; that certainly works as a decryption exponent. Your textbook might be wrong... – poncho Jan 07 '19 at 02:24

0 Answers0