Computación e información cuánticas

Tras n días sin escribir (cuando n tiende a un número muy gordo) vuelvo con un plato fuerte: la computación e información cuánticas. Aún no tengo claro cómo iré estructurando los distintos posts a partir de este momento, espero que seais comprensivos. Por cierto, he vuelto a "relajarme" en la regla aquella que dije sobre la longitud de los posts. Leedlo en dos o tres sesiones, si os satura mucho :)

Cuando uno lleva tanto tiempo sumergido en un tema y tiene que explicarlo es muy difícil hacerlo de forma que el nivel de la explicación se adecué a los lectores. Quizá haya cosas que pueda dar por obvias y no lo sean tanto y otras en las que me exceda con la explicación. Me gustaría que en los comentarios me fuerais guiando (y que nadie se corte de decir "no me he enterado de nada" o "eso que dices es tan obvio que prefiero leer elmundo.es"...).

Se puede decir que el origen de la computación cuántica se encuentra a finales de los años 70 y principios de los 80. En ese momento la miniaturización de la tecnología estaba comenzando. Una de las personas que abrió camino en ese campo (desde el punto de vista teórico) fue Richard Feynman. En sus propuestas no solo planteaba la posibilidad de construir máquinas microscópicas, sino que también teorizaba sobre la miniaturización de los computadores y su límite mínimo, que lo llevaba a proponer la utilización de un átomo por bit.

Pero miniaturizar no es un proceso tan simple como parece, no basta con reducir las dimensiones. Hoy en día todos los circuitos de los ordenadores están compuestos de transistores. Éstos, simplificando, lo único que hacen es enviar flujos de electrones en un sentido o en otro activando así otros transistores. Podría pensarse que una posible reducción de estos transistores, y quizá la mayor, sería aquella en la que los flujos fueran de un solo electron, que se movería entre tres átomos. Esta práctica tendría asociados unos problemas adicionales tremendos. Por ejemplo, la incertidumbre cuántica nos impediría conocer con precisión el movimiento y la localización del electrón, que además podría dar saltos aleatorios entre todas sus localizaciones, haciendo inútil el transistor. Pero no hace falta ir tan lejos. Actualmente los circuitos de silicio tienen serias dificultades de funcionamiento cuando se reduce su tamaño (una de las causas es la electromigración). La conclusión de esto es que para miniaturizar no basta con reducir el tamaño: también hay que resolver nuevos problemas y, a partir de ciertos límites, buscar nuevos paradigmas de funcionamiento. Feynman, con una de sus famosas analogías, equipara esta evolución a la ocurrida en aeronáutica cuando se dieron cuenta de que no se podrían superar ciertas velocidades con la propulsión mediante hélices (Ácido Cínico seguramente tendrá mas que decir en este punto ;). Ese límite no fue superado hasta que se encontró un nuevo paradigma: el reactor, que permitía alcanzar velocidades que hasta entonces parecían imposibles.

En computación cuántica ocurrió algo parecido. Se buscaron nuevos paradigmas para poder miniaturizar hasta el átomo por bit. Esto supuso la mayor revolución que nos ofrece este campo ya que nos permite utilizar una partícula por bit, pero además nos ofrece la posibilidad de utilizar en nuestro beneficio las particularidades de la mecánica cuántica. Nos olvidamos de los transistores y en su lugar utilizamos el estado de partículas individuales para representar los bits (por ejemplo, podríamos utilizar el sentido del spin de un electrón).

(... Perdonadme por los párrafos que vienen a continuación, pero es que no soy capáz de simplificar mas...)

Mientras que en computación convencional tenemos como unidad mínima el bit, en la computación cuántica utilizaremos lo que se conoce como el qubit. En mecánica cuántica, el estado "n" de una partícula se representa mediante un ket . Entonces, aplicando esto al terreno de la computación, definiremos dos estados ortogonales, que serán los equivalentes del "1" y el "0", que estarán representados por y .

La primera ventaja que nos ofrece la computación cuántica es la posibilidad de poder utilizar el principio de superposición cuántica, mediante el cual una partícula puede tener a la vez dos estados distintos. Esto quiere decir que nuestro estado no tiene porqué ser o sino que puede ser algo como

Es decir, tenemos un bit, que es 1 con probabilidad a² y 0 con probabilidad b² (evidentemente, a²+b²=1). Esto (además de liar un poco las cosas) nos permite hacer operaciones con ambos estados a la vez(¡!).

Pero también hay otra propiedad de la mecánica cuántica clave: el entrelazamiento cuántico. Que dos partículas estén entrelazadas se puede entender como que el estado de una depende directamente del estado de la otra. Es decir, dos bits separados podrán tener estados y , por ejemplo, y si los entrelazamos el estado pasa a ser único (pero sigue implicando a las dos partículas) y lo llamamos .

Si combinamos el entrelazamiento con el principio de superposición, tenemos estados compuestos, como por ejemplo:

Este estado contempla tan solo dos posibilidades, que ambos bits valgan 1, con probabilidad a², o que ambos bits valgan 0, con probabilidad b².

Estas dos propiedades de la computación cuántica nos permiten inicializar un registro con todas las opciones posibles al principio y realizar operaciones sobre todas al mismo tiempo. Por ejemplo, inicializamos el registro de tres bits:

Entonces, realizando operaciones sobre el registro podremos modificar las probabilidades (a²,b²,c²..., h²) de forma que el resultado correcto tenga una mayor probabilidad de aparecer cuando al final realicemos una lectura.

Esto deja entrever el primer problema que nos encontramos en la computación cuántica: los resultados son probabilísticos. Podemos hacer que la probabilidad del resultado correcto aumente mucho, pero siempre existirán posibilidades de leer un resultado incorrecto. Además no podemos saber qué probabilidad tenía el estado que hemos leido por lo que no sabremos que no es el correcto. En la práctica esto hace que los circuitos de corrección de errores sean, a falta de un mejor adjetivo, monstruosos; para trabajar con los 64 bits de la computación convencional actual necesitaríamos del orden de las decenas de miles de qubits.

Aquí lo dejo por el momento. Ya hay bastantes conceptos en el post como para pensar un buen rato en ello. Próximamente escribiré sobre algunos algoritmos específicos de computación cuántica que la convierten en un salto cualitativo con respecto a la tradicional. Mas tarde comenzaré con la primera aplicación madura de este campo: la criptografía cuántica.

Aleatoriedad (II)

En este post (continuación del anterior sobre aleatoriedad) voy a ser mucho mas práctico y comentaré tres formas de conseguir datos aleatorios bastante extendidas hoy en día.

Suponed que tenéis un átomo de un elemento radiactivo; es posible saber cuál es la vida media, pero lo que no es posible conocer de ninguna manera es el momento exacto de su desintegración. Es cierto que, aunque ese momento sea aleatorio, seguirá una distribución de probabilidad conocida, con lo que de por si no valdría como generador aleatorio. Por lo tanto un solo átomo no sirve, pero imaginad que tenemos una cantidad enorme de ellos. En este segundo caso podemos hacer observaciones de las desintegraciones, y lo que si sigue una distribución completamente aleatoria es la diferencia de tiempo entre una y otra. Por lo tanto, con un contador geiger conectado a un reloj, y algún postprocesado (que no es especialmente complejo) tendremos un generador verdadero de números aleatorios... bueno, al menos hasta que la mecánica cuántica aguante. Una cosa buena de este método es que cualquiera se lo puede fabricar en casa comprando un detector de humos (si, esas cosas que están en el techo de los edificios tienen fuentes de emisión de partículas alfa: lo digo como dato, no es para nada peligroso) y el detector.

Aunque la radiación alfa es la mas dañina de todas es también muy fácil protegerse de ella (un par de centímetros de aire o una lámina de papel valen) y por lo tanto no es especialmente peligroso el manejo de esas fuentes.

Hay otra forma de realizar un generador de aleatoriedad basándonos en fotones que nos proporciona una velocidad mucho mayor, aunque no puede hacerse en casa. Imaginad que polarizamos un flujo de fotones individuales en una dirección determinada (supongamos que es en vertical). Si hacemos atravesar a los fotones un filtro que solo deje pasar los polarizados en 45º resultará que la mitad de los fotones pasará y la otra mitad se reflejará. Si colocamos apropiadamente dos detectores de fotones (uno para los que pasan y otro para los que reflejan) ya tenemos nuestra fuente de números aleatorios (binaria, en este caso).



Hay sistemas comerciales que utilizan este principio (la imagen anterior es del Qantis de idquantique). El problema que tienen es que es complicado polarizar fotones en una dirección que se diferencie exactamente pi/4 con el filtro y, sobre todo, es complicado enviar fotones individuales, por lo que también necesitan un postprocesado para evitar sesgos.

Pero hay una forma mucho mas curiosa (y realizable por cualquiera en su casa) de construirse un generador de números aleatorios basándonos en la radiación de fondo. Basta con conectar una radio o televisión a un pc y sintonizarlo en una frecuencia en la que no haya nada (asegurarse de esto no es tan sencillo y previamente habría que ponerle ciertos filtros). Con un postprocesado de la señal similar al que necesitan los métodos anteriores tendremos nuestro propio generador de números aleatorios. Lo curioso de este método es que además, sabiendo que aproximadamente un 1% de ese ruido es producido por la radiación de fondo cósmica, ¡podremos presumir de que nuestra clave proviene del mismísimo Big Bang!

Aleatoriedad (I)

El otro día, mientras compraba en Alcampo, me fijé en mis movimientos caóticos para realizar las compras. Después de tantos años, conozco bastante bien dónde se encuentra cada producto aproximadamente, pero soy completamente incapaz de hacer una compra ordenada si no estoy concentrado en ello. Me recordó una investigación sobre la que me habló un amigo en la que utilizaban los movimientos de las moscas para generar números aleatorios.

Es curioso que a la aleatoriedad no se le dé el valor que realmente tiene. Es extremadamente complicado hacer un generador de aleatoriedad, por rara que pueda parecer esta afirmación. Todo el mundo pensará inmediatamente en que tirar dados, lanzar una moneda al aire, etc, son sucesos aleatorios. Pero esto desde un punto de vista físico no es cierto. De hecho lo mas que podemos aspirar es a tener un generador de números virtualmente impredecible (aquí es donde encaja la famosa mariposa que mueve las alas en algún lugar del mundo). Es decir, generadores que se vean afectados por tantas variables que sea imposible en la práctica predecir su comportamiento (mi caso con la compra en Alcampo sería un ejemplo débil de esto).

Pero no está todo perdido. Hay algo que sí que es intrínsecamente aleatorio y no sujeto a variables externas: la incertidumbre cuántica. (En este punto puedo hacer dos cosas: dar por supuesto que todos teneis nociones básicas de mecánica cuántica o empezar a escribir otro blog sobre un tema que ni siquiera domino. Elegiré la primera ;)

Los que hayáis llegado aquí (es difícil aguantar tanto, lo reconozco: ha aparecido la palabra "cuántica", y no he metido ningún dibujo ni ningún chiste) os preguntareis porqué narices os cuento todo esto y, sobre todo, porqué tiene el post tiene la etiqueta de "criptografía". Es simple: la aleatoriedad es esencial para la seguridad de un sistema criptográfico. Los ataques pueden ir, por supuesto, dirigidos al algoritmo, pero también pueden ir dirigidos a la clave. Si la clave no es todo lo aleatoria que debería, el protocolo se resiente (podemos tener el mejor algoritmo, pero si luego como clave elegimos, por ejemplo, nuestro nombre será trivial encontrarla para un atacante).

Y aquí hay que tener mas cuidado del que puede parecer, ya que puede haber secuencias de números que tengan una apariencia aleatoria pero que no lo sean en realidad. Para comprobar esto existen una serie de tests que nos permiten medir este parámetro (métodos probabilísticos que serían largos de explicar aquí).

Pero además esto tiene un debate mas filosófico. En un universo determinista (un universo "clásico"), la aleatoriedad no parece posible. Por suerte la mecánica cuántica nos condujo de nuevo a un universo no determinista (en el que la criptografía puede ser completamente segura). Por cierto, no viene muy al caso pero me apetece contarlo: a Einstein no le gustó esa idea ("Dios no juega a los dados") y perdió muchos años de su vida intentando demostrar que era falsa, hasta que al final la aceptó. Y esto es realmente curioso, porque precisamente él fue quien dio la descripción del movimiento browniano, que es un movimiento aleatorio.



Bueno, de momento lo dejo aquí. Perdonad por la extensión y la rallada, aunque he de confesar que es mucho peor de lo que pensais: el post me ha quedado tan largo que después de escribirlo lo he dividido en dos, asi que os queda una segunda parte que pondré en próximas fechas.

Criptografía asimétrica (o de clave pública)

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 :).

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! ;-)

GDKOACNYNHKYJDSK

GDKOAZMUENRSJKROFSDGUNCUT
KNYMDBZPQDYZTMISHOZPEZTUD
OGSZPAJDMKTBQOCZKGDKZBF

El criptoanálisis del método Vigenère

Por fin, con un retraso digno de Lucia alguien que se retrase mucho, llega el post sobre criptoanálisis.

Bueno, supongo que tod@s vosotr@s, querid@s lector@s (la chorradita esta de la @ para hacerse el políticamente correcto a veces tiene su punto, pero cansa mogollón), tendréis estudiado el método de cifrado polialfabético Vigenère, ya que debéis entenderlo para seguir esta explicación.

