Embed Size (px)
Citation preview
05. Criptografía de clave
pública
Criptografía
5º Curso de Ingeniería Informática
Escuela Técnica Superior de Ingeniería Informática
Universidad de Sevilla
• Cifrado con clave pública
• Ventajas e inconvenientes
• RSA
• ElGamal clásico
• ElGamal elíptico
• Comparativa
Contenido
• Primeramente propuesto por Diffie y
Hellman en 1.976.
Cifrado con clave pública
• Algoritmos basados en funciones matemáticas
y no en operaciones sobre patrones de bits.
• Es asimétrica, implica el uso de dos claves.
Éste hecho posee importantes consecuencias
en los ámbitos de la confidencialidad, distribución
de claves y la autentificación.
• Concepto de función de un solo sentido.
Intercambio Diffie-Hellman• Problema del Logaritmo Discreto (PLD)
Dado hallar )(mod pgy x )(modlog pyx g
• Para que PLD sea difícil de resolver:
–g debe dar lugar a muchas potencias distintas
–p debe ser un número primo fuerte
)(mod pgy ax
a
)(mod pgyy baba xxx
a
x
b
)(mod pgy bx
b
• Intercambio de clave, conocido (p,g):– A toma 1<xa<p-1 y envía a B
– B toma 1<xb<p-1 y envía a A
– Clave común:
Intercambio Diffie-Hellman
)(mod pgy ax
a
)(mod pgyy baba xxx
a
x
b
)(mod pgy bx
b
• Intercambio de clave, conocido (p,g):– A toma 1<xa<p-1 y envía a B
– B toma 1<xb<p-1 y envía a A
– Clave común:
57,46,21,71 ba xxgp
)71(mod16961)71(mod6121
)71(mod921 5746
57
46
b
a
y
y
Intercambio Diffie-Hellman• Problema del Logaritmo Discreto (PLD)
Dado hallar )(mod pgy x )(modlog pyx g
• Para que PLD sea difícil de resolver:
–g debe dar lugar a muchas potencias distintas
–p debe ser un número primo fuerte
Un elemento g se denomina primitivo o generador de
un grupo (G,·) si sus potencias generan todo el grupo
Un primo p se dice fuerte si es de la forma
Para ciertos primos grandes r, s y t
rp 1 sr 1 tp 1
Búsqueda de generadores
Método de selección de elementos primitivos
Entrada: p primo, con
Elegir al azar en
Para i desde 1 hasta t hacer
si entonces empezar de nuevo
Fin para
Salida: elemento primitivo
}1,,2,1{* pp Z
trrppp 11
11
}1,,2,1{},,,,1{ *220 pp
p Z
)(mod1
1
pip
p
Búsqueda de generadores23218
}18,,2,1{},,,,1{ *
19
1720 Z
}18,,2,1{,19 *
19 Zp
111111711771
118111118181
987654321
6
9
x
x
177117111111
181118181818118
181716151413121110
6
9
x
x
Búsqueda de números primos
Test de Miller-Rabin: probables primos
Entrada: n impar, con para r impar
Elegir 1<a<n al azar
si ó
entonces n es primo con una probabilidad mayor o igual que
en otro caso n es compuesto
Aplicar el test k veces aumenta la probabilidad a
12 rn s
)(mod1 nar 10),(mod12 sjna rj
4
3
k4
11
En adelante, primo significará probable primo
según Miller-Rabin
Búsqueda de primos fuertes
Test de Gordon: probables primos fuertes
Entrada: s y t primos
Elegir el primer primo r de la forma 2it+1 para i≥i0
Salida: primo fuerte, consistente en el primer primo
de la forma
0
2 para ,21)(mod2 jjjrssrsr
Requiere un 19% más de tiempo que Miller-Rabin
Funciones de un solo sentidof() es una función de un solo sentido si:
1. Dado cualquier y es computacionalmente imposible
hallar x tal que f(x)=y.
2. Existe una función h y una información secreta s tal que
conocidos s e y:
– es fácil de calcular h(s, y).
– f(h(s, y)) = y.
La información s se denomina puerta trasera.
Tras un criptosistema asimétrico siempre hay
una función de un solo sentido con puerta trasera
Se traduce en que descifrar resulta imposible...
...si no se conoce la puerta trasera
Clave pública: cifrado ingenuo
1.Cada usuario genera una pareja de claves para
el cifrado y el descifrado de mensajes.
2. Cada usuario da a conocer su clave pública.
3. Si un usuario A quiere enviar un mensaje a B,
cifra el mensaje usando la clave pública de B.
4. Cuando B recibe el mensaje, lo descifra
usando su clave privada. Ningún otro receptor
puede descifrar el mensaje pues sólo B conoce
su clave privada.
Es débil por suplantación
Clave pública: cifrado ingenuo
)(MECBKU )(CEM
BKR
A B
O)(MEOKU )'(ME
BKU
Cifrado con autenticaciónCifrado con autentificación1.Cada usuario genera una pareja de claves para
el cifrado y el descifrado de mensajes.
2. Cada usuario da a conocer su clave pública.
3. Si un usuario A quiere enviar un mensaje a B,
cifra el mensaje doblemente, primero usando
su clave privada y después la pública de B.
4. B descifra el mensaje usando primero su clave
privada y después la pública de A. Ningún otro
receptor puede descifrar el mensaje pues sólo
B conoce su clave privada. El mensaje procede
de A: lo autentifica el uso de su clave pública.
Cifrado con autentificación
A B AB
))(( MEECAB KRKU ))(( CEEM
BA KRKU
Ventajas e inconvenientes
• Ventajas
– Versátiles: resuelven muchos problemas.
– Seguros.
– No tienen problemas para la distribución de claves.
• Inconvenientes
– Lentos.
– Suelen necesitar soportes especiales: aritméticas de
grandes números y otras.
– Difíciles de implementar en hardware.
RSA
Generación de claves
1. Se eligen dos números primos suficientemente
grandes p, q. Se hace n = p·q, Φ = (p-1)· (q-1)
2. Se elige e primo con Φ y se calcula d, un
número tal que el resto de dividir d · e entre Φsea 1.
3. Clave pública: (n, e). Clave privada: d.
))((mod
)1)(1()(
1 ned
qpne
pqn
RSA
Cifrado y descifrado
• Los mensajes se dividen en bloques de bits y cada
bloque se representa con un número entre 0 y n.
• Si un bloque es x el cifrado es y, el resto de dividir
xe entre n.
• Si se recibe y, se obtiene x calculando el resto de
dividir yd entre n.
)(mod nxy e
)(mod
)(mod)(mod
)1(mod
)1(mod
qy
pynyx
qd
pd
d
)(mod)()(1 nxxxxxyknnkded
RSA
Método de la potencia rápida
Entrada: b,n,e=(ck-1,...,c0)2
t=1
Para j desde k-1 hasta 0 hacer
t=t2 (mod n)
si cj=1 entonces t=b· t (mod n)
Fin para
Salida: t=be (mod n)
0
0
1
1220
0
1
1 22ccek
k bbbccek
k
RSA
47612867 qpn
27604660)1)(1()( qpn
2503)2760(mod247247 1 de
2085)2867(mod15751575 247 CM
1575)2867(mod20852085 2503 MC
24)47(mod17
50)61(mod11)2867(mod2085
19
43
2503TCR
Euler
M
1575)10(6124134750 M
1134710614761 Bezout
Seguridad de RSA
• p y q deben ser primos no próximos entre sí
para evitar la factorización de n
• El mínimo común múltiplo de p-1 y q-1 ha de
ser grande para disminuir el número de claves
privadas útiles di para descifrar el cifrado con e
• Las elecciones de n y de e deben evitar la
proliferación de mensajes que no se cifren
Seguridad de RSA
• p y q deben ser primos no próximos entre sí
para evitar la factorización de n
Factorización de Fermat
2,
2 para ,22 qp
yqp
xynxpqn
Idea: buscar (x,y) con x2-n=y2 para x2>n
112.349,121879 nn
693350 2 nxx 1322351 2 nxx
307,39745352 2 qpnxx
Seguridad de RSA
• El mínimo común múltiplo de p-1 y q-1 ha de
ser grande para disminuir el número de claves
privadas útiles di para descifrar el cifrado con e
)(mod seay ),1,1( Sea 1 edqpmcm
Es evidente que <(n), pues p-1 y q-1 son
ambos pares, por lo que d
diferirá en general de
d. Pero
)(mod
)(mod
)(mod)(mod nM
MqM
MpMnC
Eulered
Eulered
d
dniiddi 0, para mismo Lo
Seguridad de RSA
• El mínimo común múltiplo de p-1 y q-1 ha de
ser grande para disminuir el número de claves
privadas útiles di para descifrar el cifrado con e
210)42,70( ,43,71,3053 Sea mcmqpn
14210
10330530,210103
:descifrado de válidasClaves
iidi
1573)2940(mod1572940)3053(157 1 de
103)210(mod157210157 1
de
3043,2833,2623,2413,2203,1993,1783
,1573,1363,1153,943,733,523,313,103
Seguridad de RSA
• Las elecciones de n y de e deben evitar la
proliferación de mensajes que no se cifren
)(mod
)(mod)(mod
)1(mod
)1(mod
qMM
pMMnMM
qe
pe
e
Se puede probar que la ecuación xe=x (mod p) tiene
exactamente 1+mcd(e-1,p-1) soluciones, para p primo
M
qemcdpemcdMM e
diferentes mensajes
)]1,1(1[)]1,1(1[ para
Seguridad de RSA
• Las elecciones de n y de e deben evitar la
proliferación de mensajes que no se cifren
)19(mod
)29(mod)551(mod
13
13
13
MM
MMMM
13 ,19,29,551 Sea eqpn
}28,17,12,1,0{)29(mod13 MMM
}18,12,11,8,7,1,0{)19(mod13 MMM
La primera ecuación tiene 1+mcd(12,28)=5 soluciones
La segunda ecuación tiene 1+mcd(12,18)=7 soluciones
La ecuación primigenia tiene 5·7=35 soluciones
}550,539,521,505,494,493,476,464,463,436,418,407,406,360,349,331
,278,273,220,202,191,145,144,133,115,88,87,75,58,57,46,30,12,1,0{
Ataques a RSA
• Cíclico: elevar reiteradamente el mensaje
cifrado a la clave pública e hasta que se
obtenga el mensaje cifrado original
• Factorización de n
• Merkle-Hellman: buscar exponentes i y j
tales que Mi=Mj (mod n)
ElGamal ClásicoTaher ElGamal propone en 1985 un algoritmo de cifra
que hace uso del problema del logaritmo discreto PLD
•Generar un primo fuerte p para definir el grupo Zp*
•Tomar g un elemento generador de Zp*
•Cada usuario elige un número aleatorio 1<x<p
•El valor x será la clave privada
•Cada usuario calcula gx mod p•Los valores gx mod p, g y p serán la clave pública
•Seguridad del sistema
•Para descubrir la clave privada, el atacante deberá
enfrentarse al problema del logaritmo discreto.
ElGamal clásico
Cifrado con ElGamal
Cifrado: A cifra un número M que envía a B
•El usuario B ha elegido su clave privada x, (1<x<p-1)
•El usuario B ha hecho pública su clave, g, p e y=gx mod p
•El emisor A genera un número aleatorio k de sesión
(1<k<p-1) y envía a B
C=[gk mod p, M*yk mod p]
Los mensajes se dividen en bloques de bits y cada bloque se
representa con un número entre 1 y p-1.
Cifrado con ElGamal
Descifrado con ElGamal
Descifrado: B descifra el criptograma C que envía a A
•El usuario B recibe C=[gk mod p, M*yk mod p]
•B toma el valor gk mod p y calcula [(gk)x]-1 mod p
•B descifra el criptograma C
D(C)= M*yk * [(gk)x]-1 mod p=M
yk * [(gk)x]-1 mod p=(gx)k * [(gk)x]-1 mod p=1
Descifrado con ElGamal
ElGamal clásico
Ejemplo:
•Benito toma p=2579, g=2 (elemento generador de Z*2579) y
x=765 (valor aleatorio) y calcula y=2765 mod 2579=949.
•Clave pública: (p,g,y) Clave privada: x
•.Alicia envía el mensaje M=1299 cifrado a Benito. Toma k=853aleatoriamente
•C=E(M)=[2853 mod 2579, 1299 * 949853 mod 2579]=[435, 2399]
•M=D(C)=2396 * (435765)-1 mod 2579= 1299
Ejemplo: ElGamal
ElGamal clásico
Observaciones:
•Un mismo mensaje M puede cifrase de distinta manera si se
elige distintos valores de k.
•El tamano del criptograma C es el doble del mensaje M.
•En la práctica estos sistemas sólo se úsan para cifrar claves
de sesión o resúmenes. Por tanto, M= números de centenas
de bits mientras que p (en ElGamal) y n (RSA) números de
miles de bits.
ElGamal Clásico
Curvas elípticas
Curvas elípticas
Suma de puntos
Suma de puntos
Sobre un cuerpo finito
ECC
ECC
Cifrado ECC
Descifrado ECC
Tamaños de claves
