PDF de programación - Introducción a la criptografía y sus aplicaciones

Agenda

• Definiciones Básicas

• Breve recuento histórico

• Alicia y Betito se vuelven públicos

• Criptografía post-cuántica

• A manera de conclusiones

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Introducción y Definiciones

Básicas

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Criptografía y sus Aplicaciones

•Durante milenios, la criptografía se utilizó esencialmente en

contextos militares y diplomáticos.

•En la actualidad, con la era tecnológica y nuestra creciente

dependencia en sistemas electrónicos se necesitan, cada vez más,

técnicas de cifrado y de seguridad altamente sofisticadas.

•Lo anterior obliga a contar con comunicaciones digitales

privadas y seguras disponibles para todos.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Terminología

Criptología: Término genérico utilizado para designar la
disciplina que estudia cómo lograr comunicaciones seguras
sobre canales que no lo son, junto con otros problemas
relacionados.
Criptografía: Diseño de sistemas y esquemas para realizar
comunicaciones confiables sobre canales inseguros.
Criptoanálisis: Disciplina que estudia cómo romper esquemas
criptográficos.
Texto en claro: mensaje que desea transmitirse de manera
segura.
cifra: documento que resulta después de haber cifrado el texto
en claro.
Llave o clave: información secreta que permite cifrar/descifrar
documentos.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Aspectos de la criptografía
moderna

•La criptografía moderna depende de manera directa

de las matemáticas y del uso de sistemas digitales.

•Más específicamente se puede decir que está en la

intersección de tres disciplinas: matemáticas, ciencias

computacionales e ingeniería electrónica.

•Si no se tiene una comprensión profunda de las

técnicas de criptoanálisis es

imposible diseñar

sistemas criptográficos confiables y seguros.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Comunicación Segura

Llave de cifrado

Llave de descifrado

Alicia

Texto claro

Cifrado

Texto cifrado

Descifrador

Beto

Eva

Adversario

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Objetivos del Adversario
1. Leer el mensaje original

2. Obtener la llave secreta de Alicia.

3. Modificar el contenido del mensaje original.

4. Usurpar la identidad de Alicia

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Principio de Kerckhkoff

•

se parte de la premisa que el oponente conoce el
algoritmo criptográfico utilizado. Por lo tanto, la
seguridad del sistema debe estar basada en:

• La calidad (fortaleza) del algoritmo
• El tamaño del espacio de la llave (tamaño en

bits de la llave)

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Criptografía de llave secreta

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Criptografía de llave simétrica

Formalmente un criptosistema puede ser definido como una

quíntupla {P,C,K,E,D}, donde:

P es el conjunto finito de los posibles textos en claro.
C es el conjunto finito de los posibles textos cifrados.
K el espacio de llaves, es un conjunto finito de todas las llaves

posibles.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

xxEDPxPCDCPEDDEEKkkkkkkk, que talesfuncionesson :y : Cada)descifrado de (regla cifrado) de (regla Criptografía de llave simétrica

• Las llaves de cifrado y de descifrado son conocidas por las

dos entidades (Alicia y Betito).

• Las llaves están relacionadas y es fácil derivar la llave de
descifrado a partir de la llave de cifrado (en la mayoría de
los casos las llaves son idénticas).

• Todos los criptosistemas clásicos (pre 1976) son simétricos.

Ejemplos: DES, AES, etc.

• El modelo está pues basado en que las partes han convenido

previamente un secreto compartido.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Tamaño de las llaves en criptosistemas

•De acuerdo al principio de Kerckhkoffs’s la seguridad de los

criptosistemas debe estar basada únicamente en dos propiedades

importantes: calidad del algoritmo y longitud de la llave.

•Aunque la seguridad de un esquema es difícil de determinar sí

es obvio que el tamaño de la llave debe ser lo suficientemente

grande.

• Por ejemplo el cifrador DES utiliza llaves de 56 bits, por lo que
existen 256 posibles llaves [¡muy pocas!]

•La tecnología actual obliga a tener una seguridad de más de 80

bits.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Breve recuento histórico

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Teoría Elemental de Números (1/2)

•

•

•

Euclides: Máximo

común

divisor [circa 300AC]

Eratóstenes: Criba para hallar

números primos [circa 220

AC]

Fibonacci:

algoritmo

de

factorización

de

números

enteros [circa 1200 DC]

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Teoría Elemental de Números (2/2)

•

Fermat:

teoremas

números

primos

de

y

factorización [circa 1630

DC]

•

•

Euler: generalización del

teorema petit de Fermat

[circa 1750 DC]

Gauss: nuevos algoritmos

de

factorización

[circa

1820 DC]

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Algunos cifradores clásicos

•

•

Escítala : Método de cifrado por

transposición [Esparta, circa 650 AC]

Códigos César: Método de cifrado

por

sustitución mono-alfabético

[Imperio romano, circa 50AC]

•

Cifrador mono-alfabético Babington:

Utilizado por María I, reina de los

escoceses [1542 DC]

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Cifrador por Substitución

mono-alfabética

•

El alfabeto de cifrado consiste en un

reordenamiento del

alfabeto del

texto original. Así cada letra del

alfabeto

original

es

siempre

reemplazada por una misma letra

del alfabeto de cifrado.

•

En el alfabeto castellano hay un

total de 27! llaves distintas.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Ejemplo famoso: The gold-bug

53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;

46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6
!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3
4;48)4+;161;:188;+?;

cifra

'A good glass in the bishop's hostel in the devil's seat twenty-one
degrees and thirteen minutes northeast and by north main branch
seventh limb east side shoot from the left eye of the death's-head
a bee line from the tree through the shot fifty feet out.'

Texto en
claro

Edgar Allan Poe (1809-1849)

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Nacimiento del criptoanálisis

•

Al-kindi [Bagdad, Siglo IX]:

inventó el

análisis por frecuencia . Se aplica con éxito

contra

cifradores

por

substitución

aprovechando la estructura del idioma en el

que el texto original fue escrito.

El análisis de frecuencia es capaz de romper

cualquier

cifrador por substitución mono-

alfabética.

En los siguientes 600 años, no se logró

hallar ningún nuevo esquema de cifrado

•

•

capaz de resistir este ataque.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Le chiffre indéchiffrable

•

Basado en ideas propuestas por

Alberti a mediados del siglo XV,

Blaise de Vigenère propuso en

1562

un

cifrador

que

juzgó

indescifrable.

•

El cifrador de Vigènere fue el

primer cifrador por

substitución

poli-alfabética de que se tenga

registro. Permanecería invencible

por los siguiente tres siglos.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

El rompimiento del cifrador de

Vigènere

•

•

•

Charles Babbage logró romper en

1854 el cifrador de Vigènere.

Su

descubrimiento

nunca

fue

publicado por motivos de seguridad

nacional de su país [Inglaterra]

Es al científico prusiano Kasiski a

quien se le acredita históricamente

el haber logrado romper el cifrador

de Vigènere.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

¿El criptosistema Perfecto?

•En la práctica casi todos los criptosistemas pueden
teóricamente ser rotos si se cuenta con tiempo y recursos
computacionales suficientes.
•Sin embargo, hay un criptosistema que es considerado
teóricamente invulnerable: One-time-pad (OTP) [Vernam
1917].
•Claude Shannon demostró en 1948 que su seguridad es
teóricamente perfecta.
•Su seguridad es perfecta siempre y cuando la llave fue
generada de una manera puramente aleatoria.
•OTP requiere un intercambio de llave con una longitud igual
a la del texto en claro (¡Esto lo vuelve impráctico!)

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

El telegrama de Zimmermann

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

El Telegrama de Zimmermann

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Telegram de Zimmermann

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Telegrama de Zimmermann

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Enigma y Alan Turing

•

Enigma fue el cifrador usado por el

ejército nazi para enviar comunicados

secretos durante la segunda guerra

mundial.

•

•

Enigma fue roto por un grupo de

inteligencia británico quienes habían

recibido ayuda de criptoanalistas polacos.

Enigma fue roto en una mansión llamada

Bletchley Park, donde Alan Turing

destaco con ideas brillantes que fueron

decisivas para poder romper a Enigma.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Enigma

Enigma: Fue un dispositivo utilizado durante la segunda guerra mundial por
la Alemania nazi. Se tenía tal confianza en la fortaleza de Enigma que el alto
comandoAlemán decidió utilizarlo en todos los mensajes codificados antes y
durante la guerra.

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez

Enigma

Códigos y criptografía

2enero.2010

Francisco Rodríguez Henríquez