Cifrado DES Explicado by StringManolo

DES (Data Encryption Standard) es un algoritmo de cifrado por bloques ya en desuso en su versión clásica, aunque en teoría su versión tripleDES es "segura", no se recomienda su uso debido a que hay alternativas mas seguras y rápidas. Aún así vale la pena conocer como funciona. La versión TripleDES no es mas que cifrar 3 veces el mensaje con DES.

- En el cifrado simétrico por bloques DES se utiliza una clave de 64 caracteres como entrada

Por ejemplo la clave en ASCII/UTF-8 (abcdefgh)
Cada caracter en esta clave se represta usando 1 byte (8 bits).
ASCII -> abcdefgh
Binario -> 01100001 01100010 01100011 01100100 01100101 01100110 01100111 01101000
Secuencia -> 0110000101100010011000110110010001100101011001100110011101101000

/* Ejemplo de codigo para convertir texto a binario */
 
const text = "abcdefgh";
let end = "";
for (let i in text) {
  let aux = text[i].charCodeAt(0).toString(2)
  if (aux.length < 8) {
    aux = "0".repeat(8 - aux.length) + aux;
  }
  end += aux + " ";
}
console.log(end);

El algoritmo de DES ignora un bit por cada byte de la clave. Se cree que fue una estrategia de la NSA para poder romper el cifrado antes que nadie. Asique el tamaño de clave real utilizado internamente es de 56 bits aunque la entrada requiera de 64 bits.

- El algoritmo de DES usa tablas predefindas recurrentemente para realizar permutaciones. Se conocen como PC (Permuted Choice)

La primera tabla de permutación de DES es la siguiente (PC-1):

Esta tabla nos indica la posición que debemos elegir de nuestra clave para generar la clave permutada de 56 bits a partir de la de 64 bits.

Nuestro binario es:
0110000101100010011000110110010001100101011001100110011101101000

Vamos a elegir el bit de la posición 57, después el que se encuentre en la posición 49 y así hasta finalizar toda la tabla.


Y aquí tenemos nuestra clave permutada de 56 bits con PC-1:
0000000
0111111
1111111
1110000
0110011
0011110
0010000
0000000

- El siguiente paso es divir la clave por la mitad en 2 trozos de 28 bits cada uno:
0000000
0111111
1111111
1110000

0110011
0011110
0010000
0000000

- El siguiente paso es aplicar una operación de cambio de bits hacia la izquierda a cada uno de los trozos para crear 2 grupos formados por 16 secuencias de bits cambiados.

La operación de cambio de bits hacia la izquiera se realiza moviendo cada bit hacia la izquierda pasando el que se encuentra en la primera posición al final del todo. Por ejemplo si tenemos la secuencia de bits 1101:
0° -> 1101
1° -> 1011
2° -> 0111
3° -> 1110
4° ...
5° ...

No todas las iteraciones tienen la misma cantidad de cambio de bits.
El número de bits por iteración que tenemos que desplazar hacia la izquierda es el siguiente:


El resultado es:



- Lo siguiente es agruparlos juntos:

Y aplicar otra permutación con una nueva tabla (PC-2) para obtener 48 bits a partir de estos 56 que tenemos.
La tabla PC-2 es:

Hay que aplicar esta tabla a cada uno de los 16 grupos para obtener un total de 16 claves de 48 bits cada una. Se hace igual que la primera permutación anteriormente mostrada con la tabla PC-1.

1°  -> 00000001111111111111111000001100110011110001000000000000


1°:
111000  
001011
111001
100110
000100
110010
101010
000010

Tienes que repetir este paso para el resto de las 16 secuencias. El proceso de los 15 restantes es omitido por brevedad, solo se mostrarán los resultados directamente.

Aquí el código que hice para no tener que realizarlas a mano:

/* PC a binario */
const pc = (bin, table) => {
  let result = "";
  for(let i = 0; i < table.length; ++i) {
    result += bin[table[i] - 1];
  }
 
  return result;
}
 
 
const BIN = "00000001111111111111111000001100110011110001000000000000";
const DES_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
];
 
const res = pc(BIN, DES_PC2);
console.log(res);
/* FIN DEL CÓDIGO */

Para calcular todas las secuencias, el código que añadí es:

/* Calcula las 16 secuencias con PC-2 */
const BINS = [
  "00000001111111111111111000001100110011110001000000000000",
  "00000011111111111111110000001001100111100010000000000001",
  "00001111111111111111000000000110011110001000000000000110",
  "00111111111111111100000000001001111000100000000000011001",
  "11111111111111110000000000000111100010000000000001100110",
  "11111111111111000000000000111110001000000000000110011001",
  "11111111111100000000000011111000100000000000011001100111",
  "11111111110000000000001111110010000000000001100110011110",
  "11111111100000000000011111110100000000000011001100111100",
  "11111110000000000001111111110000000000001100110011110001",
  "11111000000000000111111111110000000000110011001111000100",
  "11100000000000011111111111110000000011001100111100010000",
  "10000000000001111111111111110000001100110011110001000000",
  "00000000000111111111111111100000110011001111000100000000",
  "00000000011111111111111110000011001100111100010000000000",
  "00000000111111111111111100000110011001111000100000000000"
];
 
for (let i in BINS) {
  console.log( pc(BINS[i], DES_PC2) )
}
/* FIN DEL CÓDIGO */

Y el resultado es:
1°  -> 111000001011111001100110000100110010101010000010
2°  -> 111000001011011001110110000100000010001100000111
3°  -> 111001001101011001110110101101100000000010000100
4°  -> 111001101101001101110010010000000010001111000011
5°  -> 101011101101001101110011001101101010000000001001
6°  -> 101011110101001101011011011000100001010101000010
7°  -> 001011110101001111011001000011001010000100101010
8°  -> 000111110101100111011001011001000101110001000000
9°  -> 000111110100100111011001010010101001100001000000
10° -> 000111110110100110011101110000001100010100111000
11° -> 000111110010110110001101000010010001111000001000
12° -> 010110110010110010101101110110000101000000110000
13° -> 110110011010110010101100000000010100101000101100
14° -> 110100001010111010101110100100000011100010010000
15° -> 111100001011111000100110101000010000001000110101
16° -> 111100001011111000100110101000110100001010000000


- En DES el mensaje que quieres encryptar debe ser dividido en bloques de 64 bits.

Para el mensaje debemos realizar una permutación inicial con una nueva tabla IP (Initial Permutation):

Usaré el mensaje "hello world" como ejemplo:
h -> 01101000
e -> 01100101
l -> 01101100
l -> 01101100
o -> 01101111
  -> 00100000
w -> 01110111
o -> 01101111
r -> 01110010
l -> 01101100
d -> 01100100

En bloques de 64 bits es:
0110100001100101011011000110110001101111001000000111011101101111
011100100110110001100100

Aquí tenemos un bloque de 64 bits y otro de 24.
Para no complicar el proceso con el padding, rellenaré de ceros el resto del bloque hasta alcanzar los 64 bits.
0110100001100101011011000110110001101111001000000111011101101111
0111001001101100011001000000000000000000000000000000000000000000

Ahora se aplica la tabla de permutación inicial (IP) a cada bloque:
B1 -> 1101111101000000110111101101001000000000111111111001110111010000
B2 -> 0000011100000001000001100000000000000000000001110000001000000001


- Ahora se divide cada bloque a la mitad (32 bits).

L  -> 11011111010000001101111011010010
R -> 00000000111111111001110111010000

(Este segundo bloque lo ignoraremos, porque hay distintas formas de combinar bloques, que esto ya no entra dentro de lo que es el propio algoritmo de DES y necesitaría una entrada propia)
L  -> 00000111000000010000011000000000
R -> 00000000000001110000001000000001

- El siguiente paso es utilizar una función que toma como entradas una clave de 48 bits y un texto de 32 bits, para generar una salida de 32 bits.
Usaremos las 16 claves de 48 bits que computamos en los pasos anteriores y los trozos de 32 bits que acabamos de hacer partiendo el mensaje en 2. Necesitamos aplicar las 16 claves a cada mitad usando una función.

Las claves que ya teníamos:
1°  -> 111000001011111001100110000100110010101010000010
2°  -> 111000001011011001110110000100000010001100000111
3°  -> 111001001101011001110110101101100000000010000100
4°  -> 111001101101001101110010010000000010001111000011
5°  -> 101011101101001101110011001101101010000000001001
6°  -> 101011110101001101011011011000100001010101000010
7°  -> 001011110101001111011001000011001010000100101010
8°  -> 000111110101100111011001011001000101110001000000
9°  -> 000111110100100111011001010010101001100001000000
10° -> 000111110110100110011101110000001100010100111000
11° -> 000111110010110110001101000010010001111000001000
12° -> 010110110010110010101101110110000101000000110000
13° -> 110110011010110010101100000000010100101000101100
14° -> 110100001010111010101110100100000011100010010000
15° -> 111100001011111000100110101000010000001000110101
16° -> 111100001011111000100110101000110100001010000000

El algoritmo que necesitamos utilizar es:

L[n] = R[n - 1]
R[n] = L[n - 1] XOR F(R[n - 1], K[n])

