Hasta el momento, todos los algoritmos criptográficos que hemos visto se engloban dentro de los conocidos como "simétricos" o de clave privada. Es decir, entre Alice y Bob se comparte un secreto (la clave) que se utiliza para cifrar el contenido de un mensaje. Esto tiene un grave inconveniente y es la distribución de dichas claves: Alice y Bob se tienen que ver en persona para intercambiarla de forma que sea completamente secreta. Además, hay que tener en cuenta que una clave reduce su eficiencia con el tamaño de los mensajes cifrados, por lo que hay que cambiarlas con relativa frecuencia. Todo esto provocaba que antiguamente la distribución de claves no fuera ni sencilla ni barata. Si querías intercambiar un número grande de mensajes tenías que ver en persona a la otra parte e intercambiar un libro entero de claves. El problema surgía cuando estas claves se agotaban: había que reunirse de nuevo o enviar a alguien de plena confianza con el libro (destacando lo de "plena confianza", ya que a partir de ese momento la tercera persona podía leer todos los mensajes que se intercambiaran con tan solo conservar una copia del libro). Imaginad el problema logístico que suponía la distribución de claves en la segunda guerra mundial, controlando hasta el último detalle para minimizar el peligro de que los libros cayeran en manos enemigas.
Unos años antes, allá por el final del siglo XIX, un economista inglés, William Stanley Jevons, se percató de que el coste de una operación y su inversa puede ser muy distinto. Por ejemplo, si os pido que me calculeis los factores primos de 851 seguramente me mandéis a paseo, pero en cambio todos podéis multiplicar sin esfuerzo 23 por 37 (aunque viendo el caso que le hicisteis al criptograma de felicitación del año nuevo, que era también bastante fácil, no me atrevería a pedírlo ;).
Pero no fue hasta la década de los 70 del siglo pasado cuando se aprovechó dicha propiedad (en concreto la del ejemplo, la factorización de números primos) para utilizarla en un protocolo criptográfico, revolucionando de esta forma la criptografía. Primero el conocido como Diffie-Hellman y posteriormente el RSA se convirtieron los primeros algoritmos públicos asimétricos que generalizaron su uso. Digo "públicos" porque el ejército del reino unido tenía algún desarrollo previo (y es de esperar que otros gobiernos poderosos también los tuvieran).
¿Y qué nos permiten estos algoritmos? Pues, en contraste con los simétricos, estos nos proveen con dos claves, una sirve para cifrar y la otra para descifrar (de ahí la consideración de "asimétricos"). De esta forma, la clave que utilizamos para descifrar la podemos mantener privada y publicar la que solo sirve para cifrar. Cualquier persona puede tomar nuestra clave pública y cifrar un mensaje con ella de tal forma que solo nosotros, los poseedores de la clave privada, podremos descifrar.
Pero esta forma de comunicación es muy costosa, asi que los protocolos nos recomiendan utilizarla solamente para intercambiar una clave que posteriormente utilizaremos en un algoritmo simétrico (conocida como clave de sesión). Así, cada vez que queramos intercambiar un mensaje podemos utilizar una clave distinta sin necesidad de tener que recurrir a los costosos libros de códigos y su engorrosa distribución.
Pero lo que es también muy interesante de estos protocolos es que nos ofrecen mas funcionalidades aparte de la confidencialidad (acordaos que ya escribí un post hablando de estos servicios). Por ejemplo, permiten "firmar" un mensaje proporcionando autenticidad a la comunicación. ¿Y cómo se hace? Pues resulta que el esquema anterior se puede invertir, es decir, podemos cifrar un mensaje con nuestra clave privada, de tal forma que tan solo se pueda descifrar con la pareja pública. Así, cualquiera puede saber de quién proviene el mensaje: de la única persona que tiene la clave privada.
Con estos protocolos, por tanto, obtenemos servicios de confidencialidad y autenticidad, pero también (no lo voy a explicar ahora, pero lo haré mas adelante) se consigue integridad y no repudio, con lo que por fin tenemos un protocolo que proporciona todos los servicios necesarios para realizar comunicaciones entre dos personas con toda la seguridad posible. Pero además dan mucho juego para otro tipo de servicios muy interesantes que dejo para otra ocasión.
Como es ya costumbre dejo muchas cosas en el tintero, de las que espero hablar mas adelante. Con esto nos adentramos ya en la criptografía contemporánea, ya que los dos algoritmos que he nombrado antes se utilizan en la actualidad (vosotros los utilizais cada vez que accedeis a la página del banco o haceis un comentario en este blog, por poner dos ejemplos), y preparamos el terreno para la aparición de la criptografía cuántica (que es eso que me permite escribir en el blog menos de lo que me gustaría :).
miércoles, 24 de enero de 2007
martes, 23 de enero de 2007
¿Cuesta mucho el Psittaciforme?
Recordaba esta mañana un chiste que me contaron hace muchos años:
Tened cuidado con lo que decís y con quien habláis, no vaya a ser que os vean muchas "k" en vuestro discurso y la ciega justicia (o algún justiciero) vaya a tener que actuar. Ah, y también tened cuidado con los que tienen la verdad absoluta.
Y si quereis comprar algún pájaro, sabed que las cacatúas son de la familia de los Cacatuoidae, del orden de los Psittaciformes, no vaya a ser que tengáis un problema con la justicia por pedirla.
P.D. Si queréis, podéis seguir por aquí:
La madre de Irene Villa y su magnanimidad
Los periódicos de ficción siguen en su línea
Me pongo de pié, me vuelvo a sentar, porque a los oficios vamos a jugar
Y ya en otro tono:
Análisis de Joseph Carlin
Dios y el corderito
NOTA: De verdad que intento no mezclar la política con la criptografía, pero es que hay cosas que "claman al cielo".
Entra un tipo en una tienda de animales...Como chiste hay que reconocer que muy bueno no es, pero actualmente contarlo es peor idea.
Tipo: "¿Es cara la kakatua?"
Tendero: "Lo siento, no hablamos euskera".
Tened cuidado con lo que decís y con quien habláis, no vaya a ser que os vean muchas "k" en vuestro discurso y la ciega justicia (o algún justiciero) vaya a tener que actuar. Ah, y también tened cuidado con los que tienen la verdad absoluta.
Y si quereis comprar algún pájaro, sabed que las cacatúas son de la familia de los Cacatuoidae, del orden de los Psittaciformes, no vaya a ser que tengáis un problema con la justicia por pedirla.
P.D. Si queréis, podéis seguir por aquí:
La madre de Irene Villa y su magnanimidad
Los periódicos de ficción siguen en su línea
Me pongo de pié, me vuelvo a sentar, porque a los oficios vamos a jugar
Y ya en otro tono:
Análisis de Joseph Carlin
Dios y el corderito
NOTA: De verdad que intento no mezclar la política con la criptografía, pero es que hay cosas que "claman al cielo".
viernes, 19 de enero de 2007
12 días en silencio (actualizado x2)
Hola de nuevo. Estos 12 últimos días sin postear tienen su razón de ser: en un par de horas participaré en una charla que dá mi grupo en un máster en computación cuántica y había que preparar un montón de cosas. Mi nivel de nervios es muy alto, a pesar de que la parte de la que yo tengo que hablar es corta y fácil, pero llevo fatal eso de hablar en público.
Con toda seguridad, cuando llegue mi turno de exponer, me quedaré con esta cara:
(Con esto además aprovecho para sumarme a la campaña "una foto al día" de Gema y Marco)
Saludos nerviosos.
NOTA: La foto es de Robert Doisneau
Actualización (15:47):
La charla ha ido razonablemente bien (incluso hemos tenido un "lleno" que no es muy normal en este tipo de exposiciones)... si no tenemos en cuenta el hecho de que mi parte, una exposición puramente práctica, la he tenido que comenzar sin ningún apoyo informático ya que por el "efecto presentación" el ordenador ha dejado de funcionar. Luego he podido explicar poco de lo que tenía pensado, ya que el tiempo ha sido bastante escaso. De todas formas he controlado bastante bien las ganas de gritar y esconderme debajo de la mesa a pesar de todas las circunstancias.
Tengo que mencionar el honor (y los nervios extra) que ha supuesto para mi que en la sala se encontrara escuchando la conferencia Alberto Galindo Tixaire, catedrático de física teórica de la Universidad Complutense y presidente de la Real Academia Española de Ciencias Exactas, Físicas y Naturales, que además en el descanso nos ha felicitado por la charla (no a mi, no flipemos tanto). Quiero remarcar que tras dos horas de charla, se ha quedado y ha escuchado mi parte y la de mi compañero (a pesar de que nos hemos pasado del tiempo establecido para la conferencia).
Con la vuelta al laboratorio hemos vuelto a la normalidad de la investigación española: damos charlas al presidente de la RAC pero hemos agotado nuestro último paquete de a4 y no podremos imprimir hasta que no nos agenciemos otro (tarea mas difícil de lo que parece a priori).
Actualización 2 (20:38):
Estaba releyendo yo el post cuando me he fijado en este detalle:
Con toda seguridad, cuando llegue mi turno de exponer, me quedaré con esta cara:
(Con esto además aprovecho para sumarme a la campaña "una foto al día" de Gema y Marco)
Saludos nerviosos.
NOTA: La foto es de Robert Doisneau
Actualización (15:47):
La charla ha ido razonablemente bien (incluso hemos tenido un "lleno" que no es muy normal en este tipo de exposiciones)... si no tenemos en cuenta el hecho de que mi parte, una exposición puramente práctica, la he tenido que comenzar sin ningún apoyo informático ya que por el "efecto presentación" el ordenador ha dejado de funcionar. Luego he podido explicar poco de lo que tenía pensado, ya que el tiempo ha sido bastante escaso. De todas formas he controlado bastante bien las ganas de gritar y esconderme debajo de la mesa a pesar de todas las circunstancias.
Tengo que mencionar el honor (y los nervios extra) que ha supuesto para mi que en la sala se encontrara escuchando la conferencia Alberto Galindo Tixaire, catedrático de física teórica de la Universidad Complutense y presidente de la Real Academia Española de Ciencias Exactas, Físicas y Naturales, que además en el descanso nos ha felicitado por la charla (no a mi, no flipemos tanto). Quiero remarcar que tras dos horas de charla, se ha quedado y ha escuchado mi parte y la de mi compañero (a pesar de que nos hemos pasado del tiempo establecido para la conferencia).
Con la vuelta al laboratorio hemos vuelto a la normalidad de la investigación española: damos charlas al presidente de la RAC pero hemos agotado nuestro último paquete de a4 y no podremos imprimir hasta que no nos agenciemos otro (tarea mas difícil de lo que parece a priori).
Actualización 2 (20:38):
Estaba releyendo yo el post cuando me he fijado en este detalle:
"...pero hemos agotado nuestro último paquete de a4..."Creo que conviene aclararla porque puede dar lugar a confusiones con respecto a la pila de paquetes de a4 que tenemos normalmente. Nuestra pila es binaria, es decir, toma solo valores de 0 o 1. Pero lo que es mas curioso es que estos valores se encuentran superpuestos siguiendo las propiedades de la mecánica cuántica, por lo que hasta que no abrimos el armario donde los tenemos no colapsa la función de onda y vemos el resultado.
domingo, 7 de enero de 2007
El criptoanálisis del método Vigenère (II)
Aquí viene la segunda parte del criptoanálisis de cifrados polialfabéticos (en concreto lo hemos estado haciendo con el método Vigenère).
El método Kasisky tiene el problema de que en muchas ocasiones las posibilidades de la longitud de la clave son demasiadas. Además, pueden existir coincidencias de secuencias en el texto cifrado que no sean representaciones de la misma secuencia en el texto en claro, lo cual dificulta enormemente encontrar la longitud de la clave, ya que la diferencia entre ellas no será múltimplo del tamaño de clave y por lo tanto nos confundirá.
Aún con esos problemas el método se estuvo utilizando tal y como lo vimos durante casi un siglo, hasta que un criptógrafo del ejército de EEUU, William F. Friedman (que a mi me parece que se da un aire al abuelo de la familia Monster), descubrió que podía hacer un cálculo con los índices de coincidencia de las letras para determinar la longitud de la clave de manera mas directa y precisa. Este método, además, es mucho mas versátil ya que se puede aplicar a todos los cifrados polialfabéticos.
Su ataque se fundamenta en que si en un texto de un lenguaje determinado elegimos dos letras al azar, la probabilidad de que sean la misma es conocida (por métodos estadísticos). Esto se puede comparar con los datos obtenidos de realizar la misma operación en el texto cifrado y de esta forma hacernos una idea de la cantidad de alfabetos que se han utilizado para cifrar el mensaje. Esto ocurre porque al quedar difuminadas las frecuencias relativas de las letras (que además estarán mas difuminadas cuantos mas alfabetos se hayan utilizado para cifrar) cambiará este índice de coincidencia. Es decir, si, por ejemplo, en el inglés la probabilidad del uso de la E es la mayor de todas. Entonces, si superponemos dos textos, la probabilidad de que coincida una E sobre otra será alta. En cambio, en un texto cifrado la probabilidad observada será mucho menor, y dependerá del número de alfabetos con el que esté cifrado.
Al final, todo esto se reduce a una fórmula (que saco directamente de la wikipedia):
Donde la I es el índice de coincidencia, que viene dado por la siguiente expresión de combinatoria:
... donde los distintos valores para las enes vienen dados por las frecuencias absolutas de las apariciones en el criptograma de las 26 letras del alfabeto inglés, n es la longitud del texto, y el 0.065 es la probabilidad de que dos letras al azar en un texto inglés sean las mismas.
Este método realmente funciona para cualquier cifrado polialfabético, y en su momento consiguió romper muchos de los cifrados de algunas máquinas de rotores utilizadas. (De las máquinas de rotores ya hablaré mas adelante).
Ahora, apliquemos al ejemplo del post sobre cifrado polialfabético este método.
Hacemos un conteo de las frecuencias de las letras (A=2, B=4, C=2, D=3, E=3, F=1, G=2, H=1, I=5, J=2, K=2, L=0, M=2, N=1, O=0, P=1, Q=3, R=5, S=4, T=3, U=9, V=2, W=6, X=0, Y=1, Z=1). Antes de continuar con el método, una observación: se puede apreciar que las frecuencias relativas difieren poco unas de otras (salvo alguna excepción), que es lo que dijimos que provoca un cifrado polialfabético.
Seguimos. Calculamos el índice de coincidencia, que a mi me sale de 0,049, y lo introducimos en la primera expresión (.027*65/(64*0.049 -.038*65 + .065)) y nos da un resultado de 2,4. La longitud de la clave, por tanto, debe ser cercana a 2 o 3. Si, tenéis razón: no hemos obtenido el resultado correcto (que es 4), pero es que hay que tener en cuenta que este es un método que mejora mucho con la longitud de los criptogramas. Aun así, no tendríamos que hacer muchas pruebas hasta que diéramos con la clave correcta, ya que el resultado nos ha orientado acerca de la longitud de clave. Combinado con el método Kasisky nos permite ir seleccionando longitudes de clave que se aproximen a este valor.
Bueno, con esto queda explicado el criptoanálisis del cifrado Vigenère. Espero que os haya gustado, aunque reconozco que este post puede hacerse un poco pesado.
Es muy divertido romper textos utilizando estos métodos. Una vez que se consiguen entender, su aplicación es muy sencilla y mas rápida de lo que parece. Este tipo de criptoanálisis me trae buenos recuerdos, ya que en mi examen de criptografía me pusieron un texto cifrado y tuve que aplicar estos dos métodos para romperlo, asi que por primera vez disfruté en un exámen.
Una curiosidad descubierta en la wikipedia mientras me documentaba un poco: la universidad donde estudió William F. Friedman fue Cornell, la misma en la que han sido profesores gente como (el grandísimo) Richard P. Feynman, (el ínclito) Carl Sagan, Diane Fossy o... ¡John Cleese!... ¡todo acaba otra vez en Monty Python! ;-)
El método Kasisky tiene el problema de que en muchas ocasiones las posibilidades de la longitud de la clave son demasiadas. Además, pueden existir coincidencias de secuencias en el texto cifrado que no sean representaciones de la misma secuencia en el texto en claro, lo cual dificulta enormemente encontrar la longitud de la clave, ya que la diferencia entre ellas no será múltimplo del tamaño de clave y por lo tanto nos confundirá.
Aún con esos problemas el método se estuvo utilizando tal y como lo vimos durante casi un siglo, hasta que un criptógrafo del ejército de EEUU, William F. Friedman (que a mi me parece que se da un aire al abuelo de la familia Monster), descubrió que podía hacer un cálculo con los índices de coincidencia de las letras para determinar la longitud de la clave de manera mas directa y precisa. Este método, además, es mucho mas versátil ya que se puede aplicar a todos los cifrados polialfabéticos.
Su ataque se fundamenta en que si en un texto de un lenguaje determinado elegimos dos letras al azar, la probabilidad de que sean la misma es conocida (por métodos estadísticos). Esto se puede comparar con los datos obtenidos de realizar la misma operación en el texto cifrado y de esta forma hacernos una idea de la cantidad de alfabetos que se han utilizado para cifrar el mensaje. Esto ocurre porque al quedar difuminadas las frecuencias relativas de las letras (que además estarán mas difuminadas cuantos mas alfabetos se hayan utilizado para cifrar) cambiará este índice de coincidencia. Es decir, si, por ejemplo, en el inglés la probabilidad del uso de la E es la mayor de todas. Entonces, si superponemos dos textos, la probabilidad de que coincida una E sobre otra será alta. En cambio, en un texto cifrado la probabilidad observada será mucho menor, y dependerá del número de alfabetos con el que esté cifrado.
Al final, todo esto se reduce a una fórmula (que saco directamente de la wikipedia):
Donde la I es el índice de coincidencia, que viene dado por la siguiente expresión de combinatoria:
... donde los distintos valores para las enes vienen dados por las frecuencias absolutas de las apariciones en el criptograma de las 26 letras del alfabeto inglés, n es la longitud del texto, y el 0.065 es la probabilidad de que dos letras al azar en un texto inglés sean las mismas.
Este método realmente funciona para cualquier cifrado polialfabético, y en su momento consiguió romper muchos de los cifrados de algunas máquinas de rotores utilizadas. (De las máquinas de rotores ya hablaré mas adelante).
Ahora, apliquemos al ejemplo del post sobre cifrado polialfabético este método.
Hacemos un conteo de las frecuencias de las letras (A=2, B=4, C=2, D=3, E=3, F=1, G=2, H=1, I=5, J=2, K=2, L=0, M=2, N=1, O=0, P=1, Q=3, R=5, S=4, T=3, U=9, V=2, W=6, X=0, Y=1, Z=1). Antes de continuar con el método, una observación: se puede apreciar que las frecuencias relativas difieren poco unas de otras (salvo alguna excepción), que es lo que dijimos que provoca un cifrado polialfabético.
Seguimos. Calculamos el índice de coincidencia, que a mi me sale de 0,049, y lo introducimos en la primera expresión (.027*65/(64*0.049 -.038*65 + .065)) y nos da un resultado de 2,4. La longitud de la clave, por tanto, debe ser cercana a 2 o 3. Si, tenéis razón: no hemos obtenido el resultado correcto (que es 4), pero es que hay que tener en cuenta que este es un método que mejora mucho con la longitud de los criptogramas. Aun así, no tendríamos que hacer muchas pruebas hasta que diéramos con la clave correcta, ya que el resultado nos ha orientado acerca de la longitud de clave. Combinado con el método Kasisky nos permite ir seleccionando longitudes de clave que se aproximen a este valor.
Bueno, con esto queda explicado el criptoanálisis del cifrado Vigenère. Espero que os haya gustado, aunque reconozco que este post puede hacerse un poco pesado.
Es muy divertido romper textos utilizando estos métodos. Una vez que se consiguen entender, su aplicación es muy sencilla y mas rápida de lo que parece. Este tipo de criptoanálisis me trae buenos recuerdos, ya que en mi examen de criptografía me pusieron un texto cifrado y tuve que aplicar estos dos métodos para romperlo, asi que por primera vez disfruté en un exámen.
Una curiosidad descubierta en la wikipedia mientras me documentaba un poco: la universidad donde estudió William F. Friedman fue Cornell, la misma en la que han sido profesores gente como (el grandísimo) Richard P. Feynman, (el ínclito) Carl Sagan, Diane Fossy o... ¡John Cleese!... ¡todo acaba otra vez en Monty Python! ;-)
martes, 2 de enero de 2007
lunes, 1 de enero de 2007
Suscribirse a:
Entradas (Atom)
