I am preparing for the final exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. The sample solution at the end the textbook is more like a hint instead of being a step-by-step solution.


enter image description here

Textbook solution: Yes. They are equivalent.

My answer: I do not know to check if some scheme is equivalent to RSA. So I tried to verify $D$.

Step 2: $(P-1)(Q-1) - 1 = (PQ -P-Q+1) - 1 = (N -P-Q+1) - 1 = (N-(P+Q-1) - 1 \equiv 0 \ (mod \ E)$

Step 4: $DE = (P-1) (Q-1) (E-1) + 1 = (PQ - P-Q + 1) (E-1) + 1 = (N - P-Q + 1) (E-1) + 1 = NE-N-E(P+Q-1) + 1$

Take $(mod \ E)$ of both sides:

$[DE = NE-N-E(P+Q-1) + 1] \ (mod \ E)$

$0 \ (mod \ E) \equiv 0 - N - 0 + (P+Q-1) + 1 \ (mod \ E)$

$0 \ (mod \ E) \equiv - (N - (P+Q-1)) - 1 \ (mod \ E)$

$0 \ (mod \ E) \equiv 0 \ (mod \ E) \leftarrow$ verified $D$ is correct.

But obviously this is not a concrete reasoning on why this scheme is equivalent to RSA. Any hints would be appreciated.


You are correct; your "proof" is invalid; even if you show that $d$ is the correct value modulo $e$, that doesn't immediately imply that it is the correct value. If you replace $d$ with $d+e$, that is also is correct modulo $e$, but is also obviously wrong (it is even).

Instead, here is a better line of reasoning:

Two integers $d, e$ work as the private, public exponents modulo a product of two primes $pq$ iff both the following hold:

$$de \equiv 1 \pmod{p-1}$$ $$de \equiv 1 \pmod{q-1}$$

What you need to show is:

  • That $d$ as specified in the above formula is actually an integer; that is, that $(p-1)(q-1)(e-1)+1$ is a multiple of $e$

  • That $de \equiv 1 \pmod{p-1}$

  • That $de \equiv 1 \pmod{q-1}$

None of these three should be difficult to prove.

  • $\begingroup$ By e, p, q and d you mean E, P, Q and D? $\endgroup$ – Node.JS Apr 23 '16 at 17:57
  • 1
    $\begingroup$ @Node.JS: well, yes; I don't feel like shouting in my equations... $\endgroup$ – poncho Apr 23 '16 at 18:38
  • $\begingroup$ Thank you so much for the hint. I have a another question that is actually question 9.14 of the book which is extension of 9.13. The question is: In Exercise 9.13, suppose that Alice follows steps 1, 2 and 3 for generating her public key $(E, N)$. However in step 4, she uses $D' = \frac{(P −1)(Q−1)−1}{E}$ as her private key. Assume that Bob sends the ciphertext $c = m^E \ (mod \ N)$ to Alice, how can Alice recover $m$ from $c$ by using $D'$ and $N$? $\endgroup$ – Node.JS Apr 23 '16 at 20:41
  • $\begingroup$ Any hint would be appreciated. $\endgroup$ – Node.JS Apr 23 '16 at 20:44
  • $\begingroup$ @Node.JS: how is that $D'$ related to the "real" one? How can Alice reconstruct a working $D$ from $D'$? Hint: $x^{-1} \bmod N$ can be computed, even if you don't know the factorization of $N$. $\endgroup$ – poncho Apr 24 '16 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.