22 abril 2011

Clave pública para dummies


Antes que se enfríe el tema de la criptología, aprovecharé de agregar algunas cosas que se me estaban olvidando. El asunto es apasionante y no quiero entusiasmarme, ni sacar explicaciones largas o complicadas que ni yo mismo entiendo, sino mejor poner las ideas que hay detrás de todo el enredo.

La criptografía se dedica a las comunicaciones secretas que se transportan por un medio inseguro, o sea tengo un mensaje que se lo quiero transmitir a otra persona, ese mensaje lo pueden ver muchas personas pero solo el que yo escoja conocerá lo que yo le quise transmitir. Nadie más le verá sentido aunque lo tengan en sus manos para analizarlo como quieran. Ojo que aquí hablo de mensaje y comunicación, dos conceptos más restringidos que la información porque aquí existe un contenido semántico (significado) que si importa.

Hay muchas formas de lograr esto pero en general Shannon en su artículo identifica tres: esconder la información con significado dentro de otra con distinto significado (concealment systems), el clásico ejemplo eran los espías de la guerra fría donde el emisor y receptor tenían el mismo libro de muchas palabras (La Guerra y la Paz por ejemplo), entonces para escribir el mensaje indicaban cada palabra con tres números: la página, la fila y el lugar en la fila del libro donde esa palabra se encontraba.

En este caso si conocemos el método que están usando, la clave (key) será saber cual es el libro que están usando. Si sabemos el método y el nombre del libro no cuesta nada descifrar el mensaje secreto. Hay varios otros ejemplo como por ejemplo cuando se oculta un mensaje dentro de una imagen (esteganografía), etc. Todos estos métodos se llaman de clave simétrica, porque el que envía y el que recibe deben compartir la misma clave.

Otra familia de métodos es la que Shannon llamaba "privacy systems" que consistía en hacer alguna clase de transformación tecnológica al mensaje que solo fuese conocida por las dos partes, como por ejemplo invertir la voz o enredarla mediante "scramblers" electrónicos. En este caso el secreto (key) estaba en el método, bastaba conocer el método, se hace una máquina para revertirlo y listo.

Habrán notado que estos dos métodos dependen de que ambas partes compartan un mismo secreto, el problema es como se comunican cual es el secreto, o sea cuando deben mandar la clave por el mismo canal inseguro. Si se pueden juntar cara a cara se dicen la clave al oído (o bajo la "campana del silencio" de Maxwell Smart)no habría problema, pero lo normal es que no se puedan juntar personalmente ¿como se transmiten la clave de manera segura? No hay forma si usan una clave simétrica como las descritas.

El tercer método es el que Shannon llama "true secrecy system" que supone que el enemigo puede interceptar el mensaje, pero le resulta imposible de entender aún cuando conoce que sistema se ha usado para encriptarlo, depende completamente de conocer la clave (key) que no es el método como en los casos anteriores sino que otro mensaje mas corto que permite abrir al encriptado aplicando alguna transformación matemática.

Shannon vuelve al problema de la clave simétrica y dice que debe ser "transmitida por un canal no interceptable" (imposible porque ya definimos un medio inseguro, si hubiese un canal no interceptable no necesitamos encriptar). El intercambio de claves fue el mayor problema de la criptografía durante siglos.

La famosa máquina Enigma de los nazis producía encriptación tan complicada porque cada vez que escribía la transposición de la letra era distinta, o sea cada letra de cada mensaje usaba un método diferente. Leo en este entretenido artículo que la máquina se vendía como una curiosidad en Berlin a 144 dólares cada una, fue inventada por el ingeniero Arthur Sherbius y muchas fueron compradas y operadas por el Ejército Argentino antes de la Segunda Guerra.

EL Servicio Secreto polaco compró algunas antes de que Polonia fuese invadida y construyeron las primeras máquinas capaces de romper ese código llamadas "bombas polacas", luego de la invasión los criptógrafos polacos se fueron a trabajar a Inglaterra donde finalmente quebraron el código de las enigamas mucho más complicadas que se construyeron durante la guerra.

Como siempre el punto débil era intercambiar la clave, las máquinas Enigma venían con un libro con las claves que deberían usar cada día, a veces cambiaban más de una clave por día pero ese era el talón de Aquiles del sistema: si se recolectaban muchos mensajes enviados un mismo día había material para que los criptoanalistas dedujeran las claves y pudiesen romper el código.

El problema de la clave simétrica recién se vino a resover en 1976 cuando Diffie y Hellman publicaron su artículo New Directions in Criptography que dio origen a la criptografía asimétrica o de clave pública.

Es de esas ideas que uno se pregunta como antes no se le había ocurrido a nadie: el receptor y emisor tienen dos claves cada uno, una privada y una pública. Para encriptar y desencriptar se usan las dos claves combinadas igual que una caja fuerte que se abre solo cuando se usan dos llaves simultáneamente. Como las claves públicas por si solas no sirven para nada, las puedo publicar en el diario, mandar por correo, etc. sin problema.

Para encriptar mi mensaje uso mi clave privada y la clave publica del destinatario, para abrirlo la otra parte usa mi clave pública y su clave privada ¡ya no existe el problema de intercambiar una clave secreta!

Y para tener acceso a nuestra clave privada, que está bien guardada en algún lado de mi equipo, debo usar un password que solo yo conozco y no necesito decir a nadie, ni siquiera al destinatario de mi mensaje. Que ingenioso ¿no?. En la imagen se muestra como funciona el sistema, las dos claves (privada y pública) que se muestran en rojo y verde son las de Bob y el enemigo es Eve, que pese a tener el mensaje y las claves públicas de ambos no tiene modo de saber el secreto del mensaje, por ejemplo si le están poniendo los cuernos.

En fin, el tema da para largo pero lo que me interesaba contar era el problema de comunicarse la clave y como lo resolvió el sistema de cifrado asimetrico. Hasta mañana

22 comentarios:

  1. ´Nn capische, Tomás, la correlación necesaria entre las claves de uno y otro. No veo cómo me pueden cifrar algo que descifraré con una clave que conozco sólo yo y no el emisor salvo que las claves publicas y privadas tengan ima relación parental.
    Una vez San Martín en Lima mandó al coronel Pringles con un mensaje al sur del Perú y como lo rodearon los realistas contra un acantilado Pringles dio vuelta su caballo y saltó al mar. Increíblemente se salvó y agarrado a una roca en el agua negoció con el jefe español que, en atención a su arrojo, lo dejó salir sin requisarlo. Además el mensaje se le mojó todo. Si hubiera tenido todo esto de las dos llaves, caramba, se hubiera ahorrado el remojón. Ulschmidt

    ResponderBorrar
  2. Toda la razón Ulschmidt. Hay cosas que no expliqué por lo que el asunto de la clave pública todavía es difícil de entender.

    Primero: no dije que una "clave" en el contexto de la criptografía nueva no es un "password" o "palabra clave", sino que es un archivo que uno guarda en su computador (si es la clave privada) o lo publica (si es la clave pública).

    Para "activar" una clave privada, o sea para que el archivo de permiso para desencriptar,tenemos que usar un "password", la clave pública -que es la que se intercambia- no necesita password ni nada para activarse.

    Si alguien se apropia de tu archivo con clave privada no le sirve para nada si no conoce el password (no puede activarla).

    Cualquiera puede tener tu clave pública pero si yo le mando un mensaje para que solo Ulschmidt lo pueda leer, lo encripto con mi clave privada (activada con mi password) y la clave pública de U. simultáneamente.

    U. al recibirlo solo lo puede abrir si tiene mi clave pública y su propia clave privada (activada con password que solo el conoce) simultábeamente.

    ¡Hay una ventaja adicional! si Uleschmidt puede abrir mi mensaje, también puede estar seguro que yo lo envié, porque nadie más puede activar mi clave privada que usé para encriptarlo. ¡O sea el mensaje además viene firmado!

    ResponderBorrar
  3. P.D. Si no me interesa firmar digitalmente el mensaje, podría cifrarlo solo con la clave pública del destinatario. La única manera de abrirlo es el destinatario son la clave privada (activada con su password)

    Si solo me interesa firmar el mensaje, o sea que vaya en texto claro y que todos puedan estar seguros que yo lo envié, le aplico mi clave privada, al final del mensaje aparece un bloque de texto único que es mi "firma digital" cuando el destinatario le aplica mi clave pública verifica que esa firma, en ese texto solo la pude colocar yo, usando mi clave privada activada con mi password.

    La firma digital cambia y es única para cada texto, es un bloque "resumen" (harsh) del texto encriptado con mi clave privada.

    ResponderBorrar
  4. Ah, es como cajas y llaves. - y las puertas de las cajas son de esas que cierran solas pèro hay que abrir con llave.
    Tu me mandas dos cajas. En una está el mensaje (A) y en otra la llave para abrir la caja anterior (B). Y yo sólo tengo la llave para abrir la caja (B), que contienen la única llave paa abrir la caja (A) que contiene el verdadero mensaje.
    Y si mi analogía no se compadece en lo mas mínimo con la moderna teoría de encriptación por favor cambia la teoria de encriptación para que se parezca a mi analogía, porque no entiendo nada. Ulschmidt

    ResponderBorrar
  5. jajaja, igual por ahi va la cosa! a ver si puedo ajustarlo al ejemplo de cajas y llave que está bien bueno bueno.

    El mensaje que yo mando a U. está dentro de una caja que tiene dos cerraduras.

    Ulschmidt distribuye a todo el mundo una de las llaver requeridas que se llama "su clave pública", digamos que mandas copias al correo y el que quiera poede llevarse una.

    Yo me llevo una para mi casa y la uso en la cerradura "encriptar a U." escribo el mensaje, cierro la caja con esa llave y te la envío.

    Al recibirla, la única manera de abrir la caja y leer el chisme es con una llave en la otra cerradura, esta llave solo la posee U. es su "clave privada", que yo nunca la tuve.

    Bo se si se entiende mejor así

    ResponderBorrar
  6. ah, bueno, creo rasgar el entendimiento. Los ingenieros de la rama civil, Tomás, siempre necesitamos analogías mecánicas para entender las cosas. A ti no te pasa porque te enseñaron cuántica de chiquito y ahora crees en la magia.

    ResponderBorrar
  7. Ah no Ulschmidt, de no ser por las analogías de cajas, puertas, buzones y cerraduras que tuve que leer como 200 veces yo jamás habría llegado a entender el maldito asunto.

    No es un tema difícil pero van apareciendo miles de complicaciones extra porque es como un juego del gato y el ratón.

    Por ejemplo estos sistemas de clave pública tienen una vulnerabilidad que se conoce como "ataque de intermediario"; si yo que soy Tomás empiezoa repartir una clave -generada por mi- diciendo "yo soy Ulschmidt y esta es mi clave pública, envíeme sus mensajes secretos encriptados a yo-soy-ulschmidt@falso.com" alguien podría creerlo y empezar a mandar información al falso U. El PGP también tiene remedio para eso y esa es la baso de los famosos negocios de los "certificados digitales", ahi se arma un enredo enorme con el sistema de confianzas recíprocas

    ResponderBorrar
  8. Lo que aun no cacho, usando el ejmplo de las cajas, es que debes usar tu clave privada antes de pasar el mensaje por la clave publica de U.
    Es decir no capto la relacion entre mis claves publica y privada y porlo tanto, aparentemente no cacho una.

    ResponderBorrar
  9. Wilson, siguiendo con el ejemplo de que el mensaje está dentro de una caja que tiene dos cerraduras distintas, una cerradura se usa para meter el mensaje y la otra para sacarlo.

    Para meter el mensaje (encriptarlo de manera que solo U. lo pueda leer) uso la llave péblica de U. que está disponible para cualquiera. Una vez que hago esto ni yo mismo puedo abrir la caja, solo la puede abrir U. con su llave privada en la otra cerradura.

    Cada uno tiene dos llaves; una pública que se la reparte a todo el mundo no lleva password, y la privada que la mantiene consigo y solo se puede activar con el password que solo yo conozco.

    Para encriptarle un mensaje a U. uso su llave pública y solo el puede abrirlo con su llave privada.

    Si U. quiere contestarme encripta su respuesta con mi llave pública, que está disponible para todo el mundo, pero solo yo puedo abrirlo con mi llave privada.

    ResponderBorrar
  10. ¿Por que tenemo dos llave, una secreta y otra pública?

    La llave pública es para que cualquiera nos cifre un mensaje a mi y solo yo lo puedo abrir con mi llave privada

    La llave privada sirve para abrir los mensajes que me mandan encriptados.

    La llave privada también me sirve para firmar los mensajes, para que sepan que efectivamente los mandé yo. Esto se hace calzándola con mi llave pública.

    En suma: mi llave pública para que me encripten, mi llave privada para abrir lo que me encriptaron y para firmar, la llave pública de otra persona para mandarle un encriptado que solo el puede abrir.

    ResponderBorrar
  11. Releyendo mi primera respuesta a Ulsxhmidt veo que está confusa porque mezcle "encriptar y firmar" en un mismomensaje, a partir de las últimas dos respuestas a Wilson creo que el asunto está más claramente explicado (eso espero)

    ResponderBorrar
  12. Mi unica neurona residual, dice que cree haber cachado.
    Gracias por la explicacion

    ResponderBorrar
  13. Hay un método más "críptico" de entender, que tiene que ver con la curvatura de una elipse me parece. Hasta lo que puede llegar el ocio de los matemáticos...

    ResponderBorrar
  14. Ah, ese es uno delos dosalgoritmos que más se usan, no me metí con los algoritmos para no enredar más la cosa pero el más usado es bien sencillo: se trata de descomponer un número muy grande que es producto de la multiplicación de dos grandes números primos. Multiplicarlos no cuesta nada pero una vez multiplicados saber suales eran esos números es casi imposible. Leo en WIkipedia "Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos (RSA-200) tardó 18 meses y consumió más de medio siglo de tiempo de cálculo". Es un método muy sencillo de implementar y un `problema que no tiene solución matemática (analítica) solo sepuede atacar por fuerza bruta.

    El otro método es el que dices, de calcular un punto dentro de una curva elíptica, también es sencillo de implementar y tampoco tiene solución analítica

    ResponderBorrar
  15. Y para dejar en claro todo esto...al final no existe el algoritmo 100% infalible, se trata nada más que encontrar la solución a estos demandaría una cantidad de tiempo y recursos físicos enorme que no está disponible para el común de los mortales. Se dice que con la computación cuántica, todos los algoritmos actuales se van a tener que ir al tarro de la basura o se deben modificar los largos recomendados para las keys.

    ResponderBorrar
  16. Yo nunca he entendido eso de la "criptografia cuantica" me huele a cuento, hay muchos problemas matematicos simples que no tienen solucion y sololos algoritmos simples que pueden ser entendidos por todos son seguros.

    A la computacion cuantica no le veo pies ni cabeza, creo que anda por ahi con la inteligencia artificial y los videos de Michael Moore o Salfate

    ResponderBorrar
  17. Tomás,

    El enredo lo generaste con un dato charcha (es re fácil confundirse de términos en esto, así que si capaz que también me equivoque.) La gracia de las llaves privada y pública es que cualquiera puede encriptar un mensaje con una llave pública, pero sólo lo puedes desencriptar con la llave privada.

    Ojo, los esquemas de clave pública no requieren intercambio de claves, basta con obtener la clave pública del destinatario (por ejemplo, los usuarios nerd de PGP la ponen de signature.)

    ResponderBorrar
  18. Si, el primer ejemplo que di era encriptar y firmar y eso enredó todo.

    Pero en tu explicación simpole falta decir de quien son las claves:

    cualquiera puede encriptar un mensaje con una llave pública (del destinatario), pero sólo (el destinatario) lo puede desencriptar con su llave privada.

    Por eso uno tiene dos claves, una para que le encripten y otra para desencriptar.

    La clave pública no necesita password para activarse, la clave privada si.

    Las claves que se reparten son las publicas, con la privada se queda cada uno.

    ResponderBorrar
  19. Leonardo Moreno25 abril, 2011 12:45

    Hola Tomás,

    sigo a diario tu blog, pero no suelo comentar. Sin embargo, me asaltó una duda con este tema: al cifrar el archivo de origen con mi llave privada y la llave pública del destinatario, pero el archivo es interceptado por un tercero, ¿porque este no puede utilizar su propia llave privada? Asumo que la respuesta es que el archivo está cifrado con la llave pública del destinatario real, entonces... ¿existe alguna relación entre la llave pública y privada? Porque si es así, eventualmente se puede decifrar la llave privada en base a la pública.

    Espero se entienda mi duda :P

    Saludos!

    ResponderBorrar
  20. Excelente pregunta Leonardo, parece que entendiste muy bien el problema general cuando preguntas si existe alguna relación entre la llave pública y privada, eso es fundamental.

    Claro que existe una relación y eso es central en el problema porque esta relación es sumamente sencilla para encriptar y extremadamente difícil para desencriptar. De ese modo es casi imposible obtener la clave privada a partir de la pública, aunque en verdad están relacionadas.

    Ese es el fundamento de todos estos sistemas de clave pública. Por ejemplo el algoritmo que usa dos números primos grandes, no cuesta nada multiplicarlos pero es muy difícil factorizarlos (o sea teniendo el resultado saber cuales eran los números originales)

    Para números chicoslo puedes saber por inspección: por ejemplo te dicen 15 y tu puedes suponer que se formó multiplicando 3 por 5, pero no hay método matemático para factorizar números grandes, por ejemplo si te dan un número de 300 dígitos o más, que es el producto de dos números primos, no hay como averiguar cuales fueron esos números, excepto tratando con todas las combinaciones posibles (fuerza bruta).

    Escelente pregunta, va al hueso del asunto.

    ResponderBorrar
  21. A todo esto se sigue arrastrando la confusión por lo que escribí al principio: para encriptar un mensaje solo necesitas la llave pública del destinatario -NO tu llave privada- (esa solo si deseas firmar).

    Para desencriptarlo el destinatario lo hace con SU llave privada.

    O sea encriptas con la publica del destinatario y el desencripta con su llave privada.

    Como dice Leus es fácil confundirse en esto.

    ResponderBorrar
  22. Leonardo Moreno25 abril, 2011 14:46

    Gracias por tan pronta respuesta Tomás. Admito que no había leido en profundidad los comentarios, sabía que había algún "error" que se venía arrastrando, pero para efectos de mi duda me pareció irrelevante.

    Super buenos tus aportes al tema, y en general todos los "algo para dummies".

    Saludos!

    ResponderBorrar

"Send me a postcard, drop me a line
Stating point of view
Indicate precisely what you mean to say
Yours sincerely, wasting away
Give me your answer, fill in a form
Mine for evermore
Will you still need me, will you still feed me
When I'm sixty-four"