I Congreso Nacional de Seguridad en Sistemas

Teleinformáticos y Criptografía
25-27 de septiembre de 2001 - Buenos Aires - Argentina

CONSECRI

Autenticación y firma digital

con criptosistemas asimétricos

Dr. Jorge Ramió Aguirre

videoconferencia
Universidad Politécnica de Madrid

Curso de Seguridad Informática © Jorge Ramió Aguirre

 Nota del autor
Curso de Seguridad Informática:
Este capítulo forma parte de un curso completo de Libre
Distribución sobre Seguridad Informática y Criptografía,
(sobre 450 diapositivas) que se está actualizando y
adaptando para permitir ahora su impresión en papel y que
puede encontrar en las siguientes direcciones de Internet:
Red Temática Iberoamericana:
http://www.criptored.upm.es

Página de la Asignatura:
http://www.lpsi.eui.upm.es/Sinformatica/Sinformatica.htm

Autenticación y Firma Digital 2

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Confidencialidad v/s integridad
Confidencialidad:
Para lograrla se cifra el mensaje M ⇒ criptograma
Integridad:
Para lograrla se firma el mensaje añadiendo una marca.

Si bien en ciertos escenarios es muy importante

mantener el secreto de la información, si ésta lo
requiere, en muchos casos tiene quizás más
trascendencia el poder certificar la autenticidad
entre cliente y servidor (Internet).
Autenticación y Firma Digital 3
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Los problemas de la integridad (I)
a) Autenticidad del emisor
¿Cómo comprueba Benito (B) que el mensaje recibido del emisor
que dice ser Adelaida (A) es efectivamente de esa persona?

b) Integridad del mensaje

¿Cómo comprueba Benito (B) que el mensaje recibido del emisor
Adelaida (A) es el auténtico y no un mensaje falso?

c) Actualidad del mensaje

¿Cómo comprueba Benito (B) que el mensaje recibido del emisor
Adelaida (A) es actual, no un mensaje de fecha anterior reenviado?

Autenticación y Firma Digital 4

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Los problemas de la integridad (II)
d) No repudio del emisor
¿Cómo comprueba Benito (B) que el mensaje enviado por el emisor
Adelaida (A) -y que niega haberlo enviado- efectivamente ha llegado?

e) No repudio del receptor

¿Cómo comprueba Benito (B) que el mensaje enviado al receptor
Adelaida (A) -y que niega haberlo recibido- efectivamente se envió?

d) Usurpación de identidad del emisor/receptor

¿Cómo comprueba Benito (B) que Adelaida (A), Clarisa (C) u otros
usuarios están enviando mensajes firmados como Benito (B)?

Autenticación y Firma Digital 5

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Escenarios de integridad (I)
A envía un mensaje M a B:
1er escenario de desconfianza
A cifra M con la clave KA ⇒
EKA(M) y lo envía al Juez.
Este comprueba la integridad
1ª Solución. Uso de un Juez. de A, lo descifra y envía a B,
El Juez tendrá una clave KA cifrado con KB, el mensaje M,
con la que se comunica con la identidad de A y la firma
A y una clave KB con la que EKA(M): EKB{M, A, EKA(M)}.
se comunica con B. Ambos confían en el Juez y
ante cualquier duda éste puede
Usa criptografía simétrica desvelar la identidad de A
descifrando EKA(M).
Autenticación y Firma Digital 6
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Escenarios de integridad (II)
2º escenario de desconfianza

No está claro que pueda

2ª Solución. Prescindir de la
convertirse en un estándar.
figura del Juez y aceptar la
Permanece la figura de la
Autoridad de Certificación autenticidad e integridad por
convencimiento propio y la
... es decir confianza en los algoritmos.
Ambosconfiarán
Ambos confiaránen
enun
unprotocolo
protocoloseguro
seguro
yyse
seautenticarán
autenticaránaatravés
travésde
deuna
una
Autoridadde
Autoridad deCertificación
CertificaciónAC.
AC.

Autenticación y Firma Digital 7

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Autenticación con sistemas simétricos
Si la clave de un sistema simétrico es segura, es decir no
está en entredicho, podemos afirmar que, además de la
confidencialidad que nos entrega dicha cifra, se
obtienen también simultáneamente la integridad del
emisor y autenticidad del mensaje, en tanto que sólo el
usuario emisor (en quien se confía por el modelo de
cifra) puede generar ese mensaje.

Con los sistemas de cifra simétricos no podremos

realizar una autenticación completa (emisor y mensaje).
Ahora bien, sí podrá hacerse algo similar con
procedimientos más o menos complejos que usen
sistemas simétricos como es el caso de Kerberos.

Autenticación y Firma Digital 8

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Requisitos de la firma digital
Al existir una clave pública y otra privada que
son inversas, se autentica el mensaje y al emisor.
Permite la firma digital, única para cada mensaje