Como recordareis, se habló de que el método César se puede descifrar sin conocer la clave haciendo un análisis de frecuencias (un criptofante para Gema), cosa que inmediatamente nos revela el desplazamiento (la clave) utilizado. Como el método Vigenère utiliza múltiples desplazamientos y no tiene una longitud fija de clave, esa frecuencia relativa queda difuminada, de manera que un análisis de frecuencia no nos revelará nada.

Pero si que existen patrones que nos pueden dar pistas sobre cómo romper el algoritmo. Y es que, en los idiomas no sólo se repiten mas unas letras que otras, sino que también se repiten mas unas secuencias que otras. En español, por ejemplo, se repetirá mucho mas la secuencia "los" que la secuencia "wes" sin ninguna duda. ¿Y cómo podemos aprovechar esto? Pues fácil, si tenemos la suerte de que dichas secuencias coinciden con que estén cifradas con los mismos caracteres de la clave, ya que producirán criptogramas iguales que se repetirán a lo largo de todo el texto cifrado. Entonces, mirando las distancias entre dichas repeticiones tendremos información sobre la longitud de la clave, ya que deben ser múltiplos de la misma.

De esto se dió cuenta un criptógrafo militar prusiano a mediados del siglo XIX (fijaos lo que duró la consideración de "indescifrable" del método Vigenère) llamado Friedrich Kasiski.

Vamos a ver un ejemplo de la utilización del método:

mensaje:"Shut up. Shut up! Shut up! You can't have egg, bacon, spam and sausage without the spam"
clave: "abcd"
criptograma: "SIWWUQUKUUWSSIWWUQARUDCQTICYEF IJBBERNTRDMBPGSBWVAHGZIUJRUUVKETRDM"

He señalado en negrita las secuencias que se repiten. Podemos ver que se repite "SIWWUQ", que corresponde al primer y tercer "Shut up", y "TRDM" correspondiente a las dos apariciones de "spam". La separación entre las primeras repeticiones es de 12 posiciones, y de 24 entre las últimas. Como hemos dicho antes, estos números deben ser múltiplos de la longitud de la clave. Por lo tanto, descomponemos los números en factores primos: 12 = 2x2x3, 24= 2x2x2x3. Esto nos indica que la clave puede tener las longitudes de 2, 3, 4 (2x2), 6 (2x3) o 12 (2x2x3).

Debemos elegir una de las longitudes, y no queda mas remedio que hacerlo por prueba y error. Descomponemos el criptograma en subconjuntos en función de la longitud elegida y luego hacemos un análisis de frecuencia de letras para determinar el desplazamiento utilizado en cada uno. Es decir, si probamos con una longitud de 2, tendremos que las posiciones pares están cifradas con un alfabeto y las impares con otro y sabemos atacar a ambos conjuntos por separado, ya que no son mas que dos cifrados César. Una vez que tengamos todos nuestros subconjuntos resueltos tendremos la clave final.

Voy a dejarlo aquí porque el post ya me está quedando muy largo, asi que dejaré para los próximos algunas cosas que quería comentar. Lo que si que no me aguanto a decir es que la frase elegida para cifrar, por si os lo habeis preguntado, es de un sketch de Monty Python. Este sketch tiene la curiosidad de que es la causa por la que al correo basura se le conoce como "spam".

El principio de Kerckhoff

Como comentaba hace dos posts, sí es posible romper el cifrado Vigénere. Aunque pueda parecer que esto tiene tan solo un carácter educativo en realidad no es así. Ocurre que la gente que no está familiarizada con la criptografía suelen pensar que es sencillo crear su propio algoritmo criptográfico basando gran parte de la seguridad en hacerlo secreto, y en la mayoría de las ocasiones pasa por ser, a lo sumo, una variación de un cifrado polialfabético. En estos casos se puede llegar a romper este tipo de códigos con un simple criptoanálisis clásico. No voy a hablar aquí de momento sobre estos métodos (lo dejaré para el siguiente artículo).

Sí quería comentar en este post una de las máximas de la criptografía, conocida como el principio de Kerckhoff: "un criptosistema debe ser seguro incluso si todo lo relacionado con el funcionamiento del sistema, excepto la clave, es de conocimiento público". Es decir, que un algoritmo no debe basar su seguridad en que no se conozca por completo su funcionamiento, sino que la seguridad debe residir estríctamente en un secreto compartido en forma de clave entre emisor y receptor. Lo contrario es lo que se conoce por "security through obscurity" y es un error de principiante. Por ejemplo, la escritura con jugo de limón que todos hemos hecho de pequeños (aunque según cómo se haga podría llegar a entrar en el terreno de la esteganografía).