L es el trozo izquierdo del bloque recientemente permutado
R es el trozo derecho del bloque recientemente permutado
XOR es una operación de Bits (Disyunción Exclusiva en Español).
F es una función con múltiples pasos que se detallará en seguida.
K es la clave.
n es la iteración/ronda.


Algoritmo para n = 1 (la primera vez que aplicas el algoritmo):

n = 1;
L[1] = R[0];
R[1] = L[0] XOR F(R[0], K[1]);

n = 1:
R[0] = 00000000111111111001110111010000;
L[1] = R[0]
R[1] = 11011111010000001101111011010010 + F(00000000111111111001110111010000, 111000001011111001100110000100110010101010000010)

- Ahora vamos a empezar con la función F:

La función F utiliza una tabla de permutaciones (E) para expandir R[n - 1] de 32 bits a 48 bits.

En esta primera ronda, R[0] es 00000000111111111001110111010000

Tras expandir R[0] usando la tabla (E) para realizar la permutación, se obtiene:
000000000001011111111111110011111011111010100000

- El siguiente paso de la función es realizar un XOR entre R[0] expandido y K[1] (La primera clave)
000000000001011111111111110011111011111010100000 XOR 111000001011111001100110000100110010101010000010 -> 111000001010100110011001110111001001010000100010

El siguiente paso de F incluye el uso de S-Boxes (cajas de substitución).
Primero, hay que dividir el resultado de la clave xoreada con la mitad expandida del mensaje permutado en grupos de 6 bits:
111000 001010 100110 011001 110111 001001 010000 100010

La primera S-Box (S1) es:

La S-Box es como un mapa de coordenadas. Hay que elegir el primer y el último bit de cada grupo de 6 bits para obtener la coluna y los bits restantes (en el medio) se utilizan para elegir la fila.
En el caso de 111000:
Primer y último bit -> 10
Bits del medio -> 1100

Los pasamos a decimal:
10 -> 2
1100 -> 12

Y ahora empleamos estos 2 números como guía para obtener el decimotercero número de la tercera columna (Las columnas y filas empiezan a contar en 0).

El número que obtenemos es el 3.
3 -> 0011

Es decir, usando la S-Box con 111000 como entrada, obtenemos como salida 0011.

Ahora tenemos que repetir lo mismo para el resto de grupos de 6 bits, PERO necesitamos utilizar una S-Box distinta para cada grupo.


Aquí el código que utilicé para generar todos los bits, utilizando los grupos y las cajas de substitución:

const transformSboxes = (groups, sboxes) => {
  const ret = [];
  for (let i in groups) {
    const column = parseInt(groups[i][0] + groups[i][5], 2);
    const field = parseInt(groups[i].substring(1, 5), 2);
    let res = sboxes[i][column][field].toString(2);
    if (res.length < 4) {
      res = "0".repeat(4 - res.length) + res;
    }
    ret.push(res);
  }
 
  return ret;
}
 
const groups = [
  "111000",
  "001010",
  "100110",
  "011001",
  "110111",
  "001001",
  "010000",
  "100010"
]
 
const sBox = [
 
  [
    [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
    [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
    [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
    [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]               ],
 
  [
    [15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
    [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
    [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
    [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]
  ],
 
  [
    [10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
    [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
    [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
    [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]
  ],
 
 
  [
    [7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
    [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
    [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
    [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]
  ],
 
  [
    [2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
    [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
    [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
    [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]
  ],
 
  [
    [12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
    [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
    [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
    [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]
  ],
 
  [
    [4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
    [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
    [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
    [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]
  ],
 
  [
    [13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
    [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
    [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
    [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]
  ]
];
 
 
const res = transformSboxes(groups, sBox);
console.log(res);
/* END CODE */

Resultado:
0011 1011 1001 0001 1001 0111 0011 1011

De momento tenemos:
R[1] = 11011111010000001101111011010010 XOR F(0011 1011 1001 0001 1001 0111 0011 1011)

El último paso de la función es otra permutación:

El resultado de F es 11101111001010100110111100001010

Ahora tenemos que hacer xor a L[0] y al resultado de F para obtener R[1]:
R[1] = 11011111010000001101111011010010 XOR 11101111001010100110111100001010
R[1] -> 00110000011010101011000111011000

Ya finalizamos la primera ronda para n = 1. Recuerda:

Ahora hay que realizar los mismos pasos para n = 2:

Cuando finalizes todas las rondas (16), tendrás L[16] y R[16] (32 bits cada uno)
Solo te faltará darle la vuelta al orden. Ejemplo
Si L[16] es 00110000011010101011000111011000 y R[16] es 10110000011010101011000111011001 tendrás:
1011000001101010101100011101100100110000011010101011000111011000

Y aplicas la última permutación

El resultado es tu mensaje cifrado con DES.

Para descifrar es exactamente lo mismo.