El algoritmo RSA y Python

Enigma

Todos los problemas de computación requieren un tiempo mínimo de computo, en algunos casos ese tiempo es asumible y en otros es simplemente inabarcable. Por ejemplo; dado un problema de E entradas, si el tiempo de computo necesario es menor que un polinomio dado de E, se dice que es un problema de clase P. Este polinomio puede ser del tipo $E^{k} + E^{k-1}+...+E + C$, escrito como $O(n^{k})$ o bien puede ser de tipo logarítmico, 
$log(E)^{k} + log(E)^{k-1}+...+log(E) + C$, expresado como $O(log(n)^{k})$.  Los problemas que requieren tiempos de tipo exponencial $(n^{k})$  con n>1, son irresolubles en tiempos razonables. Por ejemplo, dado un ordenador con 6 núcleos y donde cada instrucción tarda aprox 3.7E-4 tendríamos que:

• Problema $n^{5}$ con 50 entradas (n=50); aprox. t=0.0018 segundos
• Problema $3^{n}$ con 50 entradas (n=50); aprox. t=1280 siglos

El problema de factorizar el producto de dos números primos grandes está por encima de los tiempos polinómicos pero es inferior a los exponenciales. Esta afirmación es una sospecha más que un hecho demostrado,  en cualquier caso si se eligen dos números primos suficientemente grandes el tiempo de computo es en la práctica y mientras nadie encuentre un algoritmo polinómico, inasumible. Siempre se puede pensar que el aumento de potencia de los ordenadores podría rebajar los tiempos de computo, haciendo tratable el asunto de la factorización. Sin embargo los problemas súper-polinomiales y exponenciales apenas ganan tiempo si se reduce el tiempo de ejecución de una instrucción. 

En resumen, el problema de factorizar el producto de dos números primos grandes es lo suficientemente insidioso como para ser usado como método de encriptación. Esta es la premisa de la que parte precisamente la encriptación RSA (Rivest, Shamir y Adleman). 

Shamir, Rives y Adleman

La idea es poder compartir un número entre dos personas, Shamir y Rives, a distancia y sin miedo a las escuchas del cotilla de Adleman. Recordemos que todo tiene que hacerse a distancia. La solución es brillante, por lo simple:

• Shamir y Rives afirman por la red que se van a transmitir una serie de números (x) que irán enmascarados como $s^{x}$. Todo esto lo hacen público.
• Shamir elige un número secreto (a) y le manda a Rives el número $s^{a}$, todo de forma abierta. De igual manera Rives elige un número (b) y se lo manda en la forma $s^{b}$, todo ello de manera pública. 
• Ahora Shamir multiplica lo que ha mandado el por lo que ha mandado Rives $s^{(a)b}$. Rives hace lo mismo obteniendo $s^{(b)a}$. Como podemos ver han conseguido el mismo número sin tener que pasar sus respectivas claves privadas (a,b).  

Adleman por su parte podría calcular $s^{a+b}$  pero no ${ s }^{ a\cdot b }$, que es la clave compartida. Todo esto esta muy bien si no fuera porque extraer las claves privadas conociendo s es sencillo $(a\cdot log(s))$. El método requiere alguna sutileza para evitar este problema. Para lograr la dificultar en la extracción de las claves privadas debemos emplear la función de Euler $\phi(n)$, con n producto de dos primos. Esta función es muy sencilla de calcular si se conoce la factorización de n, ya que que si n=pxq, ambos primos, tenemos que  $\phi(n)$$\phi(n)=(p-1)(q-1)$, pero si no se conocen estos dos factores su cálculo no es posible sin afrontar la factorización de n. Por tanto Shamir debe crearse una clave pública (n,e) y otra privada d: 

1. Clave pública de Shamir n siendo n=pxq el producto de dos primos muy, muy, muy grandes.
2. La clave pública de Shamir  e al azar.
3. Clave privada de Shamir d,  inverso de e módulo de $\phi(n)$. 

Encriptación:

