elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Scripting
| | |-+  algortimo RSA en phyton
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: algortimo RSA en phyton  (Leído 2,313 veces)
engel lex
CoAdmin
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
algortimo RSA en phyton
« en: 6 Enero 2015, 00:41 »

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
  1. def bidimArray(a,b): #crear array bidimensional
  2. return [[0 for x in range(b)] for x in range(a)]
  3.  
  4. def esPrimo(n): #calcula si es primo
  5.    if n <= 3:
  6.        return n >= 2
  7.    if n % 2 == 0 or n % 3 == 0:
  8.        return False
  9.    for i in range(5, int(n ** 0.5) + 1, 6):
  10.        if n % i == 0 or n % (i + 2) == 0:
  11.            return False
  12.    return True
  13.  
  14. def nvoPrimo(n): # conseguir el n-avo primo
  15. total = 0
  16. contador = 1
  17. while total < n:
  18. contador+=1
  19. if esPrimo(contador):
  20. total+=1
  21. return contador
  22.  
  23. global_factores = [] #buffer de factores
  24.  
  25. def obtenerFactores(numero): #obtiene los factores de un numero dado
  26. for i in global_factores: #si esta en buffer los saca de ahi
  27. if i[0] == numero:
  28. return i[1]
  29. factores = []
  30. buff = 1
  31. while buff/2 < numero:
  32. buff+=1
  33. if numero % buff == 0:
  34. factores.append(buff)
  35. #print global_factores #debug
  36. global_factores.append([numero,factores]) #los mete en el buffer
  37. return factores
  38.  
  39. def esCoprimo(a,b): #son coprimos?
  40. f_a = obtenerFactores(a)
  41. f_b = obtenerFactores(b)
  42. comunes = len(frozenset(f_a).intersection(f_b)) #intercepta
  43. #print comunes #debug
  44. if comunes > 0: return False #si hay coincidencia, no son coprimos
  45. return True
  46.  
  47. def calcular_e(phi,n, inicio):
  48. buff = 0 + inicio
  49. e = 0
  50. if buff < 1: buff = 1
  51. while buff < phi:
  52. buff+=1
  53. #print "{} y {}".format(buff, n) #debug
  54. if esCoprimo(buff, n) and esCoprimo(buff, phi) :
  55. e = buff
  56. break
  57. return e
  58.  
  59.  
  60. def calcular_d(e,phi,n):
  61. d = 0
  62. buff = 0
  63. for contador in range(n):
  64. buff = (contador * e)%phi
  65. #print "({} * {})%{} -> {}".format(contador,e,phi,buff) #debug
  66. if buff == 1:
  67. d = contador
  68. break
  69. return d
  70.  
  71. def cifrado(m,e,n):
  72. return pow(m,e,n) # m^e%n
  73.  
  74. def descifrado(c,d,n):
  75. return pow(c,d,n) # c^d%n
  76.  
  77. def aplicarRSA(p,q,m):
  78. if not esPrimo(p):
  79. print "p debe ser primo"
  80. exit()
  81.  
  82. if not esPrimo(q):
  83. print "q debe ser primo"
  84. exit()
  85.  
  86.  
  87. n = p * q
  88. if m >= n:
  89. print "mensaje muy grande, p y q deben ser mayores"
  90. print "maximo mensaje permitido {}".format(n-1)
  91. exit()
  92. phi = (p-1)*(q-1)
  93. e = calcular_e(phi,n,0)
  94. d = calcular_d(e,phi,n)
  95. c = 0
  96. print "p = {} y q = {}".format(p,q)
  97. print "n = {} y phi(n) = {}".format(n,phi)
  98. print "Llave publica es ({},{})".format(e,n)
  99. print "Llave privada es ({},{})".format(d,n)
  100. c = cifrado(m,e,n)
  101. print "cifrado de {} resulta {}".format(m,c)
  102. m = descifrado(c,d,n)
  103. print "descifrado de {} resulta {}".format(c,m)
  104.  
  105. aplicarRSA(nvoPrimo(20),nvoPrimo(32),100)

explico un poco las funciones

Código
  1. bidimArray(a,b)
simplemente genera un array bidimensional de el largo indicado

Código
  1. esPrimo(n)
confirma que un numero pasado sea primo bajo un metodo rapido

Código
  1. nvoPrimo(n)
genera numeros primos, genera el primo de la n-ava posicion

Código
  1. obtenerFactores(numero)
saca los multiplos de un numero

Código
  1. esCoprimo(a,b)
confirma que los numeros sean coprimos (que no tengan factores en común)

las otras son autoexplicativas

al final
Código
  1. 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í


En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
vk496

Desconectado Desconectado

Mensajes: 205


Ver Perfil
Re: algortimo RSA en phyton
« Respuesta #1 en: 6 Enero 2015, 00:47 »

Gracias por compartir.

Salu2



Solo una duda. Cito textual de Wikipedia (RSA):
Citar
Se debe observar que la seguridad de los padding-schemes como RSA-PSS son esenciales tanto para la seguridad de la firma como para el cifrado de mensajes, y que nunca se debería usar la misma clave para propósitos de cifrado y de autentificación.

Alguien podría explicarlo? Por que no recomiendas que utilice la misma clave para ambas situaciones?

Salu2



[MOD]: Porfavor, no hagas doble post.


« Última modificación: 6 Enero 2015, 01:47 por Eleкtro » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Phyton
Scripting
Error 404 2 3,010 Último mensaje 16 Marzo 2006, 01:33
por JuszR
ALGORTIMO D ROUND ROBIN
Ejercicios
diegoco 2 5,862 Último mensaje 14 Junio 2006, 00:58
por Ragnarok
Necesito desarrollar algortimo para a partir de datos sensados validarlos...
Programación C/C++
Ronny Diaz Lopez 1 1,210 Último mensaje 23 Mayo 2011, 18:05
por ShotgunLogic
Algortimo WLAN_XXXX y WLAN_XX
Hacking Wireless
dimitrix 6 3,609 Último mensaje 16 Octubre 2011, 22:31
por _pinty_
Libreria para el uso del algortimo ECDHE (criptografia) en python3
Criptografía
clay2332xd 2 884 Último mensaje 4 Enero 2020, 16:55
por engel lex
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines