Criptografía

Secretos Compartidos:
Un poco de historia de la
criptografa
Jos Galaviz Casas
Departamento de Matemticas
Facultad de Ciencias
UNAM
J. Galaviz
Secretos compartidos
Objetivos
Establecer conceptos fundamentales.
Hacer un breve recorrido por la historia de
la criptografa.
Explicar los fundamentos de los distintos
mtodos criptogrficos.
J. Galaviz
El problema
Dos personas o grupos de personas desean
comunicarse.
No quieren que nadie se entere de:
Que la comunicacin se lleva cabo.
El significado de la comunicacin.
El medio de comunicacin es inseguro.

J. Galaviz
Conceptos similares
Esteganografa
Criptografa
steganos: cubrir.
kryptos: ocultar.
Objetivo: ocultar la
Objetivo: ocultar el
existencia del mensaje.
significado del
Ejemplos:
mensaje.
Tablillas de madera
Ejemplo:
cubiertas con cera.
Ocultar mensajes en
imgenes.
J. Galaviz
Lenguaje F usado
por los nios.
Criptografa: elementos
Un conjunto de mensajes cuyo significado slo
debe ser conocido por el emisor y el receptor.
Un emisor de mensajes.
Un receptor de mensajes.
Un enemigo que no debe conocer el significado de
los mensajes.
Un canal de comunicacin que puede ser
escuchado por el enemigo.
J. Galaviz
Esquema general
J. Galaviz
Clasificacin de sistemas
criptogrficos
Simtricos: Se usa la misma clave para
cifrar y para descifrar.
Asimtricos: Las claves para cifrar y
descifrar son diferentes.
J. Galaviz
La scytala
Invento espartano.
El mensaje se escriba en una
tira de cuero enrollada en espiral
alrededor de un bastn.
Desenrollado era ilegible.
J. Galaviz
Cifrado de Csar
Julio Csar.
Guerra de las Galias.
Se hace corresponder el
alfabeto consigo mismo,
pero desplazado tres
lugares a la derecha.
Cada letra se reemplaza
por la que le corresponde.
Csar utiliz el alfabeto
griego y no el latino.
J. Galaviz
Qu tan seguro es?

En un mensaje, cada letra es reemplazada
por otra nica letra.
Las letras ms frecuentes en el mensaje
original se convierten en las letras ms
frecuentes del texto cifrado.
Cada idioma tiene su propia distribucin
(tabla de frecuencias).
J. Galaviz
10
Anlisis de frecuencia
Si sabemos que un
mensaje se cifr al estilo
de Csar
(monoalfabtico).
Si sabemos en qu idioma
estaba escrito
originalmente.
Lo podemos descifrar
analizando la frecuencias
de cada letra.
E. A. Poe, Al-Kindi S. IX.
J. Galaviz
11
Cifrado de Alberti
Leon Battista Alberti.
Arquitecto (entre otras
cosas) renacentista
italiano.
Se graba el alfabeto en dos
discos: uno fijo (exterior)
y uno mvil (interior).
Cada posicin relativa
entre los discos define un
cifrado de Csar.
J. Galaviz
12
Blaise de Vigenre
Traict des Chiffres et
Secretes Manieres d
escrire (1586).
Generalizacin del
esquema de Alberti.
Cambia el alfabeto de
cifrado con cada letra del
mensaje.
El alfabeto usado para
cifrar cada letra lo define
una palabra clave.
J. Galaviz
13
Cifrado de Vigenre
Se construye la tabla
de cifrado.
Se empata la palabra
clave con el mensaje.
Se usan las parejas
empatadas para
determinar, con la
tabla, la letra del
mensaje cifrado.
J. Galaviz
14
Cifrar y descifrar
J. Galaviz
15
Buenas ideas
El sistema de cifrado no debe ser prcticamente
descifrable sin la clave.
La seguridad del sistema debe residir en la clave y
no en mantener secreto el mtodo.
El mecanismo de cifrado debe ser fcil de usar.
Auguste Kerckhoffs, La Cryptographie
Militaire, Journal des Sciences Militaires, enero
de 1883.
J. Galaviz
16
Un secreto mal guardado

1a guerra mundial (19141918).
Hundimiento del Lusitania,
restricciones a los
submarinos.
El Kaiser decide levantar
las restricciones.
Entretener a Estados
Unidos (Japn-Mxico)
Propuesta para Carranza.
Zimmerman, Suecia,
Inglaterra, Estados Unidos,
Mxico.
J. Galaviz
17
Enigma
Arthur Scherbius, 1918.
Una generalizacin ms
de la idea de Alberti.
Muchos discos en
cascada.
Millones de
combinaciones posibles.
J. Galaviz
18
A ver descifren...
3 rotores de 26 letras
(17576).
3 o ms rotores
intercambiables (6).
Conexiones en el
panel frontal (1011).
Al teclear cdigo
cifrado se obtiene el
original
J. Galaviz
19
Si se puede
Errores de uso.
Llaves por mensaje
Reporte del clima
Criptoanlisis polaco e
ingls.
Bletchley Park, Alan
Turing, COLOSSUS.
J. Galaviz
20
Parientes cercanos
Mquinas de cifrado
de rotores CSP488, p.
ej.
Esquemas de cifrado
modernos como DES
(Data Encryption
Standard, 1976).
J. Galaviz
21
Olvidando la simetra
Que tal si usamos una clave para cifrar y otra para
descifrar.
Directorio de personas. Cada persona registra en el
directorio su clave para cifrarle mensajes.
Cada persona del directorio posee adems una clave
secreta para descifrar sus mensajes.
Cualquier persona puede enviar mensajes cifrados a
cualquier otra. Solo el destinatario puede descifrar los
mensajes.
Conocer la clave para cifrar no proporciona mucha
informacin para determinar la clave para descifrar.
J. Galaviz
22
Funciones de un solo sentido

(One-way functions)
Rompecabezas: es fcil desarmarlo, difcil
armarlo. A cada pieza le toca una posicin y
cada posicin tiene su pieza (funcin
biyectiva, invertible).
tiles en criptografa: escribir un mensaje
en un rompecabezas, numerar las piezas y
hacer un patrn. Quien tiene el patrn
puede recuperar rpido el mensaje.
J. Galaviz
23
El problema de la factorizacin
Teorema fundamental de la aritmtica: todo
nmero natural es expresable como el
producto de nmeros primos.
Es fcil multiplicar, es fcil (aunque
tardado) obtener nmeros primos, pero
dado un nmero, no es fcil obtener su
factorizacin en primos.
J. Galaviz
24
El problema del logaritmo

discreto
Dados dos nmeros naturales, es fcil
elevar uno de ellos a la potencia del otro.
Hay ciertos conjuntos finitos, pero grandes,
en los que dados dos nmeros a y b no es
fcil determinar el valor de x tal que a=bx.
J. Galaviz
25
Diffie-Hellman
Alicia y Bartolo deben
ponerse de acuerdo en
un nmero secreto.
Solo pueden hablarse
a gritos en un cuarto
lleno de enemigos que
los estn escuchando.
1976
J. Galaviz
26
Protocolo de intercambio de
clave
A y B se ponen de acuerdo en el conjunto en el que
van a trabajar y eligen un elemento g.
A escoge un nmero x y le enva a B: QA=g x.
B escoge un nmero y y le enva a A: QB=g y.
A calcula KA=QBx.
B calcula KB=QAy.
KA=KB, calcularon el mismo nmero.
Creemos que nadie puede calcularlo si no calcula el
logaritmo discreto de QA y QB
J. Galaviz
27
Transmisin de mensajes
Massey-Omura
A enva a B un mensaje
cifrado con una clave
secreta.
B no lo entiende, pero lo
cifra y lo enva de regreso.
A aplica su descifrado y
enva el resultado a B.
B recibe el mensaje de
regreso y le aplica su
descifrado, recupera el
mensaje original.
J. Galaviz
28
RSA
Rivest, Shamir,
Adleman, 1977.
Basado en el problema
de la factorizacin.
J. Galaviz
29
Seguridad en web
Taher ElGamal.
SSL (secure sockets
layer, Netscape).
Mecanismos de
cifrado para la
transmisin segura de
informacin
confidencial.
Comercio electrnico.
J. Galaviz
30
Qu sigue?
Nuevos paradigmas de computacin pueden
cambiar la nocin de qu es difcil y qu no lo es.
Usando computadoras cunticas sera posible
resolver algunos problemas difciles en tiempos
razonables.
Nuestros actuales esquemas criptogrficos dejan
de ser seguros.
Pero no hay problema, surgen nuevos posibles
esquemas criptogrficos.
J. Galaviz
31

Criptografía

Cargado por

Copyright:

Formatos disponibles

Criptografía

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Criptografía

Cargado por

Copyright:

Formatos disponibles

Secretos Compartidos:

El medio de comunicacin es inseguro.

Qu tan seguro es?

Un secreto mal guardado

Funciones de un solo sentido

El problema del logaritmo

También podría gustarte