Actualizado el 7 de Mayo del 2019 (Publicado el 15 de Septiembre del 2018)
809 visualizaciones desde el 15 de Septiembre del 2018
1,9 MB
61 paginas
Creado hace 17a (24/03/2008)
CRIPTOGRAFÍA
5º CURSO DE INGENIERÍA INFORMÁTICA
Criptografía de clave pública
E.T.S.I. Informática
Universidad de Sevilla
Curso 2007/2008
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
CRIPTOGRAFÍA DE CLAVE PÚBLICA
SI la clave es pública cualquiera puede
descifrar,… ¿o no?
Idea fundamental:
◦ Asimetría separación de claves: una pública que
cifra y otra privada que descifra.
Dos ejemplos:
1. El cartero fiel:
Clave pública: mi dirección.
Clave privada: la llave de mi buzón.
2. El fabricante de cajas de seguridad:
Clave pública: una caja abierta, que se bloquea al cerrarla.
Clave privada: mi llave de la caja.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Cifrado y descifrado asimétrico: la clave
pública la tienen todos, la clave privada
sólo la tiene el destinatario:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
¡Ni el mismo emisor puede descifrar!
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Un poco de (pre)historia:
El concepto de criptosistema de clave pública fue
descubierto por James Ellis (Government
Communications Headquarters) al final de los años
60 (7 años antes que DH).
Clifford Cocks desarrolló esas ideas y descubrió un
criptosistema equivalente a RSA en 1973 (3-4 años
antes que Rivest, Shamir y Adleman).
Malcolm Williamson, buscando fallos en el trabajo de
Cocks, descubre el Intercambio de claves DH en
1975 (un año antes que Diffie y Hellman).
Los servicios secretos no supieron valorar estos
descubrimientos, pero los mantuvieron en secreto y el mérito
fue para otros.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Whitfield Diffie y Martin Hellman publicaron
el artículo “New Directions in Cryptography”
en 1976.
• Los autores afirman que
sería posible implementar
criptosistemas de clave
pública usando esotéricas
funciones relacionadas con
difíciles problemas
matemáticos.
Hellman, Merkle y Diffie
• No hacen propuestas
concretas.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
CRIPTOGRAFÍA DE CLAVE PÚBLICA
¿Cuáles son esas mágicas funciones
matemáticas?
Funciones de un solo sentido:
◦ En realidad son funciones biyectivas… ¡de otra forma no
se podría descifrar!
◦ Lo importante es que para ser capaz de invertirlas hay
que conocer cierta información: ¡la clave privada!.
◦ Si no se conoce la clave privada es computacionalmente
imposible invertir la función.
¿Quién conoce una función así?
◦ Esta pregunta queda en pie tras el artículo de Diffie y
Hellman.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
CRIPTOGRAFÍA DE CLAVE PÚBLICA
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
La función de un solo sentido,
trabajando en el sentido fácil.
La información necesaria es
pública.
La función sólo puede invertirse
si se conoce la clave privada.
Sólo para tus ojos.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: MOCHILA DE MERKLE-HELMAN
Merkle y Hellman propusieron en 1977 el
que fue (probablemente) el primer
sistema de cifrado de clave pública.
Basado en el problema subset-sum:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
El problema es NP-completo y es llamado
a menudo el problema de la mochila.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: UN PARÉNTESIS MATEMÁTICO
El caso de la mochila supercreciente:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: GENERACIÓN DE CLAVES
Cada usuario crea su clave pública y
la correspondiente clave privada:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
MH: CIFRADO Y DESCIFRADO
B cifra un mensaje para A
A descifra el mensaje de B
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
MH: ¿POR QUÉ FUNCIONA EL DESCIFRADO?
La operación que se realiza en el descifrado es:
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
MH: SEGURIDAD
El problema general subset-sum es NP-completo,
pero el particular de la mochila derivada de una
supercreciente no lo es.
Se conoce un ataque capaz de romper el
criptosistema en tiempo polinomial.
El único sistema criptográfico basado en el
problema de la mochila para el que aún no se
conoce un ataque con éxito es el de Chor-
Rivest.
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA
En 1977 Ron Rivest, Adi Shamir y Len Adleman
propusieron un criptosistema de clave pública
sustentado en el que pasó a llamarse el
problema RSA, basado en la factorización de
enteros.
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Inversos módulo n :
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
RSA: UN PARÉNTESIS MATEMÁTICO
Teorema Chino del Resto (TCR)
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
RSA: UN PARÉNTESIS MATEMÁTICO
Cálculo de potencias enteras
o La idea:
o El seudocódigo de una versión no recursiva sería así:
s = 1, t = m, q = e;
mientras (q > 0)
si (q & 1) // si q es impar
s = s * t;
q = q / 2; // división entera(desplazamiento)
t = t * t;
retorna s;
o Sin ordenador es un poco diferente. Ejemplo de cálculo de 2100:
⟶ 1C1C0C0C1C0C0 ⟶ MCMC0C0CMC0C0 ⟶ MCMCCCMCC
100 =11001002
1 ──M──► 2 ──C──► 4 ──M──► 8 ──C──► 64
──C──► 4096 ──C──► 16777216 ──M──► 33554432
──C──► 1125899906842624
──C──► 1267650600228229401496703205376
No son100 multiplicaciones,
sino sólo 9 (máximo = 2· nº de
bits del exponente - 1).
Criptografía – 5º Curso de Ingeniería Informática – Universidad de Sevilla
Criptografía
de clave pública
El criptosistema
de mochila de
Merkle-Hellman
El criptosistema
RSA
El criptosistema
Elgamal
Criptografía de
curvas elípticas
RSA: UN PARÉNTESIS MATEMÁTICO
Construcción de primos grandes
Se construye un entero impar de
Crear cuenta
Comentarios de: 05. Criptografía de clave pública Criptografía - Criptografía de clave pública (0)
No hay comentarios