Requisitos de la Firma Digital: Condicionesmás

Condiciones más fuertes
fuertes
a) Debe ser fácil de generar. queuna
que unafirma
firmamanuscrita
manuscrita

b) Será irrevocable, no rechazable por su propietario.

c) Será única, sólo posible de generar por su propietario.
d) Será fácil de autenticar o reconocer por su propietario
y los usuarios receptores.
e) Debe depender del mensaje y del autor.
Autenticación y Firma Digital 9
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Autenticación con sistemas asimétricos

No obstante, existe un problema...

Problema:
Los sistemas de cifra asimétricos son muy lentos y el mensaje
podría tener miles o millones de bytes ...
Solución: hash

Se genera un resumen del mensaje, representativo del mismo, con

una función hash imposible de invertir. La función hash comprime
un mensaje de longitud variable a uno de longitud fija y pequeña.

Autenticación y Firma Digital 10

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Funciones hash
Mensaje = M ⇒ Función Resumen = H(M)
Firma (rúbrica): r = EdE{H(M)}
dE es la clave privada del emisor que firmará H(M)
¿Cómo se comprueba la identidad en destino?
Se descifra la rúbrica r con la clave pública del
emisor eE. Al mensaje en claro recibido M’ (se
descifra si viene cifrado) se le aplica la misma
función hash que en emisión. Si los valores son
iguales, la firma es auténtica y el mensaje íntegro:
Calcula: EeE(M’) = H(M’) ¿Qué seguridad nos da
Compara: ¿H(M’) = H(M)? un resumen de k bits?

Autenticación y Firma Digital 11

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Propiedades de las funciones hash
H(M) será segura si tiene las siguientes características:

1. Unidireccionalidad. Conocido un resumen H(M), debe

ser computacionalmente imposible encontrar M a
partir de dicho resumen.
2. Compresión. A partir de un mensaje de cualquier
longitud, el resumen H(M) debe tener una longitud
fija. Lo normal es que la longitud de H(M) sea menor.
3. Facilidad de cálculo.
Debe ser fácil calcular H(M) a
partir de un mensaje M.
4. Difusión.El resumen H(M) debe ser una función
compleja de todos los bits del mensaje M.
Autenticación y Firma Digital 12
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Colisiones: resistencia débil y fuerte
5. Colisión simple.
Conocido M, será computacionalmente
imposible encontrar otro M’ tal que H(M) = H(M’). Se
conoce como resistencia débil a las colisiones.
6. Colisión fuerte.
Será computacionalmente difícil
encontrar un par (M, M’) de forma que H(M) = H(M’).
Se conoce como resistencia fuerte a las colisiones.

Ataque por la paradoja del cumpleaños

Para tener confianza en encontrar dos mensajes con el mismo
resumen H(M) -probabilidad ≥ 50%- no habrá que buscar en
2n (p.e. 2128), bastará una búsqueda en el espacio 2n/2 (264).
¡La complejidad algorítmica se reduce de forma drástica!

Autenticación y Firma Digital 13

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 La paradoja del cumpleaños
Paradoja del cumpleaños

Problema: Cuál será la confianza (probabilidad mayor que el 50%) de que

en un aula con 365 personas -no se tiene en cuenta el día 29/02 de los años
bisiestos- dos de ellas al azar cumplan años en la misma fecha.
Solución: Se escribe en la pizarra los 365 días del año y entran al aula de
uno en uno, borrando el día de su cumpleaños de la pizarra. Para alcanzar
esa confianza, basta que entren 23 personas al aula, un valor muy bajo, en
principio inimaginable y de allí el nombre de paradoja.
Explicación: El primero en entrar tendrá una probabilidad de que su número
no esté borrado igual a n/n = 1, el segundo de (n-1)/n, etc. La probabilidad p
de no coincidencia será igual a p = n!/(n-k)nk. Para k = 23 se tiene p = 0,493
y entonces la probabilidad de coincidencia es 0,507. Interesante ¿verdad? !

Autenticación y Firma Digital 14

© Jorge
Jorge Ramió
Ramió Aguirre.
Aguirre. UPM
UPM -- Madrid
Madrid (España)
(España) 2001
2001
 Algoritmos de resumen (compresión)
• MD5: Ron Rivest 1992. Mejoras al MD4 y MD2 (1990), es más lento
pero con mayor nivel de seguridad. Resumen de 128 bits.
• SHA-1: Del NIST, National Institute of Standards and Technology,
1994. Similar a MD5 pero con resumen de 160 bits.
• RIPEMD: Comunidad Europea, RACE, 1992. Resumen de 160 bits.
• N-Hash: Nippon Telephone and Telegraph, 1990. Resumen de 128
bits.
• Snefru: Ralph Merkle, 1990. Resúmenes entre 128 y 256 bits. Ha sido
criptoanalizado y es lento.
• Tiger: Ross Anderson, Eli Biham, 1996. Resúmenes de hasta 192 bits.
Optimizado para máquinas de 64 bits (Alpha).
• Panama: John Daemen, Craig Clapp, 1998. Resúmenes de 256 bits de
longitud. Trabaja en modo función hash o como cifrador de flujo.
• Haval: Yuliang Zheng, Josef Pieprzyk y Jennifer Seberry, 1992.
Admite 15 configuraciones diferentes. Hasta 256 bits.
Autenticación y Firma Digital 15
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Algoritmo básico de MD5
Algoritmo Message-Digest 5, MD5:
a) Un mensaje M se convierte en un bloque múltiplo de 512
bits, añadiendo bits si es necesario al final del mismo.
b) Con los 128 bits de cuatro vectores iniciales de 32 bits
cada uno y el primer bloque del mensaje de 512 bits, se
realizan diversas operaciones lógicas entre ambos.
c) La salida de esta operación (128 bits) se convierte en el
nuevo conjunto de vectores; se realiza la misma función
con el segundo bloque de 512 bits del mensaje ... etc.
d) Al terminar, el algoritmo entrega un resumen que
corresponde a los últimos 128 bits de estas operaciones.
Autenticación y Firma Digital 16
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Etapas de MD5

Etapas de MD5: Esquema

a) Añadir bits para congruencia módulo 512,

reservando los últimos 64 bits para un indicador.
b) Añadir indicación de la longitud del mensaje
con los 64 bits reservados.
c) Inicializar el buffer de claves MD (vector).
d) Procesar bloques de 512 bits.
e) Obtener el resumen de los últimos 128 bits.

Autenticación y Firma Digital 17

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Esquema de la función MD5
Relleno de 1 a 448 bits K mod 264
Mensaje de K bits
(64 bits)
Mensaje 1000... K

L∗512 bits = N∗ 32 bits AA1616 == 01234567

01234567
N palabras de 32 bits BB1616 == 89ABCDEF
89ABCDEF
CC1616 == FEDCBA98
FEDCBA98
512 bits DD1616 == 76543210
76543210

Y1 Y2 Yq YL-1

RESUMEN
HMD5 HMD5 HMD5 HMD5 de 128 bits
ABCD Primer resumen

Autenticación y Firma Digital 18

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Bloque principal de MD5
¿Qué hacen las funciones F y FF...?
Bloque principal
1er bloque de 512 Nuevo Vector ABCD
bits del mensaje M de 128 bits para el
Vector próximo bloque
inicial
A Vuelta Vuelta Vuelta Vuelta A
+
B 1 2 3 4 B
+
C C
Funciones Funciones Funciones Funciones +
D D
F y FF G y GG H y HH I e II +

+ SUMA MÓDULO 232

Autenticación y Firma Digital 19

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Esquema funciones F, G, H, I en MD5
Vector inicial ABCD a b c d
128 bits
AA1616 == 01234567
01234567
BB1616 == 89ABCDEF
89ABCDEF Función no Lineal
CC1616 == FEDCBA98
FEDCBA98
DD1616 == 76543210
76543210 x, y, z ⇒ b, c, d

FF(x,(x,y,y,z)z) (b,c,c,d)
FF(b, d)
((xxAND
ANDyy))OR (NOTxxAND
OR(NOT ANDzz)) (bAND
(b ANDc)c)OR OR(NOT
(NOTbbAND
ANDd)
d)
GG(x,(x,y,y,z)z) (b,c,c,d)
GG(b, d)
((xxAND
ANDzz))OR OR((yyAND NOTzz))
ANDNOT (bAND
(b ANDd) d)OROR(c(cAND
ANDNOT
NOTd)
d)
HH(x,(x,y,y,z)z) (b,c,c,d)
HH(b, d)
xxXOR
XORyyXOR XORzz bbXOR
XORccXOR XORdd
(x,y,y,z)z)
II(x, (b,c,c,d)
II(b, d)
yyXOR
XOR((xxOR NOTzz))
ORNOT ccXOR
XOR(b (bORORNOT
NOTd) d)
Autenticación y Firma Digital 20
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Algoritmo de las funciones en MD5
Desplazamiento del registro da ab bc dc
Situación luego del desplazamiento

Se repite el proceso para Función no lineal

Mj+1 hasta 16 bloques del
texto. En las vueltas 2, 3 y 4 +
se repite el proceso ahora 32 bits
+ Mj
con funciones G, H e I. 32 bits
+ tj
El algoritmo realiza sj bits a la
4∗16 = 64 vueltas <<< sj
izquierda
+
para cada uno de los
bloques de 512 bits + Suma
mod 232

Autenticación y Firma Digital 21

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Funciones no lineales en MD5
Funciones no lineales Vector de 128 bits
en cada vuelta: a b c d

1ª Vuelta:
FF(a,b,c,d,Mj,tj,s) ⇒ a = b + ((a + F(b,c,d) + Mj + tj) <<< s)
2ª Vuelta:
GG(a,b,c,d,Mj,tj,s) ⇒ a = b + ((a + G(b,c,d) + Mj + tj) <<< s)
3ª Vuelta:
HH(a,b,c,d,Mj,tj,s) ⇒ a = b + ((a + H(b,c,d) + Mj + tj) <<< s)
4ª Vuelta:
II(a,b,c,d,Mj,tj,s) ⇒ a = b + ((a + I(b,c,d) + Mj + tj) <<< s)
Autenticación y Firma Digital 22
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Algoritmo y desplazamiento en MD5
Vector de 128 bits
a b c d

Sea f la función F, G, H o I según la vuelta.

El algoritmo será:
Para j = 0 hasta 15 hacer:
TEMP = [(a + f(b,c,d) + Mj + tj) <<<sj]
a=d
d=c
c=b
b=a
a = TEMP

Autenticación y Firma Digital 23

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Operaciones en 1ª y 2ª vueltas en MD5
FF (a, b, c, d, Mj, tj, s) GG (a, b, c, d, Mj, tj, s)

FF(a, b, c, d, M0, D76AA478, 7) GG(a, b, c, d, M1, F61E2562, 5)

FF(d, a, b, c, M1, E8C7B756, 12) GG(d, a, b, c, M6, C040B340, 9)
FF(c, d, a, b, M2, 242070DB, 17) GG(c, d, a, b, M11, 265E5A51, 14)
FF(b, c, d, a, M3, C1BDCEEE, 22) GG(b, c, d, a, M0, E9B6C7AA, 20)
FF(a, b, c, d, M4, F57C0FAF, 7) GG(a, b, c, d, M5, D62F105D, 5)
FF(d, a, b, c, M5, 4787C62A, 12) GG(d, a, b, c, M10, 02441453, 9)
FF(c, d, a, b, M6, A8304613, 17) GG(c, d, a, b, M15, D8A1E681, 14)

Segunda vuelta
FF(b, c, d, a, M7, FD469501, 22) GG(b, c, d, a, M4, E7D3FBC8, 20)
Primera vuelta

FF(a, b, c, d, M8, 698098D8, 7) GG(a, b, c, d, M9, 21E1CDE6, 5)

FF(d, a, b, c, M9, 8B44F7AF, 12) GG(d, a, b, c, M14, C33707D6, 9)
FF(c, d, a, b, M10, FFFF5BB1, 17) GG(c, d, a, b, M3, F4D50D87, 14)
FF(b, c, d, a, M11, 895CD7BE, 22) GG(b, c, d, a, M8, 455A14ED, 20)
FF(a, b, c, d, M12, 6B901122, 7) GG(a, b, c, d, M13, A9E3E905, 5)
FF(d, a, b, c, M13, FD987193, 12) GG(d, a, b, c, M2, FCEFA3F8, 9)
FF(c, d, a, b, M14, A679438E, 17) GG(c, d, a, b, M7, 676F02D9, 14)
FF(b, c, d, a, M15, 49B40821, 22) GG(b, c, d, a, M12, 8D2A4C8A, 20)
Autenticación y Firma Digital 24
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Operaciones en 3ª y 4ª vueltas en MD5
HH (a, b, c, d, Mj, tj, s) II (a, b, c, d, Mj, tj, s)

HH(a, b, c, d, M5, FFFA3942, 4) II(a, b, c, d, M0, F4292244, 6)

HH(d, a, b, c, M8, 8771F681, 11) II(d, a, b, c, M7, 411AFF97, 10)
HH(c, d, a, b, M11, 6D9D6122, 16) II(c, d, a, b, M14, AB9423A7, 15)
HH(b, c, d, a, M14, FDE5380C, 23) II(b, c, d, a, M5, FC93A039, 21)
HH(a, b, c, d, M1, A4BEEA44, 4) II(a, b, c, d, M12, 655B59C3, 6)
HH(d, a, b, c, M4, 4BDECFA9, 11) II(d, a, b, c, M3, 8F0CCC92, 10)
HH(c, d, a, b, M7, F6BB4B60, 16) II(c, d, a, b, M10, FFEFF47D, 15)
HH(b, c, d, a, M10, BEBFBC70, 23) II(b, c, d, a, M1, 85845DD1, 21)
Tercera vuelta

Cuarta vuelta
HH(a, b, c, d, M13, 289B7EC6, 4) II(a, b, c, d, M8, 6FA87E4F, 6)
HH(d, a, b, c, M0, EAA127FA, 11) II(d, a, b, c, M15, FE2CE6E0, 10)
HH(c, d, a, b, M3, D4EF3085, 16) II(c, d, a, b, M6, A3014314, 15)
HH(b, c, d, a, M6, 04881D05, 23) II(b, c, d, a, M13, 4E0811A1, 21)
HH(a, b, c, d, M9, D9D4D039, 4) II(a, b, c, d, M4, F7537E82, 6)
HH(d, a, b, c, M12, E6DB99E5, 11) II(d, a, b, c, M11, BD3AF235, 10)
HH(c, d, a, b, M15, 1FA27CF8, 16) II(c, d, a, b, M2, 2AD7D2BB, 15)
HH(b, c, d, a, M2, C4AC5665, 23) II(b, c, d, a, M9, EB86D391, 21)
Autenticación y Firma Digital 25
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Función de resumen SHA-1
Un resumen de 128 bits tiene una complejidad algorítmica de
sólo 264, un valor en la actualidad muy comprometido... "
La función SHA-1, Secure Hash Algorithm, entregará un
resumen de 160 bits ⇒ una complejidad algorítmica de 280. #
Vector Inicial : A = 67452301 B = EFCDAB89
SHA-1
C = 98BADCFE D = 10325476 E = C3D2E1F0

Algoritmo: Esta forma de tomar los bits se verá más adelante

Es muy similar a MD5. El vector inicial tiene una palabra más
de 32 bits (E) por lo que el resumen será de 160 bits. A cada
bloque de 512 bits del mensaje se le aplicarán 80 vueltas.
Autenticación y Firma Digital 26
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Esquema del resumen SHA-1
a b c d e
Vector inicial ABCDE
Función
Registro de 160 bits no lineal
AA1616 == 67452301
67452301 <<< 30
BB1616 == EFCDAB89
EFCDAB89 +
CC1616 == 98BADCFE
98BADCFE
<<< 5
DD1616 == 10325476
10325476 +
EE1616 == C3D2E1F0
C3D2E1F0 Bloques del texto a partir
del bloque de 16 palabras +
Wt 32 bits
Después de esta última operación, Una constante en cada
se produce el desplazamiento del una de las cuatro vueltas
+
registro hacia la derecha
Kt 32 bits

Suma
Ver la próxima diapositiva... + mod 232

Autenticación y Firma Digital 27

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Vueltas en funciones F,G, H e I de SHA-1
Desplazamiento del registro
FF(b,(b,c,c,d) →vueltas
d) → vueltastt==00aa19
19 ea ab bc dc de
((bbAND
ANDcc))OR ((NOTbb))AND
OR((NOT ANDdd))
GG(b,(b,c,c,d) →vueltas
d) → vueltastt==20
20aa39
39 Se repite el proceso con la
bbXORXORccXOR XORdd función F para las restantes 15
HH(b,(b,c,c,d) →vueltas
d) → vueltastt==40
40aa59
59 palabras de 32 bits del bloque
((bb AND
AND cc)) OROR ((bb AND
AND dd)) OR
OR actual hasta llegar a 20. En
((ccAND
ANDdd)) vueltas 2, 3 y 4 se repite el
d) →
(b,c,c,d)
II(b, →vueltas
vueltastt==60
60aa79
79 proceso con funciones G, H e I.
bbXORXORccXOR XORdd

Tenemos 4∗20 = 80 pasos por cada bloque de 512 bits.

Pero ... ¿cómo es posible repetir 80 veces un bloque que sólo
cuenta con 16 bloques de texto de 32 bits cada uno?
Autenticación y Firma Digital 28
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Las 80 vueltas de SHA-1
Vector de 160 bits
a b c d e

Cada bloque de 16 palabras del mensaje (M0 ... M15) se

expandirá en 80 palabras (W0 ... W79) según el algoritmo:
Wt = Mt (para t = 0, ..., 15)
Wt = (Wt-3 ⊕ Wt-8 ⊕ Wt-14 ⊕ Wt-16 ⊕) <<<1 (para t = 16, ..., 79)

y además: Kt = 5A827999 para t = 0, ..., 19

Kt = 6ED9EBA1 para t = 20, ..., 39
Kt = 8F1BBCDC para t = 40, ..., 59
Kt = CA62C1D6 para t = 60, ..., 79

Autenticación y Firma Digital 29

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Algoritmo y desplazamiento en SHA-1
Vector de 160 bits
a b c d e

El algoritmo para cada bloque de 512 bits será:

Para t = 0 hasta 79 hacer:
TEMP = (a <<<5) + ft(b,c,d) + e + Wt + Kt
a=e
e=d
d=c
c = b <<<30
b=a
a = TEMP

Autenticación y Firma Digital 30

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comparativa entre MD5 y SHA-1

• SHA-1 genera una salida de 160 bits de longitud mientras

que MD5 genera sólo 128 bits.
– La dificultad de generar un mensaje que tenga un resumen
dado es del orden de 2128 operaciones para MD5 y 2160 para
SHA-1.
– La dificultad de generar dos mensajes aleatorios distintos y
que tengan el mismo resumen (ataques basados en paradoja
del cumpleaños) es del orden de 264 operaciones para MD5 y
280 para SHA-1.
• Esta diferencia de 16 bits a favor de SHA-1 lo convierte en
más seguro y resistente a ataques por fuerza bruta que el
algoritmo MD5.

Autenticación y Firma Digital 31

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Operaciones en MD5 y en SHA-1
• Ambos algoritmos procesan bloques de 512 bits y emplean 4
funciones primitivas para generar el resumen del mensaje ... pero

• SHA-1 realiza un mayor número de pasos que MD5 (80 frente a

los 64 que realiza MD5).
• SHA-1 debe procesar 160 bits de buffer en comparación con los
128 bits de MD5.
• Por estos motivos la ejecución del algoritmo SHA-1 es más lenta
que la de MD5 bajo el mismo hardware.

Ejemplos de tiempos de ejecución

Autenticación y Firma Digital 32

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Tiempos de ejecución MD5 v/s SHA-1

Tiempos obtenidos con un Pentium a 90 MHz:

Rendimiento (Mbits / Seg)
Lenguaje C++
MD5 32,4
SHA-1 14,4

Tiempos obtenidos con un Pentium a 266 MHz:

Rendimiento (Mbits / Seg)
Lenguaje Ensamblador Lenguaje C
MD5 113,5 59,7
SHA-1 46,5 21,2

Autenticación y Firma Digital 33

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Más diferencias entre MD5 y SHA-1
• La longitud máxima del mensaje para SHA-1 debe ser
menor de 264 bits, mientras que MD5 no tiene limitaciones
de longitud.
• MD5 emplea 64 constantes (una por cada paso), mientras
que SHA-1 sólo emplea 4 (una para cada 20 pasos).
• MD5 se basa en la arquitectura little-endian, mientras que
SHA-1 se basa en la arquitectura big-endian. Por ello el
vector ABCD inicial en MD5 y SHA-1 son iguales:
– A = 01234567 (MD5) ⇒ 67452301 (SHA-1)
– B = 89ABCDEF (MD5) ⇒ EFCDAB89 (SHA-1)
– D = FEDCBA98 (MD5) ⇒ 98BADCFE (SHA-1)
– E = 76543210 (MD5) ⇒ 10325476 (SHA-1)

Autenticación y Firma Digital 34

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Arquitecturas little-endian v/s big-endian
Arquitectura little-endian:
• Esta es la arquitectura empleada en procesadores Intel de la
familia 80xxx y Pentium.
• Para almacenar una palabra en memoria, el byte menos
significativo de los que forman dicha palabra se guarda en
la posición más baja de la memoria.
Arquitectura big-endian: Ejemplo
• Empleada por otras arquitecturas como SUN.
• Para almacenar una palabra en memoria, el byte más
significativo de los que forman dicha palabra se guarda en
la posición más baja de memoria.
Autenticación y Firma Digital 35
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Ejemplo little-endian v/s big-endian
Supongamos que queremos almacenar en memoria la siguiente
palabra de 32 bits (4 bytes) representada en hexadecimal:
76543210 ⇒ 76 54 32 10

Si consideramos que las posiciones de memoria más bajas se

encuentran a la izquierda y las más altas a la derecha:

En formato little-endian se representa: 01 23 45 67

En formato big-endian se representa: 67 45 23 01

Autenticación y Firma Digital 36

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Firma digital RSA de A hacia B
Clave Pública (nA, eA) Clave Privada (dA)
Algoritmo:
Rúbrica: rAH(M) = H(M)dA mod nA Adelaida

A envía el mensaje M en claro (o cifrado) al destinatario B

junto a la rúbrica: {M, rAH(M)}
El destinatario B tiene la clave pública eA,nA de
A y descifra rAH(M) ⇒ {(H(M)dA)eA mod nA}
obteniendo así H(M). Como recibe el mensaje
M’, calcula la función hash H(M’) y compara:
Benito Si H(M’) = H(M) se acepta la firma. $
Autenticación y Firma Digital 37
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Ejemplo de firma digital RSA (B → A)
Hola. Te envío el documento. Saludos, Beni.

Sea H(M) = F3A9 (16 bits)

Benito Adelaida

Claves Benito 216 < 65.669 < 217 Claves Adelaida

nB = 65.669 luego, firmará con nA = 66.331
eB = 35, dB = 53.771 bloques de 16 bits eA = 25, dA = 18.377

Firma H (M) = F3A916 = 62.37710

rH(M) = H(M)dB mod nB
rH(M) = 62.37753.771 mod 65.669 = 24.622
Benito envía el par (M, r) = (M, 24.622)
Autenticación y Firma Digital 38
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comprobación de firma RSA por A
Claves Benito Claves Adelaida
nB = 65.669 nA = 66.331
eB = 35, dB = 53.771 eA = 25, dA = 18.377
Benito Teníamos que: H (M) = F3A916 = 62.37710 Adelaida
rH(M) = H(M)dB mod nB rH(M) = 62.37753.771 mod 65.669 = 24.622
Benito había enviado el par (M, r) = (M, 24.622)

Adelaida recibe un mensaje M’ junto con una rúbrica r = 24.622:

• Calcula reB mod nB = 24.62235 mod 65.669 = 62.377.
• Calcula el resumen de M’ es decir H(M’) y lo compara con H(M).
• Si los mensajes M y M’ son iguales, entonces H(M) = H(M’) y se
acepta la firma como válida.
• NOTA: No obstante, H(M) = H(M’) no implica que M = M’.
Autenticación y Firma Digital 39
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Firma digital ElGamal de A hacia B
ElGamal: El usuario A generaba un número
aleatorio a (clave privada) del cuerpo p. La
clave pública es αa mod p, con α generador.
Adelaida

Firma:((rr,,ss))
Algoritmo de firma: Firma:
1º El usuario A genera un número aleatorio h, que será primo
relativo con φ(p): h / mcd {h, φ(p)} = 1
2º Calcula h-1 = inv {h, φ(p)} M
M==a∗r
a∗r++h∗s
h∗smod φ(p) ∴
modφ(p) ∴
3º Calcula r = αh mod p ss==(M
(M--a∗r)∗inv[h,φ(p)]
a∗r)∗inv[h,φ(p)]mod φ(p)
modφ(p)
4º Resuelve la siguiente congruencia:
Autenticación y Firma Digital 40
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comprobación de firma ElGamal por B
Algoritmo comprobación de firma:
1º El usuario B recibe el par (r, s) y calcula:
Benito
rs mod p y (αa)r mod p Conoce: p y (α αa) mod p
2º Calcula k = [(αa)r ∗ rs] mod p
Seacepta
Se aceptalalafirmafirma
Como r era igual a α mod p entonces:
h

k = [(αar∗αhs] mod p = α(ar +hs) mod p = αβ mod p

3º Como M = (a∗r + h∗s) mod φ(p) y α es una raíz
primitiva de p se cumple que:
αβ = αγ ssi β = γ mod (p-1) [(αaa))rr∗∗rrss]]mod
Sikk==[(α
Si modpp
4º Comprueba que k = αM mod p igualaaααMMmod
esigual
es modpp......
Autenticación y Firma Digital 41
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Ejemplo firma digital ElGamal (B → A)
¡Hola otra vez! Soy Benito de nuevo... Salu2.

Sea H(M) = A69B (16 bits)

Benito Adelaida
Claves Benito 216 < 79.903 < 217
pB = 79.903 α = 10 luego, firmará con
αb mod p = 3.631 bloques de 16 bits
Firma b = 20, h = 31

1) h-1 = inv[h, φ(p)] = inv (31, 79.902) = 5.155

2) r = αh mod p = 1031 mod 79.903 = 11.755
3) s = [H(M) - b∗r]∗[inv(h,φ(p)] mod φ(p) H(M) = A69B16 = 42.65110
4) s = [42.651-20∗11.755]∗5.155 mod 79.902
5) s = 68.539 Luego, la firma será (r, 11.755, ,68.539
(r,s)s)==((11.755 68.539))

Autenticación y Firma Digital 42

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comprobación de firma ElGamal por A
Claves Benito
pB = 79.903 α = 10
H(M) = A69B = 42.651
αb mod p = 3.631
Benito b = 20, h = 31 Adelaida

Adelaida recibe el par (r, s) = (11.755, 68.539)

Comprobación de la firma: Como hay igualdad

1) rs mod p = 11.75568.539 mod 79.903 = 66.404 se acepta la firma
2) (αa)r mod p = 3.63111.755 mod 79.903 = 12.023
3) (αa)r ∗ rs mod p = (66.404 ∗ 12.023) mod 79.903 = 64.419 = k
4) αH(M) mod p = 1042.651 mod 79.903 = 64.419

Autenticación y Firma Digital 43

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 El generador α en la firma de ElGamal
Claves Benito
α = 10 es un generador
pB = 79.903 α = 10
αb mod p = 3.631 del cuerpo p = 79.903
Benito b = 20, h = 31 puesto que:
1039.951 mod 79.903 = 79.902
p-1 = 79.902 = 2∗32∗23∗193 1026.634 mod 79.903 = 71.324
q1 = 2; q2 = 3; q3 = 23; q4 = 193 103.474 mod 79.903 = 2.631
y se cumple 10(p-1)qi mod p ≠ 1 10414 mod 79.903 = 41.829

