PDF de programación - Criptografía 5º curso de ingeniería informática - Criptografía de clave pública

Imágen de pdf Criptografía 5º curso de ingeniería informática - Criptografía de clave pública

Criptografía 5º curso de ingeniería informática - Criptografía de clave públicagráfica de visualizaciones

Publicado el 15 de Septiembre del 2018
315 visualizaciones desde el 15 de Septiembre del 2018
1,9 MB
61 paginas
Creado hace 12a (11/02/2009)
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 2008/2009

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
  • Links de descarga
http://lwp-l.com/pdf13503

Comentarios de: Criptografía 5º curso de ingeniería informática - Criptografía de clave pública (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad