# Trying to udnerstand textbook sample solution

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.

Question: 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.

• By e, p, q and d you mean E, P, Q and D? – Node.JS Apr 23 '16 at 17:57
• @Node.JS: well, yes; I don't feel like shouting in my equations... – poncho Apr 23 '16 at 18:38
• 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$? – Node.JS Apr 23 '16 at 20:41
• Any hint would be appreciated. – Node.JS Apr 23 '16 at 20:44
• @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$. – poncho Apr 24 '16 at 11:24