-[ 0x05 ]--------------------------------------------------------------------
-[ Del PGP a un Foton. Presente y Futuro ]-----------------------------------
-[ by SiuL+Hacky ]----------------------------------------------------SET-21-


                DEL PGP A UN FOTON. PRESENTE Y FUTURO.
                ======================================

En el pasado numero de SET (20), Falken a~adio al articulo de Homs una
breve introduccion sobre criptografia cuantica que me ha "motivado" a hacer
una pausa en el curso de cracking bajo linux, y extenderme un poco mas en ese
y otros temas estrechamente relacionados.

Llamaba ciertamente la atencion la noticia aparecida (en la edicion
electronica al menos) el pasado 29 de Septiembre en el Sunday Times 

http://www.sunday-times.co.uk/news/pages/tim/99/09/
                    29/timintint02001.html?1341861

En resumen venia a decir que segun noticias filtradas por el Instituto
Israeli Weizmann, tenian disponible un dispositivo (incluso un dispositivo de
mano) que rompia el codigo RSA-512 bits en 12 microsegundos. Para tan noble
tarea, utilizaba un dispositivo mezcla de procesamiento optico y de computacion
cuantica.

Que nadie se alarme, a pesar de que en criptografia nada se puede asegurar,
era una patra~a sensacionalista. El articulo estaba firmado por un tal Ben
Hammersley, y era un batiburrillo de ideas mal pegadas. Mezclaba seguramente
la noticia aparecida meses atras, donde se presentaba un dise~o de un

http://www.rsa.com/rsalabs/html/twinkle.html

dispositivo electro-optico para atacar el citado sistema, con algun articulo
leido en la red. Por cierto, este dispositivo electro-optico, a pesar de
todo, dejaba las claves de 768 y 1024 bits como inabordables. La noticia del
Sunday es falsa; en primer lugar porque este tipo de hallazgos no se filtran
(y menos por los israelies), en segundo porque no existen ordenadores
cuanticos de ese numero de bits, y en tercero porque ni mucho menos estaria
disponibles en un sistema de mano.

A pesar de que no pasa de ser ejercicio de sensacionalismo, podria ser en un
futuro mas o menos lejano algo cierto. La base teorica, existe, pero de
momento no se sabe como llevar a cabo satisfactoriamente. El que la
seguridad de las claves RSA (por ejemplo) se vea completamente en
entredicho, vendria de la mano de la casi recien nacida: COMPUTACION
CUANTICA.

COMPUTACION CUANTICA -------------------------------------------------------

Es indudable el exito que han alcanzado hoy en dia los computadores
digitales electronicos. La miniaturizacion ha llevado a los micropocesadores
a un papel crucial dentro de la actual era tecnologica. Probablemente ni
Intel (ni los japoneses que les encargaron el proyecto), ni nadie,
sospechaba que la tecnologia pudiera evolucionar hasta la cotas actuales.
Esto da idea de lo dificil que es anticipar el desarrollo de los avances
tecnologicos. Esta situacion tiende a hacer creer la idea de que todo es
simulable y computable. Aquellos problemas en los que no se ha tenido exito
todavia (como la realidad virtual), parece que se solucionan dejando pasar
el tiempo y que el aumento de la velocidad de procesamiento haga el resto.

Pero realmente ¿ todo es computable ? No parece que desde la primera mitad
del siglo, cuando Turing y Church expusieron sus teorias, se halla avanzado
mucho en estos aspectos teoricos. Se puede dar como buena la proposicion
conocida como "Tesis de Church": todos los dispositivos computacionales se
pueden simular mediante una maquina de Turing. Esta proposicion no deja sin
embargo una definicion clara de lo que seria un dispositivo computacional.
De cualquier forma, si que parece haber acuerdo en que todo NO es
computable, o para ser mas preciso, no todo es eficientemente computable.
Esta ineficiencia, no seria una cualidad propia de un dispositivo particular
(por ejemplo, un dispositivo no optimizado), sino que afectaria a todos
ellos. En el terreno de otros temas mas delicados, como la inteligencia, o
la consciencia, no parece nada claro si podran ser alguna vez simulables.

