PDF de programación - 05. Criptografía de clave pública

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

Contenido

• Cifrado con clave pública

• Ventajas e inconvenientes

• RSA

• ElGamal clásico

• ElGamal elíptico

• Comparativa

Cifrado con clave pública

• Primeramente propuesto por Diffie y

Hellman en 1.976.

• 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

• Para que PLD sea difícil de resolver:

–g debe dar lugar a muchas potencias distintas
–p debe ser un número primo fuerte

• 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:

)(modpgyx)(modlogpyxg)(modpgyaxa)(modpgyybabaxxxaxb)(modpgybxbIntercambio Diffie-Hellman

• 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:

)(modpgyaxa)(modpgyybabaxxxaxb)(modpgybxb57,46,21,71baxxgp)71(mod16961)71(mod6121)71(mod92157465746bayyIntercambio Diffie-Hellman
• Problema del Logaritmo Discreto (PLD)

Dado hallar

• 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

)(modpgyx)(modlogpyxgrp1sr1tp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Ztrrppp1111}1,,2,1{},,,,1{*220pppZ)(mod11pippBúsqueda de generadores

23218}18,,2,1{},,,,1{*191720Z}18,,2,1{,19*19Zp11111171177111811111818198765432169xx17711711111118111818181811818171615141312111069xx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
En adelante, primo significará probable primo
según Miller-Rabin

12rns)(mod1nar10),(mod12sjnarj43k411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

Requiere un 19% más de tiempo que Miller-Rabin

02 para ,21)(mod2jjjrssrsrFunciones de un solo sentido
f() es una función de un solo sentido si:

1. Dado cualquier y es computacionalmente imposible

hallar x tal que f(x)=y.
Se traduce en que descifrar resulta imposible...
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.

...si no se conoce la puerta trasera

–

–

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

Clave pública: cifrado ingenuo

Es débil por suplantación

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.

Clave pública: cifrado ingenuo

)(MECBKU)(CEMBKRABO)(MEOKU)'(MEBKUCifrado con autentificación
Cifrado con autenticación
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 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

ABAB))((MEECABKRKU))((CEEMBAKRKU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 eprimo con Φ y se calcula d, un

número tal que el resto de dividir d · eentre Φ
sea 1.

3. Clave pública: (n, e). Clave privada: d.

))((mod)1)(1()(1nedqpnepqn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 xel cifrado es y, el resto de dividir
xe entre n.

Si se recibe y, se obtiene xcalculando el resto de
dividir yd entre n.

)(modnxye)(mod)(mod)(mod)1(mod)1(modqypynyxqdpdd)(mod)()(1nxxxxxyknnkded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)

001122001122ccekkbbbccekkRSA

47612867qpn27604660)1)(1()(qpn2503)2760(mod2472471de2085)2867(mod15751575247CM1575)2867(mod208520852503MC24)47(mod1750)61(mod11)2867(mod208519432503TCREulerM1575)10(6124134750M1134710614761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

Idea: buscar (x,y) con x2-n=y2 para x2>n

2,2 para ,22qpyqpxynxpqn112.349,121879nn6933502nxx13223512nxx307,397453522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

Es evidente que <(n), pues p-1 y q-1 son
ambos pares, por lo que d diferirá en general de
d. Pero

)(mod seay ),1,1( Sea1edqpmcm)(mod)(mod)(mod)(modnMMqMMpMnCEuleredEuleredddniiddi0, 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1421010330530,210103 :descifrado de válidasClavesiidi1573)2940(mod1572940)3053(1571de103)210(mod1572101571de3043,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

Se puede probar que la ecuación xe=x (mod p) tiene
exactamente 1+mcd(e-1,p-1) soluciones, para p primo

)(mod)(mod)(mod)1(mod)1(modqMMpMMnMMqepeeMqemcdpemcdMMe 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

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

)19(mod)29(mod)551(mod131313MMMMMM13 ,19,29,551 Seaeqpn}28,17,12,1,0{)29(mod13MMM}18,12,11,8,7,1,0{)19(mod13MMM}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ásico
ElGamal Clásico

Taher 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 gun elemento generador de Zp

*

•Cada usuario elige un número aleatorio 1<x<p

•El valor xserá la clave privada

•Cada usuario calcula gxmod p

•Los valores gxmod p, g y pserán la clave pública

•Seguridad del sistema

•Para descubrir la clave privada, el atacante deberá
enfrentarse al problema del logaritmo discreto.

Cifrado con ElGamal

Cifrado con ElGamal

Los mensajes se dividen en bloques de bits y cada bloque se
representa con un número entre 1 y p-1.

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, pe y=gxmod p

•El emisor A genera un número aleatorio kde sesión
(1<k<p-1) y envía a B

C=[gkmod p, M*ykmod p]

Descifrado con ElGamal

Descifrado con ElGamal

Descifrado: B descifra el criptograma C que envía a A

•El usuario B recibe C=[gkmod p, M*yk mod p]

•B toma el valor gkmod p y calcula [(gk)x]-1mod p

•B descifra el criptograma C

D(C)= M*yk* [(gk)x]-1mod p=M

yk* [(gk)x]-1mod p=(gx)k * [(gk)x]-1mod p=1

Ejemplo: ElGamal

ElGamal clásico

Ejemplo