Cifrado RSA#
Introducción#
En este capítulo vamos a ver el algoritmo RSA, el cual es un cifrado asimétrico. Esto significa que usa dos claves diferentes, pero que están relacionadas matemáticamente, una clave es pública y la otra es privada. Este sistema de cifrado es ampliamente utilizado en la seguridad informática para proteger la comunicación en línea y garantizar la autenticidad de los datos. La seguridad de este cifrado se basa en la dificultad de factorizar un número cuando esta compuesto de dos primos excesivamente grandes. Vamos a presentar el algoritmo, veremos cómo cifrar y descifrar un mensaje. Además hablaremos de por qué es complicado descifrar mensajes cuando no se conocen los primos involucrados.
Idea general del cifrado RSA#
El cifrado RSA es un criptosistema de llave pública, es decir, que existe una llave que puede ser conocida por cualquiera y es la que se utiliza para cifrar mensajes. En otros tipos de cifrados, la clave de cifrado la conocen únicamente el emisor y el destinatario del mensaje.
Este criptosistema fue propuesto en 1976 por Whitfield Diffie y Martin E. Hellman de la Universidad de Stanford. Aunque Diffie y Hellman no proporcionaron una implementación práctica de un sistema de cifrado de clave pública, desarrollaron tres propiedades que un criptosistema de este tipo debe tener:
Cada usuario debe tener una clave de cifrado \(E\) (que se hace pública) y una clave de descifrado \(D\) (que se mantiene en secreto) de manera que \(M = E(D(M)) = D(E(M))\) para cada mensaje \(M\). Por lo tanto, los algoritmos \(E\) y \(D\) son operaciones inversas.
Es computacionalmente fácil para el usuario calcular las claves \(E\) y \(D\).
Es computacionalmente inviable para un usuario no autorizado emplear la clave de cifrado \(E\) para desarrollar la clave de descifrado \(D\), lo que garantiza la seguridad del sistema.
En un criptosistema de clave pública, el algoritmo de cifrado \(E\) de cada usuario del sistema se hace público como en una guía telefónica, mientras que el algoritmo de descifrado correspondiente \(D\) es conocido sólo por el usuario previsto, la persona que recibirá el mensaje. Aunque la clave de cifrado \(E\) es de conocimiento público, es computacionalmente inviable emplearla para descubrir la clave de descifrado \(D\), por lo que es prácticamente imposible para un criptoanalista descifrar el sistema.
Supongamos que tenemos \(5\) usuarios de un criptosistema de llave pública. Cada persona tiene una clave de cifrado \(E_i\) que es pública para todos los usuarios. Si el usuario \(1\) quisiera enviar un mensaje \(M\) al usuario \(3\) tendría que buscar la clave de cifrado \(E_3\) del usuario \(3\) y luego cifrar el mensaje usando esa clave, es decir \(C = E_3(M)\). Luego, el usuario \(3\) podría leer el mensaje usando su algoritmo de descifrado secreto \(D_3\), \(D_3(C) = D_3(E_3(M)) = M\), ya que \(E_3\) y \(D_3\) son operaciones inversas. Es decir que todos pueden enviar mensajes bajo la clave de cifrado, pero sólo la persona que contiene la clave de descifrado puede descifrar el mensaje.
En 1978, Ronald L. Rivest, Adi Shamir y Leonard Adelman del Instituto Tecnológico de Massachusetts desarrollaron una forma práctica de implementar el elegante concepto de Diffie y Hellman. Este sistema de clave pública, conocido popularmente como criptosistema RSA, es un sistema de cifrado exponencial basado en la exponenciación modular y el teorema de Euler (RSA es el acrónimo de Rivest, Shamir y Adelman).
Cifrar un mensaje con RSA#
La clave del cifrado RSA es el par \((e,n)\), donde \(e\) es un entero positivo y \(n\) es el módulo que vamos a ocupar en este cifrado. El número \(n\) es un número compuesto por dos primos diferentes \(p\) y \(q\). Normalmente esos primos deben de ser números de alrededor de \(100\) dígitos de longitud o más grandes. Además, vamos a necesitar que \((e,\varphi(n)) = 1\).
Para cifrar un mensaje vamos a volver a utilizar la tabla Observación 22 para convertir las letras del texto plano a su correspondencia numérica. Luego, vamos a agrupar los números en bloques de longitud \(2m\), tales que el número que se forma en el bloque sea menor que \(n\).
Como estamos trabajando con un alfabeto de \(27\) letras, podemos formar bloques de diferentes tamaños. Si tomamos \(m = 2\), tendríamos bloques de longitud \(2m = 2\cdot 2 = 4\) y el número más grande que podemos formar con bloques de longitud \(4\) es \(2626\). Cuando \(m = 3\), tendríamos bloques de longitud \(2m = 2\cdot 3 = 6\) y el número más grande que podemos formar con bloques de longitud \(6\) es \(262626\). El valor de \(m\) lo podemos elegir de esa manera para asegurarnos que el número formado en los bloques no sea más grande que \(n\).
Ejemplo 157
Veamos un ejemplo de como podemos elegir el valor de \(m\). Si tomamos \(p = 599\) y \(q = 601\), tendríamos que \(n = 359999\).
Notemos lo siguiente
Hay algunas consideraciones para los bloques que se forman.
Todos los bloques deben ser del mismo tamaño.
Si el último bloque tiene longitud menor que \(2m\), entonces vamos a completar con el número \(24\) que corresponde a la letra \(\text{X}\) del alfabeto hasta que tenga longitud \(2m\).
Observación 26 (Congruencia de cifrado)
Una vez que fijamos el valor de \(n\) y \(e\), obtenemos los bloques \(P_i\) de longitud \(2m\). Luego, encriptamos el mensaje utilizando la congruencia
Consideraciones.
Para hacer las cuentas en la congruencia de cifrado se omiten los ceros a la izquierda del número formado por el bloque.
Si el resultado de la congruencia da un bloque con longitud menor a \(2m\), entonces rellenamos con ceros antes del valor hasta tener longitud de \(2m\).
Veamos un ejemplo para ilustrar con más detalle el algoritmo. Recordemos que seguimos usando las mismas condiciones para escribir un mensaje en texto plano.
Ejemplo 158
Usa el algoritmo RSA para cifrar el siguiente mensaje.
Solución.
Primero vamos a convertir el mensaje de texto plano en su correspondencia numérica utilizando la tabla Observación 22. Entonces tendremos que:
La persona a la que le vamos a enviar el mensaje ya nos ha proporcionado de alguna manera su clave pública, \((e,n) = (31, 359999)\). Nuestro destinatario es quién generó el par de números primos \(p\) y \(q\), y por tanto, también calculó \(n = pq\), \(\varphi(n)\), \(e\), además, ya se ha encargado de corroborar que \((e,\varphi(n)) = 1\), ya que él conoce los primos involucrados en la factorización de \(n\) y por lo tanto ya tiene su clave privada \((d,n)\). Esto se debe a que el destinatario es quien necesita la clave privada para descifrar los mensajes.
Lo que tenemos que encontrar ahora es el valor de \(m\). Notemos que
Por lo tanto, vamos a tomar \(m = 3\). Creamos bloques de longitud \(6\) con la cadena de números anterior. Entonces tendremos los siguientes bloques,
En el último bloque sólo nos había quedado el número \(19\), por lo cual lo rellenamos con \(2424\) que representa a la letra \(\text{X}\). Esto se hace para que todos los bloques tengan la misma longitud.
Ahora vamos a utilizar la congruencia de cifrado \(C_i\equiv {P_i}^{31}\pmod{359999}\). A manera de ejemplo, vamos a aplicar la congruencia para los primeros bloques.
Si tomamos el bloque \(041100\), entonces tendríamos que omitir el cero a la izquierda del bloque para hacer las operaciones.
Si tomamos el bloque \(110615\), entonces tendríamos que,
A este valor de \(C_2\) debemos agregarle un cero a la izquierda para que el bloque tenga longitud \(6\), es decir que \(C_2 = 093349\).
Para procurar que todos los bloques \(C_i\) tengan la misma longitud, vamos a rellenar con ceros a la izquierda hasta que el bloque \(C_i\) tenga la misma longitud que el entero \(n\).
Ahora, vamos a mostrar todos los valores después de aplicar la congruencia de cifrado.
Por lo tanto, este es nuestro mensaje cifrado con el algoritmo RSA.
Código para cifrar un mensaje usando RSA#
Vamos a presentar un código que nos ayudará a cifrar un mensaje utilizando el algoritmo RSA.
Para ellos vamos a suponer que ya no han proporcionado la clave pública \((e,n)\) del destinatario. Primero vamos a ponernos del lado del destinatario, vamos a crear un código que nos ayude a calcular \(n = pq\), \(\varphi(n)\) y \((e, \varphi(n)) = 1\).
Vamos a utilizar el código para calcular el máximo común divisor de \(2\) números.
def algoritmo_euclides(a,b):
while (a % b) != 0:
a_1, b_1 = a, b
a = b_1
b = a_1 % b_1
return b
Ahora, con el siguiente código vamos a calcular la clave pública.
def llave_publica(p,q,e):
n = p*q
phi_n = (p-1)*(q-1)
primos_relativos = algoritmo_euclides(e,phi_n)
if primos_relativos == 1:
print(f"La clave pública es: ({e},{n}).")
else:
print(f"Revisa tus valores!, el máximo común divisor de e y phi de n es : {primos_relativos}.")
Suponiendo que conocemos la llave pública del destinatario \((e,n)\). El siguiente código toma un mensaje en texto plano y nos regresará el texto plano cifrado con el algoritmo RSA.
def cifrado_rsa(texto,n ,e):
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
texto_cifrado = []
for letra in texto:
if letra in alfabeto:
indice = str(alfabeto.index(letra))
if len(indice) == 1:
indice = '0' + indice
texto_cifrado.append(indice)
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
grupos_m = [texto_cifrado[i:i+longitud_bloque] for i in range(0,len(texto_cifrado),longitud_bloque)]
lista_bloques = []
for bloque in grupos_m:
numero = "".join(bloque)
if len(numero) < 2*longitud_bloque:
numero = numero + (longitud_bloque - len(numero)//2)*"24"
c = (int(numero)**e)%n
if len(str(c)) < len(str(n)):
c = (len(str(n)) - len(str(c)))*"0" + str(c)
else:
c = str(c)
lista_bloques.append(c)
return " ".join(lista_bloques)
llave_publica(599, 601, 31)
La clave pública es: (31,359999).
texto_plano = "EL ALGORITMO RSA SE BASA EN LA DIFICULTAD DE FACTORIZAR PRIMOS"
n = 359999
e = 31
cifrado_rsa(texto_plano, n, e)
'111842 093349 156669 173164 230921 208981 006117 248959 186156 242813 347083 173392 014320 124825 277063 195401 267142 135023'
llave_publica(661, 733, 37)
La clave pública es: (37,484513).
texto_plano = "LA FUNCION PHI DE EULER SE UTILIZA PARA CALCULAR EL EXPONENTE PRIVADO D"
n = 484513
e = 37
cifrado_rsa(texto_plano, n, e)
'108572 223761 278886 237147 342726 104819 168663 348967 147564 247646 422323 189911 143577 225445 225944 005338 444245 350268 418759 366011'
llave_publica(1009, 1013, 97)
La clave pública es: (97,1022117).
texto_plano = 'EL ALGORITMO RSA OBRA MAESTRA DE RIVEST SHAMIR Y ADLEMAN CONTINUA PROTEGIENDO NUESTROS DATOS EN UN MUNDO CADA VEZ MAS DIGITAL'
n = 1022117
e = 97
cifrado_rsa(texto_plano, n, e)
'0890234 0001643 0711031 0372538 0603069 0106677 1017359 0399841 0483788 0076205 0321845 0906081 0278522 0933496 1016365 0425996 0028240 0657722 0680346 0875150 0542434 0757994 0658898 0399841 0175354 0277578 0053728 0959861 0564806 0635611 0444643 0904649 0880943 0984123 0573950'
Descifrar un mensaje con RSA#
La persona que recibe el mensaje cifrado, es quién generó el par de números primos \(p\) y \(q\), por tanto es sencillo para esa persona calcular el valor de \(\varphi(n) = (p-1)(q-1)\). Entonces puede descifrar el mensaje calculando su clave privada \((d,n)\) de la siguiente manera.
Para descifrar un mensaje cifrado con el algoritmo RSA necesitamos calcular el inverso de \(e\) módulo \(\varphi(n)\). Esta es la razón por la cual en la sección de cifrar un mensaje con RSA pedimos que se cumpla que \((e,\varphi(n)) = 1\), para que el inverso \(d\) exista, es decir que la siguiente congruencia tenga solución
Notemos que la congruencia anterior es equivalente a \(de = 1 + k\varphi(n)\) para algún entero \(k\). Entonces tendríamos lo siguiente,
Por el Teorema 39 de Euler, tendríamos que \(P^{\varphi(n)}\equiv 1\pmod{n}\) si \((P,n) = 1\). Entonces el par \((d,n)\) es la llave de descifrado.
A pesar de que \((P,n) = 1\) no se cumpla, el algoritmo RSA funciona. Veamos por qué. Como \(n = pq\), tenemos los siguientes casos.
\((P,n) = n\).
Esto no podría suceder ya que formamos el número \(P\) de tal forma que fuera menor que \(n\), por lo tanto como \(P<n\) sucede que \((P,n) \neq n\).
\((P,n) = p\).
Entonces tendríamos que \((P, q) = 1\), entonces por el Teorema 35 de Fermat tendríamos que \(P^{q-1}\equiv 1\pmod{q}\). Como tenemos que
esto es equivalente a \(de \equiv 1 + k(p-1)(q-1)\) para algún entero \(k\). Por lo tanto tendríamos que
Como \((P,n) = p\), entonces tendríamos que \(C^d \equiv P^{de} \equiv 0 \equiv P\pmod{p}\). Así tendríamos que \(C^d\equiv P\pmod{p}\) y \(C^d\equiv P\pmod{q}\), por lo tanto por el Teorema 50 concluimos que \(C^d\equiv P\pmod{n}\).
\((P,n) = q\).
Procedemos de la misma forma que el caso anterior y también concluimos que \(C^d\equiv P\pmod{n}\).
De hecho si \(p\) y \(q\) son primos de mas de \(100\) dígitos, la probabilidad de que ocurran los últimos \(2\) casos anteriores es extremadamente insignificante.
Ahora vamos a ver un ejemplo de como descifrar un mensaje encriptado con el algoritmo \(RSA.\)
Ejemplo 159
Descifra el mensaje
sabiendo que la clave pública es \((e,n) = (37, 484513) = (37, 661\cdot 733)\).
Solución.
Lo primero que tenemos que encontrar es \(d\), resolviendo la congruencia \(de\equiv 1\pmod{\varphi(n)}\). Para encontrar este valor, primero calculamos lo siguiente
Luego, tendríamos que resolver la congruencia \(37d\equiv 1\pmod{\varphi(483120)}\), o lo que es lo mismo, que \(37d - 483120k = 1\). Si resolvemos la ecuación lineal diofantina, tendríamos que
Después, utilizando las ecuaciones tendremos que
Por lo tanto, obtenemos que
Ahora, para recuperar el mensaje tendríamos que usar la congruencia \(P_i\equiv {C_i}^d \pmod{483120}\), en donde \(d = 130573\).
Aplicaremos la congruencia para los primeros bloques, pero las cuentas serán realizadas computacionalmente por la magnitud de los valores. Recordemos que si el bloque llegara a tener ceros a la izquierda, estos se omiten para realizar las cuentas.
Si tomamos los primeros \(5\) bloques \(C_i\) con \(i = 1,2,3,4,5\), tendríamos que
Para los resultados que tengan longitud menor que \(6\), rellenamos con ceros a la izquierda para que todos los bloques tengan el mismo número de cifras. Así, obtenemos el siguiente resultado.
Ahora, usando la tabla Observación 22 cambiamos los valores por letras.
Finalmente, si acomodamos las palabras obtendremos
Código para descifrar un mensaje conociendo los primos \(p\) y \(q\)#
Vamos a construir un código que nos ayude a descifrar un mensaje que fue cifrado con el algoritmo RSA, conociendo los primos \(p\) y \(q\) con los que se crea \(n\) y la llave de cifrado \(e\).
El siguiente código nos ayuda a calcular el inverso \(d\), resolviendo la congruencia \(de\equiv 1\pmod{\varphi(n)}\).
def euclides_extendido_ciclos(a,b):
s=[1,0]
t=[0,1]
while b!=0:
q=a//b
r=a%b
nuevo_s=s[-2]-q*s[-1]
nuevo_t=t[-2]-q*t[-1]
s.append(nuevo_s)
t.append(nuevo_t)
a,b=b,r
return s[-2],t[-2],a
def congr_lin_sol (a,b,m):
if a >= m or a < 0:
a = a%m
if b >= m or b < 0:
b = b%m
s,t,d = euclides_extendido_ciclos(a,m)
return (s * (b // d))%m
El siguiente código nos regresa el mensaje descifrado.
def descifrado_rsa_con_pq(texto_cifrado,e,p,q):
n = p*q
phi_n = (p-1)*(q-1)
d = congr_lin_sol(e,1,phi_n)
bloques_p = texto_cifrado.split()
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
texto_descifrado = []
for p in bloques_p:
c = (int(p)**d)%n
if len(str(c)) < 2*longitud_bloque:
c = (2*longitud_bloque - len(str(c)))*"0" + str(c)
else:
c = str(c)
texto_descifrado.append(c)
letras_descifrado = []
for palabra in texto_descifrado:
for i in range(0,len(palabra),2):
letra = palabra[i] + palabra[i + 1]
letra = int(letra)
letras_descifrado.append(letra)
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
texto_plano = ''
for i in letras_descifrado:
letra = alfabeto[i]
letra = str(letra)
texto_plano += letra
return texto_plano
texto_cifrado = '108572 223761 278886 237147 342726 104819 168663 348967 147564 247646 422323 189911 143577 225445 225944 005338 444245 350268 418759 366011'
e = 37
p = 661
q = 733
descifrado_rsa_con_pq(texto_cifrado, e, p, q)
'LAFUNCIONPHIDEEULERSEUTILIZAPARACALCULARELEXPONENTEPRIVADODX'
texto_cifrado = '111842 093349 156669 173164 230921 208981 006117 248959 186156 242813 347083 173392 014320 124825 277063 195401 267142 135023'
e = 31
p = 599
q = 601
descifrado_rsa_con_pq(texto_cifrado,e,p,q)
'ELALGORITMORSASEBASAENLADIFICULTADDEFACTORIZARPRIMOSXX'
texto_cifrado = '0890234 0001643 0711031 0372538 0603069 0106677 1017359 0399841 0483788 0076205 0321845 0906081 0278522 0933496 1016365 0425996 0028240 0657722 0680346 0875150 0542434 0757994 0658898 0399841 0175354 0277578 0053728 0959861 0564806 0635611 0444643 0904649 0880943 0984123 0573950'
e = 97
p = 1009
q = 1013
descifrado_rsa_con_pq(texto_cifrado,e,p,q)
'ELALGORITMORSAOBRAMAESTRADERIVESTSHAMIRYADLEMANCONTINUAPROTEGIENDONUESTROSDATOSENUNMUNDOCADAVEZMASDIGITAL'
¿Se podrá descifrar sin conocer los números primos?#
Como vimos durante esta sección, encriptar y desencriptar mensajes utilizando el algoritmo RSA puede ser sumamente tedioso si el valor de \(n\) es grande. En esta notas trabajamos con primos de \(3\) cifras, ya que estamos limitados por los cálculos tanto físicos como computacionales. Para que el criptosistema RSA sea realmente útil, el valor de \(n\) debe de ser muy grande, es decir que para elegir \(n\), primero tenemos que encontrar dos primos \(p\) y \(q\) grandes, que tengan alrededor de \(100\) dígitos o más, es decir que \(n\) tendría \(200\) dígitos o más.
A pesar de que ese valor de \(n\) es público, no implica que los primos relacionados sean públicos, y factorizar un número de \(200\) dígitos es una tarea que consume muchísimo tiempo.
Una vez que los valores de \(p\) y \(q\) han sido seleccionados, escogemos el exponente de cifrado \(e\), el cual debe ser elegido de tal forma que \((e,\varphi(n)) = 1\). Luego, necesitamos calcular el exponente de descifrado \(d\), el cual es calculado resolviendo la congruencia \(de\equiv 1\pmod{\varphi(n)}\). Nuevamente, la manera más fácil de calcular \(\varphi(n)\) es utilizando el Lema 7 y el Teorema 20, es decir, necesitamos saber los primos involucrados, en otras palabras, factorizar el número.
A pesar de que esto pueda cambiar con el tiempo y la tecnología, el sistema RSA es seguro en el presente. Además, si existieran técnicas de factorización o computadoras más rápidas, entonces se podría aumentar el tamaño de los factores para mantener la seguridad del sistema.
Aunque no podemos mostrar qué tanto se tardaría una computadora en factorizar un número de mas de \(100\) dígitos, podemos poner a competir dos códigos para ver cuál es más rápido encontrando el valor de \(\varphi(n)\). La diferencia entre estos dos códigos es que al primero se le proporcionaran los primos en la factorización de \(n\) y el segundo tendrá que encontrarlos por fuerza bruta. Veamos estos códigos.
Primer código.
La siguiente función recibe como argumento los primos \(p\) y \(q\) involucrados en la factorización de \(n\). Para calcular el valor de la función \(\varphi(n)\), utiliza el Teorema 20 y Lema 7.
def phi_euler_pq(p,q):
phi_n = (p-1)*(q-1)
return print(f"El valor de phi es: {phi_n}")
Ahora, vamos a medir los tiempo que tarda en calcular el valor de la función \(\varphi(n)\). Tomando los números primos \(p\) y \(q\), los cuales comenzarán teniendo \(2\) cifras, y los iremos alargando hasta llegar a \(10\) cifras.
La lista de primos es la siguiente:
lista_primos = [[71, 97], [101, 821], [5003, 8009], [10007, 15013], [100003, 150001], [1000003, 1500007], [10000019, 15000017], [100000007, 150000001], [1000000007, 1500000001]]
El siguiente código registra los tiempos de cómputo para cada pareja de primos en la lista.
import time
for primos in lista_primos:
print(f"Los primos involucrados son: {primos}")
inicio = time.time()
phi_euler_pq(primos[0],primos[1])
fin = time.time()
tiempo_total = fin - inicio
print(f"El tiempo de cómputo es: {tiempo_total} \n")
Los primos involucrados son: [71, 97]
El valor de phi es: 6720
El tiempo de cómputo es: 0.0
Los primos involucrados son: [101, 821]
El valor de phi es: 82000
El tiempo de cómputo es: 0.0
Los primos involucrados son: [5003, 8009]
El valor de phi es: 40056016
El tiempo de cómputo es: 0.0
Los primos involucrados son: [10007, 15013]
El valor de phi es: 150210072
El tiempo de cómputo es: 0.0
Los primos involucrados son: [100003, 150001]
El valor de phi es: 15000300000
El tiempo de cómputo es: 0.0
Los primos involucrados son: [1000003, 1500007]
El valor de phi es: 1500009000012
El tiempo de cómputo es: 0.0
Los primos involucrados son: [10000019, 15000017]
El valor de phi es: 150000430000288
El tiempo de cómputo es: 0.0
Los primos involucrados son: [100000007, 150000001]
El valor de phi es: 15000000900000000
El tiempo de cómputo es: 0.0
Los primos involucrados son: [1000000007, 1500000001]
El valor de phi es: 1500000009000000000
El tiempo de cómputo es: 0.0
Segundo código.
La siguiente función recibe como argumento el valor entero \(n\), lo que hace es buscar los dos números primos que están involucrados en su factorización y luego calcula el valor de la función \(\varphi(n)\).
def phi_euler_n(n):
numero = n
lst = []
for i in range(2, numero+1):
while numero % i == 0:
lst.append(i)
numero //= i
if numero == 1:
break
print(f"Los primos involucrados son: {lst}")
resultado = 1
sin_repetir = list(set(lst))
for i in sin_repetir:
resultado *= (i - 1)
return print(f"El valor de phi es: {int(resultado)}")
Antes de medir los tiempos, vamos a generar los números \(n\) multiplicando cada pareja de primos.
lista_primos = [[71, 97], [101, 821], [5003, 8009], [10007, 15013], [100003, 150001], [1000003, 1500007], [10000019, 15000017], [100000007, 150000001], [1000000007, 1500000001]]
lista_n = []
for i in lista_primos:
n = i[0]*i[1]
lista_n.append(n)
print(lista_n)
[6887, 82921, 40069027, 150235091, 15000550003, 1500011500021, 150000455000323, 15000001150000007, 1500000011500000007]
El siguiente código registra los tiempos de cómputo para cada valor de \(n\) en la lista.
import time
for n in lista_n:
inicio = time.time()
phi_euler_n(n)
fin = time.time()
tiempo_total = fin - inicio
print(f"El tiempo de cómputo es: {tiempo_total} \n")
Los primos involucrados son: [71, 97]
El valor de phi es: 6720
El tiempo de cómputo es: 0.0
Los primos involucrados son: [101, 821]
El valor de phi es: 82000
El tiempo de cómputo es: 0.000997304916381836
Los primos involucrados son: [5003, 8009]
El valor de phi es: 40056016
El tiempo de cómputo es: 0.0009980201721191406
Los primos involucrados son: [10007, 15013]
El valor de phi es: 150210072
El tiempo de cómputo es: 0.0035071372985839844
Los primos involucrados son: [100003, 150001]
El valor de phi es: 15000300000
El tiempo de cómputo es: 0.03191208839416504
Los primos involucrados son: [1000003, 1500007]
El valor de phi es: 1500009000012
El tiempo de cómputo es: 0.28051304817199707
Los primos involucrados son: [10000019, 15000017]
El valor de phi es: 150000430000288
El tiempo de cómputo es: 2.5647244453430176
Los primos involucrados son: [100000007, 150000001]
El valor de phi es: 15000000900000000
El tiempo de cómputo es: 25.018394947052002
Los primos involucrados son: [1000000007, 1500000001]
El valor de phi es: 1500000009000000000
El tiempo de cómputo es: 301.800452709198
Como podemos notar, la diferencia de la potencia de cómputo empieza a separarse cuando los primos empiezan a ser grandes. También depende de la máquina en donde se este ejecutando el código, con mejores componentes será mas rápida de hacer los cálculos.
Explicación del código#
En este capítulo usamos la librería time la cual sirve para decirnos la hora actual, es así como pudimos medir los tiempos que se tardaban en ejecutar los códigos.
La idea sería tomar la hora antes de ejecutar una función y tomar la hora después de la ejecución. Luego haciendo la resta encontramos el tiempo que se tardó en ejecutar la función. La estructura sería la siguiente.
hora_inicial = time.time()
mi_funcion(argumento)
hora final = time.time()
También usamos mas propiedades de los objetos de tipo cadena. Primero, vimos que podemos cambiar el tipo de un objeto usando la función str(), esta función se puede aplicar a diferentes objetos dentro de Python, en esta ocasión la utilizamos para convertir objetos del tipo entero a cadenas.
número = 23
texto = str(23)
En el ejemplo anterior, la variable «texto» se convierte en un objeto del tipo str. Esto hace que tengamos de resultado \('23'\), entre comillas.
Lo anterior nos lleva a ver la operación + entre cadenas. Entre los objetos de tipo str, esta operación lo que hace es juntar las cadenas o concatenarlas.
texto_1 = 'Hola'
texto_2 = ' '
texto_3 = 'Mundo'
concatenar = texto_1 + texto_2 + texto_3
En el ejemplo anterior, el valor de la variable «concatenar» es igual a la cadena \(\text{'Hola Mundo'}\). El orden de las palabras en el resultado, depende del orden en el que pongamos las variables en la concatenación.
Otra operación que podemos aplicar es la multiplicación * por un entero. A diferencia de la operación numérica, cuando la aplicamos a una cadena de texto lo que hace es repetir la cadena el número de veces que le indiquemos.
texto = 'Hola'
repetir = 4*texto
En el ejemplo anterior, el resultado de la variable «texto» sería la cadena \(\text{'HolaHolaHolaHola'}\).
Ya habíamos mencionado que las cadenas de texto también eran un objeto indexado, es decir, que a los elementos de la cadena tienen asignado un índice. Esto nos deja utilizar el slicing para seleccionar una parte específica de un texto utilizando un rango de índices.
texto = 'Hola, esta es una cadena'
fragmento = texto[0:4]
En el ejemplo anterior, el valor de la variable «fragmento» sería la cadena \(\text{'Hola'}\).
Primero, revisemos el código que nos ayuda a crear la clave pública.
def llave_publica(p,q,e):
n = p*q
phi_n = (p-1)*(q-1)
primos_relativos = algoritmo_euclides(e,phi_n)
if primos_relativos == 1:
print(f"La clave pública es: ({e},{n}).")
else:
print(f"Revisa tus valores!, el máximo común divisor de e y phi de n es : {primos_relativos}.")
Definimos una función llamada «llave_publica», la cual recibe \(3\) argumento. Los primeros dos son los primos \(p\) y \(q\). El tercer argumento es el valor de la llave de cifrado \(e\).
Luego creamos tres variables. Primero «n», que es el valor del producto \(p\) por \(q\). Luego la variable «phi_n», que toma el valor del producto \(p-1\) por \(q-1\). Por último la variable «primos_relativos», en la cual guardamos el valor del máximo común divisor entre las variables «e» y «phi_n».
def llave_publica(p,q,e):
n = p*q
phi_n = (p-1)*(q-1)
primos_relativos = algoritmo_euclides(e,phi_n)
Ahora, con un condicional
ifverificamos el valor de la variable «primos_relativos». Si el valor de la variable es \(1\), el código nos regresa la clave \((e,n)\). Si el valor de la variable es diferente de \(1\), el código nos imprime una advertencia de revisar los valores ingresados.
if primos_relativos == 1:
print(f"La clave pública es: ({e},{n}).")
else:
print(f"Revisa tus valores!, el máximo común divisor de e y phi de n es : {primos_relativos}.")
Veamos, cómo funcionan los códigos realizados en este capítulo.
Veamos cómo funciona el código para cifrar un mensaje con el algoritmo RSA.
def cifrado_rsa(texto,n ,e):
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
texto_cifrado = []
for letra in texto:
if letra in alfabeto:
indice = str(alfabeto.index(letra))
if len(indice) == 1:
indice = '0' + indice
texto_cifrado.append(indice)
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
grupos_m = [texto_cifrado[i:i+longitud_bloque] for i in range(0,len(texto_cifrado),longitud_bloque)]
lista_bloques = []
for bloque in grupos_m:
numero = "".join(bloque)
if len(numero) < 2*longitud_bloque:
numero = numero + (longitud_bloque - len(numero)//2)*"24"
c = (int(numero)**e)%n
if len(str(c)) < len(str(n)):
c = (len(str(n)) - len(str(c)))*"0" + str(c)
else:
c = str(c)
lista_bloques.append(c)
return " ".join(lista_bloques)
Definimos una función llamada «cifrado_rsa» la cual recibe como argumento \(3\) valores el primero es un mensaje en texto plano el cual debemos guardar previamente en la variable «texto», luego introducimos los valores de la clave pública \(n\) y \(e\). Además, creamos la variable «alfabeto» la cual contiene todas la letras del alfabeto y nos ayuda a generar sus respectivos índices.
def cifrado_rsa(texto,n ,e):
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
Creamos la variable «texto_cifrado» la cual es una lista vacía.
Comenzamos un cicloforel cual toma cada letra de la variable «texto». Luego revisamos con un condicionalifsi la letra está en la variable «alfabeto», si se encuentra ahí, calculamos el índice de la letra con la instrucciónstr(alfabeto.index(letra))y lo guardamos en la variable «indice». Luego, con otro condicionalifrevisamos la longitud del índice. Si el índice tiene longitud \(1\) entonces le agregamos un cero a la izquierda para que sea de longitud \(2\). Finalmente, agregamos ese valor a la lista «texto_cifrado», es decir que vamos a obtener el mensaje de texto plano convertido en números.
texto_cifrado = []
for letra in texto:
if letra in alfabeto:
indice = str(alfabeto.index(letra))
if len(indice) == 1:
indice = '0' + indice
texto_cifrado.append(indice)
Una vez obtenida la cadena de números, pasamos a calcular el tamaño de los bloques. Creamos una variable «longitud_bloque» que contiene la cadena de texto “26”. Luego, iniciamos un ciclo
whileel cual se repite hasta que se deje de cumplir la condición de que la variable «longitud_bloque» trasformada en entero deje de ser menor que «n», mientras el ciclo se siga repitiendo a la variable «longitud_bloque» se le agrega la cadena “26” lo cual va haciendo el número más grande. Como la condición se deja de cumplir cuando la variable «longitud_bloque» es más grande, necesitamos quitar la última cadena de “26” por eso es que usamos la instrucciónm[0:len(m) - 2], para obtener el valor final de «longitud_bloque» dividimos entre \(2\) la longitud.
Después, creamos la variable «grupos_m» la cual contiene listas y cada una de esas listas contiene los números de cada bloque pero separados por elementos, es decir el primer elemento se vería como \(['09','11','22']\).
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
grupos_m = [texto_cifrado[i:i+longitud_bloque] for i in range(0,len(texto_cifrado),longitud_bloque)]
Ahora lo que se quiere lograr con este bloque de código es juntar el número y convertirlo en un solo objeto, es decir, pasar de tener \(['09','11','22']\) a tener \(['091122']\).
Se crea la variable «lista_bloques» como una lista vacía. Comenzamos un cicloforque va tomando las listas de números de la variable «grupos_m», luego con la instrucción"".join(bloque)logramos juntar los valores y así obtener el número en un solo bloque. Después, con un condicionalifse verifica si la longitud del bloque es de tamaño \(2m\), si no es del tamaño deseado entonces lo completamos con la cadena de texto “24”, la cual se multiplica por un entero, logrando la longitud deseada.
lista_bloques = []
for bloque in grupos_m:
numero = "".join(bloque)
if len(numero) < 2*longitud_bloque:
numero = numero + (longitud_bloque - len(numero)//2)*"24"
Ahora, lo que hacemos es el cifrado del valor utilizando la congruencia \(C \equiv P^e \pmod{n}\), esta operación se calcula y se guarda en la variable «c».
Nuevamente con un condicionalifrevisamos si el resultado tiene la misma longitud que el entero \(n\). Si no se cumple entonces rellenamos con la cadena “0” a la izquierda del número. Si tiene la longitud deseada, pasa al condicionalelseque solo convierte el valor en cadena. El valor de «c» se va agregando a la lista «lista_bloques» la cual va a contener los bloques cifrados. Finalmente, la función nos regresa los bloques de números separados por un espacio.
c = (int(numero)**e)%n
if len(str(c)) < len(str(n)):
c = (len(str(n)) - len(str(c)))*"0" + str(c)
else:
c = str(c)
lista_bloques.append(c)
return " ".join(lista_bloques)
Ahora, veamos el código para descifrar mensajes.
def descifrado_rsa_con_pq(texto_cifrado,e,p,q):
n = p*q
phi_n = (p-1)*(q-1)
d = congr_lin_sol(e,1,phi_n)
bloques_p = texto_cifrado.split()
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
texto_descifrado = []
for p in bloques_p:
c = (int(p)**d)%n
if len(str(c)) < 2*longitud_bloque:
c = (2*longitud_bloque - len(str(c)))*"0" + str(c)
else:
c = str(c)
texto_descifrado.append(c)
letras_descifrado = []
for palabra in texto_descifrado:
for i in range(0,len(palabra),2):
letra = palabra[i] + palabra[i + 1]
letra = int(letra)
letras_descifrado.append(letra)
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
texto_plano = ''
for i in letras_descifrado:
letra = alfabeto[i]
letra = str(letra)
texto_plano += letra
return texto_plano
Definimos una función llamada «descifrado_rsa_con_pq» la cual recibe como argumentos, un texto cifrado con el algoritmo RSA que se guarda previamente en la variable «texto_cifrado», luego el valor de «e» que es la llave de cifrado, y finalmente los dos números primos \(p\) y \(q\). Luego creamos \(4\) variables, «n» que toma el valor de multiplicar los primos \(p\) y \(q\), «phi_n» en donde se calcula el valor de la función phi de Euler con la fórmula \((p-1)(q-1)\), luego la variable «d» en la cual se calcula el inverso de \(e\) módulo \(\varphi(n)\) y la variable «bloques_p» la cual convierte la cadena de texto cifrado en una lista que contiene como elementos los bloques de números.
def descifrado_rsa_con_pq(texto_cifrado,e,p,q):
n = p*q
phi_n = (p-1)*(q-1)
d = congr_lin_sol(e,1,phi_n)
bloques_p = texto_cifrado.split()
Volvemos a utilizar el algoritmo realizado en el código para cifrar. Este nos ayuda para saber de que longitud son los bloques en el texto descifrado.
longitud_bloque = "26"
while int(longitud_bloque) < n:
longitud_bloque = longitud_bloque + "26"
longitud_bloque = longitud_bloque[0:len(longitud_bloque) - 2]
longitud_bloque = len(longitud_bloque)//2
Creamos la variable «texto_descifrado» que es una lista vacía.
Empezamos un cicloforel cual va tomando los bloques de números de la lista «bloques_p», luego en la variable «c» calculamos el valor descifrado con la congruencia \(P\equiv C^d\pmod{n}\), con un condicionalifrevisamos si el resultado tiene la misma longitud que los bloques originales. Si no es así, se agregan ceros a la izquierda del bloque, si ya tienen la longitud deseada pasan al condicionalelseel cual convierte el valor en una cadena. Finalmente, se agrega el valor a la lista «texto_descifrado».
texto_descifrado = []
for p in bloques_p:
c = (int(p)**d)%n
if len(str(c)) < 2*longitud_bloque:
c = (2*longitud_bloque - len(str(c)))*"0" + str(c)
else:
c = str(c)
texto_descifrado.append(c)
Ahora, lo que queremos es separar los bloques y partirlos en bloques de tamaño \(2\). Entonces creamos la variable «letras_descifrado» la cual es una lista vacía. Empezamos un ciclo
for, el cual toma los bloques de la lista «texto_descifrado» y lo que hace es partir ese bloque en pequeños bloques de tamaño \(2\), esto lo hacemos porque cada dos números corresponden a una letra en nuestro alfabeto, esos bloques de tamaño \(2\) se van guardando en la lista «letras_descifrado».
letras_descifrado = []
for palabra in texto_descifrado:
for i in range(0,len(palabra),2):
letra = palabra[i] + palabra[i + 1]
letra = int(letra)
letras_descifrado.append(letra)
Finalmente, lo que queremos es regresar los números a su letra correspondiente en el alfabeto. Entonces, creamos la variable «alfabeto» la cual contiene el abecedario completo y nos sirve para obtener los índices de cada letra. Creamos la variable «texto_plano» la cual es una cadena vacía. Luego comenzamos un ciclo
forel cual va tomando los bloques de tamaño \(2\) y los va cambiando a su correspondiente letra en el alfabeto, estas letras se van guardando en la variable «texto_plano» usando la concatenación. La variable «texto_plano» va a contener nuestro mensaje pero con todas las letras juntas y es lo que nos regresa como valor la función.
alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
texto_plano = ''
for i in letras_descifrado:
letra = alfabeto[i]
letra = str(letra)
texto_plano += letra
return texto_plano
Ejercicios de práctica#
Sea \(n\) un entero que es el producto de dos números primos. Demuestra que los divisores primos de \(n\) son las raíces de la ecuación cuadrática \(x^2 - (n + 1 - \varphi(n))x + n = 0\).
Encuentra los factores primos de \(n\) sabiendo que \(n = 221\) y \(\varphi(n) = 192\).
Encuentra los factores primos de \(n\) sabiendo que \(n = 6059\) y \(\varphi(n) = 5904\).
Descifra los siguientes mensajes que fueron cifrados con el algoritmo RSA con la clave de cifrado \((e,n) = (17,2867)\) Y \(\varphi(n) = 2760\).
\(2229\ 1749\ 2229\ 1468\ 1194\ 2359\ 2577\ 2577\ 0187\ 2673\ 0592\ 2509\ 2399\ 1944\).
Descifra los siguientes mensajes que fueron cifrados con el algoritmo RSA con la clave de cifrado \((e,n) = (17,3953)\) Y \(\varphi(n) = 3828\).
\(0734\ 2121\ 0194\ 3559\ 1572\ 1221\ 2043\ 1144\ 3559\ 3302\ 3519\ 3721\ 2235\ 2832\ 2386\).
Intenta hacer criptoanálisis.