Se suele poner el limite de las "cosas" eficientemente computables, como
aquellas que contando con un numero de elementos variables N, los recursos
consumidos para su computacion, incluido el tiempo, dependen polinomicamente
de N. Por ejemplo, supongamos un sistema cuya computacion requiera:

N^2 + 6*N^3 + N^10 recursos

(N^2 significa N elevado a 2)

para N=3 elementos tendriamos 3^2 + 6*3^3 + 3^10 = 59220 recursos
para N=6 elementos tendriamos 6^2 + 6*6^3 + 6^10 = 60467508 recursos

parece que crece rapido, bueno pues esto SI es eficientemente computable.
Hay otros problemas, cuyos recursos no crecen polinomicamente, sino
exponencialmente con el numero de elementos N. Un ejemplo muy conocido es el
de la factorizacion de numeros, en el que se basan las claves RSA. Hallar
los factores primos de un numero, con el mejor algoritmo convencional
conocido, es un problema que consume unos recursos exponencialmente
crecientes con N. Esto no significa que mañana, alguien, muy listo por
cierto, descubra una nuevo algoritmo que rompa con todo esto y convierta la
factorizacion en un problema EFICIENTEMENTE computable.

A veces es complicado tener presente la diferencia en que algo que crece
como N^10, crezca mas despacio que algo que crece con e^N (donde e es un
numero entero cualquiera mayor que uno). Veamos un ejemplo.

	(a) Problema A. Recursos crecen con N^10
	(b) Problema B. Recursos crecen con e^N

Empezando con N=10 elementos:
	
	(a) Problema A. Recursos = 10^10
	(b) Problema B. Recursos = 10^3

parece que esto nos contradice. El problema A consume unos recursos 7 ordenes
de magnitud (10.000.000 de veces) mayores ... y este era el EFICIENTE.
Doblemos N a ver que pasa. Con N=20 elementos:

	(a) Problema A. Recursos = 20^10 = 2*10^11
	(b) Problema B. Recursos = 10^8

la distancia se ha reducido notablemente. Parece claro que, a pesar de la
diferencia inicial, los crecimientos son muy diferentes. Cuadrupliquemos el
numero de elementos a ver que pasa (N=80).

	(a) Problema A. Recursos = 80^10 = 8*10^11
	(b) Problema B. Recursos = 10^34

Parece increible, pero el multiplicar el numero de elementos por 4, en el
problema exponencial, ha supuesto usar 26 ordenes de magnitud (mas de un
billon de billones) mas en recursos. Bien sabemos que doblar la velocidad de
procesamiento es algo complicado, pues eso da una muy buena idea de que el
problema NO ES EFICIENTEMENTE COMPUTABLE.

Entre este tipo de problemas, esta no solo la factorizacion de numeros, sino
la simulacion de sistemas cuanticos o la simulacion de fluidos. Conviene
repetir que en el caso de la factorizacion, la traba no radica
intrinsecamente en la factorizacion, sino en los algoritmos de factorizacion
existentes. 

Precisamente la mecanica cuantica presenta este tipo de problemas, pero de
una forma intrinseca, ya que para describir un sistema con N posibles
estados (posteriormente quedara mas claro, que significa esto), hacen falta
2^N numero complejos. Es por ello, que Feynman y otros cientificos,
propusieron en los 80' que un sistema computacional que se comportara
cuanticamente deberia ser util a la hora de simular fenomenos de este tipo,
y ayudar asi a comprenderlos.

¿ Que significa esto de comportarse cuanticamente ? Toca ahora entrar
brevemente en un poquito de teoria al respecto. No puedo prometer que lo
vaya a entender todo el mundo, pero voy a intentarlo y espero aclare
bastantes equivocos al respecto. Lo que si puedo asegurar es que el
modelo de "realidad" que presenta, esta bastante a disgusto con el modelo de
realidad cotidiana que nos toca vivir.

Supongamos un sistema que consideraremos clasico en cuanto a que no conoce
la mecanica cuantica ni de oidas: un dado por ejemplo. De un dado, podemos
definir (entre otras cosas) 6 estados, dependiendo del numero que marque en
la cara frontal. Situado en una superficie horizontal, desechando que pueda
caer de canto, SIEMPRE se encuentra en un estado muy definido.

Pero un dia nos vienen unos cientificos y nos presentan una nueva realidad,
de la que como ejemplo muestran un dado cuantico. La diferencia, es sutil,
pero brutal: resulta que si lanzamos el dado dentro de una caja, que
cerramos antes de que caiga (para no poder verlo): el dado no se encuentra
en ningun estado concreto, sino en una composicion de estados; es decir, es
como si el dado marcara 1,2,3,4,5 y 6 a la vez.

Nadie puede negarlo, porque nadie ha visto el dado dentro de la caja. El
caso es que cuando se abre, tachannn, esa composicion de estados se
transforma en uno concreto: hemos hecho una medida. ¿ Y porque ha salido un
3 o un 6, o lo que sea, y no otro numero ? Bueno, de la composicion de
estados que teniamos con la caja cerrada, algunos podrian ser "mas
importantes" que otros, en el sentido de que es mas probable que aparezcan
cuando abramos la caja (un dado trucado por ejemplo). No es este el caso que
nos ocupa, ya que los 6 estados son igual de "importantes" (o probables).

Visto el dado, y hecha la medida, hasta que no cambie algo, y esto es algo
que no se suele tener claro, por mucho que cerremos y abramos la caja, el
estado no va a cambiar y no hay probabilidades de por medio.

Este ejemplo, que ya considerareis si es mas o menos afortunado, pretende
ilustrar las peculiaridades de los estados cuanticos. El estado mas general
de una particula/sistema es una composicion de estados. Si, es una especie
de estado fantasmagorico, que hasta que no lo medimos no se concreta en uno.
Si no se perturba, midamos una o mil veces, el valor sera el mismo; siempre
que se mida la misma "cualidad" y no se intente conocer cualidades
"incompatibles" de forma simultanea (como velocidad y posicion). No se si os
habeis dado cuenta, pero el hecho de que una particula se encuentre en una
composicion de estados (y no en uno concreto), trae consigo una serie de
consecuencias filosoficas sobre la realidad en las que no entrare, pero
que os las dejo para consumo posterior. La paradoja de gato de Schrodinger,
pone de manifiesto los problemas que surgen al aplicar la teoria cuantica
(comprobada hasta la saciedad) a un pobre gatito.

Fin de la parte teorica, imprescindible en mi opinion para comprender algo
de como habria de funcionar un computador cuantico. El equivalente cuantico
de un bit, es lo que se conoce como qubit (quantum bit). En los ordenadores
digitales sus dos posibles estados: 1 o 0, corresponden con dos niveles de
tension electrica distintos. Para el equivalente cuantico, se toma una
particula con dos posibles estados. La gran diferencia es que el qubit no se
va a encontrar en un estado concreto, sino en una composicion de estados, es
decir, cada qubit es un 1 con una cierta probabilidad y un 0 con otra. Al
aplicarse puertas logicas, ira variando la probabilidad del estado "1" y del
estado "0", pero la salida sera tambien una composicion de estados.

Esta peculiaridad, aparte de marcar una clara diferencia con los sistemas
digitales que conocemos, le confiere la potencia que luego explicara
comportamientos casi magicos. El trabajar con composiciones de estados le
dota de un parelelismo interno que hace que un ordenador cuantico de N
qubits, trabaje con 2^N bits a la vez, y cada operacion posterior se lleva a
cabo sobre todas las combinaciones a la vez. Tomemos un ordenador de 3 qubits,
su estado general sera:

estado = a*000 + b*001 + c*010 + d*011 + e*100 + f*101 + g*110 + h*111