Lo triste es cuando el que busca seguridad con jugo de limón no es un niño jugando al amigo invisible sino una empresa de software que pretende ofrecer soluciones serias en el campo de la seguridad. Hay innumerables casos de estas malas práxis (seguramente algunos leereis esto desde un sistema operativo de Microsoft, todo un ejemplo de "insecurity" a pesar de la "obscurity"). También podemos encontrar entre ellos el famoso cifrado A5 con el que funcionan los móviles GSM, que quedó roto cuando se comprendió su funcionamiento mediante técnicas de ingeniería inversa; por lo que hoy en día cualquiera que se pueda permitir la compra del equipo necesario (que se vende por internet) puede escuchar el contenido de cualquier conversación realizada con un teléfono móvil. Quizá no tan cercano a nosotros pero con implicaciones muy serias en la sociopolítica internacional podemos hablar sobre las máquinas de voto utilizadas en las elecciones en el país autoproclamado líder del mundo libre; las cuales, por cierto, llegaron a contabilizar totales negativos para el candidato demócrata Al Gore en algunos colegios de Florida (recomiendo a este respecto un documental, titulado "Hacking democracy", en el que además de comentar ésto demuestran la facilidad con la que se pueden manipular dichas máquinas).

Bueno lo dejamos aquí por hoy, que es nochebuena y tampoco quiero saturar.

El cifrado polialfabético Vigenère

Ahora me gustaría escribir una serie de posts con los que espero que disfruteis tanto como yo lo hice en su momento. En este explicaré el cifrado polialfabético, en el siguiente explicaré una técnica de criptoanálisis para este tipo de cifrados (vereis lo tremendamente divertido que es romper un texto cifrado). Del tercero aún no diré nada. Con esto dejaremos atrás mas de dos mil años de criptografía y comenzaré con cosas mas modernas.

Es curioso que hasta el siglo XVI no surgiera este cifrado, cuando no es mas que una extensión lógica del cifrado César; este hecho dice mucho sobre la sociedad europea desde la caida del imperio romano hasta ese momento.

La diferencia principal con el método César radica en que si antes utilizábamos un desplazamiento igual para todos los caracteres del mensaje, en este nuevo método utilizaremos uno distinto para cada carácter en función de la clave. Dicha clave además adquiere una longitud arbitraria en lugar de ser de longitud uno exclusivamente. Un ejemplo:

Mensaje: "a la de tres atacamos"
Clave: "bletchley"

Pues bien, para cifrar este texto hacemos lo siguiente: para la 'a' utilizamos el alfabeto indicado por la letra 'b' de la clave, para la 'l' el indicado por la 'l' de la clave... Cuando nuestra clave se agote (al cifrar la 's' con el alfabeto de la 'y') volvemos a empezar la clave (cifrando la 'a' de "atacamos" con la 'b' de la clave). Perfecto, pero nos falta saber cómo se aplica dicha clave. Es sencillo, basta con mirar en esta tabla el carácter que aparezca en la unión de la fila (o columna) del del texto en claro con la columna (o fila) del correspondiente en la clave:



El texto cifrado quedaría así:

Texto: "aladetresatacamos"
Clave: "BLETCHLEYBLETCHLE"
Criptograma: "BWEWPACIQBE..." (me da pereza seguir ^_^)

Para descifrar basta con mirar en la columna (o fila) correspondiente a la letra de la clave en qué posición aparece la letra del criptograma y ver a que fila (o columna) corresponde.

Como podeis ver, este método, como los anteriores, tan solo proporciona confidencialidad. A pesar de ésto, el cifrado de Vigenère supone un gran avance con respecto al César ya que al no conservar las frecuencias relativas de las letras el ataque no es tan trivial (de hecho se llegó a considerar como indescifrable en un principio). No obstante, se puede atacar también mediante métodos estadísticos. Pero eso es otra historia y debe ser contada en otra ocasión (en el siguiente post).

NOTA: La imágen está sacada de la wikipedia.

El cifrado César

Aunque es conocido por el nombre del famoso Julio César se sospecha que en realidad no fué utilizado por él, aunque si por otros emperadores menos famosos.

La mecánica del método es muy sencilla. Tan simple como ir cogiendo uno a uno los caracteres del mensaje e irlos sustituyendo por el que corresponda a un desplazamiento determinado. Es decir, miramos la posición que ocupa dicho carácter en el alfabeto, le sumamos el desplazamiento y escribimos el carácter que se encuentra en la posición resultante. Evidentemente esto lo hacemos de manera circular, es decir, si tenemos un alfabeto de 27 letras y la suma de la posición mas el desplazamiento es, por ejemplo, 28, corresponderá a la letra en posición 1.

