La encriptación RSA

Las primeras cosas que estoy subiendo al servidor son los libros y artículos que se me han ido juntando con el tiempo, cosas que me han llamado la atención lo suficiente como para descargarlas. Es un trabajo largo y tedioso porque tengo que buscar uno por uno y deben ser miles, luego tendré que poner nombre intligible a los que no lo tienen, pero en eso estoy y los que llevo subidos pueden verlos en http://tombrad.com/biblioteca,  Lo bueno es que he descubierto entre la profundidades de los discos duros varias cosas interesantes, como un ejemplo con números simples del método de encriptación RSA y un ejemplo de ataque a su seguridad.

Como funciona el RSA, ejemplo con números
He escrito varias veces sobre el método de encriptación RSA de clave pública y revisando la biblioteca me encuentro con este lindo ejemplo con números, sabia que lo tenía pero no lo encontraba, así es que se los copio a continuación:

Paso 1: elegimos al azar dos números primos p y q, luego los multiplicamos obteniendo n=p*q. Para nuestro ejemplo numérico lo números serán p=3, q=11 y entonces n=3*11=33

Paso 2: calculamos el "Indicador de Euler" con la siguiente fórmula: phi(n) = phi(p*q) = (p-1)*(q-1). Para nuestro n=33 tenemos phi(33) = (3-1)*(11-1) = 20

Paso 3: buscamos el "exponente de cifrado" que llamaremos e =mod(e,phi(n))=1 es decir un número que no tenga ningún factor común con e. En este ejemplo n=20 y sus factores comunes son 2 y 5. Podemos escoger entonces e=3 por ejemplo

Paso 4: ahora calculamos el exponente de descifrado que llamaremos d, este debe cumplir con 1 menos que d menor que phi(n). es decir un número entre 1 y 20, que debe cumplir además con e*d=1 mod(phi(n)). o sea un número entre 1 y 20, que al multiplicarlo por 3 y dividirlo por 20 debe dar el resto 1. En este ejemplo ese número d=7 (porque 7*3=21 y 21/20 da resto 1).

Con esto ya tenemos los números primos p=3, q=11, el indicador de Euler phi(33)=20, el exponente de cifrado e=3 y el exponente de descifrado d=7, estamos casi listos.

Las claves: la clave pública corresponde a la pareja de números (n, e) o sea (33, 3) en nuestro ejemplo. La clave privada  es el número d, o sea 7 en nuestro ejemplo. Los números p, q y phi(n) deben ser mantenidos en secreto por el que envía el mensaje.

Cifrado y descifrado: supongamos ahora que el mensaje M que queremos cifrar es el número 5, entonces el mensaje cifrado sería C=M elevado a e mod n. Para nuestro ejemplo C =  5 elevado a 3 mod 33 = 26. Para descifrar usamos M = C elevado a d mod n, o sea en nuestro ejemplo M = 26 elevado a  7 mod 33 =5 ¡voila!

El sistema es muy simple y solo usa aritmética elemental, tal vez lo único "raro" que podría encontrar, digamos, un sociólogo en esto es la operación "mod", que no es otra cosa que el resultado entero de una división, sin considerar decimales, el resto son operaciones simples de multiplicación, resta y elevación a potencia. Bueno, también hay que saber lo que son los números primos, creo que he escrito antes de esos números maravillosos.

Recapitulemos: tenemos un mensaje que es el número M = 5, y deseamos mandarlo escondido por un canal inseguro para que solo nuestro destinatario lo puede descifrar, como el canal es inseguro, cualquiera puede leer el mensaje cifrado C=26, también cualquiera puede conocer n=33 y e=3, pero con esos tres números, si p y q son suficientemente grandes es tan complicado descifrar M que nos podría tomar varias veces la edad del universo hacerlo con los métodos conocidos. La razón es que no existe un algoritmo para factorizar números muy grandes y la única forma de descifrar es conociendo los factores p y q.

Bueno, ustedes me podrían decir ¡un momento! ¿para que diablos me sirve encriptar un número si lo que yo quiero es encriptar el mensaje "nos juntamos a las 11 cuando mi marido vaya al trabajo"? Es muy simple, resulta que cualquier texto se puede hacer equivalente a un número en el computador, porque existe una tabla (el código ASCII) que le signa un número único a cada letra o caracter.

Por qué usar dos claves y no solo una
¿Y por qué molestarse con toda esta tontera de clave privada y clave pública cuando sería mucho más sencillo juntarse y ponerse de acuerdo con una palabra clave? de hecho ese sistema existe, es mucho más seguro pero no siempre es posible por el problema de como ponerse de acuerdo en la clave. Imaginen que una esposa infiel y su amante se ponen de acuerdo en que usarán la clave "noselodigasanadie", todo perfecto pero para hacerlo tienen que juntarse en un lugar discreto donde nadie los escuche. En el mundo de Internet, donde tenemos que mandar mensajes encriptados a personas que están en otro continente, etc. esa posibilidad no existe.

Esta situación es lo normal en la seguridad de Internet, donde no nos vemos las caras. SI yo quiero tener comunicación encriptada para entrara a la tarjeta del banco, por ejemplo, no sería nada práctico juntarse con el gerente del banco en un lugar discreto para que acordemos la clave secreta, tampoco me haría gracia que un maldito gerente sepa mi clave, mucho mejor que se haga todo intercambiando las claves entre máquinas. es lo mismo cuando entramos a un sitio seguro de Internet con SSL. Por eso la genialidad de usar el par de claves pública y privada.

¿Cuan seguro es el RSA?
En principio usando cálculos de fuerza bruta, es decir probando muchos billones de veces, se puede encontrar los números p y q a partir de n, pero es absurdamente difícil mientras más grandes son las claves que se usan. Como el algoritmo es tan sencillo existen multitud de profesionales y aficionados tratando de romper las claves. Hasta ahora la clave más grande que se ha podido romper es de 232 dígitos, eso fue hace 10 años atrás y desde entonces no se han podido romper claves más grandes. El tamaño normal de las claves que se usan hoy son de 1024, 2048 y más bits, así es que por ese lado el RSA es muy seguro.

Pero hay un problema en la implementación, porque para elegir el par de números primos normalmente se usan programas generadores de números al azar, y estos programas no generan números realmente al azar porque se basan en un número "semilla" y si la semilla se ocupa más de una vez resulta más fácil quebrar la clave. Por eso se dice que el RSA es 99.8% seguro, pero que diablos, si nada es seguro en este cochino mundo, aparte de los cuernos y la muerte. Lo dice la Ley de Hierro de Bradanovic y esa ley si que siempre se cumple.