donde a,b,c,d,e,f,g y h dan una idea de la probabilidad de cada estado.
Cualquier operacion digital la haremos sobre los 2^3=8 estados a la vez. Un
algoritmo que buscara el numero 011 como solucion de algun problema, deberia
procurar que todos los coeficientes (a,b,c,e,f,g,h) se anularan, excepto el
que va sobre si mismo (d), que seria igual a uno.

estado = 011

evidentemente, si la composicion de estados solo se compone de ese estado,
al medirlo, obtendriamos 011. Dicho de otra manera, deberia ir eliminando
todas las posibles combinaciones que NO son solucion de ese problema en
particular.

Esto es una somera idea de como se comportaria. El como se llega es otra
historia. No se sabe como construir un ordenador con un numero
arbitrariamente grande de qubits. Hay diversos prototipos de ordenadores
cuanticos de 2 o 3 qubits a lo sumo. Para hacerse una idea de lo poco que
tienen que ver con los ordenadores actuales (y con el dispositivo de mano
famoso), uno de los dise~os mas prometedores se basa en mediciones de
resonancia magnetica nuclear (si, esto donde miran si un futbolista se ha
hecho pupa). Recuerda un poco a lo mastodonticos que eran los primeros
ordenadores, y quien sabe como evolucionara esto que practicamente acaba de
nacer.

¿ A que viene entonces tanto bombo? Fundamentalmente a 2 descubrimientos que
vienen a dar idea de como esa potencialidad se puede aplicar a problemas
palpables y no resueltos hasta ahora:

(a) En 1994, Peter Shor (Bell Labs) propone un algoritmo, susceptible de ser
ejecutado en un ordenador cuantico, que factoriza dos numeros en un tiempo
polinomico. La razon de que esto no cause alarma, es que no hay computadores
cuanticos de un numero de bits tales, que permitan abordar claves
comercialmente utilizadas. Al menos ya existe la base teorica.

(b) En 1997 Grover (tambien de Bell Labs) publica un algoritmo de busqueda
ciertamente revolucionario (tambien cuantico, claro). Las bases de datos,
basan la potencia de sus mecanismos de busqueda en una ordenacion previa de
los datos. En un conjunto de N elementos desordenados, encontrar un elemento
particular, lleva indefectiblemente una media de N/2 intentos. El algoritmo
de Grover lo consigue en raiz_cuadrada(N) intentos. Volvamos al ejemplo
numerico:
                      intentos                           intentos
                   alg. convencional                    alg. Grover
    si N=1000              500                                 31
    si N=1 millon      500.000                               1000

la diferencia vuelve a ser evidente.

¿ Progresara o se convertira en puro ejercicio mental ? Solo el tiempo lo
dira. Queda tambien por demostrar en cuantos de los problemas reales se
muestra mas eficiente que los metodos actuales; y es que hasta ahora hay muy
pocos algoritmos en los que se muestren mas eficientes.

Si todo sale bien, quiza la criptografia no pueda volver a basarse en
planteamientos matematicos. Quien hace la ley, hace la trampa, y la solucion
vendria entonces de confiar no en conjeturas matematicas, sino en leyes
fisicas (igual son lo mismo :):

CRIPTOGRAFIA CUANTICA  ----------------------------------------------------

A diferencia de este panorama un tanto especulador, el campo de la
criptografia cuantica si que se encuentra lo suficiente consolidado como
para pensar que puede ser una realidad proxima en sistemas opticos que
requieran una seguridad excepcional. 

Su origen no es mucho mas antiguo que el de la computacion cuantica, data de
principios de los ochenta, y sin que este muy claro (como siempre) el
autentico padre de la idea. De lo que caben menos dudas, es de que el primer
dispositivo experimental, tal y como apunto Falken en el articulo de set20,
se construye en 1989 por Bennett y Brassard (IBM, para que veais quien anda
metido en estos ajos). Transmitieron a lo largo de 32 cm. No parece mucho,
pero en otras circunstancias, 32 cm es una cifra destacable.

Para explicar como funciona esto, y que cada uno de vosotros vea por si
mismo el quid de la cuestion, voy a utilizar el problema que ya introdujo
Falken, pero me voy a extender bastante mas para que no queden cabos
sueltos. 