Un ejemplo:

Alfabeto: abcdefghijklmnñopqrstuvwxyz
Clave: 2
Mensaje: "bletchley park es un blog muy chulo"
Criptograma: "DNGVEJNGARCTMGUWODNQIÑWAEJWNQ"

Para descifrar el mensaje basta con conocer la clave ("2") y hacer el proceso inverso: restar la clave a cada carácter.

Mensaje descifrado: "bletchleyparkesunblogmuychulo"

Como podeis ver, también es un método tremendamente sencillo (y poco seguro), pero al contrario que el método de la escitala espartana, que era de trasposición, este es un método de sustitución. Y en relación a esto os hago una pregunta:
Si interceptais a un mensajero con un criptograma, ¿cómo podríais saber si está cifrado con cifrado César o con el método de la escitala espartana? De manera mas general: ¿cómo reconoceríais la diferencia entre un texto cifrado por un método de trasposición y por otro de sustitución? No hace falta utilizar métodos de CSI para saberlo... ni tampoco hace falta ser violentos con el mensajero.

Funcionalidades

Hasta el momento no he planteado este problema: ¿qué podemos pedirle a la criptografía? Me explico: hasta ahora sólo he hablado de que la criptografía permitía el envio de mensajes de manera que unicamente un destinatario legítimo pueda leer el conenido. Esto se conoce como confidencialidad, y obviamente es el primer objetivo que queremos conseguir.

Pero también hay otras cosas importantes cuando hablamos de enviar mensajes. Por ejemplo, mirando el método anterior (la escitala espartana) vemos claramente que proporciona confidencialidad (de una manera mas o menos fiable). Pero si nos ponemos en el lado del receptor del mensaje ¿estamos seguros de quien nos envia el mensaje? Si un adversario intercepta al mensajero y, de alguna forma, consigue descubrir el método de cifrado y el grosor del bastón (la clave), bien puede enviarnos otro mensaje haciéndose pasar por nuestro amigo. En ese caso no hay forma de saber que estamos siendo engañados. Esto es porque el método no ofrece autenticidad.

Pero no nos vayamos tan lejos. Imaginad que quien ha interceptado el mensaje no ha sido capaz de saber cual es el método ni la clave. Al menos puede coger el mensaje y cortarle un trozo asegurándose de que lo que nos va a llegar es algo incomprensible. Como destinatarios no tendríamos forma de saberlo. El método tampoco asegura integridad en los mensajes.

Ahora poneos en la situación en la que ni siquiera nos han interceptado al mensajero. Nuestro colega militar ha decidido hacer un movimiento que no es muy inteligente, pero como tenemos un rango inferior tenemos que hacerle caso (ya sabeis como son los militares: si no lo hacemos aparecerá algún héroe y dirá eso de: "señor, queda usted relevado del mando de esta unidad" y no podremos hacer nada por mucho que gritemos eso de "¡ya nos veremos en su consejo de guerra!"). Cuando vayamos a rendir cuentas a nuestra ciudad y nos quieran cargar con la responsabilidad podríamos decir que el fallo ha sido suyo... pero no sería muy inteligente ya que él puede argumentar que el mensaje que hemos recibido no ha sido escrito por él sino por el enemigo (utilizando la misma clave). Y lo que es peor: en realidad no podemos saber si esto es cierto o no. El método no ofrece la funcionalidad de "no repudio" (que se conseguiría firmando de alguna manera el mensaje).


Pero hay otra cosa mas que el método no nos ofrece (y realmente es difícil de ofrecer en cualquier caso) y es la disponibilidad de la información (los escasos comentarios de la anterior entrada proponían métodos de ataque sobre esta funcionalidad). Es muy fácil capturar a los mensajeros y, aunque no descifremos el mensaje ni simulemos ser el origen autorizado, siempre podemos matarlos y quemar el mensaje, haciendo que no esté disponible para el destino legítimo (es uno de los famosos ataques por denegación de servicio).

La escitala espartana

Dejamos de momento mas conceptos que tengo que explicar y paso a contar una técnica muy primitiva de enviar mensajes secretos, conocida como la escitala espartana. El orginen parece que se remonta al año 400 antes de Cristo en la antigua Grecia y fue inventado, o al menos utilizado de manera regular, por los ejércitos espartanos.

Es un método de transposición. Esto quiere decir que el algoritmo de cifrado no sustituye letras o conjuntos de letras por otras sino que "baraja" el mensaje para hacerlo irreconocible.