Por ejemplo, si se elige α = 11, para el exponente 39.951 se

obtiene el valor 1 y entonces no sirve para la firma. Será
imposible comprobarla mediante la ecuación k = αM mod p.
Autenticación y Firma Digital 44
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Estándares de firma digital
1991: National Institute of Standards and Technology (NIST)
propone el DSA, Digital Signature Algorithm, una
variante de los algoritmos de ElGamal y Schnoor.
1994: Se establece como estándar el DSA y se conoce como
DSS, Digital Signature Standard.
1996: La administración de los Estados Unidos permite la
exportación de Clipper 3.11 en donde viene inmerso el
DSS, que usa una función hash de tipo SHS, Secure
Hash Standard.
El peor inconveniente de la firma propuesta por ElGamal es que
duplica el tamaño del mensaje M al enviar un par (r, s) en Zp y φ(p).
No obstante, se solucionará con el algoritmo denominado DSS.
Autenticación y Firma Digital 45
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Digital Signature Standard DSS
Parámetros públicos de la firma:
• Un número primo grande p (512 bits)
• Un número primo q (160 bits) divisor de p-1
• Un generador α “de orden q” del grupo p
Generador de orden q es aquella raíz α en el cuerpo Zp de
forma que q es el entero más pequeño que verifica:
αq mod p = 1

