Trying to udnerstand textbook sample solution

Question

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.

Answer 1

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.