Encriptado RSA
¿Qué tiene que ver la teoría de números con la seguridad informática?
\[\Phi(p q)=\Phi(p) \Phi(q)=(p-1)(q-1)\]Aquí veremos a detalle el funcionamiento de RSA, aplicaremos gran parte de lo que hemos visto en los capítulos anteriores, también dejaremos un código en Mathematica que automatiza el algoritmo.
Algoritmo:
-
Escogemos dos números primos grandes \(p\) y \(q\)
-
Calculados \(n=p q\) y \(\Phi(n)\)
Sabemos que como \(n=p q\) y \(p\) y \(q\) son primos, entonces \(\Phi(p q)=(p-1)(q-1)\).
Entonces a pesar de que \(p\) y \(q\) son muy grandes y \(n\) aún más se vuelve sencillo calcular \(\Phi(n)\) y esto nos interesa.
- Luego buscamos un e tal que m.c.d \((\Phi(n), e)=1\)
Este e lo podemos acotar para encontrarlo fácilmente también. \(2<e<\Phi(n)\)
- Calculamos \(d\) tal que \(d \cdot e \equiv 1\) (mód \(\Phi(n)\))
Podemos ver que \(d \cdot e-k \Phi(n)=1\) y por el teorema de Bezout observamos que esto se reduce a usar el algoritmo de Euclides, pero en este caso el algoritmo extendido que nos permite siempre encontrar la combinación lineal del m.c.d
Y esta combinación lineal nos dice quien es \(d\).
Bien, ahora le decimos a los que se quieran comunicar con nosotros que utilicen e y \(n\) para cifrar los datos
Entonces supongamos que nos quieren enviar un mensaje \(m\), primero este mensaje se debe convertir en números.
La forma más usual de proceder es usar ASCII
Ya que nos permite hacer este trabajo de representar textos con números y debemos verificar que \(m<n\), es decir que el número que representa nuestro mensaje es menor que \(n\), pero por eso mismo usamos primos muy grandes, para evitar ese detalle.
Una vez hecho esto calculamos \(c \equiv m^e\) (mód \(\left.n\right)\) y listo, $c$ es el mensaje cifrado que nos enviaran a nosotros.
Ahora nosotros podemos recuperar el mensaje original resolviendo la congruencia.
\[m \equiv c^d \quad(\text { mód } n)\]¿Pero por qué?
\[c^d \equiv\left(m^e\right)^d \quad(\text { mód } n)\]y sabemos que \(e \cdot d=k \Phi(n)+1\), luego
\[c^d \equiv m^{k \Phi(n)+1} \quad(\text { mód } n)\]Entonces
\[c^d \equiv m\left(m^k\right)^{\Phi(n)}(\text { mód } n) \equiv m(\text { mód } n)\]Note que ese último paso usa fuertemente el teorema de Euler.
Y listo, ya sabemos como se cifran y descifran los mensajes, pero, ¿por qué es seguro?
Si un atacante pudiera interceptar nuestro tráfico de datos en internet y quisiera saber el contenido de los mensajes cifrados debe conocer el valor de \(d\) para aplicar el proceso de descifrado que ya vimos.
Y como \(d \cdot e \equiv 1\) (mód \(\Phi(n))\), entonces el atacante debe conocer \(\Phi(n)\) y para ello debe o calcular el valor a fuerza bruta o conocer la factorización de \(n\), y sabemos que factorizar números grandes es demasiado costoso.
Cualquier camino que escoja para calcular \(\Phi(n)\) es demasiado costoso para cualquier computador. A día de hoy no hay algoritmos que factoricen enteros en orden polinomial.
Recordemos en el post de Notación O grande que incluso los algoritmos de orden polinomial no son necesariamente muy eficientes, entonces sí, los atacantes se enfrentan a un problema matemáticamente muy muy denso.
Y eso es lo que mantiene seguro nuestro tráfico, al menos por ahora, aunque hay cifrados alternativos, RSA se sigue usando muchísimo, la razón para buscar alternativas es básicamente estar preparados para cuando este no sea seguro.
RSA usa solo dos números primos para construir el compuesto grande porque usar más puede volver más lento el calculo de \(\Phi(n)\) y por tanto el encriptado.
Además entre más primos hay en la factorización de $n$, más fácil para el atacante factorizarlo.
Y la idea de la criptografía siempre es hacer algoritmos eficientes para nosotros, pero difíciles de romper para un atacante.
Código en Wolfram Mathematica:
ListToNumber[list_] := First[list] /; Length[list] == 1
ListToNumber[list_] :=
1000*ListToNumber[Reverse[Rest[Reverse[list]]]] + Last[list]
TextToNumber[string_] := ListToNumber[ToCharacterCode[string]]
NumberToList[number_] := {number} /; number < 1000
NumberToList[number_] :=
Append[NumberToList[(number - Mod[number, 1000])/1000],
Mod[number, 1000]]
NumberToText[number_] := FromCharacterCode[NumberToList[number]]
En esa primera parte definimos las funciones que transforman el texto en números y viceversa.
Encipher[message_] :=
PowerMod[TextToNumber[message], e, n]
Decipher[number_] :=
NumberToText[PowerMod[number, d, n]]
En esta el encriptado y desencriptado
InitializeRSA := Module[{},
p = NextPrime[Random[Integer, {10^100, 10^101}]];
q = NextPrime[Random[Integer, {10^100, 10^101}]];
n = p*q;
\[CurlyPhi] = (p - 1)*(q - 1);
e = \[CurlyPhi];
While[Not[GCD[\[CurlyPhi], e] === 1],
e = NextPrime[
Random[Integer, {10^50, 10^51}]]];
d = PowerMod[e, -1, \[CurlyPhi]]
]
Esta función inicia RSA lo que nos dará en pantalla el valor de \(d\)
{e, n}
Esta parte nos da el valor de \(e\) y \(n\) en pantalla.
message = "Basado"
En es esta parte escribimos el mensaje que queremos c
result = Encipher[message]
Esto nos entrega el mensaje cifrado
Decipher[result]
Finalmente esta instrucción lo descifra y listo. Dejaremos un enlace para descargar desde GitHub el cuaderno completo donde se encuentra el código.