UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
1
Implementaci´on del Algoritmo Criptogr´afico RSA en Lenguaje Python Luis Alejandro Sosa B.1 - Sandra Ximena Rengifo A.1 - Esteban Andr´es Guerrero N.1 Curso de Criptografia Especializaci´on en Proyectos Inform´aticos Facultad de Ingenier´ıa Universidad Distrital Fancisco Jose de Caldas Bogota D.C. , Colombia
[email protected] -
[email protected] - esteban
[email protected]
˜ e Abstract—El presente articulo detalla el an´alisis, diseno implementacion del algoritmo RSA sobre lenguaje python Palabras claves—Cifrado, RSA, algoritmo de Euclides, Euler, primos,coprimos, modulo, clave publica, clave privada. ´ I. I NTRODUCCI ON Seg´un el Diccionario de la Real Academia, la palabra Criptograf´ıa proviene del griego y su definicion es: ”Arte de escribir con clave secreta o de un modo enigm´atico”. Obviamente la Criptograf´ıa hace a˜nos que dej´o de ser un arte para convertirse en una t´ecnica, o m´as bien un conglomerado de t´ecnicas, que tratan sobre la protecci´on y el ocultamiento frente a observadores no autorizados de la informaci´on. Entre las disciplinas que engloba cabe destacar la Teor´ıa de la Informaci´on, la Teor´ıa de N´umeros o Matem´atica Discreta, que estudia las propiedades de los n´umeros enteros, y la Complejidad Algor´ıtmica. El m´etodo de encriptado de datos conocido como algoritmo RSA, por los nombres de sus inventores (Rivest, Shamir y Adleman) es uno de los m´as usados hoy para la transmisi´on segura de datos a trav´es de canales inseguros. El presente articulo pretende detallar las bases mat´ematicas del algoritmo hasta llegar a su implementaci´on en Phython, uno de los lenguajes de programacion mas usados en el area de Seguridad. ´ ´ II. A N ALISIS M ATEM ATICO El algoritmo RSA va a permitir establecer una comunicacion segura entre un emisor E y un receptor R. Cuando el emisor envia un mensaje atraves del canal este no puede asegurarse que el mensaje no sea interceptado por lo que si sucediera el atacante no podra conocer el significado del mensaje ya que este se encuentra cifrado y solo puede ser descifrado con las claves privadas del receptor R El procedimiento matematico empleado para implementar el algoritmos RSA fue el siguiente. 1 Estudiantes
Especializacion en Proyectos Inform´aticos
A. Codificacion del mensaje Debido a que el algoritmo RSA esta basado en la teoria de matematicas discretas y la factorizacion de numeros primos, este solomanete puede cifrar numeros, ya que para este caso en particular se debe cifrar un mensaje en texto plano este debe ser traducido a numeros, es decir, debe ser codificado, para tal caso se utilizara el metodo de codificaci´on ASCII. . B. Definici´on de n Para definir n R debe escoger dos numeros primos p y q lo suficientemente grandes para generar dificultad de factorizacion donde: n=p∗q
(1)
C. Definicion de la funcion multiplicativa de Euler φ(n) El receptor R obtiene el valor de la funci´on multiplicativa de Euler φ(n) apartir de n calculado en el paso B, de tal manera que: φ(n) = φ(pq) = φ(p)φ(q)
(2)
y dado que p y q son primos entre s´ı, y cada uno de ellos es primo, entonces: φ(n) = (p − 1)(q − 1)
(3)
D. Definicion de claves publicas y privadas El emisor E debe realizar el cifrado del mensaje con la clave publica e del receptor R y este a su vez lo descifra con su clave privada d. Para generar e el receptor del mensaje debe escojer un numero tal que: 1 < e < φ(n) de tal manera que esea primo relativo con φ(n)
(4)
UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
2
a partir de la porcion de la clave publica e calculamos la porcion de clave privada d la cual representa el inverso de e en modulo φ(n) quedando: d = (e−1 )φ (n)
(5)
Calculados e y d las claves publicas y privadas quedaran definidas por los pares de numeros (e, n) y (d, n) as´ı: ClaveP ublica = (e, n)
(6)
ClaveP rivada = (d, n)
(7)
E. Cifrado con clave p´ublica Al tener definida la clave p´ublica se puede pasar a realizar el cifrado del mensaje m que E le envia a R, para ello el mensaje luego de ser codificado se cifra elevandolo a la potencia e en modulo n asi: mcif rado = (me )n
(8)
F. Descifrado con clave privada Como lo indica la ecuacion (6) la porcion de la clave privada d es el inverso de e, por eso cuando R recibe el mensaje cifrado de E, lo descifra utilizando el inverso d: mdescif rado = ((mcif rado )d )n
(9)
y reemplazando 9 : mdescif rado = ((me )d )n = (med )n
def genclaves(bitn): p = genprime(bitn) q = genprime(bitn) n = p * q phi = (p - 1) * (q - 1) e=65537 while (phi%e) == 0: e=genprime(17) d = inverse_mod(e, phi) public = (n, e) private = (n, d) return public, private C. Procedimiento de cifrado Para el procedimiento de cirfrado se creo la funcion cif rar(n, public) la cual hace uso de la funcion modex(base, exponente, modulo) tambien llamada desde el m´odulo rsam ath. def cifrar(m, public): c = modex(m, public[1], public[0]) return c
(11)
D. Procedimiento de descifrado
En resumen R ya puede conocer el mensaje enviado por E III. I MPLEMENTACION DEL A LGORITMO EN P YTHON A. Codificac´ıon de Texto plano Para realizar la codificacion de la cadena de texto plano que se desea cifrar se utilizo la funcion ord(), la cual convierte un caracter unicode a su equivalente en ASCII, para realizar la codificaci´on del texto completo se creo una funci´on que realiza el procedimiento recorriendo cada caracter de manera que codifique el texto entero, esta funcion se definio como text2ascii para luego de solicitar el texto llamarla y realizar la codificacion correspondiente def text2ascii(Cadena): cod = ’’ for i in Cadena: cod += str(ord(i)) + ’,’ return cod
Para la generacion de claves publicas y privadas se creo la funcion genclaves(bitn) la cual ademas de calcular la claves e y d, genera q y p apartir de la funcion genprime(bitn)1 la cual genera nuemeros primos de cierto tama˜no de bits,n ,φ(n) y la clave privada d apartir de la funcion inverse mod para obtener el inverso. Todas estas funciones fueron generadas a partir de una llamada al modulo rsa math
(10)
y como e y d son inversos en modulo φ(n) entonces mdescif rado = (med )n = (m)n
B. Definicion de Claves Publicas y privadas
Para el procedimiento de descifrado se utiliza la misma funcion del paso anterior solamente que que se cambia de la clave p´ublica a la privada: def descifrar(c, private): p = modex(c, private[1], private[0]) return p E. Decodificaci´on a Texto Plano Para realizar la decodificacion y poder tener el texto en claro y entendible se hizo uso de la funcion chr() la cual es la inversa de la funcion ord() que se utilizo para codificarla quedando: def ascii2text(Cadena): decod = ’’ for i in Cadena.split(): . decod += chr(int(i)) return decod 1 La funcion genprime(bitn) se genera apartir del test de primalidad de fermat
UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
3
IV. C OMO SE ATACA EL ALGORITMO Si un atacante intercepta el mensaje cifrado, no puede ejecutar la operaci´on de descifrado porque no conoce d. La unica manera en que pudiera conocerla es calcul´andola como la inversa de e (que es publica) en modulo φ(n), y eso no es posible porque no conoce φ(n). Aun as´ı, se podr´a pensar que no es dif´ıcil conocer φ(n) dado n (que es publico): se descompone n en factores primos, lo que dar´ıa n = pq, y se calcula φ(n) como (p − 1)(q − 1). El problema est´a en que descomponer un numero en factores primos es un algoritmo que se supone NP-completo (o sea, su complejidad es exponencial con el tama˜nodel n´umero), y actualmente la descomposici´on de un n´umero de 200 cifras llevar´ıa del orden de un mill´on de a˜nos de c´alculo, incluso el computador mas potente. La clave de todo este algoritmo est´a precisamente aqu´ı: calcular un n´umero dada su descomposicion en factores primos es trivial, pues basta multiplicar los factores. Sin embargo, hallar los factores dado el numero es costos´ısimo computacionalmente. Otras alternativas mas eficiente para atacar exitosamente el algoritmo son: A. Ataque al secreto mediante cifrado c´ıclico Este ataque consiste en encontrar el n´umero en claro N(Mensaje codificado) sin necesidad de conocer d, la clave privada del receptor. Como C = N e modn, se realizan cifrados sucesivos de los criptogramas Ci resultantes con la misma clave p´ublica hasta obtener nuevamente el cifrado C original.
i = 2C2 = 629 mod247 = 93
(18)
i = 3C3 = 9329 mod247 = 175
(19)
i = 4C4 = 17529 mod247 = 54
(20)
i = 5C5 = 5429 mod247 = 123
(21)
i = 6C6 = 12329 mod247 = 119
(22)
El ataque a dado resultado rapidamente: como se ha obtenido otra vez el criptograma C = 119, es obvio que el paso anterior con C = 123 se correspond´ıa con el texto en claro. B. La paradoja del cumplea˜nos Este algoritmo fue propuesto por Merkle y Hellman en 1981 y consiste en: • El atacante elige dos n´ umeros aleatorios distintos i, j que esten contenidos en n.Adem´as se elige un mensaje o n´umero N. i j • Para i = i + 1 y para j = j + 1 calcula N mod n y N mod n. • Cuando encuentra una coincidencia de igual resultado de cifra para una pareja (i, j), ser´a capaz de encontrar d
V. C ODIGO RSA EN LENGUAJE P YTHON
Ci = C(e i − 1)mod(n)
(12)
El codigo de implementacion RSA en Python se puede descargar atraves del siguiente enlace:
(i = 1, 2, 3, 4...)
(13)
Descarga aqui el c´odigo Implementaci´on RSA en python
C0 = C
(14)
Con y Si en el cifrado i´esimo se encuentra el criptograma C inicial, entonces es obvio que el cifrado anterior (i-1) ser´a el n´umero buscado. Esto se debe a que RSA es un grupo mutiplicativo. Para evitarlo hay que usar primos seguros de forma que los subgrupos de trabajo sean lo suficientemente altos. Ejemplo Sea p = 13, q = 19, n = 247, φ(n) = 216, e = 29 (d = 149, no conocido) El n´umero a cifrar ser´a M = 123 de donde C = 12329 mod 247 = 119 iCi
(15)
i = 0C0 = 119
(16)
i = 1C1 = 11929 mod247 = 6
(17)
R EFERENCES [1] Seguridad Inform´atica y Criptograf´ıa v 4.1, de marzo de 2006. Dr. Jorge Rami´o Aguirre - Universidad Polit´ecnica de Madrid. Capitulo 14, El Algoritmo RSA [2] Guia Matematicas para computaci´on, Curso Ingenier´ıa en Informatica, Universidad de Valencia, Capitulo 12
