Metodo RSA Phyton

Vista previa del material en texto

Asignatura: Controles Criptográficos y de Seguridad 
 
Entregable Final 02/07/2022 
 
 
 
 
índice 
 
➢Resumen de los modelos y descripción de variables 
 
➢ Aplicaciones de los modelos 
 
➢ Código y/o fórmulas de la automatización de los modelos 
 
➢ Manual de uso de la automatización 
 
➢ Conclusiones 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
introducción 
En 1977, un año después de la introducción de la criptografía de clave publica por Diffie y 
Hellman, se desarrolló un algoritmo conocido como el algoritmo RSA. El nombre se debe a 
las letras iniciales de los apellidos de los investigadores: Ron Rivest, Adi Shamir y Leonard 
Adleman. En el algoritmo RSA se generan un par de claves, donde una de ellas es revelada 
al mundo exterior (clave pública) y la otra se mantiene en secreto para el usuario (clave 
privada). Para generar las claves el algoritmo RSA utiliza un concepto de la teoría de 
números que es llamada función de una vía. Esta función es fácil de evaluar, pero su función 
inversa es muy difícil. Esta propiedad es aprovechada para generar una clave privada 
conociendo la clave pública del usuario y, de ese modo, el mensaje permanece en secreto. 
(S. Azad, 2015) 
 
RSA 
Se asume que dos personas, digamos Yarett y Luis, quieren intercambiar mensajes secretos 
entre ellos usando criptografía de clave asimétrica, especialmente el algoritmo RSA. Ellos 
primero generan sus claves y publican su clave publica de manera que la otra parte pueda 
tener acceso a esta. Las notaciones para la clave pública y clave privada de Yarett son PUA y 
PRA, respectivamente. Análogamente, para PUB y PRB. Cada uno de los participantes 
mantiene su clave privada en secreto. cuando Yarett quiere enviar un mensaje a Luis, ella 
encripta el mensaje usando PUB, a la cual ella puede acceder. Para cualquier mensaje, M, 
Yarett genera un texto cifrado(ciphertext), C, de la siguiente manera: 
C = PUB(M). 
Después de recibir C, Luis puede desencriptar el mensaje empleando su clave privada, PRB. 
Esto se puede expresar formalmente como: 
M = PRB(C). 
Alguien, que no sea Luis ni Yarett, que intercepta C no será capaz de reproducir M incluso 
teniendo acceso a PUB pues: 
1. En criptografía de clave asimétrica es imposible generar una clave cuando no 
sé tiene acceso a la otra clave. 
2. Un mensaje que es encriptado mediante una clave no es posible desencriptar 
utilizando una clave similar. 
3. La clave pública y privada para cualquier participante están emparejados y 
son inversas una de la otra, es decir, 
M = PRB(PUB(M)) 
M = PUB(PRB(M)) 
Consecuentemente, un mensaje que es encriptado usando la clave pública puede solo ser 
desencriptado con su pertinente clave privada. 
Un poco de teoría de números 
Dos números enteros a y b se dice que son números primos relativos si no tienen ningún 
factor primo en común. Por ejemplo: 6 y 35 son primos relativos, pero 6 y 27 no son primos 
relativos. También se dice que a y b son primos relativos ⇐⇒ mcd(a,b) = 1. 
Función ϕ de Euler. Si n es un número entero positivo, ϕ(n) se define como la cantidad de 
enteros positivos menores o iguales a n y que además son primos relativos con n. Por 
ejemplo, ϕ(5) = 4 y ϕ(6) = 2. Para un número primo p se cumple ϕ(p) = p−1. Si p y q son 
primos relativos, entonces ϕ(pq) = ϕ(p)ϕ(q) = n−(p+q)+1. Por ejemplo, ϕ(30) = ϕ(5)ϕ(6) = 
30 − (5 + 6) + 1. 
Teorema de Euler-Fermat. Si a y n son primos relativos, entonces 
 aϕ(n) = 1(modd n) 
. 
 El algoritmo RSA 
El algoritmo RSA comprende tres pasos: 
1. Generación de clave 
2. Encriptación 
3. Decriptacion 
 Generación de clave 