¿Y cómo consiguen hacerlo? Imaginad una vara sobre la que enrollais una cinta de papel. Si el mensaje se escribe longitudinalmente, y teniendo la precaución de escribir un solo carácter por línea, quedará desordenado sobre la cinta de papel. Si el mensajero es interceptado sólo encontrarán una cinta de papel con caracteres que no tienen ningún sentido. Para recuperar el mensaje basta con tener un bastón del mismo diámetro.

Vale, ahora me pregunto: ¿qué ofrecía este método a los militares griegos? Pues ofrecía cierta confidencialidad en el envío de mensajes. ¿Pero en qué se basaba dicha confidencialidad? Pues en realidad en el conocimiento del grosor del bastón.

Y ahora una pregunta que dejo al aire: si soy de un ejército rival e intercepto un mensajero ¿qué puedo hacer con el criptograma en mis manos?

Conceptos previos

Bueno, aquí estoy de nuevo. Estoy tardando en postear por diversas razones, llevo unos días con poco tiempo libre y para escribir quiero hacerlo con tiempo y relax. Además, cuando pienso en todo lo que quiero contar sobre criptografía no sé por dónde empezar.

En fin, "vayamos por partes", que dijo Jack el Destripador. Empezaré hoy definiendo diversos conceptos básicos porque es mejor que se tengan claros antes de seguir con el resto de cosas.

Del griego kriptos (oculto), la criptografía se podría definir como la escritura oculta. Es decir, la capacidad para transmitir información de forma que no pueda ser leida nada mas que por su destinatario. Aunque originalmente se utilizaba para definir tan solo el cifrado, hoy en dia la palabra engloba toda la ciencia de la escritura oculta.

Por cierto, el verbo correcto en español es cifrar (y descifrar) y no encriptar (y desencriptar) como se suele escuchar (por una traducción a piñón del inglés encrypt y decrypt). Suelo ser bastante pesado en este punto y hago que el peso de la RAE recaiga sobre aquél que osa meter cosas en criptas en lugar de ocultar mensajes.

Seguimos definiendo términos y nos encontramos con los nombres que se da a la información que queremos transmitir. Cuando el mensaje no está cifrado se le denomina "texto en claro" (plaintext en chéspir) y cuando está cifrado se le conoce como criptograma.

Repasemos. Ya tenemos a Alice que quiere enviar un mensaje secreto a Bob. Cifra su texto en claro y manda el criptograma a Bob, que tras descifrarlo obtiene a su vez el texto en claro original. ¿Qué pasa si alguien no legítimo quiere leer el mensaje? Pues que deberá recurrir al criptoanálisis, la rotura de los códigos, una de las partes mas interesantes de la criptografía.

¿Por qué he hablado de una tal Alice y un tal Bob? Pues es muy normal cuando se explican conceptos de criptografía. En lugar de utilizar "A quiere enviar un mensaje a B" se utilizan nombres que empiecen por las mismas letras. Alice siempre es quien tiene la información, Bob es quien quiere recibirla. También normalmente suele encontrarse a dos personas que quieren robar la información: Eve y Mallory. Eve se utiliza por el término inglés "eavesdropper" y suele ser un elemento pasivo, mientras que Mallory puede interceptar y modificar los mensajes. Si en el esquema hacen falta mas personas se siguen eligiendo nombres. En la wikipedia tienen una recopilación de los mas comunes. Parecerá una tontería, pero es una forma muy útil de hacer mucho mas comprensibles las situaciones.

Para terminar, al lado de la criptografía y muy relacionada con ésta podemos encontrar la esteganografía. Ambas se encargan de ocultar mensajes, pero de manera distinta: la primera oculta el mensaje transformándolo en algo incomprensible, mientras que la esteganografía oculta el mensaje escondiéndolo de la vista de quien no sabe buscarlo. Un ejemplo muy básico de esteganografía se puede ver en la serie Prison Break, cuando Lincoln Barrows recibe una carta de su abogada en la que está oculto un mensaje de su hijo que se puede leer escogiendo las últimas palabras de cada línea de texto. La esteganografía tiene la ventaja de que puede pasar desapercibida y ser confundida con un mensaje sin valor. Por ejemplo, durante mucho tiempo los espias se han transmitido información en las secciones de clasificados de los periódicos. Hoy hay métodos mas rápidos: hace poco se habló de que en imágenes de productos de ebay se habían encontrado mensajes esteganografiados.

Bueno, con esto quedan resumidos los conceptos mas importantes. Pronto, mas cosas.

Bletchley Park

He empezado ya tres veces esta entrada, y cada vez que me pongo a escribirla me da miedo. Son muchas cosas las que podría contar aquí, asi que he llegado a la determinación de que voy a intentar ser breve (recordad el punto dos del decálogo) y al final pondré unas referencias para que quien tenga mas interés y mas tiempo pueda ampliar la información.

