Reading the article "Twenty Years of Attacks on the RSA Cryptosystem" by Dan Boneh, I am trying to understand the proof of the Fact 1 (Given the private key $d$, one can efficiently factor the modulus $N = pq$). Particularly this statement:
We have $g^k = 1$ for every $g \in Z_N^∗$
that's obviously a mistake that meant to be:
We have $g^k \equiv 1(\mod{N})$ for every $g \in Z_N^*$
where:
- $k = ed - 1$
- $N = pq$, where $p$ and $q$ are prime
- $(N,e)$ is a public RSA key
- $(N,d)$ is a private RSA key
- $Z_N^∗$ – multiplicative group (thanks @Matthew Towers)
I have problems understanding this claim. Where did it come from?
My (wrong) reasoning. According to the article:
By definition of $d$ and $e$ we know that $k$ is a multiple of $\phi(N).$
That would make Euler's theorem applicable: $g^{\phi(N)} \equiv 1 (\mod{N})$ for those values of $g \in Z_N^*$ which are coprime with $N$. But it wouldn't necessarily be true for $g = p \in Z_N^*$ and $g = q \in Z_N^*$, it seems, which are not coprime with $N = pq$... That's where I got lost.
UPD. My mistake was that I got $Z_N = \{0, ..., N-1\}$ (set of residues) mixed up with $Z_N^*$ (multiplicative group, or subset of $Z_N$ in which all numbers are coprime to $N$). Thanks for help!
Note that $Z_N=\{0,1,\ldots,N-1\}$ is the set of all residues mod $N$ (it's a ring, with two operations, addition and multiplication modulo $N$) while $Z_N^\ast$ is the subset of co-prime (with $N$) residues (of size $\phi(N)$, under the operation multiplication modulo $N$ (it is a group). So $p,2p,q,2q, \ldots \notin Z_N^\ast$, contrary to what you seem to think.
You know that $e$ and $d$ are each other's inverses modulo $\phi(N)$ (this is how RSA works and how $e$ and $d$ are chosen, and it ensures that $x \to x^e \pmod{N}$ and $x \to x^d \pmod{N}$ are mutual inverses on $Z_N$), by Euler's theorem.
So $ed \equiv 1 \pmod{\phi(N)}$, or $ed-1 \equiv 0 \pmod{\phi(N)}$, so $k:= ed-1$ is a multiple of $\phi(N)=(p-1)(q-1)$, and so a multiple of the group order of $Z_N^\ast$ and hence the first statement holds.