El algoritmo RSA genera un par de claves. Estas claves son usualmente generados 
empleando números primos grandes. El algoritmo para la generación de claves es el 
siguiente: 
Paso 1 Elegir, de manera aleatoria, dos primos grandes p y q tal que p 6= q. 
Paso 2 Calcular n tal que n = p × q. 
Paso 3 Calcular ϕ(n) = ϕ(p) × ϕ(q) = (p − 1) × (p − 1). 
Paso 4 Seleccionar un entero e tal que 1 < e < ϕ(n) y mcd(e,ϕ(n)) = 1, donde e y ϕ(n) son 
primos relativos. 
Paso 5 Calcular d como el inverso multiplicativo de e( mod (ϕ(n)), es decir, de = 1 mod ϕ(n). 
Paso 6 Publicar El par PU = (e,n) como la clave pública del participante. 
Paso 6 Mantener el par PE = (d,n) tan secreto como la clave privada del participante. 
 Encriptación 
Alguien que desee mandar un mensaje puede utilizar la clave pública (e,n). En el ejemplo 
previo, cuando Yarett desea enviar un mensaje a Luis, ella puede ahora encriptar el mensaje 
M de la siguiente manera: 
 C = Me(mod n) 
Yarett manda el texto cifrado, C, a Luis. 
 Decriptacion 
Después de recibir C de Yarett, Luis ahora puede desencriptar el mensaje utilizando la clave 
privada relativa. El puede obtener´ M usando la siguiente expresión: 
 M = Cd(mod n) 
Desde que nadie más tiene la clave privada de Luis, nadie más que Luis puede ser capaz de 
desencriptar el mensaje. 
 
Aplicaciones del método RSA 
La aplicación del método rsa es para poder proteger información fue muy diversa, ya que 
en su tiempo fue un método muy aplicado y así se podía proteger la información de manera 
segura, el método era solido y fue muy usado en su momento. En la actualidad sigue 
sirviendo pero ya no es tan seguro dado que puede ser ya descifrado por el poder de la 
tecnología actual. 
 
A continuación, se mostrará el programa de automatización del método con las formulas 
usadas y ejemplos de como poder hacer el método. El programa está en Python y muestra 
de cierta manera lo aprendido en clase de manera matemática. 
 
 
 
 
 
 
Primero nos pide que elijamos los valores para p y q para esto se genera una lista de números 
primos para que se puedan elegir 
 
 
Posteriormente se elige el numero 
 
 
En caso de que no escojas un numero primo te lo dirá y tendrás que escoger de nuevo con la 
función 
 
 
Como escogí un 4 y no es primo, pide que escoja un numero diferente, sugeridos en la lista 
 
 
De los cuales yo escogí 7 y 5 
 
 
 
Ya que los valores están guardados en sus respectivas variables el programa hace el cálculo de ( n ) 
 
 
Después muestra el cálculo de ( ø ) 
 
 
 
 
 
Por consiguiente, calculamos (e) 
 
 
 
Después no arroja las opciones posibles para (e) 
 
 
 
 
 
En este caso yo seleccione el 5 para poder calcular la d 
 
 
 
Finalmente se crea la llave 
 
 
 
 
 
 
Después nos pedirá que pongamos el mensaje que queremos encriptar esto fue logrado con las 
siguientes funciones 
 
 
 
 nos pedirá que coloquemos el mensaje a descifrar 
 
 
 
 
 
En este caso yo escogí el nombre del profesor Joan y nos cifra el mensaje 
 
 
 
Por último se puede comprobar que el mensaje cifrado con el método RSA 
 
 
Al hacer la prueba de poner diferentes números nos arroja un mensaje erroneo para comprobar 
que el sistema funciona 
 
 
 
 
Se colocan los números correctos 4 14 0 13 Y nos arroja mensaje cifrado original 
 
 
 
 
Código del programa 
def verifica_primo(n): 
 c=0 
 x=2 
 if n>=2: 
 while x<=n/2: 
 if n%x==0: 
 c=c+1 
 x=x+1 
 else: 
 x=x+1 
 if c==0: 
 return True 
 else: 
 return False 
 else: 
 return False 
def genera_primos(n): 
 lp=[] 
 x=2 
 while n!=0: 
 if verifica_primo(x)==True: 
 lp.append(x) 
 x=x+1 
 n=n-1 
 else: 
 x=x+1 
 return lp 
def pyq(): 
 
 p=int(input("\tValor de (p)=")) 
 while verifica_primo(p)==False: 
 print("\t(p) tiene que ser un numero primo !!!") 
 p=int(input("\tValor de (p)=")) 
 q=int(input("\tValor de (q)=")) 
 while verifica_primo(q)==False or q==p: 
 print("\t(q) tiene que ser un numero primo diferente de (p) !!!") 
 q=int(input("\tValor de (q)=")) 
 lpq=[p,q] 
 return lpq 
 
def calculae(ø): 
 e=2 
 le=[] 
 while e>1 and e<ø : 
 if mcd(e,ø)==1: 
 le.append(e) 
 e=e+1 
 else: 
 e=e+1 
 print("\nVALORES PARA (e)="+str(le))e=int(input("\n\tValor de (e)=")) 
 while mcd(e,ø)!=1: 
 print("\n\tEliga un valor de la lista !!!") 
 e=int(input("\n\tValor de (e)=")) 
 return e 
 
def mcd(e,ø): 
 m=ø%e 
 while m!=0: 
 ø=e 
 e=m 
 m=ø%e 
 return e 
 
def congruente(e,ø): 
 k=1 
 m=(1+(k)*(ø))%(e) 
 while m!=0: 
 k=k+1 
 m=(1+(k)*(ø))%(e) 
 d=int((1+(k)*(ø))/(e)) 
 return d 
 
def cifrarmensaje(msj,key): 
 msj=msj.upper() 
 lm=msj.split(" ") 
 cmc="" 
 lmc=[] 
 for i in lm: 
 pal=cifrarpalabra(i,key) 
 lmc.append(pal) 
 for j in lmc: 
 cmc=cmc+str(j)+" " 
 return cmc 
 
def cifrarpalabra(m,k): 
 lpc=[] 
 lp=[] 
 n,e=k 
 cpc="" 
 for i in m: 
 x=buscarpos(i) 
 lp.append(x) 
 for j in lp: 
 c=(j**e)%n 
 lpc.append(c) 
 for k in lpc: 
 cpc=cpc+str(k)+" " 
 return cpc 
 
 
def buscarpos(x): 
 alf="ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
 c=0 
 for i in alf: 
 if x==i: 
 return c 
 else: 
 c=c+1 
 
def descifrarmensaje(msj,key): 
 msj=msj.upper() 
 lm=msj.split(" ") 
 cmc="" 
 lmc=[] 
 for i in lm: 
 pal=descifrarnumero(i,key) 
 lmc.append(pal) 
 for j in lmc: 
 cmc=cmc+str(j)+" " 
 return cmc 
 
def descifrarnumero(m,k): 
 lnc=[] 
 ln=[] 
 n,d=k 
 cnc="" 
 men=m.split(" ") 
 for i in men: 
 x=int(i) 
 ln.append(x) 
 for j in ln: 
 m=(j**d)%n 
 lnc.append(m) 
 for k in lnc: 
 l=buscarlet(k) 
 cnc=cnc+str(l) 
 return cnc 
 
def buscarlet(x): 
 alf="ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
 c=0 
 for i in alf: 
 if x==c: 
 return i 
 else: 
 c=c+1 
 
 
print("\t\t\t\t//////////////// METODO DE CIFRADO (RSA) ///////////////////////") 
 
print("\n#1 ELEGIMOS VALORES DE NUMEROS PRIMOS PARA (p) y (q) ") 
lista_primos=genera_primos(50) 
print("\nLISTA DE NUMEROS PRIMOS ="+str(lista_primos)+"\n") 
p,q=pyq() 
print("\t(p)="+str(p)+"\n\t(q)="+str(q)) 
 
print("\n#2 CALCULAMOS EL VALOR DE (n) ") 
n=p*q 
print("\t(n)=(p)*(q)") 
print("\t(n)=("+str(p)+")*("+str(q)+")") 
print("\t(n)="+str(n)) 
 
print("\n#3 CALCULAMOS (ø) ") 
ø=(p-1)*(q-1) 
print("\t(ø)=(p-1)*(q-1)") 
print("\t(ø)=("+str(p)+"-1)*("+str(q)+"-1)") 
print("\t(ø)="+str(ø)) 
 
print("\n#4 CALCULAMOS (e) ") 
print("\t(e)/ 1<e<ø and mcd(e,ø)==1") 
e=calculae(ø) 
print("\t(e)="+str(e)) 
 
print("\n#5 CALCULAMOS (d) ") 
print("\t(d)/ (d)*(e) =sea congruente a= (1)*(mod ø) ") 
d=congruente(e,ø) 
print("\t(d)="+str(d)) 
 
print("\n#6 FINALMENTE OBTENEMOS LA LLAVE PUBLICA Y PRIVADA ") 
key_public=[n,e] 
key_private=[n,d] 
print("\n\tLLAVE PUBLICA="+str(key_public)+"\n\tLLAVE PRIVADA="+str(key_private)) 
 
print("\n#7 AHORA PODEMOS CIFRAR MENSAJES CON EL METODO (RSA)") 
mensaje=input("\n\tMensaje : ") 
mensaje_cifrado=cifrarmensaje(mensaje,key_public) 
print("\tMensaje Cifrado : "+str(mensaje_cifrado)) 
 
print("\n#8 AHORA PODEMOS DESCIFRAR MENSAJES CON EL METODO (RSA)") 
mensaje_cifrado=input("\n\tMensaje Cifrado : ") 
mensaje_descifrado=descifrarmensaje(mensaje_cifrado,key_private) 
print("\tMensaje Descifrado : "+str(mensaje_descifrado)) 
 
 
 
Conclusiones 
En mi opinión el método RSA me pareció muy interesante ya que tiene una llave, ya que 
sin ella es complicado lograr descifrar el mensaje , si hay maneras ya en la actualidad pero 
no es tan sencillo, se requiere de cierto conocimiento ya que al principio se me hizo confuso 
pero después ya al intentar razonar como hacer el programa lo comprendí mejor. Dado el 
casi mi sistema de automatización fue seguir los pasos del método para cifrar y demostrar 
que de cierta manera hubo una comprensión del algoritmo RSA. La materia fue muy 
interesante ya que se necesita de cierto conocimiento matemático y muestra como al jugar 
con los números se pueden logra cosas impresionantes 
 
 
 
 
 
 
 
 
 
 
 
 
 
Screen shoot 
 
 
Bibliografía 
S. Azad, A.-S. K. (2015). Criptografia practica. boca raton. 
 
W. Diffie and M. E. Hellman (1976) New Directions in Cryptography, IEEE Transactions on 
Information Theory, Vol. IT-22, no 6, 644-654. 
R.L. Rivest, A. Shamir, and L. Adleman (1978) A Method for Obtaining Digital signatures and Public-
Key Cryptosystems, Programming Techniques, Vol. 21, no.2, 120-126.