PDF de programación - Cómo Ordenadores cuánticos aniquilarían la criptografía actual

Cómo los ordenadores
cuánticos aniquilarían
la criptografía actual
Verónica Fernández Mármol

Instituto de Seguridad de la Información (ISI)

CSIC

[email protected]

http://www.ifa.csic.es/

Índice

• Amenaza del ordenador cuántico a la

criptografía actual

• Solución? Criptografía cuántica
• Cómo funciona:

• Protocolos
• Sistemas experimentales y comerciales

• Nuestro sistema

Índice

• Amenaza del ordenador cuántico a la

criptografía actual

• Solución? Criptografía cuántica
• Cómo funciona:

• Protocolos
• Sistemas experimentales y comerciales

• Nuestro sistema

Criptografía simétrica

o

clave secreta

Una sola clave

Debe mantenerse en

secreto

ejemplo paradigmático

¿Es seguro DES?

¿Por qué no?

Fuerza bruta

Longitud

128 a 256 bits

Son muy rápidos

Discos duros

Audio y vídeo

Base de datos

Comunicaciones de red

Cifran cantidades

grandes

Clave

Claro

Cifrar

Cifrado

Descifrar

Claro

A

B

¿Cómo distribuir la

clave?

Criptografía asimétrica

o

clave pública

Diffie y Hellman (1976)

claves: pública y

privada

Clave pública

la conoce todo el mundo

Clave privada

sólo la conoce una

persona

Clave
púb

Clave
priv

Cifrar

Claro

Cifrado

Descifrar

Claro

bits de longitud

mínima

Son muy lentos

Cifran cantidades

pequeñas

Clave
púb

Clave
priv

Cifrar

Ks

EKpub(Ks)

Descifrar

Ks

Claves secretas

RSA

Clave pública

N = p*q

e, primo con (p-1)*(q-1)

Clave privada

d, tal que d*e mod (p-1)(q-1) = 1

Cifrado

c = me mod N

Descifrado

m = cd mod N

Ejemplo

Clave pública
N = p*q
e, primo con (p-1)*(q-1)
Clave privada
d, tal que d*e mod (p-1)(q-1) = 1
d*3 mod 20 = 1

p=11, q=3, N=33
e=3 (primo con 20),

d=7

(21 mod 20 =1)

Cifrado

c = me mod N = 73 mod 33 = 343 mod 33=13

Descifrado

m = cd mod N = 137 mod 33 = 7

¿Es seguro RSA?

¿En qué se basa su

fortaleza?

Problema de la
factorización

¿Factores de 15?

3 x 5

¿Factores de 391?

17 x 23

Último reto RSA

640 bits en 5 meses en 80 PCs

¿Cuánto se tarda en
hacer operaciones

matemáticas?

Sumar dos números de

N bits

Tiempo lineal: O(N)

Multiplicar dos
números de N bits

Tiempo cuadrático: O(N2)

Factorizar un número

de N bits

Tiempo exponencial:

O(eN)

No se ha probado que

RSA sea seguro

Problema difícil, pero

¿imposible?

Ordenadores cuánticos

¿Podrán resolver en
tiempo polinómico

problemas intratables?

¿Cómo funcionan los

ordenadores?

NOT

OR

XOR

AND

NAND

Puertas lógicas

entrada

salida

Suma de dos bits

+
0
1

0
00
01

1
01
10

Suma = x XOR y

Acarreo = x AND y

x
y

suma
acarreo

¿Pueden usarse
estados cuánticos?

Bit 0:

Bit 0:

0

0
Qubits

Bit 1:

1
Bit 1:

1

Pueden existir como una
superposición de estados

Superposición

hυ

1

hυ

hυ

0

  



0



1

Gato de Schrödinger



a

0



b

1

2

a

 b

12


|0>
z

|1>

x

y

Esfera de Bloch

Ninguna medida revela
el estado original de un

qubit desconocido

No pueden obtenerse

a y b

Entradas:

1
2

0(



)1

Superposición de estados

Computación clásica