En este caso se cumple para todo t que:

αt = αt (mod q) mod p
Autenticación y Firma Digital 46
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Generación de firma DSS de A → B
GENERACIÓN DE LA FIRMA POR PARTE DE A
• Claves públicas de A: primos p, q y el generador α
• Clave secreta de la firma: a (1 < a < q) aleatorio
• Clave pública de la firma: y = αa mod p
• Para firmar un mensaje 1 < M < p, el firmante elige un
valor aleatorio 1 < h < q y calcula:
• r = (αh mod p) mod q
• s = [(M + a∗r) ∗ inv (h,q)] mod q
• La firma digital de M será el par (r, s)

Autenticación y Firma Digital 47

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comprobación de firma DSS por B
COMPROBACIÓN DE LA FIRMA DE A POR B
• B recibe el par (r, s) La firma tendrá en este caso
• Luego calcula: un tamaño menor que q, es
• w = inv (s, q) decir, menos bits que los del
módulo de firma p ya que se
• u = M ∗ w mod q elige por diseño p >> q
• v = r ∗ w mod q
• Comprueba que se cumple la relación:
• r = (αu yv mod p) mod q
• Si se cumple, se acepta la firma como válida.

Autenticación y Firma Digital 48

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Ejemplo de firma DSS de B → A
Hola Adelaida, soy Benito y firmo con DSS.
Sea H(M) = 1101000 = 104 (un elemento de pB)
Benito Adelaida
Claves Benito
pB = 223 qB = 37 α = 17 28 < pB = 223 < 27
y = αb mod p = 30 Luego firmará
Firma b = 25, h = 12 bloques de 7 bits

