¿Cómo funcionan las matemáticas de la trampilla RSA?

Question

Usted tiene la función unidireccional del candidato $$f_{n,e}(x) = x^e \mod n,$$ donde $n = pq$ con $p,q$ primos con $|p| = |q|$ (misma longitud de bits) y $\gcd(e, (p-1)(q-1)) = 1$ .

Entonces la trampilla, es decir, lo que necesitas para encontrar eficientemente $x$ dado $f(x)$ y $n,e$ son los números $p,q$ .

Hasta aquí todo bien. Ahora se explica por qué esto funciona.

Vuelves $y^d \mod n$ donde $ed \mod (p-1)(q-1) = 1$ . Esto funciona porque $$y^d \mod n = x^{ed} \mod n = x^{ed \mod (p-1)(q-1)} \mod n.$$

Este es el paso que no entiendo. ¿Cómo sabemos que $x^{ed} \mod n = x^{ed \mod (p-1)(q-1)} \mod n$ ?

Answer 1

Desde $ed \equiv 1 \mod (p-1)(q-1)$ existe $a$ tal que $ed = a(p-1)(q-1) + 1$ . Así, $$ y^d \equiv x^{ed} \equiv x^{a(p-1)(q-1) + 1} \mod n $$ Si $x$ es un múltiplo de $p$ entonces $x^{a(p-1)(q-1) + 1} = x \, x^{a(p-1)(q-1)} \equiv 0 \equiv x \mod p$ . Si no, por el pequeño teorema de Fermat, $x^{a(p-1)(q-1) + 1} = x \, \left(x^{a(q-1)}\right)^{p-1} \equiv x \mod p$ . Asimismo, $x^{a(p-1)(q-1) + 1} \equiv x \mod q$ . Desde $p$ y $q$ son primos distintos, son coprimas, así que por el teorema chino del resto, $x^{a(p-1)(q-1) + 1} \equiv x \mod pq$ . En otras palabras: $y^d \equiv x \mod n$ .