El algoritmo RSA es un algoritmo asimétrico de criptografía clásica. Esto significa que es un conjunto de pasos para encriptar y des-encriptar información, y se usa una llave publica, que todo el mundo conoce, y una clave privada. Como es asimétrico, nadie, a excepción del navegador, conoce la llave privada.
Implementación en python
Primero, se necesitan números primos que funcionen como las claves p y q. La seguridad que da el algoritmo RSA está construido sobre el desafío matemático de factorizar el producto de dos números primos grandes, p y q. Se dice que N=p*q, siendo N el largo de la clave RSA, que entre más larga, es más segura. Se importara randrange de random para luego probar si son primos. Nos aseguramos de que solo retorne resultados de n-bits, además de impares.
Para hacer el test de primalidad más eficiente, se prueba primero contra los primeros 50 números primos luego del 2.
La siguiente prueba de primalidad se conoce como el test de primalidad de Miller-Rabin, que utiliza el pequeño teorema de Fermat para determinar probabilisticamente si un número es compueto o posiblemente es un primo. Funciona de la siguiente forma: Por el pequeño teorema de Fermat, si a no es múltiplo de un número primo n, se tiene que an− 1 ≡ 1mod(n).
Entonces si n > 2, n − 1 es un número par expresado de la forma 2s * d, donde s y d son positivos y d es impar; Implicando a2s * d ≡ 1mod(n). Si al lado izquierdo de la ecuación se le aplica raiz cuadrada y módulo, se obtiene 1 o − 12. Si se obtiene 1, entonces a2rd ≡ − 1mod(n), donde r es un número entre [0,s-1].
De lo contario, si no se obtiene un 1, entonces ad ≡ 1mod(n). Entonces, si n es un número primo mayor a 2, alguna de las afirmaciones debe ser correcta. Si se encuentra un $a$ que para cualquier 0≤r≤s-1 que satisfaga las ecuaciones a2rd ≠ − 1mod(n) y ad ≠ 1mod(n) ,entonces n no debe ser un número primo. Para probar un número n, luego de calcular los valores de s y d, se escoje una base a aleatoriamente para probar ambas ecuaciones iterativamente. Entre más rondas de repetición, es menor el margen de error en el resultado.
a * x + b * y = mcd(a,b)
, substituyendo a=e y b=m=λ(N) porque e y λ(N) son coprimos ((d*e)modλ(N)=1):
Eso finaliza el algoritmo. Para usarlo, se crea un objeto RSA (emisor) y el mensaje, para posteriormente usar encrypt y decript.
Resultados
Se revisará el desempeño del algoritmo usando secuencias aleatorias y midiendo el tiempo que toma el algoritmo en manipularlas.
Probamos imprimiendo el tamaño de la llave y en que momento de la ejecución se logra encriptar.
Conclusiones
Esta implementación es bastante básica, e ignora conscientemente pasos "tradicionales" del algoritmo RSA para encriptar información de forma más segura, además de trabajar con claves más pequeñas que las necesarias en el mundo de la ciberseguridad.
Obviando lo anterior, el algoritmo RSA ha ganado su reputación durante las últimas décadas gracias a su ingenioso mecanismo para encriptar información basado en números primos y aritmética modular, pues factorizar un número grande como producto de dos primos es un trabajo largo y laborioso, sobretodo si se considera que los mensajes de mayor confidencialidad usan primos de hasta 200 dígitos.
En los resultados obtenidos, midiendo la velocidad y tamaño de la clave, nos damos cuanta que a mayor tamaño, el algoritmo toma más tiempo encriptando; relacionando una clave con más dígitos a una mayor seguridad. También es bastante beneficioso que este algoritmo sea asimétrico, pues es difícilmente reversible y tener una clave tanto privada como personal hace que no se detenga el proceso aunque falte la clave privada de un emisor o receptor.
Referencias
Urgellés, J. G. (2018). Un secreto a voces: la criptografía de clave pública. In Matemáticas y códigos secretos. essay, RBA Libros.
Zixi. (2023, March 11). Implement textbook RSA in python. PacketMania. https://www.packetmania.net/en/2022/01/22/Python-Textbook-RSA/#performance-tests
0 Comentarios