El 15 de mayo de 1973, la Agencia Nacional de Normalización hizo un llamamiento en el Registro Federal para la creación de un algoritmo de cifrado que cumpliera con los siguientes requisitos:
Ofrecer un alto nivel de seguridad relacionado con una pequeña clave utilizada para cifrado y descifrado
Ser comprensible
No depender de la confidencialidad del algoritmo
Ser adaptable y económico
Ser eficaz y exportable
A finales de 1974, IBM propuso "Lucifer", que gracias a la Agencia Nacional de Seguridad fue modificado convirtiéndose en DES (Data Encryption Standard o Estándar de Cifrado de Datos).
Se trata de un sistema de cifrado simétrico por bloques de 64 bits, de los que 8 bits (un byte) se utilizan como control de paridad para la verificación de la integridad de la clave.
El algoritmo se encarga de realizar combinaciones, sustituciones y permutaciones entre el texto a cifrar y la clave, asegurándose al mismo tiempo de que las operaciones puedan realizarse en tanto para el cifrado como para el descifrado.
El algoritmo se puede describir de la siguiente manera:
Fraccionamiento del texto en bloques de 64 bits (8 bytes)
Permutación inicial de los bloques
Partición de los bloques en dos partes: izquierda y derecha
Permutación y sustitución repetidas 16 veces (denominadas rondas)
Reconexión de las partes izquierda y derecha, seguida de la permutación inicial inversa.
Generación de llave
Dado que el algoritmo DES mencionado anteriormente es público, toda la seguridad se basa en la complejidad de las claves de cifrado.
A continuación se muestra cómo obtener el conjunto de llaves usando la llave publica de 64 bits, cada una de ellas utilizadas para el algoritmo DES.
Como primer paso se realiza una permutación denominada PC1, de esta forma se eliminan los bits de paridad de la llave para obtener una llave que posea una longitud de 56 bits. La tabla de la permutación PC1 es la siguiente:
PC1
57
49
41
33
25
17
9
1
58
50
42
34
26
18
10
2
59
51
43
35
27
19
11
3
60
52
44
36
63
55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4
A continuación, se divide el resultado en dos mitades y , cada una de ellas de 28 bits.
Con y definidas, ahora se crean 16 bloques y , con . Cada par de bloques ( , ) se forma a partir del par anterior(es decir , ), usando para ello una tabla de rotaciones a la izquierda prefijadas de la siguiente forma:
Iteración:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Desplazamientos:
1
1
2
2
2
2
2
1
2
2
2
2
2
2
2
1
Una vez obtenidos los dos bloques de 28 bits de cada iteración, cada par se agrupa en un bloque de 56 bits. Esto da como resultado 16 bloques de 56 bits, de los cuales cada uno de los bloques pasa por una permutación, denominada PC2:
PC2
14
17
11
24
1
5
3
28
15
6
21
10
23
19
12
4
26
8
16
7
27
20
13
2
41
52
31
37
47
55
30
40
51
45
33
48
44
49
39
56
34
53
46
42
50
36
29
32
Esto da como resultado 16 bloques de 48 bits que representan el conjunto de 16 llaves a utilizadas en el algoritmo DES.
Cifrado
A partir de ahora se usan los bloques de 64 bits pertenecientes al mensaje.
Cada bit de un bloque está sujeto a una permutación inicial, que puede representarse mediante la siguiente matriz de permutación inicial (anotada como IP):
IP
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
Esta tabla de permutación muestra que el bit número 58 del bloque de 64 bits está en la primera posición, el bit numero 50 está en la segunda posición y así sucesivamente.
A continuación, se divide el bloque permutado en dos mitades: una parte izquierda denominada y una parte derecha denominada , ambas de 32 bits.
Los bloques y están sujetos a un conjunto de transformaciones iterativas denominadas rondas.
Las rondas comienzan con el bloque . Los 32 bits del bloque se expanden a 48 bits gracias a una tabla llamada tabla de expansión que se anota como E, en la que los 48 bits se mezclan y 16 de ellos se duplican:
E
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
El algoritmo DES aplica después OR exclusivas entre la primera clave y el bloque resultante de la expansión.
Después, el bloque obtenido se divide en 8 bloques de 6 bits. Cada uno de estos bloques se procesa a través de las llamadas cajas de sustitución, denominadas generalmente S-Box.
Esta es la primera caja de sustitución, representada en una tabla de 4 por 16:
S1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
1
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
2
4
1
14
8
13
6
2
11
15
12
9
7
3
10
5
0
3
15
12
8
2
4
9
1
7
5
11
3
14
10
0
6
13
Un ejemplo del funcionamiento de la caja de sustitución es el siguiente:
Sea 101110 el primero de los 8 bloques. El primer y último bit dan 10, es decir, 2 en valor binario. Los bits 2, 3, 4 y 5 dan 0111, o 7 en valor binario. Por lo tanto, el resultado de la caja de sustitución es el valor ubicado en la línea 2, de la columna 7. Es el valor 11 o 1011 en binario.
Cada uno de los 8 bloques de 6 bits pasa a través de la función de selección correspondiente, dando un resultado de 8 valores con 4 bits cada uno. A continuación se presentan las cajas de sustitución restantes:
S2
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
15
1
8
14
6
11
3
4
9
7
2
13
12
0
5
10
1
3
13
4
7
15
2
8
14
12
0
1
10
6
9
11
5
2
0
14
7
11
10
4
13
1
5
8
12
6
9
3
2
15
3
13
8
10
1
3
15
4
2
11
6
7
12
0
5
14
9
S3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
10
0
9
14
6
3
15
5
1
13
12
7
11
4
2
8
1
13
7
0
9
3
4
6
10
2
8
5
14
12
11
15
1
2
13
6
4
9
8
15
3
0
11
1
2
12
5
10
14
7
3
1
10
13
0
6
9
8
7
4
15
14
3
11
5
2
12
S4
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
7
13
14
3
0
6
9
10
1
2
8
5
11
12
4
15
1
13
8
11
5
6
15
0
3
4
7
2
12
1
10
14
9
2
10
6
9
0
12
11
7
13
15
1
3
14
5
2
8
4
3
3
15
0
6
10
1
13
8
9
4
5
11
12
7
2
14
S5
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
2
12
4
1
7
10
11
6
8
5
3
15
13
0
14
9
1
14
11
2
12
4
7
13
1
5
0
15
10
3
9
8
6
2
4
2
1
11
10
13
7
8
15
9
12
5
6
3
0
14
3
11
8
12
7
1
14
2
13
6
15
0
9
10
4
5
3
S6
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
12
1
10
15
9
2
6
8
0
13
3
4
14
7
5
11
1
10
15
4
2
7
12
9
5
6
1
13
14
0
11
3
8
2
9
14
15
5
2
8
12
3
7
0
4
10
1
13
11
6
3
4
3
2
12
9
5
15
10
11
14
1
7
6
0
8
13
S7
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
4
11
2
14
15
0
8
13
3
12
9
7
5
10
6
1
1
13
0
11
7
4
9
1
10
14
3
5
12
2
15
8
6
2
1
4
11
13
12
3
7
14
10
15
6
8
0
5
9
2
3
6
11
13
8
1
4
10
7
9
5
0
15
14
2
3
12
S8
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
13
2
8
4
6
15
11
1
10
9
3
14
5
0
12
7
1
1
15
13
8
10
3
7
4
12
5
6
11
0
14
9
2
1
7
11
4
1
9
12
14
2
0
6
10
13
15
3
5
8
1
2
1
14
7
4
10
8
13
15
12
9
0
3
5
6
11
Por lo tanto, cada bloque de 6 bits se sustituye por un bloque de 4 bits. Estos bits se combinan para formar un bloque de 32 bits.
Finalmente, el bloque de 32 bits se somete a una permutación P. A continuación, mostramos la tabla:
P
16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25
El conjunto de estos resultados salidos de P están sujetos a un OR exclusivo con inicial, para devolver , en tanto que la inicial devuelve .
Estos nuevos valores son los que serán usados en la siguiente ronda como y iniciales.
El conjunto de estos pasos (rondas) se reitera 16 veces.
Al final de las rondas, los dos bloques y se vuelven a conectar y se someten a una permutación inicial inversa conocida como IP-1:
IP-1
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 resultado que surge es el texto cifrado.
Descifrado
El proceso de descifrado es exactamente igual al cifrado descrito anteriormente, pero invirtiendo el orden en el que se hace uso del conjunto de sub llaves. Es decir, para el cifrado comenzamos usando la primer sub llave en la primer ronda y seguimos de forma ascendente hasta , para el descifrado comenzaríamos usando en la primer y seguimos de forma descendente hasta .
Referencias
Douglas Stinson. (1995). Cryptography: Theory and Practice. United States: CRC Press.
Prof. Dr. Eng. Monica Borda. (2011). Fundamentals in Information Theory and Coding. Berlin Heidelberg: Springer.
Wade Trappe, Lawrence C. Washington. (2006). Introduction to Cryptography with Coding Theory. United States: Prentice Hall.
Para generar el conjunto de llaves, la llave debe ser escrita en binario Posteriormente se realiza una permutacion entre la llave en binario y la matriz de permutación PC1, de esta forma se eliminan los bits de paridad de la clave
PC1
Al obtener la permutacion principal, comienzan las iteraciones
Nota:Para la primer iteración se hace uso del resultado de la permutacion principal, para las iteraciones posteriores se hace uso del resultado de la rotacion de la iteracion anterior
El resultado de la permutacion principal se divide en la mitad izquierda y la mitad derecha y cada uno se desplaza el numero de posiciones dado por la tabla de rotaciones En la primer iteracion el desplazamineto de los bits es de una posición
Iteración:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Desplazamientos:
1
1
2
2
2
2
2
1
2
2
2
2
2
2
2
1
Una vez teminada la rotacion, se unen izquierda y derecha
Al obtener la rotacion se aplica una permutacion con la matriz PC2
PC2
Al obtener la primer llave se termina la primer iteración Para obtener el conjunto de llaves restantes repetir 15 veces mas la rotacion y permutacion con PC2
El mensaje en claro debe ser escrito en binario Posteriormente se realiza una permutacion entre el mensaje en claro y la matriz de permutación IP, y el resultado obtenido es divido en la mitad izquierda (L) y la mitad derecha (R)
IP
Al obtener la permutacion, comienzan las iteraciones
Para el nuevo valor de R, se le aplica una permutacion con la tabla de expancion, a esta operacion se le llama expancion
E
Al resultado obtenido en la expancion se le aplica una operacion de XOR con la primer llave del conjunto de llaves obtenido previamente
Después se divide en 8 bloques de 6 bits y cada uno de estos bloques se procesa a través de cajas de sustitución La sustitucion se realiza tomando el primer y ultimo bit del bloque, la union de estos bits representará la fila y los cuatro bits restantes representan la columna; con este par de coordenadas se obtiene el resultado de cada sustituión
S1
S2
S3
S4
S5
S6
S7
S8
El bloque de 32 bits se somete a una permutacion con la tabla P
P
El ultimo paso de la iteracion es realizar la operacion XOR entre L y el resultado de S-Box De esta forma obtendremos el nuevo valor de R que sera usado para la siguiente iteracion Para obtener el nuevo valor de L que se usara en la siguiente iteracion, se toma el valor de R con el se inicio en la iteracion Este proceso se realiza 15 vecez mas usando el conjunto de llaves ordenado de forma acendente
Para conseguir el texto cifrado, L y R obtenidos en la ultima iteracion son unidos y permutados usando la tabla IP inversa, de esta forma se obtiene el texto cifrado
Para generar el conjunto de llaves, la llave debe ser escrita en binario Posteriormente se realiza una permutacion entre la llave en binario y la matriz de permutación PC1, de esta forma se eliminan los bits de paridad de la clave
PC1
Al obtener la permutacion principal, comienzan las iteraciones
Nota:Para la primer iteración se hace uso del resultado de la permutacion principal, para las iteraciones posteriores se hace uso del resultado de la rotacion de la iteracion anterior
El resultado de la permutacion principal se divide en la mitad izquierda y la mitad derecha y cada uno se desplaza el numero de posiciones dado por la tabla de rotaciones En la primer iteracion el desplazamineto de los bits es de una posición
Iteración:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Desplazamientos:
1
1
2
2
2
2
2
1
2
2
2
2
2
2
2
1
Una vez teminada la rotacion, se unen izquierda y derecha
Al obtener la rotacion se aplica una permutacion con la matriz PC2
PC2
Al obtener la primer llave se termina la primer iteración Para obtener el conjunto de llaves restantes repetir 15 veces mas la rotacion y permutacion con PC2
El texto cifrado debe ser escrito en binario Posteriormente se realiza una permutacion entre el texto cifrado y la matriz de permutación IP, y el resultado obtenido es divido en la mitad izquierda (L) y la mitad derecha (R)
IP
Al obtener la permutacion, comienzan las iteraciones
Para el nuevo valor de R, se le aplica una permutacion con la tabla de expancion, a esta operacion se le llama expancion
E
Al resultado obtenido en la expancion se le aplica una operacion de XOR con la ultima llave del conjunto de llaves obtenido previamente
Después se divide en 8 bloques de 6 bits y cada uno de estos bloques se procesa a través de cajas de sustitución La sustitucion se realiza tomando el primer y ultimo bit del bloque, la union de estos bits representará la fila y los cuatro bits restantes representan la columna; con este par de coordenadas se obtiene el resultado de cada sustituión
S1
S2
S3
S4
S5
S6
S7
S8
El bloque de 32 bits se somete a una permutacion con la tabla P
P
El ultimo paso de la iteracion es realizar la operacion XOR entre L y el resultado de S-Box De esta forma obtendremos el nuevo valor de R que sera usado para la siguiente iteracion Para obtener el nuevo valor de L que se usara en la siguiente iteracion, se toma el valor de R con el se inicio en la iteracion Este proceso se realiza 15 vecez mas usando el conjunto de llaves ordenado de forma descendente
Para conseguir el texto descifrado, L y R obtenidos en la ultima iteracion son unidos y permutados usando la tabla IP inversa, de esta forma se obtiene el texto descifrado
Referencias