Mariapandora.com
[Visita nuestro patrocinador]

Literatura | Música | Imagen | Ciencia | Desasosiegos





Deabruak.com
RSA, una clave secreta que muy probablemente ha usado sin saberlo

por Santiago Egido

Una de los razones por las que el comercio electrónico no ha crecido con mayor rapidez es que muchos usuarios tienen miedo de mandar por la internet información sensible como sus números de tarjetas de crédito. Aunque conviene tener cuidado con a quién le damos nuestro número, ya sea en la internet o en la calle, tampoco hay que ser demasiado paranoico; veamos una de las formas en que es posible mandar información confidencial por la internet.

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 web browser (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, pues 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 web browser, 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.

Un truco de magia

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. Si le aburre esta sección puede saltar al siguiente título gordo.

¿Quiere entretener a un crío? No es necesario que sepa hacer números de prestidigitación, le basta con una calculadora para asombrarle.

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 nultiplicará 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.

Admito que hay trucos de magia más vistosos, pero a los niños les impresionan los números grandes. 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. Esto no es magia, por supuesto, pero dígale a un chaval que le va a enseñar una consecuencia del teorema de Euler-Fermat y verá cómo corre el enano.

Cómo funciona el método RSA

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á "a por tabaco", 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.

Firmas digitales y certificados

Una ventaja de los sistemas de clave pública es que todo el mundo te puede mandar un mensaje, pero esto puede resultar también un inconveniente, porque el hecho de que recibas un mensaje adecuadamente cifrado no implica que te lo haya mandado alguien en quien confías. Parece como si todo el mundo pudiese mandarle mensajes a tu banco haciéndose pasar por ti para sacar dinero de tu cuenta.

Afortunadamente es posible usar RSA para comprobar quién ha mandado un mensaje. La idea se basa en una característica más bien atípica de este método: es posible descifrar un mensaje que no ha sido cifrado todavía. Esto no se puede hacer normalmente porque los mensajes cifrados suelen tener un formato que no tienen los textos originales. Por ejemplo, antes hablamos de un método para convertir un mensaje en un número, por el procedimiento de sustituir cada "a" por "01", etc. Imaginemos por un momento que usásemos este procedimiento para cifrar textos; ¿cómo descifraríamos un mensaje como "999"? No sólo tiene un número impar de cifras, sino que en el alfabeto no hay 99 letras; aunque no lo hayamos descrito explícitamente, los mensajes cifrados de esta forma tienen un formato bastante específico.

Una ventaja de usar números en vez de letras, como hace RSA, es que su formato es poco importante. Pensemos en el ejemplo anterior, cuando elevábamos al cubo para cifrar y a la séptima potencia para descifrar; ¿qué es lo que nos impide elevar primero a la séptima potencia y después al cubo? (y quedándonos siempre con los restos al dividir los resultados por 33). El resultado de descifrar primero y cifrar después es lo mismo que cifrar primero y descifrar después, porque para cualquier número n se cumple que

(n3)7 = n3*7 = n7*3 = (n7)3

Es muy posible que la fórmula anterior le traiga recuerdos del bachillerato; recuérdela de todas formas, el día que sus hijos le pregunten para qué sirve la propiedad conmutativa del producto usted podrá responderles que sirve para certificar cosas en la internet.

Imagínese que usted es un notario y tiene que certificar, por ejemplo, una declaración para un juicio en Madagascar. Mandar la declaración por correo electrónico no bastaría, porque cualquiera podría falsificarla. Sin embargo, si usted tuviese una clave RSA, podría mandar la declaración dos veces: una copia legible por humanos y, además, una copia descifrada. Cuando alguien desease comprobar que esa declaración ha sido certificada por usted, lo único que tendría que hacer sería cifrar la copia descifrada de la declaración con la clave de su despacho de notario, que se podría sacar de un registro oficial en la internet. Si el resultado de cifrar la declaración descifrada es idéntico a la copia de la declaración que se recibió sin descifrar, entonces se sabe que ese mensaje fue efectivamente mandado por usted, porque nadie más es capaz de descifrar usando su clave.

De esta forma, el que todo mundo pueda usar su clave para cifrar mensajes se convierte en una forma de comprobar que fue usted quien descifró algo. Hace ya años que existen compañías privadas que ofrecen servicios de certificación por internet, pero la gente no confía en estas tecnologías, que apenas se usan para proporcionar acceso a páginas pornográficas. Lo más posible es que, para cuando el mundo haya espabilado, este mercado haya sido acaparado por el Servicio Postal de los Estados Unidos, que cobrará un tanto por ciento de todas las transferencias bancarias, un pellizquito cada vez que alguien lea una revista de pago en la internet, etc.

Bien, pero ¿cómo firmamos un mensaje secreto? No podemos mandar una versión descifrada, porque todo el mundo podría cifrarla y leer el mensaje.

El truco consiste en que tanto el emisor como el receptor tengan claves RSA. Cuando yo quiera mandarle un mensaje a usted, le mando mi texto cifrado con su clave pública, seguido del texto primero descifrado con mi clave privada y luego cifrado con su clave pública. Parece un trabalenguas, pero la idea es la misma de antes, solo que todo el envío se hace cifrado con su clave para que sólo usted pueda comprobar que fui yo quien mandó el mensaje.

Nota técnica: en realidad, una firma digital no contiene todo el mensaje cifrado, sino tan solo el equivalente a un número de unas 40 o 80 cifras obtenido del texto de tal forma que la más mínima modificación sería detectada; pero eso es otra historia.

Todo esto puede parecer ciencia ficción, pero lo más probable es que usted haya usado ya este método sin saberlo al navegar por la web. Además, todo esto es más bien viejo. La patente de 20 años de RSA expira el 20 de septiembre de 2000. La primera versión de PGP data de 1991. Otro estándard que incluye muchas de las cosas discutidas aquí es MIME, el protocolo de correo electrónico que probablemente usa usted todos los días. Los cajeros automáticos también usan técnicas parecidas.

No, ya no es ciencia ficción, aunque la gente siga sin fiarse; quizás el mayor éxito de la criptografía comercial haya sido hasta qué punto se ha infiltrado en nuestras vidas sin habernos molestado.

 

 

Texto, Copyright © 2000 Santiago Egido. Todos los derechos reservados.
Para aprender más:
Simson Garfinkel y Gene Spafford, Web Security & Commerce, O´Reilly & Associates Inc., ISBN 1-56592-269-7.
Curso de criptografía en español en Kriptópolis: http://www.kriptopolis.com/cr_cur.html
El FAQ de RSAlabs: http://www.rsasecurity.com/rsalabs/faq/
mariapandora.com
[Visita nuestro patrocinador]

 


Babab.com
Correo: Colaboraciones
Última actualización: martes, 29 de febrero de 2000

Copyright © 2000-01 Mañana Es Arte A.C.
Prohibida la reproducción de cualquier parte de este sitio web sin permiso del editor. Todos los derechos reservados.