RSA: ¿Cómo se utiliza el Teorema de Euler?

Question

Estoy tratando de entender el funcionamiento del algoritmo RSA. Me estoy confundiendo en la parte de descifrado. Estoy asumiendo que

$$n = pq$$ $$m = \phi(n) = (p - 1)(q - 1)$$

E es la clave de cifrado $\gcd(\phi(n), E) = 1$

D es la clave de descifrado, y $DE = 1 \mod \phi(n)$

$x$ es el texto sin formato

El cifrado funciona como ( $y = x^E \mod n$ ) y la desencriptación funciona como ( $x = y^D \mod n$ )

La explicación de por qué la desencriptación funciona es que como $DE = 1 + k\phi(n)$ ,

$$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$

La razón por la que la última expresión funciona es $x^{\phi(n)} = 1 \mod n$ ? Según el teorema de Eulers esto es cierto sólo si $x \text{ and }\phi(n)$ son coprimas. Pero $x$ sólo se limita a ser $0 < x < n$ y $\phi(n) < n$ . Así que $x$ debe elegirse para que sea coprima con $\phi(n)$ ?

¡Ayúdame a aclarar la confusión!

Answer 1

Incluso si el texto plano $x$ no es coprima por pares con $p$ o $q$ El RSA sigue funcionando como se anuncia. Aquí está la razón:

$p$ y $q$ son primos, por lo que $x$ es un múltiplo de $p$ o $q$ dada la restricción de que $x < pq$ .

Supongamos que $x \equiv 0 \pmod p$ . Si es congruente con $0$ mod $q$ lo que se indica a continuación sigue siendo válido, sólo hay que cambiar el nombre asignado a los dos primos.

$x^k \equiv 0 \pmod p$ para todos $k > 0$ es decir $x^k \equiv x \pmod p$ .

$$ \begin{align*} x^{1+ z \phi(n)} & \equiv x^{1+ z \phi(p) \phi(q) } \\ &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*} $$

Combinando ambas ecuaciones con el Teorema del Resto Chino se obtiene $x$ el texto plano.

Answer 2

En primer lugar, la declaración debería decir $x^{\phi(n)}\equiv1\pmod{n}$ no modulo $\phi(n)$ . Tienes razón en que esto supone que $x$ y $n$ son coprimos. Dado que $p,q$ son primos muy grandes, la fracción de posibles $x$ que no es coprima con $n$ es excesivamente pequeño: $\frac1p+\frac1q-\frac1n$ . De hecho, la seguridad del método se basa en la pequeñez de este número: si hubiera alguna posibilidad razonable de encontrar un número $m$ no coprima con $n$ eligiendo un número al azar entre $0$ y $n$ , entonces se podría calcular $\gcd(m,n)\in\{p,q\}$ usándolo, y el factor $n$ . Pero formalmente, la prueba de la coprimalidad del texto llano $x$ con $n$ debe ser realizado por el codificador, al igual que la prueba que ya supuso que $x\neq0$ . En el caso muy improbable de que la coprimalidad falle, hay que añadir algo de ruido al texto plano.

Answer 3

Aparte de que es poco probable que $\gcd(x,n) \neq 1$ , tenga en cuenta que las únicas posibilidades son $\gcd(x,n) \in \{1,p,q,n\}$ . Por lo tanto, si $x$ y $n$ son no coprima, el uno puede descifrar el texto de todos modos (ya que uno entonces sabe o $p$ o $q$ y puede encontrar fácilmente el otro factor, y por lo tanto $n$ ).

En otras palabras, si $x \in \mathbb{Z}/ n \mathbb{Z}$ no es una unidad, sabemos que $$ x^{ED} \equiv x \pmod{n} \Longleftrightarrow \left\{\begin{array}{ccc} x^{ED} \equiv x \pmod{p} \\ x^{ED} \equiv x \pmod{q} \end{array} \right\}. $$

Espero que esto ayude.