El algoritmo DES
- Introducción.
- El algoritmo DES.
- Descifrado en DES.
- Debilidades del algoritmo DES.
1. Introducción
El algoritmo DES está basado en el algoritmo Lucifer, diseñado
por IBM a principios de los setenta. Después de algunas modificaciones
de la NSA (National Security Agency), fué publicado en 1977 por el NBS
(National Bureau of Standards), una sección del departamento de defensa
de los EEUU.
DES utiliza claves de 56 bits y un cifrado de bloques de 64 bits. Este
algoritmo cumple con los principios de confusión y difusión
de Shannon.
Principios de confusión y difusión de Shannon:
Shannon propuso dos técnicas que deben utilizar los criptosistemas
de bloque para evitar ataques basados en métodos estadísticos.
2.El algoritmo DES
Esquema general:
El algoritmo DES cifra la información por bloques, es decir, el texto
en claro debe ser dividido en bloques de 64 bits que serán encriptados
uno tras otro.
DES utiliza claves de 56 bits, aunque estas suelen distribuirse en forma
de números de 64 bits. De estos 64 bits, uno de cada ocho, es utilizado
como bit de paridad (64-8=56).
A grandes rasgos el algoritmo DES sigue el siguiente esquema:
Bloque de entrada 64 bits
|
-----
| A |
-----
|
------------------
| 16 iteraciones |
------------------
|
-----
| B |
-----
|
Bloque de salida 64 bits
La tabla de permutación A:
Después de recibir un bloque de entrada de 64 bits, el primer paso
consiste en aplicar al bloque de entrada una permutación A mediante la
tabla siguiente:
--------------------------
| Tabla de permutación A |
--------------------------
| 58 50 42 34 26 18 10 2 |
| 60 52 44 36 28 20 12 4 |
| 62 54 46 38 30 22 14 6 |
| 64 56 48 40 32 24 16 8 |
| 57 49 41 33 25 17 9 1 |
| 59 51 43 35 27 19 11 3 |
| 61 53 45 37 29 21 13 5 |
| 63 55 47 39 31 23 15 7 |
--------------------------
El primer bit de la entrada será colocado en la posición 58, el
segundo bit en la posición 50 ...
La tabla de permutación B:
De la misma manera, después de las 16 iteraciones se realiza otra
permutación mediante la tabla B:
--------------------------
| Tabla de permutación B |
--------------------------
| 40 8 48 16 56 24 64 32 |
| 39 7 47 15 55 23 63 31 |
| 38 6 46 14 54 22 62 30 |
| 37 5 45 13 53 21 61 29 |
| 36 4 44 12 52 20 60 28 |
| 35 3 43 11 51 19 59 27 |
| 34 2 42 10 50 18 58 26 |
| 33 1 41 9 49 17 57 25 |
--------------------------
El primer bit de la entrada será colocado en la posición 40, el
segundo bit en la posición 8 ...
Las 16 iteraciones:
Después de la permutación A y antes de la B, el algoritmo DES
realiza 16 iteraciones. Cada iteración realiza lo siguiente:
- Los 64 bits de entrada se dividen en dos partes de 32 bits.
- La mitad de la derecha (R) se introduce en una función (f) que se
describirá más adelante.
- Se realiza un XOR entre la salida de la función y la parte izquierda
(L).
- El resultado (32 bits) pasará a ser la parte derecha de la siguiente
iteración, mientras que la parte derecha actual pasará a ser
la parte izuierda.
Li+1 = Ri
Ri+1 = Li XOR f(Ri,K)
En la última iteración (i=16) no se realizará el paso 4.
La función F:
Ahora pasamos a describir la función f, veamos un esquema general:
D i-1
|
| 32 bits
-----
| C |
-----
| 48 bits
|
XOR --- K (48 bits)
|
|
--------------------------------------------------------------
|||||| |||||| |||||| |||||| |||||| |||||| |||||| ||||||
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
|||| |||| |||| |||| |||| |||| |||| ||||
------------------------------------------------------------
| 32 bits
|
-----
| P |
-----
| 32 bits
|
Los 32 bits de la parte derecha entran en la función f. El primer paso
consiste en transformar la entrada de 32 bits a 48 bits mediante la
tabla C.
--------------------------
| Tabla transformación C |
--------------------------
| 32 1 2 3 4 5 |
| 4 5 6 7 8 9 |
| 8 9 10 11 12 13 |
| 12 13 14 15 16 17 |
| 16 17 18 19 20 21 |
| 20 21 22 23 24 25 |
| 24 25 26 27 28 29 |
| 28 29 30 31 32 1 |
--------------------------
A continuación se realiza un XOR con una subclave de 48 bits. Dado que
la clave inicial era de 56 bits (representada como 64 bits) es necesario
generar, a partir de esta, subclaves de 48 bits. Más adelante se
describe detalladamente el proceso de generación de subclaves.
A continuación los 48 bits se dividen en bloques de 6 bits, cada uno de
de los cuales es utilizado como entrada de lo que se conoce como una caja S.
Observe el esquema anterior.
Los 6 bits que forman cada bloque b1, b2, b3, b4, b5 y b6, son utilizados
para leer de cada caja S. b1 y b6 indican la fila mientras que b2, b3, b4,
y b5 indican la columna. Es decir, si utilizamos como entrada 000011,
b1b6 -> 01 indican la primera fila y b2b3b4b5 -> 00001 indican la primera
columna.
A continuación se muestran las ocho cajas S existentes:
S-1
---------------------------------------------------
| 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 |
| 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 |
| 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00 |
| 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 |
---------------------------------------------------
S-2
---------------------------------------------------
| 15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10 |
| 03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05 |
| 00 14 07 11 10 04 13 01 04 08 12 06 09 03 02 15 |
| 13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09 |
---------------------------------------------------
S-3
---------------------------------------------------
| 10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08 |
| 13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01 |
| 13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07 |
| 01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12 |
---------------------------------------------------
S-4
---------------------------------------------------
| 07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15 |
| 13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09 |
| 10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04 |
| 03 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14 |
---------------------------------------------------
S-5
---------------------------------------------------
| 02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09 |
| 14 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06 |
| 04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14 |
| 11 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03 |
---------------------------------------------------
S-6
---------------------------------------------------
| 12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11 |
| 10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08 |
| 09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06 |
| 04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13 |
---------------------------------------------------
S-7
---------------------------------------------------
| 04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01 |
| 13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06 |
| 01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02 |
| 06 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12 |
---------------------------------------------------
S-8
---------------------------------------------------
| 13 02 08 04 06 15 11 01 10 09 03 14 05 00 12 07 |
| 01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02 |
| 07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08 |
| 02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11 |
---------------------------------------------------
Generación de sublcaves K:
Este esquema se realiza para cada una de las iteraciones:
K (56 bits)
|
-----
| D |
-----
|
---------------------
| |
------------------ ------------------
| Desplazamiento | | Desplazamiento |
------------------ ------------------
| |
---------------------
|
-----
| E |
-----
|
ki (48 bits)
El primer paso consiste en una permutación mediante la tabla D:
------------------------
| Tabla permutación D |
------------------------
| 57 49 41 33 25 17 09 |
| 01 58 50 42 34 26 18 |
| 10 02 59 51 43 35 27 |
| 19 11 03 60 52 44 36 |
| 63 55 47 39 31 23 15 |
| 07 62 54 46 38 30 22 |
| 14 06 61 53 45 37 29 |
| 21 13 05 28 20 12 04 |
------------------------
Los 56 bits se dividen en dos partes de 28 bits. Cada una de estas partes
rota hacia la izquierda un número X de bits en cada iteración,
conforme a la tabla siguiente:
----------------------------------------------------------------------
| Iteración | 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 |
| Desplazamiento | 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 1 |
----------------------------------------------------------------------
Finalmente, mediante la tabla de compresión E los 56 bits (28+28)
del resultado se comprimen formando una subclave de 48 bits (la
utilizada en la función f).
--------------------------
| Tabla de compresión E |
--------------------------
| 14 17 11 24 01 05 |
| 03 28 15 06 21 10 |
| 23 19 12 04 26 08 |
| 16 07 27 20 13 02 |
| 41 52 31 37 47 55 |
| 30 40 51 45 33 48 |
| 44 49 39 56 34 53 |
| 46 42 50 36 29 32 |
--------------------------
3. Descifrado en DES
Una de las partes positivas de DES es que podemos descifrar los mensajes
utilizando el mismo algoritmo que utilizamos para cifrar. La única
diferencia consiste en el orden en que se aplican la subclaves, dado que
en el descifrado se utilizan en orden inverso. Es decir, primero se
utiliza la subclave k16, después la k15 ... k1.
3. Debilidades del algoritmo DES
Desde la aparición del algoritmo DES han aparecido algunas
críticas sobr el criptosistema. La principal es la longitud de la clave,
de solo 56 bits, que hacen posible los ataques de fuerza bruta.
Por otra parte, la arbitrariedad de las cajas S, podría ser causa de
la existencia de una clave maestra que permitiese descifrar cualquier mensaje.
Una forma de solucionar el problema de la longitud de la clave es el uso del
cifrado triple, conocido como Triple DES.
daniellerch.com