1. Shamir tiene una clave pública (n,e) que todo el mundo conoce. Cualquiera que quiera mandar un código a Shamir deberá emplear estas dos claves.
2. Shamir construye n multiplicando dos primos (p,q), es decir n=pxq. Solo el conoce estos dos números y deberían ser muy grandes. 
3. El número e se elige al azar  con una sola condición, que no tenga factores comunes con $\phi(n)$, siendo esta la función de Euler. Recordemos que $\phi(n)$ es la colección de números menores o iguales que n y coprimos de este, es decir, que no tienen factores comunes. 
4. Finalmente Shamir tiene una clave privada (d) que debe ser el inverso de e módulo de $\phi(n)$. Esto es:

$ed \equiv 1  mod \phi(n)$

Descodificar:

1. Shamir usando su clave privada usa:

$(m'^{d}(mod(n))$ m' el msg recibido

 

Ejemplo:

1. Rives quiere mandar en clave un número, digamos el m=1071, como Rives dispone de las claves públicas (n, e), que ha publicado Shamir, calcula el número $m^{e}mod (n)$. Por ejemplo, supongamos que Shamir elige dos primos (p=103, q=233), por lo que n=23999. A continuación selecciona un número e al azar, recordemos que este no debe tener factores comunes con $\phi(23999)$, por ejemplo el 151. Por tanto el par público de Shamir (23999, 151). Ahora Rives calcula $1071^{151}mod (23999)$, esto es 8368 y lo manda.   
2. Shamir recibe este número y lo descodifica, para ello usa su clave privada d. Recordemos que d = inverso de e módulo de $\phi(n)$ y que en este caso da 22567. La fórmula que tiene que aplicar para descodificar es la siguiente $(m'^{d}(mod(n))$, donde m' es le mensaje cifrado. El resultado es, como era de esperar, el número que transmitió Rives.    

 ¿Que ocurre si Adleman  captura el mensaje m'?. Pues tan solo tendía que hacer

$(m'^{d}(mod(n))$, el problema es que desconoce el valor de d, pero podría calcularlo mediante d = inverso de e módulo de $\phi(n)$, desde luego conoce e y también n. Pero, ¿es posible calcular $\phi(n)$ si no se conoce su factorización?. Lo cierto es que el único camino es emplear $\phi(n) = (p-1)(q-1)$, por lo que el problema equivale a factorizar n, que como hemos visto resulta ser muy, muy complicado.
Una implementación sencilla en python es inmediata, lo único destacable es el cálculo del valor d que implica la inversa de e modulo $\phi(n)$. La siguiente función, muy sencilla, permite este cálculo :

def inversemodule(e, module):
    for cont in range(0, module-1):
        if cont*e % module == 1:
            return cont
    return -1 

Calcular un primo, o saber si un número es primo es sencillo, por ejemplo, podemos recurrir a any  que devuelve true si hay algo en la lista. Veamos como:

from math import sqrt

def es_primo(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return not any(num % i for i in range(3, int(sqrt(num)) + 1, 2))

Desdeluego hay otras formas más eficientes para saber si un número es primo, especialmente si se trata de un número alto. Tenemos los algoritmos de Fermat, el de Miller-Rabin, este último especialmente rápido y algunos otros. La implementación es sencilla y no la vamos a repetir aquí ya que se encuentra muy bien descrita en esta página. En cualquier caso lo más lógico sería hacer uso de alguna implementación de las que podemos encontrar en python, tal como Crypto.

El algoritmo es muy seguro, desde luego siempre que se usen grandes primos, no obstante hay formas de atacar la encriptación de RSA. El ataque Wiener es efectivo para d pequeños, al igual que el método de Coppersmith. En cualquier caso existe un método efectivo para lograr una factorización en tiempo polinómico y es usando el algoritmo de factorización de Shor. El problema es que necesita para ser ejecutado un ordenador cuántico. Una explicación sencilla la encontramos aquí, si se desea saber algo más sobre computación cuántica recomiendo el libro "Procesado de información con sistemas cuánticos"  publicado por la Universidad de Vigo. Puede que todo esto suene a ciencia-ficción, el que así lo crea le recomiendo una visita a esta página de IBM.