Vamos a utilizar para el invento fotones polarizados. No es necesario ser el
maestro de los fotones polarizados para entender lo que hacen en este
ejemplo, asi que, que nadie se asuste. Los fotones vibran de maneras muy
diferentes. Lo que en realidad vibra es el campo electromagnetico asociado a
ellos, pero quedemonos en que pueden vibrar. Por ejemplo, de forma parecida a
como vibra la cuerda de una guitarra, o un pendulo: bien de arriba a abajo,
bien de derecha a izquierda, bien en diagonal, etc ... Al primer caso se les
llama con polarizacion vertical, al segundo polarizacion horizontal y al
tercero polarizacion diagonal (razones evidentes). Un polarizador se
comporta como una especie de filtro que solo deja pasar a determinados
fotones: un polarizador vertical deja pasar los fotones con polarizacion
vertical. Una cosa es importante aclarar: cuando atraviesa un foton un
polarizador, o pasa, o no pasa, pero no cometais el error de que pasa
"empeque~ecido" o con alguna propiedad cambiada.

Veamos algunos ejemplos:

(a) Un foton polarizado verticalmente (|), atraviesa un polarizador vertical
P(|)

           foton(|) ->  P(|) -> foton(|)

ese foton SIEMPRE PASARA.

(b) Un foton polarizado horizontalmente (-), atraviesa un polarizador
vertical P(|)

           foton(-) ->  P(|) -> foton muerto

ese foton NO PASA NUNCA.

(c) Un foton polarizado diagonalmente (\) o (/), atraviesa un polarizador
vertical P(|)

           foton(/) ->  P(|) -> 50 % de la veces foton (|)
                             -> 50 % de la veces foton muerto

inescrutables los caminos de la mecanica cuantica. Este hecho resulta
ciertamente magico, pero es asi.

Espero que hayais captado la idea aunque no haya reflejado todas las
combinaciones. Ahora, establecemos (igual que la que puso Falken), el codigo
binario de equivalencia para nuestros fotones:

        / = 1
        - = 1
        \ = 0
        | = 0

El esquema de la transmision va a ser el siguiente: Un emisor, equipado con
un buen generador de numeros aleatorios, produce una secuencia, susceptible
de ser utilizada como llave de encriptacion. Para enviarla, traduce los 1s y
0s a fotones polarizados segun tenemos escrito arriba (para cada 1 o 0 elige
aleatoriamente cada una de las dos opciones disponibles). El receptor, que
debe estar sincronizado con el emisor, elige, tambien aleatoriamente medir
cada foton con P(|) o con P(\) Detras de cada polarizador hay un detector de
fotones que comprueba si han pasado o no. Una vez realizada la transmision,
el emisor y receptor se comunican por un canal "publico" el tipo de
polarizacion que han utilizado para cada bit. Los casos en los que hayan
coincidido (50% en principio) se toman como validos, y el resto se deshechan
(otro 50%):

        -------- secuencia binaria
        |                                                      -------
   -----------------                                      P(|)-|     |
   |  generador de |                                    /      | Mux |- bits
   |   fotones     |====================================       |     |
   -----------------            fibra optica            \ P(\)-|     |
                                                               -------
      EMISOR                                                RECEPTOR

      
en el detector he puesto polarizadores vertical (|)  y diagonal hacia la
izquierda (\), pero vereis que es indiferente de elegir horizontal (-) y
vertical derecha (/). La caja etiquetada "Mux", es un multiplexor (o era
demultiplexor ?:-/) que se ocupa de que el foton pase por un polarizador u
otro (solo uno para cada bit/foton). Veamos ahora como eligiendo la misma
base de polarizacion en el emisor y en el receptor, la comunicacion funciona.

(a) Emisor con P(+)-------- Detector con P(|)

   Envia un "1"                                        Recibe un "1"
     foton(-)       ->      P(|)      ->   foton muerto

   Envia un "0"                                        Recibe un "0"
     foton(|)       ->      P(|)      ->   foton(|)

