How does the math in the RSA trapdoor work?

96 Views Asked by At

You have the candidate one-way function $$f_{n,e}(x) = x^e \mod n,$$ where $n = pq$ with $p,q$ primes with $|p| = |q|$ (same bit length) and $\gcd(e, (p-1)(q-1)) = 1$.

Then the trapdoor, that is, what you need to efficiently find $x$ given $f(x)$ and $n,e$ is the numbers $p,q$.

So far so good. Now it gets explained why this works.

You return $y^d \mod n$ where $ed \mod (p-1)(q-1) = 1$. This works because $$y^d \mod n = x^{ed} \mod n = x^{ed \mod (p-1)(q-1)} \mod n.$$

This is the step i don't get. How do we know that $x^{ed} \mod n = x^{ed \mod (p-1)(q-1)} \mod n$?

1

There are 1 best solutions below

0
On

Since $ed \equiv 1 \mod (p-1)(q-1)$, there exists $a$ such that $ed = a(p-1)(q-1) + 1$. Thus $$ y^d \equiv x^{ed} \equiv x^{a(p-1)(q-1) + 1} \mod n $$ If $x$ is a multiple of $p$ then $x^{a(p-1)(q-1) + 1} = x \, x^{a(p-1)(q-1)} \equiv 0 \equiv x \mod p$. Otherwise, by Fermat's little theorem, $x^{a(p-1)(q-1) + 1} = x \, \left(x^{a(q-1)}\right)^{p-1} \equiv x \mod p$. Likewise $x^{a(p-1)(q-1) + 1} \equiv x \mod q$. Since $p$ and $q$ are distinct primes, they are co-prime, so by the Chinese remainder theorem, $x^{a(p-1)(q-1) + 1} \equiv x \mod pq$. In other words: $y^d \equiv x \mod n$.