criptoc_2013

CriptografaDesde Roma hasta Fotones Polarizados.

Juan David Rey Conrado

Esp. en Seguridad de la Informacin

Universidad de los Andes.

CriptografaDesde Roma hasta Fotones Polarizados.

1. Historia de la Criptografa.

2. Estndares Actuales.

3. Introduccin a la Criptografa Cuntica

Qu es Criptografa?Etimologa:

- krypto: oculto

- graphos: escritura.

Tcnicas de cifrado y descifrado para mantener oculta la informacin de quien no debe tener acceso a ella (asegurar la confidencialidad de la informacin).

No existen las palabras encriptar o desencriptar.

Otros conceptosALGORITMO: Es un conjunto de pasos y reglas que permiten realizar algo sin generar dudas. Proceso repetible.

CIFRAR: Utilizar un algoritmo (algoritmo de cifrado) con una clave (clave de cifrado) para transformar un mensaje, dejndolo incomprensible para quien no tenga una clave particular (clave de descifrado).

CRIPTOANLISIS: Tcnicas para encontrar la informacin que ha sido ocultada mediante tcnicas de criptografa.

Problema elemental

ALICE BOB

Mensaje

EVETRUDY

Criptografa ClsicaJULIO CSAR. (aprox. 70 A.C.)

Reemplazar cada letra del mensaje por la letra 3 posiciones adelante.

A D

B E

C F

X A

Y B

Z C

m i m e n s a j ep l p h q v d m h

ATBaSH.

Mtodo del espejo. Se sustituye la primera letra con la ltima, la segunda por la penltima y as sucesivamente.

Criptografa Clsica

m i m e n s a j en r n v m h z q v

Mtodo de las cajas. Mtodo del telfono.

Criptografa Clsica

ABC DEF GHIJKL MN OPQRST UVW XYZ

m i m e n s a j e. . . . . . . . .

CRIPTOANLISIS DE UN CIFRADO DE SUSTITUCIN

Si el alfabeto tiene dos (2) smbolos, las posibles sustituciones reversibles son:

2

Si el alfabeto tiene tres (3) smbolos, las posibles sustituciones reversibles son:

3 * 2

Criptografa Clsica

PERMUTACIONES

Un alfabeto de n smbolos tiene n!posibles sustituciones reversibles.

28! = 3,04 x 1029

CRIPTOANLISIS DE UN CIFRADO DE SUSTITUCIN

Criptografa Clsica

Problema elemental

ALICE BOB

Mensaje

TRUDY

Mensaje Cifrado

C=E(k,m) m=D(k,c)

k

NUEVO PROBLEMA

Cmo compartir la llave sin que esta caiga en manos de Trudy?

Clave SecretaMquina Enigma (Nazis).

Mquina basada en rotores que giran cambiando cada vez la clave con que se cifra. Se genera un mensaje cifrado que solo puede descifrarse con la mquina Enigma inicializada con la misma clave inicial.

http://enigmaco.de/enigma/enigma.swf

Informacin como bitsCriptografa Tradicional: Se envan textos claros compuestos por las letras del alfabeto. Las operaciones de sustitucin o transposicin se hacen sobre cada letra.

A {A,B,C,D, Z}

28 posibilidades

Criptografa Computacional: Se envan bits y se operan bits.

A (ASCII 65) 0100 0001

256 posibilidades

XOR: La operacinAsociativa:

(ab)c=a(bc),Conmutativa:

ab =ba,Otras:

ab =ab,aa =0,a0=a,a1=a,aa=1,(ab)=ab=ab,

Cifrar:ci = mi kiDescifrar:mi = ci ki

ONE TIME PADUtilizacin de una clave que no tenga patrones definidos y que no se repita.

Clave aleatoria si se puede intercambiar o enviar entre los extremos o preferiblemente pseudo-aleatoria (que se pueda reproducir a partir de una semilla).

:3,1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912

SeguridadIncondicional: Sin importar los recursos computacionales, intelectuales o de otro tipo, el mensaje cifrado no da informacin suficiente para que se pueda obtener el mensaje original.

Computacional: El mensaje cifrado no puede ser quebrantado dadas las limitaciones computacionales. A medida que la tecnologa avanza, la seguridad computacional se puede ver afectada.

Nuevos Retos de la Criptografa

Confidencialidad (Privacidad): El mensaje es entendible por quien debe serlo y para los dems es secreto.

Autenticidad: El mensaje sea enviado por quin realmente dice enviarlo. No hay suplantacin.

Integridad: El mensaje llega inalterado desde un extremo al otro.

No repudio: El mensaje enviado no pueda ser negado por quin lo envi.

Estndares Actuales de cifradoSimtrico

Data Encription Standard (DES)

Triple DES

Mensaje CifradoDES

K1

CifradoDES

K1

CifradoDES

K2

DescifradoDES

K1

DescifradoDES

K1

DescifradoDES

K2

Cifrado

Cifrado Mensaje

Estndares Actuales de cifradoAsimtrico

PrincipiosGracias a la Aritmtica modular y al teorema de congruencia

Hay dos nmeros a y b.

Cifrado:

Descifrado:

PROBLEMA

Intercambio de claves.

Principios

RSASeleccin de Claves:

Se seleccionan 2 primos grandes y aleatorios (p>2512,q>10154)

Se calcula n=p.q Se calcula (n)=(p1)(q1) Se encuentra un primo e relativo a (n)(e

RSACifrado:

Descifrado:

El ataque consiste en factorizar n (2048 bits).

Kpub {e,n} Kpri {d,n}

RSA

PROBLEMA

Intercambio de claves.

Diffie-HellmanSeleccin de Claves:

Se selecciona un primo grande y se calcula un generador g Zp.

Alice escoge a al azar y calcula:

Alice enva A a Bob. Bob escoge b al azar y calcula:

Bob y Alice calculan la clave.

Diffie-Hellman

Criptografa Cuntica (Cifrado simtrico)

PrincipiosEl cifrado digital simtrico (xor) es perfecto si:

1. La clave es aleatoria.2. La clave se usa slo una vez.

La mecnica cuntica:

1. Un estado cuntico no puede ser copiado, y, por tanto, espiado. (NO-CLONNING)

2. Cualquier intento de obtener informacin sobre un sistema cuntico lo modifica.

3. Las medidas cunticas son irreversibles.

BB84Se utilizan bases no ortogonales. Cada fotn representa un bit de informacin (acordado segn las bases).

Ejemplo clsico:Base segn ejes X y Y (+).Base diagonal (x).Bit 0 es fotn en base + y en base x.Bit 1 es fotn en base + y en base x.

BB84Intercambio de Llaves:

Alice: Genera dos secuencias aleatorias de bits.

La primera son bits a transmitir. La segunda las bases a utilizar.

Transmite (fotones polarizados) la primera secuencia segn las bases de la segunda.

Sec1. 0 1 1 0 1 1 0Sec2. 1 0 0 1 1 1 0Base x + + x x x +Fotones


Bob: Genera una secuencia aleatoria de bits.

Las bases a utilizar.

Realiza mediciones de los Fotones enviados por Alice.

Fotones Sec1. 0 1 0 1 0 1 1Base x + x + x + +Medidas


Alice y Bob: Intercambian las bases usadas.

Realizan mediciones para determinar la clave a utilizar.

Bits 0 1 1 0 1 1 0Base x + + x x x +Fotones

Base x + x + x + +Medidas

Clave 0 1 1 0

ALICE

BOB

COMUN

E91Se utilizan bases no ortogonales. Cada fotn representa un bit de informacin.Se necesita una fuente EPR (Einstein, Podolski, Rosen)

Tres preparaciones distintas de parejas entrelazadas:

E91Se utilizan tres alfabetos alternativos.

Operadores de Medida:

E91Se genera un estado j (j aleatorio)Cada fotn se enva a un extremo (Alice y Bob).

Alice y Bob de forma aleatoria eligen un operador de medida y lo aplican al fotn.

Alice y Bob intercambian la lista de operadores de medida usados.

Se utilizan los bits medidos con el mismo operador. Se descartan los dems.

Vida Real

Alice Bob

Distancia mayor a 100 Km

QEBR=20%

Vida Real Futura.

Alice Bob

quantum non-demolition box

Sistema de correccin de

Errores

Referencias.1. Simon Singh. The Code Book: The Science of Secrecy from

Ancient Egypt to Quantum Cryptography. 2000.2. Quantum cryptography is hacked

(http://www.nature.com/news/2007/070423/full/news070423-10.html).

3. Xu, Qi y Lo. Experimental demonstration of phase-remapping attack in a practical quantum key distribution system. arXiv:1005.2376 [quant-ph] (http://arxiv.org/pdf/1005.2376v1.pdf)

4. M. Baig. Criptografa Cuntica. Grup de Fsica Terica IFAE. Universitat Autnoma de Barcelona.

5. Mark Stamp. Applied Cryptanalysis. John Wiley & Sons. 2007.

Documents

criptoc_2013