(b) Emisor con P(X)---------Detector con P(X)

   Envia un "1"                                        Recibe un "1"
     foton(/)       ->      P(\)      ->   foton muerto

   Envia un "0"                                        Recibe un "0"
     foton(\)       ->      P(\)      ->   foton(\)

en este caso la convencion sera: si se recibe un foton, consideraremos un
"0", si no se recibe consideraremos un "1". La convencion se puede cambiar,
modificando los polarizadores del receptor. Para los casos en que han
elegido bases distintas: el 50% de las veces se vera un 1 (foton muerto) y
el otro 50% un 0 (foton detectado); esto **independientemente** de que el
emisor enviara un 1 o un 0.

Y ahora empieza la magia. Resulta que hay un espia en medio de nuestro canal
de transmision (que he puesto una fibra, pero podria ser espacio abierto).
Nuestro espia, la unica opcion que tiene de interceptar la comunicacion es
interponer sus polarizadores y detectores. Debera igualmente elegir para
cada bit una base (+ o X) y dependiendo de lo que detecte, debera generar
nuevos fotones para que el receptor no sospeche nada raro. Ahora bien, el no
conoce la base utilizada por el emisor, luego por puro azar el 50% de las
veces elegira la opcion equivocada. En ese 50% de fotones "mal leidos" leera
datos aleatorios. De estos datos aleatorios, en principio la mitad
coincidiran con los verdaderos, y la otra mitad NO. ¿ Que implica esto ? Que
la tasa de errores cuando hay un espia de por medio, sera siempre alrededor
del 25%. En ese caso, la clave habra quedado comprometida.

Esta es la gran diferencia con los sistemas de intercambio de claves
convencionales: se sabe cuando la llave NO ha sido comprometida. En caso de
tasas altas de error, estos se podran deber a un espia o a fallos de nuestro
propio sistema (ya veremos muchos luego).

Es maravilloso el mundo de los experimentos teoricos, pero desgraciadamente,
cuando se trata de implementarlos en un sistema real, empiezan a aparecer
las pegas:

	* Para empezar no existen hasta la fecha fuentes de fotones capaces
funcionar de una forma tan sincrona como las que necesitaria nuestro
experimento.

	* Hay que evitar enviar mas de un foton por bit, ya que seria
posible para un espia retener uno de ellos y dejar al otro seguir su curso.
En una conjetura mental, dificilmente realizable (no hay que dejar lugar a
la duda), podria almacenarlos hasta que emisor/receptor anunciaran su
eleccion, y utilizar entonces estos datos para hacer las medidas correctas.

	* Inevitablemente la fibra optica presenta absorcion, con lo que un
determinado numero de fotones se perdera por el camino. En el caso de la
atmosfera, eligiendo determinados tipos de fotones (determinada luz
infrarroja por ejemplo), la absorcion es muy baja, pero existen fenomenos
atmosfericos capaces de modificar la polarizacion de los fotones.

	* La efectividad de los detectores de fotones dista mucho,
muchisimo de ser perfecta. Por un lado algunos fotones no se van a detectar,
y otros se van a detectar aunque no existan. Esto engrosara la tasa de
errores, que a pesar de ello es posible mantenerla todavia lejos de ese 25%.

¿ Y que es lo que se ha conseguido en experimentos reales ? Pues los
progresos son ciertamente positivos, aunque se trate unicamente de
prototipos.

 En fibra, recientemente se ha conseguido una comunicacion a lo largo de 48
Kms, que ya es una distancia utilizable. Mas importante parece la
aplicacion en comunicaciones al aire libre, especialmente comunicaciones por
satelite. El gran problema es lo "ruidoso" que es el sol. Por ello tan solo
se han publicado transmisiones en torno a 500 m y de forma nocturna. Es de
esperar, no obstante, que las perturbaciones atmosfericas en un enlace
tierra-tierra se minimizaran bastante en un enlace tierra-satelite, ya que
la parte alta de la atmosfera presenta condiciones mas estable. 

Veremos, veremos ...

SiuL+Hacky

*EOF*