distribucion cu antica de claves: luces y sombras1tfc1s5rx-d21jlb-4p1...cu antica de claves sumario...
TRANSCRIPT
DISTRIBUCION CUANTICA DECLAVES: LUCES Y SOMBRAS
Fausto Montoya
Instituto de Fısica Aplicada, MadridConsejo Superior de Investigaciones Cientıficas
[email protected]; http://www.iec.csic.es/∼fausto
X RECSISalamanca 2008
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
1 Introduccion
2 Revolucion
3 Ordenadores cuanticos
4 Criptografıa cuantica
5 Protocolo B92
6 Critica a la QKD
Equipo clasico:
Gaius Julius Caesar100 - 44 AEC
Diffie-Hellman-Merkle1976
Intercambio de claves
Edward Lorenz1963
ELECTRODINAMICA CUANTICA
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Afirmaciones arriesgadas
�La criptografıa clasica ha muerto�.
�Solamente se puede considerar segura su nueva variantecuantica�.
�El advenimiento de los futuros —y todopoderosos—ordenadores cuanticos pondra en peligro todos losmetodos de criptografıa clasica�.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Un apasionado de la criptografıa cuantica:Hoi-Kwong Lo, Univ. of Toronto, Canada.
�The advent of quantumcomputers will lead to a retroactivetotal security break withcatastrophic consequences. ButIronically, quantum mechanics alsocomes to the rescue�.
Hoy-Kwong Lo, Quantum Cryptology, inIntroduction to Quantum Computation andInformation, World Scientific (1998).
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Mas entusiastas
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Juan Ignacio Cirac, Instituto Max Planckde Optica Cuantica, Garching, Alemania
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Y los periodistas despistados de siempre
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Reconozcamos que el tiempo pasa incluso para elalgoritmo RSA
RSA original
RSA 2003
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Otra posible amenaza a los criptosistemas debasados en teorıa de numeros
Viene de la propia teorıa de numeros.
Por ejemplo el algoritmo AKS (2002) es el primeralgoritmo determinista que decide en tiempo polinomico siun numero es primo.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Manindra Agrawal, Neeraj Kayal y Nitin Saxena
Department of Computer Science and EngineeringIndian Institute of Technology Kanpur, INDIA
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Pregunta clave: ¿Esta a punto de descubrirse unalgoritmo de factorizacion en tiempo polinomico?
Muy probablamente sı.
Responsable: Hugo Scolnik et al.Universidad de Buenos Aires
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Ordenadores cuanticos
Se basan en las propiedades cuanticas de la materia paraalmacenar informacion.
Se sirven, de dos estados diferentes de un atomo o de dospolarizaciones distintas de un foton.
La unidad de informacion cuantica es el qubit.
El qubit puede estar en los estados, 0, 1 y en lasuperposicion coherente de ambos.
Esto es, ¡se puede encontrar en el estado 0 y 1 a la vez!
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
¿Que es la superposicion de dos estados cuanticos?
�Those who are not shocked whenthey first come across quantumtheory cannot possibly haveunderstood it�.Niels Bohr.
�It is safe to say that nobodyunderstands quantum mechanics�.Richard Feynman.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
El gato de Schrodinger
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Computacion cuantica facil(para electronicos y matematicos)
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
¿Que pueden hacer los ordenadores cuanticos?
Un ordenador cuantico con longitud de palabrade 32 qubits tendrıa una potencia de calculoequivalente a la de unos 232 ' 4 300 000ordenadores personales de 32 bits actuales.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Ordenadores cuanticos: como amenazan a loscriptosistemas convencionales
Todas las operaciones seran mas rapidas:
La prueba exhaustiva de claves, (ataque por fuerza bruta).
La factorizacion de numeros primos, (rotura de clavesasimetricas).
Busqueda de coincidencias en funciones resumen, (ataquea las firmas electronicas con clave asimetrica).
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Tiempo necesario para prueba exhaustiva de claves
Con ordenador convencional: O(N).
Con ordenador cuantico y algoritmo de Grover (1996):O(√
N),y memoria de O(log N).
Equivale en el ordenador clasico a claves de la mitad delongitud en bits.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Tiempo para busqueda de colisiones en funcionesarbitrarias r a 1 (ataque a funcion resumen)
Con ordenador convencional: O(√
N).
Con ordenador cuantico y algoritmo de Brasard, Høyer yTapp, (1997): O( 3
√N/r) operaciones.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Factorizacion de numeros compuestos N
Con ordenador convencional:
O(23√log N ).
¡Exponencial con el numero de bits!
Con ordenador cuantico y algoritmo deShor (1994):
O((logN)3),
y memoria de O(logN).
¡POLINOMIAL con el numero de bits!
Peter Shor, 1994.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Moraleja
Frente a los ordenadores cuanticos, el unico sistema queno perderıa absolutamente ninguna seguridad es el
CIFRADO DE VERNAM
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Cifrado de VERNAM
Joseph Mauborgne y Gilbert Vernam, 1920.
Requiere una clave tan larga como el mensaje.
La clave se usa una sola vez.
La clave se envıa en mano mediante un agente seguro.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Criptografıa cuantica
La criptografıa cuantica sustituye el Agente Seguro delcifrado de Vernam por una transmision fotonica, por fibraoptica o espacio libre.
Realiza una Distribucion Cuantica de Claves (quantum keydistribution [QKD]).
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Experimentos
1989: 32 cm, a 1Kb/s, IBM.
1993: 100 km a 2 kb/s Toshiba, U.K.
1994: 30 Km British Telecom.
1995: 22.8 km a 0.1 Kb/s Univ.de Ginebra.
1999: 48 km, Los Alamos.
2005: 40 km, 100 Kb/s, NEC.
2006: 144 km, aire, La Palma-Tenerife.
2007: 148,7 km Los Alamos.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Companıas que venden equipos de distribucioncuantica de claves
id Quantique (Ginebra), 1 kbit/s
MagiQ Technologies (Nueva York).
SmartQuantum (France).
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Companıas que investigan en distribucion cuanticade claves
Toshiba
Hewlett Packard.
IBM
Mitsubishi
NEC
NTT
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Distribucion cuantica de claves
Alicia genera y transmite a Benito una clave bruta por elcanal cuantico.
Alicia y Benito concilian la clave final a traves del canalpublico, ordinario, no seguro.
Alicia y Benito se comunican con el Cifrado de Vernam yla clave final, a traves de un canal no seguro.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Protocolos de QKD
BB84: Bennett y Brassard, 1984.
Artur Ekert, 1991.
B92: Bennett, 1992.
Plug an Play QKD: Muller y otros, 1997.
Zbinden, Beechman, Gisin y G. Ribordy, 1998.
Hughes y Nordholt, 1999.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Protocolo de criptografıa cuantica: polarizacion defotones, Charles Bennett y Gilles Brassard, 1984
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Segundo protocolo de criptografıa cuantica:entrelazamiento cuantico, Artur Ekert, 1991
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Entrelazamiento cuantico
Se basa en el efecto Einstein-Podolsky-Rosen.
Una fuente genera un par de fotones entrelazados.
Cada foton tiene una polarizacion indefinida.
Los fotones tienen dos estados cuanticos complementarios(estan cuanticamente anticorrelados).
Los fotones se envıan a dos lugares alejados.
Cuando se mide un foton se fija su estado.
Automaticamente el otro foton adquiere el estadocontrario: ¡efecto a distancia!
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Polarizacion ortogonal de fotones
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Polarizacion diagonal de fotones
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Protocolo B92
Alicia transmite fotones individuales, polarizados en dossistemas de referencia incompatibles, seleccionados al azar:vertical y diagonal a derechas.
Benito mide con uno de dos polarizadores, elegido al azar:horizontal y diagonal a izquierdas.
Benito encontrara un foton solo el 25 % de las veces.
Benito, comunica a Alicia, por un canal publico, noseguro, cuando ha recibido un foton y cuando no.
Se fija la clave bruta comun anotando los valores de laspolarizaciones en que se ha recibido un foton(conciliacion).
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Protocolo B92
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Errores de transmision
Se producen errores de transmision que pueden llegar al5 %.
Por imperfecciones del sistema: giro de la polarizacion delas fibras, cambios de temperatura, fallos de losdetectores...
Por ruido: en los sistemas por aire.
Se usan procedimientos de correccion de error .
La correccion de errores produce una clave destilada,mucho mas corta que la clave bruta.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Ataque pasivo al protocolo B92 si se envıanimpulsos con varios fotones
Si Alicia envıa varios fotones en cada impulso:
Eva roba la mayorıa de fotones y los mide, dejando pasaralgunos.
Cuantos mas fotones robe Eva, mejor conocimiento de laclave lograra.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Generacion de fotones individuales
Es difıcil generar fotones individuales
Se utiliza un laser ordinario y se atenua su salida hasta quese garantiza que la probabilidad de emitir mas de un fotones < 1 %.
Resulta que la probabilidad de emitir un foton se reduce asolo un 10 %.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Generacion de fotones individuales con puntocuantico
Punto cuantico.Paul Alivisatos,Berkeley Lab NanotechnologyLaboratory.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Otro punto cuantico
Puntocuantico,IMM, CSIC,2008.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Primer ordenador electronico: Colossus, BletchleyPark. Criptoanalisis de la maquina Lorenz, 1944.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Ataque fallido al protocolo B92, cuando Aliciaenvıa un unico foton
Eva no puede robar fotones, solo medirlos con unpolarizador, copiarlos y retransmitirlos.
Eva modifica el 25 % de fotones al medirlos.
Alicia y Benito observan un 25 % de errores, detectan laintervencion de Eva.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
B92: Errores introducidos por Eva al copiar yretransmitir
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Deteccion de errores introducidos por Eva
Eva puede conformarse con medir parte de los fotones yenterarse solo de parte de la clave.
Si Eva mide solo parte de los fotones introduce menos del25 % de errores.
Cuando la tasa de errores es inferior al 10 % se estima queEva no esta espiando; o si esta espiando no consigueinformacion relevante.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Cantidad de fotones utiles
La cantidad de bits de la clave destilada final es muchomas pequena que el numero de disparos del laser.
La generacion de fotones individuales pierde el 90 % de losfotones que se intenta enviar.
El protocolo B92 pierde el 75 % de los fotones restantes.
La correccion de errores puede perder el 50 % de losfotones restantes.
La atenuacion del canal de transmision ocasiona unaperdida adicional variable dependiendo de la distancia.
La perdida total es como mınimo del 99 %.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Rendimiento
id Quantique (Ginebra), fibra optica, 25km, 1 kbit/s:tarda 435 dıas en llenar un DVD de 4,7 GB
Entrelazamiento de fotones, 144 km, aire, LaPalma-Tenerife, (2006)transmitio 178 bits en 75 segundos:tarda 500 anos en llenar el DVD.
Veronica Fernandez en Univ. Heriot-Watt, (Edimburgo),200 kb/s a 4 km:tarda solo 2 dıas en llenar el DVD.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Reduccion de pretensiones debido al bajorendimiento
Los actuales sistemas comerciales de QKD resultan muylentos generando clave util.
Es necesario renunciar al cifrado de Vernam, porque gastaun bit de clave por cada bit del mensaje.
La solucion de compromiso es generar claves de 256 bits ycifrar con AES de 256 bits.
Para cifrar con Vernam es preciso esperar a sistemas quegeneren GB/s.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Ataque activo al protocolo B92
Mario corta todos los canales.
Establece dos comunicaciones simultaneas y separadas conAlicia y Benito.
Suplanta a Benito cuando habla con Alicia y suplanta aAlicia cuando habla con Benito.
Mario se entera de todo e inventa lo que quiera.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Defensa frente al ataque activo
Para evitar el ataque por intromision de Mario, Alicia yBenito se autentican en el canal auxiliar.
Usan el protocolo de autenticacion de Wegman y Carterde 1981:
1 Se comparte una clave secreta finita.
2 Esta clave se agota con el uso en autenticacion, (como enel Vernam).
3 Problema de esta implementacion concreta: Cuando seacaba la clave, se rellena con nuevos bits ¡provenientes dela propia QKD!
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Defensa frente al ataque activo
Para evitar el ataque por intromision de Mario, Alicia yBenito se autentican en el canal auxiliar.
Usan el protocolo de autenticacion de Wegman y Carterde 1981:
1 Se comparte una clave secreta finita.
2 Esta clave se agota con el uso en autenticacion, (como enel Vernam).
3 Cuando se acaba la clave, se rellena con nuevos bitsprovenientes de la QKD.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Critica a la QKD
Si Mario habıa conseguido apoderarse de una clave secretainicial, o intermedia, se enterara de todas las futuras.
El rellenado de la clave del algoritmo de Wegman conmaterial suministrado por propio mecanismo de la QKD esuna mala practica criptografica. Se estan estudiandoalternativas.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Estado actual
Es un tema del maximo interes para ejercitos, bancos ycompanıas de telecomunicacion.
Hay importantes companıas de electronica ytelecomunicaciones invirtiendo grandes sumas en lainvestigacion de la criptografıa cuantica.
La NASA, la ESA, los operadores de telecomunicacion ylas corporaciones bancarias estan financiando a nivelmundial investigacion en criptografıa cuantica.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Estado actual en Espana
La UPM experimenta con un sistema de fibra optica de idQuantique, a 1 kbit/s para Telefonica.
El Instituto de Ciencias Fotonicas (ICFO) de Barcelona yel Grupo de Comunicaciones Opticas y Cuanticas de laUPV trabajan en un Transceptor Cuantico para la ESA.
El Instituto de Microelectronica de Madrid (CSIC) trabajaen el desarrollo de puntos cuanticos.
El Instituto de Fısica Aplicada (CSIC) esta desarrollandoun sistema de distribucion cuantica de claves en aire, a 3GHz de frecuencia de reloj, para trasmitir claves a unoscuantos Mbit/s, para Telefonica.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Futuro de la distribucion cuantica de claves
La Distribucion Cuantica de Claves, muy probablementesea el mecanismo que se use en el futuro para intercambiode claves en sistemas ultra seguros.
La criptografıa cuantica actual no es un solido candidatopara relevar a las tecnicas criptograficas clasicas a cortoplazo, pero si en el futuro.
Resulta algo lenta, imperfecta y muy cara; pero losproblemas tecnicos se van resolviendo de forma acelerada.
La QKD es por el momento un hıbrido entre mecanismosclasicos y cuanticos, queda por resolver aun la consecucionde protocolos criptograficos TOTALMENTECUANTICOS.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
Repercusiones en el uso de la criptografıaestandar actual
Hay que prever el advenimiento de los ordenadorescuanticos al disenar algoritmos de cifrado clasicos.
La solucion consiste, mientras tanto, en doblar (o mas) lalongitud de las claves.
El recien disenado Advanced Encryption Standard (AES),para cifrado en bloque, resulta hoy seguro con una clavede 128 bits de longitud, pero esta disenado para usarclaves de hasta 256 bits, con las que serıa inmune a unataque cuantico.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
CONCLUSION
La distribucion cuantica de claves(QKD) no puede minusvalorarse deningun modo.
Tampoco es la panacea universal.
Debe ser considerada como otraconstructiva contribucion a lacriptologıa, con mucho futuro.
Distribucioncuantica de
claves
Sumario
Introduccion
Revolucion
Ordenadorescuanticos
Criptografıacuantica
ProtocoloB92
Critica a laQKD
GRACIAS