Criptografía.
Autentificación y Firmas
Digitales
Enrique Arias Antúnez
[email protected]
Departamento de Informática
Escuela Politécnica Superior de Albacete
Universidad de Castilla - La Mancha
Auditorı́a y Seguridad Informática
Albacete, 2003-2004 – p.1/58
Índice
Criptografía
Introducción
Criptosistemas
Clasificación de los Criptosistemas: De
clave pública y de clave privada
Autentificación y Firmas Digitales
Introducción
Firmas Digitales. Funciones Resumen
Algoritmo MD5
Algoritmo SHA-1
Albacete, 2003-2004 – p.2/58
Criptografía. Introducción
Criptología proviene del griego krypto (oculto)
y logos (escritura) y es la ciencia que versa
sobre los problemas teóricos relacionados
con la seguridad en el intercambio de
información en clave entre un emisor y un
receptor, a través de un canal de
comunicación
La criptología se divide en criptografía y
criptoanálisis
Esteganografía
Albacete, 2003-2004 – p.3/58
Criptografía. Introducción
O BJETIVOS
Mantener la confidencialidad de los datos
Autentificación: el emisor del mensaje es
quién dice ser y no otro.
Integridad: El mensaje que se lee es el
mismo que se envía.
No repudio: El emisor no puede negar el
haber enviado su mensaje.
Albacete, 2003-2004 – p.4/58
Criptografía. Criptosistemas
Un alfabeto A
Un espacio de claves K
Unas Transformaciones de cifrado E
Unas Transformaciones de descifrado D
a c a
E(k,a) D(k’,c)
k k’
Albacete, 2003-2004 – p.5/58
Criptografía. Clasificación
Criptosistemas simétricos o de clave privada
Criptosistemas asimétricos o de clave pública
Combinación de ambos: Mensajes largos se
codifican con algoritmos simétricos más
eficientes que los asimétricos, usando los
algoritmos asimétricos para codificar las
claves privadas de los algoritmos simétricos.
Computacionalmente seguros
El coste de romper la encriptación >> valor de la
información
El tiempo de romper la encriptación >> tiempo de vida
útil de la información
Albacete, 2003-2004 – p.6/58
Criptografía. Clave privada
Definición: Aquel tipo de criptosistema en el
que la clave de cifrado K, puede calcularse a
partir de la clave de descifrado K 0 , y viceversa
(suelen coincidir) y deben mantenerse en
secreto entre emisor y receptor.
Desventaja: La clave común se envia sin
cifrar.
Los criptosistemas que funcionan a nivel de
bit se denominan cifradores de flujo , sino,
se denominan cifradores de bloque .
Ejemplos: El sistema Caesar , Vigènere ,
DES , IDEA y AES .
Albacete, 2003-2004 – p.7/58
Criptografía. Cifradores de bloque
E STRUCTURA DE C IFRADOR DE F EISTEL
Tamaño de Bloque
Tamaño de Clave
Número de Rondas
Algoritmo de Generación de Subclaves
Función de las rondas
Albacete, 2003-2004 – p.8/58
Criptografía. Cifradores a bloques
M ODO ECB
Albacete, 2003-2004 – p.9/58
Criptografía. Cifradores a bloques
M ODO CBC
Albacete, 2003-2004 – p.10/58
Criptografía. Criptosistema AES
Conocido como el algoritmo de Rijndael
Adoptado el 2 de Octubre de 2000 (tras 4
años de selección) por la NIST (National
Institute for Standards and
Technology) como nuevo Estándar
Avanzado de Cifrado (AES).
Consensuado: selección, revisión y estudio
se llevó cabo de forma pública y abierta, de
entre 15 candidatos.
Albacete, 2003-2004 – p.11/58
Criptografía. Criptosistema AES
C ARACTERÍSTICAS
Seguridad: La clave de AES puede ser de
128, 192 o 256 bits. El criptosistema con
clave de 128 bits no se rompería hasta 2066
y con clave de 256 se tardaría varios siglos.
Prestaciones: Ejecutado en diferentes
plataformas proporcina un buen ratio
seguridad-prestaciones, y es simple de
implementar tanto en software como en
hardware.
Propiedad Intelectual: Dominio público.
Albacete, 2003-2004 – p.12/58
Criptografía. Criptosistema AES
Estructura
Albacete, 2003-2004 – p.13/58
Criptografía. Criptosistema AES
E STRUCTURA
Ronda: una composición de 4 funciones
invertibles diferentes
1. DesplazarFila: Permutación fila a fila.
2. MezclarColumnas: Sustitución que altera cada
byte de una columna como una función de
todos los bytes de la columna.
3. ByteSub: Utiliza una tablas (S-box) para
realizar una sustitución byte a byte de un
bloque.
4. Or-exclusivo: XOR del bloque actual con la
calve expandida,
Albacete, 2003-2004 – p.14/58
Criptografía. Criptosistema AES
Estructura
La capa de mezcla lineal : Funciones como
DesplazarFila o MezclarColumnas, permiten
obtener un alto nivel de difusión (permutado)
a lo largo de varias rondas
Albacete, 2003-2004 – p.15/58
Criptografía. Criptosistema AES
Estructura
La capa no lineal : Una función ByteSub que
consiste en la aplicación paralela de s-cajas
con propiedades óptimas de no linealidad.
Las s-cajas son pequeñas tablas que
permiten realizar sustituciones sencillas
(confusión). Por tanto una s-caja de m × n
bits es una tabla de sustitución que toma
como entradas cadenas de m bits y da como
resultado cadenas de n bits.
Albacete, 2003-2004 – p.16/58
Criptografía. Criptosistema AES
E STRUCTURA
32 bits
... ... ... ...
S− Caja 8x6
... ... ... ...
24 bits
a) b)
Albacete, 2003-2004 – p.17/58
Criptografía. Criptosistema AES
E STRUCTURA
La capa de adición de clave : Consiste en un
simple or-exclusivo entre el estado intermedio y
la subclave correspondiente en cada ronda.
Albacete, 2003-2004 – p.18/58
Criptografía. Criptosistema AES
E STRUCTURA
Albacete, 2003-2004 – p.19/58
Criptografía. Criptosistema AES
E LEMENTOS
Aplicar un número determinado de rondas a
un valor intermedio que se denomina estado
∈ N 4×Nb de bytes (Ejemplo: si el bloque
contiene 160 bits, Nb será igual a 5 (160 bits ≡
20 bytes, dispuestos en una matriz de 4 × 5).
Clave ∈ N 4×Nk de bytes.(Ejemplo, si la clave
es de 128 bits, Nk será igual a 4 (128 bits ≡ 16
bytes, dispuestos en una matriz de 4 × 4).
Albacete, 2003-2004 – p.20/58
Criptografía. Criptosistema AES
E LEMENTOS
1. Calcular K0 , K1 , . . . , Kn subclaves de la clave
K.
2. S ← B ⊗ K0 .
3. Para i = 1 hasta n hacer
4. Aplicar ronda i-ésima del algoritmo con
la subclave Ki
Albacete, 2003-2004 – p.21/58
Criptografía. Criptosistema AES
R ONDAS DE AES
El número de rondas es variable ya que se
permite emplear longitudes de bloque y clave
diferentes.
Nb = 4 N b = 6 N b = 8
Nk = 4 10 12 14
Nk = 6 12 12 14
Nk = 8 14 14 14
Albacete, 2003-2004 – p.22/58
Criptografía. Criptosistema AES
R ONDAS DE AES
1. S ← ByteSub(S).
2. S ← DesplazarF ila(S).
3. S ← M ezclarColumnas(S).
4. S ← Ki ⊗ S.
En la última ronda se eliminará el paso 3
Albacete, 2003-2004 – p.23/58
Criptografía. Criptosistema AES
C ÁLCULO DE LAS SUBCLAVES
Transformación de expansión sobre la clave
K: La operación de expansión permite
obtener, a partir de una clave K, una
secuencia W de 4(n + 1)Nb bytes, siendo n el
número de rondas.
Transformación de seleción: La función de
selección va tomando consecutivamente de
la secuencia previamente obtenida, bloques
del mismo tamaño que la matriz de estado, y
los va asignado a las diferentes Ki .
Albacete, 2003-2004 – p.24/58
Criptografía. Criptosistema AES
O BTENCIÓN DE LA SECUENCIA
Si Nk ≤ 6
1. Para i desde 0 hasta Nk − 1 hacer
2. W (i) ← (K(4i), K(4i+1), K(4i+2), K(4i+3)).
3. Para i desde Nk hasta Nb (n + 1) hacer
4. tmp ← W (i − 1)
5. Si mod(i, Nk ) = 0
6. tmp ← Sub(Rot(tmp)) ⊗ R(i/Nk )
7. W (i) ← W (i − Nk ) ⊗ tmp
Albacete, 2003-2004 – p.25/58
Criptografía. Criptosistema AES
O BTENCIÓN DE LA SECUENCIA
Si Nk > 6
1. Para i desde 0 hasta Nk − 1 hacer
2. W (i) ← (K(4i), K(4i+1), K(4i+2), K(4i+3)).
3. Para i desde Nk hasta Nb (n + 1) hacer
4. tmp ← W (i − 1)
5. Si mod(i, Nk ) = 0
6. tmp ← Sub(Rot(tmp)) ⊗ Rc(i/Nk )
7. Si mod(i, Nk ) = 4
8. tmp ← Sub(tmp)
9. W (i) ← W (i − Nk ) ⊗ tmp
Albacete, 2003-2004 – p.26/58
Criptografía. Criptosistema AES
O BTENCIÓN DE LA SECUENCIA
Sub:Devuelve el resultado de aplicar las s-caja de
AES, a cada uno de los bytes del registro de cuatro
bytes que se le pasa como parámetro.
Rot: Lleva a cabo un desplazamiento a la izquierda de
los bytes del registro.
Rc(j): es una constante definida como sigue:
Rc(j) = (R(j), 0, 0, 0).
Cada R(i) es el elemento de GF (28 )
correspondiente al valor de x(i−1) .
Albacete, 2003-2004 – p.27/58
Criptografía. Clave pública
O Criptosistemas asimétricos , se basan en
un par de claves, una clave de cifrado que se
hace de conocimiento general ( clave pública
), y de otra clave de descifrado que se ha de
mantener en secreto ( clave privada ).
A partir de la clave pública no es posible
obtener la privada, lo que hace imposible su
descifrado si no se dispone de ésta.
Ejemplos: El criptosistema RSA , El
criptosistema de ELGamal y El
criptosistema DSA .
Albacete, 2003-2004 – p.28/58
Criptografía. Clave pública
F UNCIONAMIENTO BÁSICO
Albacete, 2003-2004 – p.29/58
Criptografía. Clave pública
F UNCIONAMIENTO BÁSICO
1. Cada usuario genera un par de claves para
cifrar y descifrar
2. La clave pública se sitúa en un fichero o
registro público
3. Si A envía un mensaje a B, A cifra el
mensaje con la clave pública de B. Cuando B
recibe el mensaje, éste lo descifra con su
clave privada
Albacete, 2003-2004 – p.30/58
Criptografía. Clave pública
A PLICACIONES
1. Cifrar/Descifrar: El emisor cifra un mensaje
con la clave púlica del receptor
2. Firma Digital: El emisor ”firma” un mensaje
con su clave privada. La firma se obtiene
aplicando un algoritmo criptográfico a un
mensaje o a un pequeño bloque de datos que
es una función del propio mensaje
3. Intercambio de claves
Albacete, 2003-2004 – p.31/58
Criptografía. Criptosistema RSA
I NTRODUCCIÓN
RSA (Ronald R ivest, Adi S hamir y
Leonard A dleman), se utiliza tanto para
cifrar como para autentificar.
Se basa en la dificultad para factorizar
grandes números. Las claves pública y
privada se calculan a partir de un número
que se obtiene como producto de dos
números primos grandes .
Albacete, 2003-2004 – p.32/58
Criptografía. Criptosistema RSA
F UNCIONAMIENTO
KP y Kp se obtienen a partir de un dos
números aleatorios primos grandes p y q
(n = pq).
Se escoge e relativo a (p − 1)(q − 1), dando
lugar así a la clave pública (e, n).
Puesto que e ha de tener inversa módulo
(p − 1)(q − 1), existirá un número d tal que
d = e−1 (mod(p − 1)(q − 1)), obteniendo la
clave privada (d, n).
Albacete, 2003-2004 – p.33/58
Criptografía. Criptosistema RSA
F UNCIONAMIENTO
La codificación se lleva a cabo según la
expresión:
e
c = m M od n.
La decodificación se realiza según la
expresión:
m = cd M od n.
Albacete, 2003-2004 – p.34/58
Criptografía. Criptosistema RSA
E JEMPLO
Sean dos números primos: p = 47 y q = 71
Calcular n = p × q = 3337
Hallar clave de cifrado e. Para ello no ha de tener factores
en común con (p − 1)(1 − 1) = 46 × 70 = 3220. Se escoge
e = 79.
Hallar clave de descifrado
d = e−1 M od n = 79−1 M od 3220 = 1019
Publicar e y n y mantener d secreta. Descartar p y q
Albacete, 2003-2004 – p.35/58
Criptografía. Criptosistema RSA
E JEMPLO
n = 3337, e = 79, d = 1019
Publicar e y n y mantener d secreta. Descartar p y q
Sea el mensaje m = 688232..., y el tamaño de bloque igual
a 3 dígitos. Por tanto m1 = 688, m2 = 232, etc.
m1 se cifra como 68879 mod 3337 = 1570 = c1
Aplicando lo mismo sobre los diferentes bloques se obtiene
c = 1570 2756 ...
Para descifrar se haría 15701019 mod 3337 = 688 = m1 . Lo
mismo con el resto de bloques
Albacete, 2003-2004 – p.36/58
Autentificación y Firmas Digitales
I NTRODUCCIÓN
El objetivo de los sistemas de identificación
de usuarios son identificar y autentificar .
Desde el punto de vista de transmisión de
mensajes, doble finalidad de verificar la
procedencia de los mensajes y que éstos no
han sido modificados
Métodos de autentificación
Autentificación de mensaje ( firmas digitales )
Autentificación de usuario mediante contraseña
Autentificación de dispositivos
Albacete, 2003-2004 – p.37/58
Firmas Digitales
F UNCIONAMIENTO BÁSICO
Albacete, 2003-2004 – p.38/58
Funciones Resumen
La criptografía asimétrica permite la
autentificación de mensajes, con la ayuda de
Funciones Resumen (conocidas como MAC
(Modification Authentication
Code), que nos permiten obtener Firmas
Digitales a partir de un mensaje.
Un mensaje m puede ser autentificado
codificando con la clave privada Kp , el
resultado de aplicarle una función resumen,
EKp (r(m)).
Albacete, 2003-2004 – p.39/58
Funciones Resumen
F UNCIONAMIENTO BÁSICO
(1) A y B comparten clave privada
(5) B calcula otro resumen
(6) B compara el resumen del mensaje con el su
(4) B recibe el mensaje
(3) El resumen se adjunta al mensaje
(2) A quiere enviar a B. Calcula resumen
Albacete, 2003-2004 – p.40/58
Funciones Resumen
F UNCIONAMIENTO AVANZADO
Albacete, 2003-2004 – p.41/58
Funciones Resumen
F UNCIONAMIENTO AVANZADO
Albacete, 2003-2004 – p.42/58
Funciones Resumen
F UNCIONAMIENTO AVANZADO
Albacete, 2003-2004 – p.43/58
Funciones Resumen
C ARACTERÍSTICAS DE LA FUNCIÓN RESUMEN
r(m)
1. r(m) es de longitud fija, independendientemente de la
longitud de m. (One-Way Hash Function)
2. Dado m, es sencillo calcular r(m).
3. Dado r(m), es computacionalmente intratable
recuperar m.
4. Dado m, es computacionalmente intratable obtener un
m0 tal que r(m) = r(m0 ) (Se recomienda emplear
firmas de al menos 128 bits, siendo 160 bits el valor
más usado).
Albacete, 2003-2004 – p.44/58
Funciones Resumen
C ARACTERÍSTICAS DE LA FUNCIÓN RESUMEN
r(m)
Las funciones resumen se basan en la idea de
funciones de compresión , que dan como resultado
bloques de longitud n a partir de bloques de longitud
m.
La entrada en el paso i sea función del i-ésimo bloque
del mensaje y de la salida del paso i − 1.
Se suele incluir en alguno de los bloques del mensaje
m, información sobre la longitud total del mensaje.
Albacete, 2003-2004 – p.45/58
Algoritmo SHA-1
I NTRODUCCIÓN
Fue desarrollado por la National
Security Agency (NSA) para ser incluido
en el estándar Digital Signature
Standard (DSS).
Se considera seguro y libre de puertas traseras
y produce firmas de 160 bits, a partir de
bloques de 512 bits del mensaje original.
Albacete, 2003-2004 – p.46/58
Algoritmo SHA-1
F UNCIONAMIENTO
Albacete, 2003-2004 – p.47/58
Algoritmo SHA-1
F UNCIONAMIENTO
Se inicializa añadiendo un uno seguido de
tantos ceros como sea necesario al final del
mensaje, hasta completar 448 bits en el
último bloque, para luego añadir la longitud
en bytes del propio mensaje (64 bits)
Albacete, 2003-2004 – p.48/58
Algoritmo SHA-1
F UNCIONAMIENTO
Se inician los siguientes registros
A = 67452301
B = EF CDAB89
C = 98BADCF E
D = 10325476
E = C3D2E1F 0
Se copiarán los valores de A, B, C, D y E en
las variables a, b, c, d y e.
Albacete, 2003-2004 – p.49/58
Algoritmo SHA-1
F UNCIONAMIENTO
El bucle principal consta de cuatro rondas con
20 operaciones cada una
F (X, Y, Z) = (X ∧ Y ) ∨ ((¬X) ∧ Z)
G(X, Y, Z) = X ⊗ Y ⊗ Z
H(X, Y, Z) = (X ∧ Y ) ∨ (X ∧ Z) ∨ (Y ∧ Z)
F se emplea en la primera ronda (t entre 0 − 19),
G en la segunda y cuarta (t entre 20−39 y 60−79)
y H en la tercera (t entre 40 − 59).
Albacete, 2003-2004 – p.50/58
Algoritmo SHA-1
F UNCIONAMIENTO
Se definen de las siguientes variables
K0 = 5A827999
K1 = 6ED9EBA1
K2 = 8F 1BBCDC
K3 = CA62C1D6.
Albacete, 2003-2004 – p.51/58
Algoritmo SHA-1
F UNCIONAMIENTO
m se trocea en 16 partes de 32 bits (m0 a m15 )
y se convierte en 80 trozos de 32 bits (ω0 a
ω79 ) usando la siguiente formulación
Si t = 0, . . . , 15 : ωt = mt ,
Si t = 16, . . . , 79 : ωt = (ωt−3 ⊗ ωt−8 ⊗ ωt−14 ⊗ ωt−16 ) C 1.
Albacete, 2003-2004 – p.52/58
Algoritmo SHA-1
F UNCIONAMIENTO
Los valores de a y e son sumados a los
valores de A y E, continuando el algoritmo
con el siguiente bloque de datos.
Albacete, 2003-2004 – p.53/58
Algoritmo SHA-1
F UNCIONAMIENTO
F OR t = 0 T O 79
i = div(t, 20)
tmp = (a C 5) + F U N C(b, c, d) + e + ωt + Ki
e = d
d = c
c = b C 30
b = a
a = tmp
Albacete, 2003-2004 – p.54/58
Algoritmo SHA-1
F UNCIONAMIENTO
Albacete, 2003-2004 – p.55/58
Bibliografía
Antonio Villalón Huerta. ”Seguridad en UNIX y
Redes”. Versión 2.1, Julio-2002. Caps. 8 y 20.
http://www.rediris.es/cert/doc/unixsec/
Manuel José Lucena López. ”Criptograf´ ıa y
Seguridad de Computadores”. Tercera Edición
(Versión 1.14). Marzo 2002.
http://wwwdi.ujaen.es/m̃lucena/.
RSA Laboratories. ”Frequenly Asked Questions
about Today’s Cryptography”. Version 4.1,
May-2000.
http://www.rsasecurity.com/rsalabs/.
Albacete, 2003-2004 – p.56/58
Bibliografía
William Stallings. ”Network Security Essentials”.
Ed. Prentice-Hall, 2003.
Bruce Schneier. ”Applied Cryptography”. Ed John
Wiley & Sons, 1996.
William E. Burr. ”Selecting the Advanced Encryption
Standard”. IEEE Security & Privacy, Vol. 1, n. 2,
pp. 43-52, March-April, 2003.
Albacete, 2003-2004 – p.57/58
Criptografía. Autentificación y Firmas
Digitales
Enrique Arias Antúnez
[email protected] Departamento de Informática
Escuela Politécnica Superior de Albacete
Universidad de Castilla - La Mancha
Auditorı́a y Seguridad Informática
Albacete, 2003-2004 – p.58/58