1) inv (h,q) = inv (12, 37) = 34

2) r = (αh mod p) mod q = (1712 mod 223) mod 37 = 171 mod 37 = 23
3) s = [H(M)+b∗r]∗[inv (h,q)] mod q = [104+25∗23]∗34 mod 37 = 35
4) La firma digital de H(M) = 104 será: (r, s) = (23, 35)
5) Benito transmite a Adelaida el bloque (M, r, s) = (M, 23, 35)
Autenticación y Firma Digital 49
© Jorge Ramió Aguirre. UPM - Madrid (España) 2001
 Comprobación de firma DSS por A
Claves Benito
pB = 223 qB = 37 α = 17
y = αb mod p = 30 Adelaida recibe:
Benito b = 25, h = 12 (M, r, s) = (M, 23, 35) Adelaida
¿igualdad?
Comprobación de firma Se acepta la firma
1) w = inv (s, q) = inv (35, 37) = 18 Y el tamaño será
2) u = M∗w mod q = 104∗18 mod 37 = 22 menor que qB = 37
3) v = r∗w mod q = 23∗18 mod 37 = 7 es decir << PB = 223 que
u v era el punto débil de ElGamal
4) ¿(α y mod p) mod q = r ?
5) [(1722307) mod 223] mod 37 = 23 Fin del Tema

Autenticación y Firma Digital 50

© Jorge Ramió Aguirre. UPM - Madrid (España) 2001