algortimo RSA en phyton

Ya que se estaba discutiendo el asunto de algoritmos asimetricos decidí esta vez hacer un codigo y epxlicarlo un poco

Para los que no sepan RSA es un algoritmo de cifrado asimetrico (el que usa http para compartir las contraseñas) el cual se basa en la creacion de 2 claves, una privada y otra publica, la llave publica cifra, la privada descifra...

esto es creado por una serie de problemas:
1. la dificultad de manejar multiples contraseñas para comunicarse con mutiples sujetos
2. la complicacion de compartir contraseñas sobre internet sin que un hombre en el medio se entere

con este metodo uno comparte su llave publica para que se comuniquen con uno

la llave publica solo cifra, para descifrar se necesita la llave privada

si quieren más detalles todo está en wikipedia

para hacer el proceso se necesitan 2 factores "p" y "q" ambos numeros primos diferentes y de una cantidad de bites similar por seguridad (actualmente se usan numeros de unas 150 cifras de largo)

de aquí sacamos 2 factores más
"n" que es la multiplicacion de "p" y "q"
"phi" que será el resultado de la multiplicacion de la funcion phi de "p" y "q", que en resumen al ser ambos primos serán (p-1) y (q-1)

de todo esto necesitamos calcular el factor "e" es un factor tal que 1 < e < phi

con "e" procedemos a calcular "d" siendo este un factor que satisfaga la ecuacion

Código:

(d*e)%phi == 1

"e" es el factor que armará la clave publica y "d" la clave privada

el cifrado se hace bajo la siguiente formula

y el descifrado con la siguiente

esto funciona porque (para quien sepa matematica)

bueno, sin dar más vueltas aquí el codigo con verificaciones

Código

def bidimArray(a,b): #crear array bidimensional
	return [[0 for x in range(b)] for x in range(a)] 
 
def esPrimo(n): #calcula si es primo
    if n <= 3:
        return n >= 2
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(n ** 0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True
 
def nvoPrimo(n): # conseguir el n-avo primo
	total = 0
	contador = 1
	while total < n:
		contador+=1
		if esPrimo(contador):
			total+=1
	return contador
 
global_factores = [] #buffer de factores
 
def obtenerFactores(numero): #obtiene los factores de un numero dado
	for i in global_factores: #si esta en buffer los saca de ahi
		if i[0] == numero:
			return i[1]
	factores = []
	buff = 1
	while buff/2 < numero:
		buff+=1
		if numero % buff == 0:
			factores.append(buff)
	#print global_factores #debug
	global_factores.append([numero,factores]) #los mete en el buffer
	return factores
 
def esCoprimo(a,b): #son coprimos?
	f_a = obtenerFactores(a)
	f_b = obtenerFactores(b)
	comunes = len(frozenset(f_a).intersection(f_b)) #intercepta
	#print comunes #debug
	if comunes > 0: return False #si hay coincidencia, no son coprimos
	return True
 
def calcular_e(phi,n, inicio):
	buff = 0 + inicio
	e = 0
	if buff < 1: buff = 1
	while buff < phi:
		buff+=1
		#print "{} y {}".format(buff, n) #debug
		if esCoprimo(buff, n) and esCoprimo(buff, phi) : 
			e = buff
			break
	return e
 
 
def calcular_d(e,phi,n):
	d = 0
	buff = 0
	for contador in range(n):
		buff = (contador * e)%phi
		#print "({} * {})%{} -> {}".format(contador,e,phi,buff) #debug
		if buff == 1:
			d = contador
			break
	return d
 
def cifrado(m,e,n):
	return pow(m,e,n) # m^e%n
 
def descifrado(c,d,n):
	return pow(c,d,n) # c^d%n
 
def aplicarRSA(p,q,m):
	if not esPrimo(p):
		print "p debe ser primo"
		exit()
 
	if not esPrimo(q):
		print "q debe ser primo"
		exit()
 
 
	n = p * q
	if m >= n:
		print "mensaje muy grande, p y q deben ser mayores"
		print "maximo mensaje permitido {}".format(n-1)
		exit()
	phi = (p-1)*(q-1)
	e = calcular_e(phi,n,0)
	d = calcular_d(e,phi,n)
	c = 0
	print "p = {} y q = {}".format(p,q)
	print "n = {} y phi(n) = {}".format(n,phi)
	print "Llave publica es ({},{})".format(e,n)
	print "Llave privada es ({},{})".format(d,n)
	c = cifrado(m,e,n)
	print "cifrado de {} resulta {}".format(m,c)
	m = descifrado(c,d,n)
	print "descifrado de {} resulta {}".format(c,m)
 
aplicarRSA(nvoPrimo(20),nvoPrimo(32),100)

explico un poco las funciones

Código

bidimArray(a,b)

simplemente genera un array bidimensional de el largo indicado

Código

esPrimo(n)

confirma que un numero pasado sea primo bajo un metodo rapido

Código

nvoPrimo(n)

genera numeros primos, genera el primo de la n-ava posicion

Código

obtenerFactores(numero)

saca los multiplos de un numero

Código

esCoprimo(a,b)

confirma que los numeros sean coprimos (que no tengan factores en común)

las otras son autoexplicativas

al final

Código

aplicarRSA(nvoPrimo(20),nvoPrimo(32),100)

aplica RSA con el 20-avo primo, y 32-avo primo como p y q, y el mensaje es 100... pueden colocar lo que quieran y usar primos directamente...

si... el codigo solo lo hace con calculos numericos y puede tardar algunos segundos en finalizar si los nvo primos están sobre 1000, el mensaje debe ser menor a "n"

si cualquier duda o correción pueden publicarla aquí