PDF de programación - Capítulo 14 Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14

Cifrado Asimétrico Exponencial

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 89 diapositivas

v 4.1

Material Docente de
Libre Distribución

Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.

Curso de Seguridad Informática y Criptografía © JRA

Capítulo 14: Cifrado Asimétrico Exponencial

Página 622

Aquí ciframos números, no mensajes

• La operación característica de la cifra asimétrica es mediante un

cifrado exponencial. La operación a realizar será C = AB mod n, en
donde n es el cuerpo de cifra del orden de 1.024 bits, B es una clave
pública 17 bits para el intercambio de clave y cerca de 1.024 bits de la
clave privada para firma digital. A será siempre un número N (nunca
un mensaje M) y por lo general del orden de las centenas de bits.

•

• Esto es así porque este tipo de cifra es muy lenta y sería muy costoso
en tiempo cifrar, por ejemplo, mensajes de cientos o miles de bytes.
Por lo tanto, cuando se cifre con la clave pública de destino para
hacer un intercambio de clave, se tratará de un número N del orden de
los 128 bits (la clave de sesión), y cuando se cifre con la clave
privada de emisión para una firma digital, se tratará de un número N
de 160 bits, por ejemplo un hash SHA-1 sobre el mensaje M.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 623

Otros casos de cifra exponencial

• La cifra con la clave privada de recepción cuando desciframos
un número o dato que se nos ha enviado confidencialmente, o
bien la cifra con la clave pública del emisor para comprobar
así su firma digital, serán casos de descifrado.

• En el primero de ellos, puesto que se recibe un número muy

grande dentro del cuerpo de cifra con n bits y la clave privada
será también de esa magnitud, en el caso de RSA se realizará
el descifrado usando el Teorema del Resto Chino.

• Si deseamos cifrar mensajes M con estos algoritmos, se puede
hacer formando bloques de cifra, al igual que se hace con los
sistemas simétricos, pero recuerde que esto tiene sentido sólo
para prácticas de laboratorio y nunca en sistemas reales.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Página 624

Cifrado exponencial con clave del receptor

• Al cifrar el número N y en el descifrado del criptograma
C se usará una exponenciación: Ee(N) = C y Ed(C) = N.
• En la operación de cifrado, el subíndice e significará el
uso de la clave pública del receptor (R) en el extremo
emisor y el subíndice d el uso de la clave privada del
receptor (R) en el extremo receptor.

C = EeR(N) = NeR mod nR ⇒ N = EdR(C) = CdR mod nR

• N deberá ser un elemento del CCR de nR.
• Esta operación se usará para realizar el intercambio de

una clave de sesión entre un emisor y un receptor.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 625

Cifrado exponencial con clave del emisor

• En la operación de cifrado el subíndice d significa el uso
de la clave privada del emisor (E) en el extremo emisor,
y el subíndice e el uso de la clave pública del emisor (E)
en el extremo receptor.

C = EdE(N) = NdE mod nE ⇒ N = EeE(C) = CeE mod nE

• N deberá ser un elemento del CCR de nE.
• Esta operación se usará para autenticar la identidad de un
usuario mediante una firma digital, al mismo tiempo que
se demuestra la integridad del mensaje mediante un hash.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Página 626

Cifrado exponencial genérico tipo RSA

Sea el grupo de trabajo n = p∗q ⇒ φ(n) = (p-1)(q-1)
Se eligen una clave pública e y una privada d de forma que:
e∗d mod φ(n) = 1 ⇒ e∗d = k(p-1)(q-1) + 1.

Si e∗d = kφ(n) + 1

Por el Teorema de Euler
se tiene que:

y ...

Nkφ(n) mod n = 1

para todo N primo con n

Por el Teorema del Resto
Chino se tiene que:
Ned = N mod n

ssi Ned = N mod p
Ned = N mod q
Luego, el sistema de cifra será
válido para cualquier valor de N

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 627

Operación de descifrado exponencial

Al cifrar el número N con una clave pública e (en este caso
para realizar un intercambio de clave, aunque es igual de
válido con una clave d en caso de firma digital) tenemos:
Cifrado:
Descifrado: Cd mod n = (Ne)d mod n = Ned mod n

C = Ne mod n

Cd mod n = Nkφ(n)+1 mod n = N∗Nkφ(n) mod n
Cd mod n = N∗1 mod n = N mod n

Por lo tanto, la operación Cd mod n recuperará el número N.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Página 628

Comprobación de la recuperación de N

