ing sistemas

CRIPTO II – UT II – N° 03

ASIMETRICA I

cripto-scolnik-hecht

UT-2
UNIDAD TEMÁTICA N° 2: Criptografía Asimétrica.
Funciones Unidireccionales. Funciones Trampa.
Historia de la Criptografía Asimétrica. Protocolo
de Diffie y Hellman para el intercambio de claves.
Métodos asimétricos y de clave pública (PohligHellman, RSA, Fiat-Shamir). Ataques a RSA.
Criptosistema de McElieceCriptosistemas
Basados en el Problema de la Mochila: MerkleHellman. Criptosistemas varios. Criptosistemas
Basados en el Problema de logaritmo discreto:
ElGamal, Ataque a El Gamal. Criptosistemas
Basados en Curvas Elípticas.

cripto-scolnik-hecht

CRIPTOGRAFIA ASIMETRICA
LOS
CRIPTOSISTEMAS
ASIMETRICOS
ESTAN
BASADOS EN SISTEMAS REVERSIBLES PERO POR
CAMINOS
DIFERENTES
EN
TERMINOS
DECOMPLEJIDAD ALGORITMICA PARA QUIEN NO
DISPONGA DE TODA LA INFORMACION NECESARIA

plano

plano

complejidad

complejidad

P

P

complejidad

NP

cifrado

cifrado

´criptosistema simétrico

´criptosistema asimétrico

cripto-scolnik-hecht

CRIPTOGRAFIA ASIMETRICA
CRIPTOGRAFIA
ASIMETRICA
NO
NECESARIAMENTE ES CRIPTOGRAFIA
DE CLAVE PUBLICA.
POR EJEMPLO EL ALGORITMO DEENCRIPCION DE POHLIG-HELLMAN ES
ASIMETRICO
PERO
NO
POSEE
INFORMACION PUBLICA.
criptografía asimétrica
criptografía de clave pública

cripto-scolnik-hecht

CRIPTOGRAFIA DE CLAVE PUBLICA
LOS CRIPTOSISTEMAS DE CLAVE PUBLICA SE BASAN
(AL IGUAL QUE EL RESTO DE LA CRIPTOGRAFIA
ASIMETRICA) EN PROBLEMAS COMPUTACIONALMENTE
COMPLEJOS (CLASES NP o NP-Completo) Y CUYAS
NPVIAS INVERSAS SEANSIMPLES (CLASE P) PERO NO
DEDUCIBLES UNA A PARTIR DE LA OTRA. LAS
FUNCIONES TRAMPA DE UNA VIA PERMITEN
IMPLEMENTAR ESTOS SISTEMAS DE AUTENTICACION,
ENCRIPCION Y FIRMA DIGITAL. LA VIA SIMPLE SE
HACE PUBLICA, LA CLAVE EXTRA DE LA VIA COMPLEJA
SE MANTIENE EN SECRETO Y PERMITE IDENTIFICAR A
QUIEN LA POSEE.

cripto-scolnik-hecht

FUNCIONES ASIMETRICAS
FUNCION DE UNA VIA:

y=f(x) es“computacionalmente fácil” (∈P)
P
pero x=f-1(y) es “computacionalmente difícil”
(∈ NP
NP)

FUNCION TRAMPA DE UNA VIA:

y=f(x) es “computacionalmente fácil” (∈ P)
y x=f-1(y) es “computacionalmente difícil”
(∈ NP pero contando con una “clave” extra
NP),
de información (trapdoor information)
x=f-1(y) se vuelve computable (∈ P)

cripto-scolnik-hecht

FUNCION DE UNA VIA

Tome el
platopreferido de
su señora y
arrójelo con
fuerza contra
el suelo

vía

P

vía

NP

Comprese “la
gotita” y
reconstruya
cuidadosamente
el plato

cripto-scolnik-hecht

FUNCION DE UNA VIA
FUNCION DIRECTA (∈P)
P

134078079299425970995740249982058461274793658205923933777235614
437217640300735469768018742981669034276900318581864860508537538
82811946569946433649006084171

x327339060789614187001318969682759915221664204604306478948329136
809613379640467455488327009232590415715088668412756007100921725
6545885393053328527588513

=

438889925503495094660474900094976741605951410874586565608960159
076495790540773835773214055962909023489062778027029768939596654
709019571832257928297343946696576711205193879175320603384442571957421143180749826560824534764835125246615339407939420184344133
72443658976181837273211017980201029191954963730727723

(t=1 µs)

cripto-scolnik-hecht

FUNCION DE UNA VIA
FUNCION INVERSA (∈ NP
NP)

438889925503495094660474900094976741605951410874586565608960159
076495790540773835773214055962909023489062778027029768939596654
709019571832257928297343946696576711205193879175320603384442571957421143180749826560824534764835125246615339407939420184344133
72443658976181837273211017980201029191954963730727723

=

134078079299425970995740249982058461274793658205923933777235614
437217640300735469768018742981669034276900318581864860508537538
82811946569946433649006084171

x

327339060789614187001318969682759915221664204604306478948329136
809613379640467455488327009232590415715088668412756007100921725...