Explicando cifrado RSA (Fácil)

Hola a todos, en este post mi objetivo es explicarles que es el cifrado RSA, su importancia, sus usos, como encriptar cualquier mensaje utilizandolo y tambien el camino inverso, es decir, desencriptar mensajes. Empecemos ¿Qué es y para qué sirve? Cuando se navega por la web, de vez en cuando se llega a una "página segura", como aquellas en las que se proporcionan números de tarjetas de créditos al hacer una compra. Si está usando Netscape, al visualizar esa página aparecerá una llave en la esquina inferior izquierda de su ventana; si está usando Internet Explorer, aparecerá un candado cerca de la esquina inferior derecha. Estos símbolos indican que la información que proporcione a la tienda se transmitirá cifrada, sin que usted tenga que hacer nada para ello. Bueno, estos símbolos indican también otras cosas; entre ellas, que esa misma página que usted está viendo le ha sido mandada también cifrada. De forma que aunque usted pueda ver su dirección electrónica en la ventana de su buscador (Netscape o Explorer), alguien que hubiese pinchado los cables de su teléfono sería incapaz de reconocerla y mandarle correo basura. Otra cosa es que la tienda en la que está comprando venda luego su dirección, claro. Esto puede parecer imposible, porque usted y la tienda no se han puesto de acuerdo con anterioridad en usar ninguna clave para mandarse mensajes secretos. Así que parece de sentido común que si alguien escuchase desde el principio el diálogo entre su ordenador y el de la tienda, entonces sería capaz de interceptar las claves que se intercambien y descifrarlo todo. Bueno, no. Es posible que todo el mundo conozca las claves usadas y tenga todos los mensajes, y que sin embargo nadie pueda descifrar nada. De hecho, en la internet es relativamente frecuente que la gente incluya su clave de PGP al final de cada mensaje mandado por correo electrónico. Hay varias formas de hacer esto, pero el sistema de cifrado de clave pública más extendido es el método RSA, así llamado por las iniciales de sus inventores, Ronald Rivest, Adi Shamir, y Leonard Adleman. Este método está instalado en su buscador, que se encarga por usted de generar claves, intercambiarlas, y usarlas cuando llega a una página segura. Sin entrar en detalles demasiado técnicos, veamos cómo funciona y por qué es seguro. ¿Cómo funciona? Para entenderlo mejor puede empezar leyendo esto o puede pasar directamente al próximo título Para entender cómo funciona el sistema RSA hace falta saber un poquito de matemáticas; tan poquito que lo podemos presentar como un juego. Póngase una chistera y pídale a su público que le diga dos números primos. Recordemos que los números primos son aquellos que sólo se puede dividir exactamente por 1 y por sí mismos. Por concretar, imaginemos que le dan el 3 y el 11. Usted hará dos cosas con estos números. Por un lado los multiplicará para obtener 3*11=33. Por otro lado, les restará 1, los multiplicará, y al resultado le volverá a sumar 1; en nuestro caso, (3-1)*(11-1)+1=2*10+1=21. Y entonces dará a conocer un sorprendente secreto de los números 33 y 21, llámele fórmula mágica o cualquier tontería por el estilo. Resulta que si empezamos con cualquier número entre 0 y 32 y lo elevamos a la potencia 21 obtendremos un resultado enorme que, al dividirlo por 33, nos dará un resto que será... el número con el que empezamos. Si usted tiene una calculadora podrá hacer la prueba con números pequeños como el 2; 2 elevado a la potencia 21 resulta ser 2.097.152, que al dividirlo por 33 da 63.550 y resto 2. Si tiene un ordenador a mano la cosa tiene más gracia porque los números que aparecen son enormes; por ejemplo, 27 a la potencia 21 da 1144561273430837494885949696427, y al dividirlo por 33 obtenemos 34683674952449621057149990800 y resto 27. No falla, el resto es siempre el número con el que empezamos. Método RSA Ahora si: Es posible que le asuste el nombre, pero usted ya ha aprendido toda la aritmética modular que le hará falta, así que vayamos al grano. Antes de nada necesitamos un sistema para convertir mensajes en números. Lo más típico es sustituir cada letra del texto por dos cifras indicando su posición en el alfabeto; es decir, cambiamos cada "a" por "01", cada "b" por "02", cada "c" por "03", etc, y de esta forma podemos convertir un importantísimo mensaje secreto como "hola" en "08151201". Debería haber alguna forma de incluir espacios y signos de puntuación, pero estos detalles no son esenciales; lo importante es que a partir de ahora los mensajes que queremos cifrar y descifrar son simplemente números. A diferencia de otros métodos más tradicionales, en los que tanto el emisor como el receptor tienen que conocer la misma clave, en RSA es el receptor quien tiene TODA la clave; al emisor le deja conocer la parte pública de la clave, que sirve para cifrar mensaje. El receptor guarda muy cuidadosamente la parte privada de la clave, que sirve para descifrar. Construir una clave es fácil, de hecho ya lo hicimos en el apartado anterior. Buscamos dos números primos como 3 y 11 y hacemos dos cosas con ellos. Primero los multiplicamos para obtener 33. Luego les restamos uno, los multiplicamos, y al resultado le sumamos 1, para obtener (3-1)*(11-1)+1=21. Y a continuación (esto es nuevo) buscamos un divisor pequeño de 21, por ejemplo 3, y calculamos 21/3=7. Ya tenemos nuestra clave: para cifrar elevamos a la potencia 3, dividimos por 33, y nos quedamos con el resto. Para descifrar, elevamos a la potencia 7, dividimos por 33, y nos quedamos con el resto. Recordemos el truco de magia de la sección anterior: si elevamos un número entre 0 y 32 a la potencia 21 y dividimos por 33, el resto es el número con el que empezamos. Pero 21=3*7, así que elevar a la potencia 21 es lo mismo que elevar primero a la potencia 3 y después elevar el resultado a la potencia 7. Bueno, pues elevar a la potencia 3 es lo que hace el emisor para cifrar el mensaje; elevar a la potencia 7 es lo que hace el receptor para descifrar el mensaje. Y "mágicamente" el resultado de ambas operaciones es el mismo número con el que se empezó, es decir, el mensaje original. Ahora que tenemos nuestra clave, anunciamos la parte pública a todo el mundo que nos quiera mandar mensajes. Esto lo podemos hacer poniendo nuestra clave de PGP en nuestra página en la web, o con un anuncio en el periódico: Diario El País, edición internacional Anuncios por palabras Soy Bond, James Bond, la clave RSA para enviarme mensajes es elevar a la potencia 3, dividir por 33, y mandarme el resto. Por supuesto, en el anuncio no se menciona para nada el número 7, que sirve para descifrar los mensajes; ésta es la parte privada de la clave, la que guarda en secreto el receptor. Un ejemplo. Queremos mandar el mensaje "27" al agente 007. Bueno, pues lo elevamos a la potencia 3, obtenemos 19.683, lo dividimos por 33 y nos da 596 y resto 15. Como no tenemos ni idea de dónde está James Bond, lo que hacemos es poner nuestro mensaje cifrado (15) en el periódico, y nos da igual que los rusos o espectra lo puedan leer junto con la clave, no podrán descifrarlo. Diario El País, edición internacional Anuncios por palabras Soy Bond, James Bond, la clave RSA para enviarme mensajes es elevar a la potencia 3, dividir por 33, y mandarme el resto. Mensaje para James Bond: 15. El agente 007 estará infiltrado en algún sitio que no se puede divulgar. Un día saldrá, comprará el periódico, y para recuperar nuestro mensaje elevará 15 a la potencia 7 y obtendrá 170.859.375, que al dividirlo por 33 le dará 5177556 y resto 27, nuestro mensaje original. ¿Por qué no se puede descifrar? Hemos asegurado un poco dogmáticamente que se puede publicar un mensaje cifrado junto a la clave sin que sea posible descifrarlo. Veamos por qué. Todos los sistemas de clave pública conocidos se basan en que, de alguna forma, es posible representar la misma información de dos formas diferentes, tales que pasar de una forma a la otra es fácil, pero pasar de la otra a la una es prácticamente imposible. En el caso de RSA, en principio es lo mismo tener los números primos 3 y 11 que tener su producto, 33. Decimos "en principio" porque dados dos números es fácil multiplicarlos, y dado un número es teóricamente posible factorizarlo en producto de números primos - todos hemos hecho esto en la escuela para, por ejemplo, simplificar quebrados. Ahora bien, imaginemos que los números primos que hemos usado para construir nuestra clave son enormes y tienen unas cien cifras cada uno. Cualquier ordenador puede encontrar números primos así de grandes en un periquete y multiplicarlos en una milésima de segundo para obtener un resultado de doscientas cifras. De hecho, su ordenador lo hace; cada vez que usted visita una página segura, su web browser genera sobre la marcha una nueva clave de usar y tirar. Pero, ¿cuánto cuesta descomponer en factores primos un número con doscientas cifras? Esta es la gracia del sistema, es prácticamente imposible. Sin entrar en detalles, desde el punto de vista matemático descifrar un mensaje cifrado con RSA es exactamente el mismo problema que factorizar la clave (el número 33 en nuestro ejemplo). Ambas tareas son equivalentes, y si pudiésemos hacer una podríamos hacer la otra. Como "se sabe" que los números así de grandes no se pueden factorizar, el método es seguro. Esto nos lleva a una curiosa observación. Se podría pensar que lo más seguro es usar un sistema de claves inventado por uno mismo, sin que nadie más lo conozca. Pero lo más probable es que uno reinventase un método ya conocido y bastante descifrable. Sin embargo, el problema de factorizar números grandes ha sido atacado por miles de matemáticos a lo largo de muchos siglos. Puede parecer sorprendente, pero esta cuestión es realmente importante, y nadie ha encontrado una forma realmente rápida de hacerlo. Quien lo consiga se hará rico y famoso, pero hay razones teóricas para pensar que muy posiblemente no exista tal método. Parece ser que los expertos están de acuerdo en que, paradójicamente, los métodos más seguros son los que ya conoce todo el mundo y han superado la prueba del tiempo. Sí, en principio es posible factorizar números de doscientas cifras. Pero incluso el ordenador más potente del mundo usando los mejores métodos conocidos tardaría demasiado tiempo. Hay teorías cosmológicas que dicen que dentro de billones de años el universo empezará a contraerse gravitacionalmente y colapsará en un Big Crunch bastante parecido al Big Bang, solo que al revés. Si estas teorías son ciertas, para cuando se acabe el mundo nuestro ordenador más grande no habría hecho sino una fracción insignificante del trabajo necesario para factorizar un número de 200 cifras. Es cierto que la potencia de los ordenadores crece muy rápidamente, y que los algoritmos que se usan para factorizar números han mejorado también mucho; hace treinta años apenas se podían factorizar números de 50 cifras, mientras que hoy ya se ha conseguido llegar a las 120. Conviene aclarar que de vez en cuando se anuncia que se ha conseguido factorizar algún número mucho mayor, pero no son números cualquiera, sino que pertenecen a ciertos grupos interesantes para los matemáticos con propiedades especiales que ayudan a factorizarlos. Imaginemos que hubiese razones para pensar que el gobierno de los EEUU es capaz de factorizar rutinariamente números de quinientas cifras. Lo que haríamos los demás sería usar claves de mil cifras. Este incremento les sería fatal a ellos, que volverían a necesitar trillones de años para factorizar claves, mientras que nuestro perjuicio sería que para cifrar y descifrar mensajes tardaríamos décimas de segundo en vez de milésimas. Comentemos que uno de los primeros programas que implementó RSA dedicaba intencionadamente la mayor parte de su tiempo a no hacer nada, porque los usuarios tendían a no creer que un método tan veloz pudiese ser fiable. Los ordenadores rápidos están de nuestro lado; si se multiplicase por diez la velocidad de los procesadores, nosotros podríamos usar claves el doble de largas en el mismo tiempo, lo cual multiplicaría por unos cuantos millones el tiempo que requerirían los americanos en factorizarlas. Es una competición simplemente injusta en la que nosotros tenemos la ventaja. Dos notas técnicas. Por un lado, las potencias no se calculan como hemos hecho nosotros, ya que los resultados son demasiado grandes incluso para un ordenador; hay trucos para averiguar cuál será el resto de la división sin tener que hacer la potencia. Por otro lado, un ordenador cuántico podría factorizar números rápidamente, pero estos dispositivos tardarán bastante tiempo en ser una realidad. Si usted tiene que mandar un mensaje secreto con la absoluta certeza de que dentro de 200 años seguirá siendo imposible descifrarlo, entonces no use RSA. Resumen (no tan LVL5) : Crear el mensaje: A01 B02 C03 D04 E05 F6 G7 H8 I9 J10 K11 L12 M13 N14 Ñ15 O16 P17 Q18 R19 S20 T21 U22 V23 W24 X25 Y26 Z27 Ej: HOLA -> 08151201 Crear la clave: 1) Buscamos dos numeros primos Ej: 3 y 11 2) los multiplicamos (da 33) 3) y por otro lado les restamos 1 (3-1 y 11-1) los multiplicamos (10*2) y al resultado le sumamos 1 (20+1= 21) 4) Buscamos un divisor pequeño para el resultado del paso 3 (21/3= 7) 5) Ya tenemos la clave Para cifrar: Elevamos a la potencia 3 (en este caso) el mensaje a encriptar, dividimos por 33 y nos quedamos con el resto Para descifrar: Elevamos a la potencia 7 (en este caso) el mensaje encriptado, dividimos por 33, y nos quedamos con el resto