Para entender qué fue Bletchley Park debemos remontarnos al periodo de entreguerras en Europa. Los alemanes, ante la pasividad de los franceses e ingleses (y la preocupación de los polacos), están realiazndo discretamente la reconstucción de su ejército. Pero tras el tratado de Versalles esto no era muy legítimo, por lo que los Alemanes tenían que mantenerlo lo mas en secreto posible. Para ello, compraron una modificación de una máquina de cifrado comercial que llevaba en el mercado desde 1918 con un éxito relativo. La máquina en concreto es la famosa Enigma, de la que espero hablar otro día mas detenidamente.

Cuando la segunda guerra mundial estalló el ejército alemán estaba perfectamente reconstruido y preparado (además de la población alemana tras un largo periodo de crisis y de pagos millonarios al resto de los paises europeos). Pero además tenían algo que el resto de Europa tardó en temer mas de lo que hubiera sido prudente: las evoluciones de la máquina Enigma constituian, por aquel entonces, el mejor sistema de cifrado de la historia de la humanidad. (Por cierto, los polacos si que supieron ver la amenaza y empezaron a trabajar en los códigos de Enigma seriamente antes de que empezara la segunda guerra mundial; evidentemente Polonia se encontraba mas amenazada por el naciente nazismo).

El caso es que incluso una vez iniciada la guerra los ingleses no valoraban lo suficiente a su sección de criptografía, en funcionamiento desde la primera guerra mundial, incluso hasta el punto de que su director, sir Hugh Sinclair, no fue capaz de que el gobierno le financiara las instalaciones necesarias para desarrollar su labor.

A unos 90 kilómetros al noroeste de Londres se encontraba Bletchley Park, una mansión construida en 1711. Por su situación era un lugar ideal para un servicio de inteligencia: Se encontraba en un pueblo pequeño, suficientemente lejos del ajetreo de Londres pero lo suficientemente cerca como para no estar aislado (tenía línea de ferrocarril directa). Estaba a su vez cerca de las universidades de Cambridge y Oxford; y la lejanía con Londres le separaba de posibles objetivos de bombardeos y además hacía que su existencia fuera facilmente mantenida en secreto.



Así que el almirante Sinclair decidió comprar de su propio bolsillo la mansión y construir los barracones adyacentes (se fueron construyendo poco a poco a medida que fue creciendo el personal involucrado). Además, reclutó a las mejores mentes del país para trabajar en el criptoanálisis de los códigos alemanes. La persona mas conocida quizá es Alan Turing, un matemático del que espero hablar en otra entrada algún día (tuvo una vida interesante con un final trágico).

El caso es que se puede decir que gracias a Bletchley Park y a la gente que trabajó allí los aliados ganaron la guerra (o como poco adelantaron el final), pero curiosamente permanecieron en el anonimato hasta finales de los años 70 cuando el gobierno desclasificó la información sobre la mansión. El mayor logro conseguido fue romper el código de las máquinas Enigma, con una inestimable ayuda, también es justo reconocerlo, de los criptógrafos polacos.



Entre las referencias en el cine a la mansión se pueden destacar dos películas: "Enigma", basada en una novela; y "U-571", que narra con algunas imprecisiones el capítulo en el cual los aliados consiguieron un libro de claves de la Enigma. Algunos libros que hablan sobre este episodio son: "The codebreakers", de David Kahn, es un libro que cuenta la historia de la criptografía (con un precio desorbitado y sin traducción al español); y "Los códigos secretos", de Simon Singh, otra historia de la criptografía mas amena y resumida (agotado en la editorial y sin intención de sacar una nueva edición, pero si lo fotocopiais la cultura se morirá). También en la novela de ficción de "El criptonomicón" (uno de cuyos personajes principales es Alan Turing) algunos capítulos se desarrollan. En internet, por supuesto, el artículo sobre Bletchley Park en la wikipedia (de donde ha salido la foto que decora mi blog). Y no me puedo olvidar la serie de artículos dedicados a la máquina Enigma escritos por Román Ceano y publicados en Kriptópolis, muy completos e interesantes.

Bueno, ahora ya sabeis el porqué del nombre del blog: como apasionado de la criptología quería rendir un homenaje a la gente que participó en uno de los momentos cumbre de la historia en ese campo. Como el post ya es bastante largo (un tirón de orejas para mi por no respetar mis mandamientos en el 50% de los posts que llevo escritos) dejaré para el futuro algunas cosas que me habría gustado comentar.