Práctica del RSA¶
Ahora mostramos un ejemplo explícito del uso del RSA con una historia entre dos amigos, Andrés y Sofía.
Digamos que Andrés tienen algo muy importante que decirle a su amiga Sofía. Para que Andrés le pueda enviar el mensaje secreto, Sofía implementa un sistema de RSA. Lo primero que hace entonces es seleccionar dos números primos \(P\) y \(Q\) muy grandes.
#En este algoritmo seleccionamos dos primos P y Q al azar entre un rango de números a y b
import random
def isPrime(n):
k=0
for i in range(2,n):
if n%i==0:
k=i
break
if k==0:
return(True)
else:
return(False)
a=1000
b=2000
P = random.randint(a,b)
while not isPrime(P):
P=random.randint(a,b)
print("P =",P)
Q = random.randint(a,b)
while not isPrime(Q):
Q=random.randint(a,b)
print("Q =",Q)
P = 1753
Q = 1021
Enseguida, Sofía calcula \(N=P\cdot Q\) y elije un exponente \(e\) que tenga un inverso multiplicativo módulo \(\varphi(N)\), digamos \(d\). Este número \(d\) es entonces la “clave privada” de Sofía. Ahora que Sofía tiene su clave privada \(d\), está lista para publicar los números \(N\) y \(e\) que son la “clave pública” para que Andrés pueda encriptar su mensaje. (El siguiente algorítmo elige un \(e\) al azar y trata de calcular su inverso multiplicativo \(d\) módulo \(\varphi(n)\). Si lanza error es porque \(e\) no tiene inverso y por lo tanto debería volverse a correr el código hasta encontrar un \(e\) que tenga inverso multiplicativo módulo \(\varphi(n)\)).
#Este algoritmo elije un número e al azar entre un rango de números alpha y beta.
#Luego calcula N=P*Q y el inverso multiplicadivo d de e módulo phi(N).
alpha=10
beta=50
e = random.randint(alpha,beta)
N = P*Q
def gcd(v1,v2):
if(v2==0):
return v1
else:
return gcd(v2,v1%v2)
def phi(n):
k=0
for i in range(1,n+1):
if gcd(n,i)==1:
k=k+1
return k
phiN=(P-1)*(Q-1)
exp=(phi(phiN))-1
D=e**exp
d=D%phiN
while not (e*d)%phiN==1:
e = random.randint(alpha,beta)
D=e**exp
d=D%phiN
print("La clave privada de sofía es el número d =", d)
print("La clave pública que publica Sofía es el par (N,e) =","(",N,",",e,")")
La clave privada de sofía es el número d = 862709
La clave pública que publica Sofía es el par (N,e) = ( 1789813 , 29 )
Con esta información, Andrés codifica el mensaje que le quiere enviar a Sofía. En este caso, el mensaje que le quiere enviar es “te amo”. Supongamos que Andrés y Sofía ya habían hablado previamente sobre su relación y que Sofía había decidido darle una oportunidad a Andrés para que le dijera lo que realmente sentía. Para esto, Sofía le dio entonces un tiempo Andrés para que pensara y le dio la siguiente lista con códigos para cuando Andrés quisiera responderle: 1=si, 2=no, 3=te, 4=quiero, 5=amo, 6=ver. El mensaje de Andrés codificado con esta lista sería entonces \(M=35\). Así, Andrés procede a encriptar su mensaje con ayuda de la clave pública de Sofía \((N,e)\) efectuando la siguiente operación \(C=M^e\)(mod \(N\)) y publica su mensaje encriptado \(C\). (El lector también puede escoger un mensaje diferente, codificarlo con la lista dada y pasárselo al siguiente método. Lo único que tiene que verificar es que su mensaje no sea mayor que \(N\) y que sea distinto a los dos primos \(P\) y \(Q\))
#En este método calculamos el mensaje público encriptado de Andrés.
M=int(input("El mensaje de Andrés para Sofía es (luego de insertar el mensaje oprima ENTER): "))
exp=M**e
C=exp%N
print("C =",C)
El mensaje de Andrés para Sofía es (luego de insertar el mensaje oprima ENTER): 34657
C = 1271845
Finalmente, Sofía recibe el mensaje encriptado de Andrés \(C\) y obtiene el mensaje descifrado con ayuda de su clave privada \(d\) calculando \(MD=C^d \mod N\)
#En este método desciframos el mensaje encriptado de Andrés
exp=C**d
m=exp%N
print("MD =",m)
MD = 34657
De esta manera, Sofía se entera de que Andrés en efecto sí la ama y sabe que nadie más, además de ella y Andrés, lo sabe. Así, Sofía y Andrés pudieron comunicarse de manera segura y Andrés pudo decirle lo que realmente sentía a Sofía.