Sea n = p∗q = 5∗11 = 55 ⇒ φ(n) = (5-1)(11-1) = 40
Sea el número N = 50 = 2∗52 (debe ser un elemento de n = 55)
Se elige e = 3 ⇒ d = inv[e, φ(n)] = inv (3, 40) = 27

e∗d mod φ(n) = 3∗27 mod 40 = 81 mod 40 = 1

C = Ne mod n = 503 mod 55 = (2∗52)3 mod 55
C = [(2)3 mod 55 ∗ (52)3 mod 55] mod 55 - por reducibilidad -
N = Cd mod n = {[(2)3 mod 55 ∗ (52)3 mod 55] mod 55}27 mod 55
N = [(2)3∗27 mod 55 ∗ (52)3∗27 mod 55] mod 55
N = [22φ(n)+1 ∗ 52φ(n)+1 ∗ 52φ(n)+1] mod 55
Por el Teorema de Euler y del Resto Chino = 2 ∗ 5 ∗ 5 mod 55 = 50

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 629

Intercambio de clave de Diffie y Hellman

• El comienzo de los sistemas de clave pública se debe al estudio

hecho por Whitfield Diffie y Martin Hellman (1976).

Protocolo de Intercambio de Claves de Diffie y Hellman

A y B seleccionan un grupo multiplicativo (con inverso) p
y un generador α de dicho primo, ambos valores públicos.

• A genera un número aleatorio a y envía a B αa mod p
• B genera un número aleatorio b y envía a A αb mod p
• B calcula (αa)b mod p = αab mod p y luego destruye b
• A calcula (αb)a mod p = αba mod p y luego destruye a
• El secreto compartido por A y B es el valor αab mod p

http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/diffie-hellman.pdf



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Página 630

Ejemplo de intercambio de clave de DH

Adela (A) y Benito (B) van a intercambiar una clave de
sesión dentro del cuerpo primo p = 1.999, con α = 33. El
usuario A elegirá a = 47 y el usuario B elegirá b = 117.

Algoritmo:
• A calcula αa mod p = 3347 mod 1.999 = 1.343 y se lo envía a B.
• B calcula αb mod p = 33117 mod 1.999 = 1.991 y se lo envía a A.
• B recibe 1.343 y calcula 1.343117 mod 1.999 = 1.506.
• A recibe 1.991 y calcula 1.99147 mod 1.999 = 1.506.

La clave secreta compartida por (A) y (B) será K = 1.506

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 631

¿Puede un intruso atacar la clave DH?

Un intruso que conozca las claves públicas p y α e
intercepte el valor αa mod p que ha enviado A y el
valor αb mod p que ha enviado B no podrá descubrir
los valores de a, de b y ni menos αab mod p ...

Salvo que se enfrente al Problema del Logaritmo
Discreto (PLD) que, como ya hemos visto, se
vuelve computacionalmente intratable para valores
del primo p grandes.

© Jorge Ramió Aguirre Madrid (España) 2006

http://en.wikipedia.org/wiki/Discrete_logarithm



Capítulo 14: Cifrado Asimétrico Exponencial

Página 632

Seguridad del intercambio de clave de DH

• La seguridad del intercambio de clave de Diffie y Hellman radica

en la imposibilidad computacional a la que se enfrentará el
criptoanalista al tener que resolver el problema del logaritmo
discreto para encontrar la clave privada que se encuentra en el
exponente de la expresión αi mod p = C.

• Como p y α serán públicos, al capturar el valor C el atacante
deberá resolver i = logα C mod p, un problema no polinomial
(debido a la operación final dentro del módulo p) que para valores
grandes de p (del orden o superior a los 1.000 bits) resulta
computacionalmente imposible encontrar su solución.

• El algoritmo propuesto inicialmente es vulnerable ante un ataque
del tipo “man in the middle” como veremos a continuación. No
obstante, esta vulnerabilidad puede evitarse.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 14: Cifrado Asimétrico Exponencial

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 14: Cifrado Asimétrico Exponencial

Página 633

¿Es vulnerable el protocolo de DH?
• A elige un número a con 1 < a < p-1 y envía a B αa mod p
• C intercepta este valor, elige un número c con 1 < c < p-1 y

envía a B αc mod p

• B elige un número b con 1 < b < p-1 y envía a A αb mod p
• C intercepta este valor y envía a A αc mod p (valor anterior)
• A y B calculan sus claves kA = (αc)a mod p, kB = (αc)b mod p
• C calcula también las claves:

¿Qué hacer?

• kCA = (αa)c mod p
• kCB