y 

)(xf

Computación cuántica

a

0

f
 

b

1

fa

)0(



fb

)1(

La función f se evalúa
para ambos valores a

la vez

0+0
0+1
1+0
1+1

Salida: superposición
de todas las posibles

respuestas

La medida obtendrá un

resultado aleatorio

¿Cómo obtener
resultados útiles?

Las puertas lógicas
anteriores no sirven
con estados cuánticos

AND, OR, XOR son

irreversibles

Pérdida de información

En mecánica cuántica
no es posible perder
información sin medir

Puertas cuánticas

reversibles

Mismo nº de entradas y

salidas

NOT

CNOT

Control 1  Cambia el blanco

Control 0  No cambia el
blanco

Cualquier función se

puede realizar a partir de
puertas CNOT y puertas
de qubits individuales

92

00
01
10
11






00
01
11
10

Control:

1
2

0(



)1

Blanco: 0

Entrada

1
2

0(



0)1



1
2

00(



)10

Superposición de:

1
2
1
2

00

10

1
2

00(



)10

CNOT

1
2

00



1
2

11

1
2

00(



)11

Entrelazado cuántico

No pueden expresarse
como producto de dos
estados individuales

Medir el estado de una
partícula determina el

estado de la otra

1
2

00(



)11

Puerta Hadamard

H

0



H

1



0(

1
2
1
0(
2



)1



)1

Control:

Blanco:

1
2
1
2

0(



)1

0(



)1

1
2

0(



)1



1
2

0(



)1

1
2

1
2

00(



01



10



)11

CNOT

00(



01



11



)10

1
2

0(



)1



1
2

0(



)1

No hay entrelazado

Resultado definido de

la medida

estado en
superposición

CNOT

estado
definido

Importantes
aplicaciones

Juego mental
CNOT rota

Control desconectado

00
01
10
11






00
01
10
11

Control loco

00
01
10
11






01
00
11
10

Una sola medida por

puerta

¿Cómo encontrar la

CNOT buena?

Las combinaciones
clásicas no funcionan

1
2

1
2

00(



01



10



)11

CNOT

desconectada

00(



01



10



)11

1
2

0(



)1



1
2

0(



)1

1
2

1
2

00(



01



10



)11

CNOT loca

01(



00



11



)10

1
2

0(



)1



1
2

0(



)1

1
2

1
2

00(



01



10



)11

CNOT

00(



01



11



)10

1
2

0(



)1



1
2

0(



)1

1
2
1
2
1
1
2
2

0(



)1



0(



)1



0(
0(




)1
)1




1
2
1
2
1
1
2
2

0(



)1

0(



)1

0(
0(




)1
)1

Resultado definido y

computación en paralelo

1011

ordenador

clásico

0101

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

ordenador
cuántico

0100
1111
0010
0011
0001
0101
0110
1101
1000
0111
1010
1011
1100
1001
0000
1110

búsqueda en la guía

Problema

telefónica

N/2 búsquedas en

promedio

¿Puede ayudar la
mecánica cuántica?

Algoritmo de Grover

0 X
1 R
2 P
3 A

xf
si,1)(
xf
,0)(




x
correspond
caso
en
contrario


Pa e

f

1)2(


Superposición de todas

las x posibles

11,10,01,00

1
2

0(



)1



1
2

0(



)1

1
2

00



1
2

01



1
2

10



1
2

11

|00>

|01>

|10>

|11>

1/2

1/2

1/2

1/2

Ordenador
cuántico

si f(x)=1, invierte la fase

1/2

1/2

1/2

1/4

‐1/2

Inversión sobre

la media

l*=m-(l-m)=2m-l

1

probabilidad de

encontrar la respuesta

correcta

4 qubits

…|0010>…

‐1/4

11/16

1/4

1/4

3/16

7/32

probabilidad de

encontrar la respuesta

correcta

17/128

11/16

‐11/16

61/64

3/16

3/16

5/64

probabilidad de

encontrar la respuesta

correcta

¿Cuántas iteraciones

para 100%?

N



4




Guía telefónica con
1 millón de nombres

días con algoritmos

clásicos

minutos con algoritmo

de Grover

Impacto en criptografía

Búsqueda exhaustiva

de claves

Amenaza a la criptografía

simétrica

¿Qué pasa con la

asimétrica?

Problema de la
factorización

Tiempo exponencial

¿Puede acelerarse

cuánticamente?

Algoritmo de Shor

Transformada de

Fourier

1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, …

periodo = 4

71=7,
72=49,
73=343,
74=2401,
75=16807,
76=117649,
77=823453,
…

mod 15

7, 4, 13, 1, 7, 4, 13, …

Exponenciación

modular

ax mod N

Si la periodicidad es
par se pueden calcular

los factores de N

m.c.d (aq/2 + 1, N)

m.c.d (aq/2 – 1, N)

Ejemplo

a=7, N=15, q=4,

¿factores?

m.c.d (aq/2 + 1, N)

m.c.d (74/2 + 1=50, 15)=5

m.c.d (aq/2 -1, N)

m.c.d (74/2 - 1=40, 15)=3

15 = 3 x 5

Los circuitos lógicos
cuánticos son rápidos
buscando periodicidades

QFT

Paso 1

Registro de 2c > N estados

superpuestos

|00…000> + |00…001> + |00…010> +…+ |11…110> + |11…111>

Paso 2

Registro de c qubits a |0>

00

0000

Elegir un número a < N al azar y

Paso 3

primo con N

|0>|0>+|1>|0>+|2>|0>+|3>|0>+|4>|0>+|5>|0>+|6>|0>+… 1er registro
2º registro

ax mod N

N=15
a=7

|0>|1>+|1>|7>+|2>|4>+|3>|13>+|4>|1>+|5>|7>+|6>|4>+…

Medida en 2º registro

|1>|7>+|5>|7>+|9>|7>+|13>|7>+…

Transformada Fourier

período = 4

Tiempo polinómico

¿El fin de la criptografía

clásica?

Cifrado de Vernam

1 0 0 1 1 1 1 0 1 0 0
0 0 1 0 1 1 0 0 0 1 0
1 0 0 1 0 0 1 0 1 1 0

Secreto perfecto

kme


Matemáticamente
100% seguro …

… si se utiliza una sola

vez

e
e

1
2
km
(
)

1
mm
(
)

1
2
mm

1
2

(



m
2
k
(

k
k

)
)

… y si la clave es
100% aleatoria

¿Cómo generar claves

aleatorias?

Transmisión cuántica de

claves

Índice

• Amenaza del ordenador cuántico a la

criptografía actual

• Solución? Criptografía cuántica
• Cómo funciona:

• Protocolos
• Sistemas experimentales y comerciales

• Nuestro sistema

El único método de

transmitir claves

criptográficas en el que la
presencia de un intruso es

detectada

Basada en las leyes de la

Física Cuántica

Principio de Incertidumbre de Heisenberg

x p  


2

Heisenberg

Protocolo BB84

1101000110010110

Secuencia
aleatoria
Bases

Alice quiere mandar una secuencia aleatoria a Bob

ALICE

Alice utiliza aleatoriamente

las bases:

Rectilínea

Circular

Protocolo BB84

1101000110010110

Secuencia
aleatoria
Bases

Polarización

ALICE

Alice utiliza uno de los cuatro posibles estados de

polarización para codificar sus estados

0

1

0

1

Protocolo BB84

1101000110010110

Secuencia
aleatoria
Bases

Polarización

ALICE

Alice manda su secuencia de

fotones aleatoriamente codificados a

Bob

BOB

Protocolo BB84

Secuencia
aleatoria
Bases

Polarización

ALICE

BOB

1101000110010110

No todos los fotones que manda Alice

son recibidos por Bob. Algunos se
pierden como consecuencia de la

absorción del canal cuántico

Protocolo BB84

1101000110010110

Secuencia
aleatoria
Bases

Polarización

ALICE

BOB

Rectilínea

Circular

Bob utiliza la base circular o
rectilinea de forma aleatoria
para medir los fotones
recibidos

Prisma de Wollaston

O divisor por polarización (PBS)

Protocolo BB84

Detector 0

Detector 0

0

PBS

Base rectilínea

D
e
t
e
c
t
o
r

1

D
e
t
e
c
t
o
r

1

1

PBS

Base rectilínea

Detecta ‘0’ con 100% de

probabilidad

Detecta ‘1’ con 100%

probabilidad

Protocolo BB84

Detector 0

Detec