Ir al contenido principal

Criptografía (XLIX): el algoritmo DES (I)

DES (Data Encryption Standard) fue desarrollado por IBM a petición de la Oficina Nacional de Estandarización (National Bureau of Standards) de los Estados Unidos. Su diseño se basó en otro algoritmo anterior, Lucifer, y fue adoptado como estándar de cifrado en 1976 por el Gobierno de los EE.UU.

Es un algoritmo de cifrado simétrico (se utiliza la misma clave para cifrar y para descifrar) por bloques (la información a cifrar se divide en bloques y se aplica el algoritmo a cada uno de ellos) que se basa en una estructura denominada Red de Feistel (cifrado de producto iterativo de n rondas en el que la salida de cada una de ellas se usa como entrada en la siguiente).

Este algoritmo opera sobre bloques de 64 bits del texto en claro, dividiendo cada uno de ellos en dos mitades, L (los 32 bits de la izquierda) y R (los 32 bits de la derecha), y emplea una clave de 56 bits.

Básicamente, el cifrado consiste en una permutación inicial, una Red de Feistel de 16 rondas (16 iteraciones en las que se repiten una serie de operaciones: permutaciones, aritmética modular y sustituciones. Ver conceptos de difusión, confusión y cifrado de producto en este post) y una permutación final.

En principio la longitud de la clave (K) es de 64 bits, pero el bit menos significativo de cada byte se ignora, por lo que sólo se emplean 56 bits.

Si no lo he entendido mal, su funcionamiento sería el siguiente:

1.- Como paso previo al cifrado, a partir de la clave de 64 bits se calculan 16 subclaves (Ki) de 48 bits cada una (una para cada ronda).

1.1.- Permutación de los bits de K conforme a la posición de cada uno de ellos que se indica en la siguiente tabla:
Nótese que en esta tabla no figuran los bits menos significativos de cada byte (8, 16, 24, 32, 40, 48, 56 y 64), por lo que éstos son ignorados (como he dicho antes, en la práctica se emplean 56 bits de la clave).

Pongo un ejemplo:
1.2.- Ahora, los bits de la mitad izquierda (C0) y de la mitad derecha (D0), obtenidas tras la permutación PC-1, ambas de 28 bits, se van rotando circularmente a la izquierda conforme al número de bits a desplazar a la izquierda que se indica en la siguiente tabla:
Es decir, el número de bits a desplazar a la izquierda es 2, excepto para las iteraciones 1, 2, 9 y 16 en las que se desplaza sólo 1 bit a la izquierda.

En nuestro ejemplo:
1.3.- Tras cada una de las iteraciones anteriores se aplica la permutación PC-2 a  los bits de la concatenación de Ci || Di (donde £ i £ 16), conforme a la posición de cada uno de ellos que se indica en la siguiente tabla:
Y, de esta forma, se obtienen las 16 subclaves (Ki; donde £ i £ 16); como he dicho antes, cada una de ellas con una longitud de 48 bits. Siguiendo con nuestro ejemplo:
Hasta el momento, gráficamente:
Y ahora ya se está en disposición de cifrar el texto en claro.

2.- Cifrado: Supongamos que vamos a cifrar un bloque (64 bits) del texto en claro. El siguiente:

M = 0100 0101 0100 1010 0100 0101 0100 1101 0101 0000 0100 1100 0100 1111 0100 1101


2.1.- Se aplica una permutación inicial (IP) a los bits del bloque a cifrar conforme a la posición de cada uno de ellos que se indica en la siguiente tabla:
En nuestro ejemplo:
2.2.- A partir de aquí el algoritmo realiza 16 rondas utilizando una función (f), de la siguiente manera:
Es decir, en cada ronda, la mitad derecha pasa a ser la mitad izquierda de la siguiente iteración y la mitad izquierda, a la que se suma módulo 2 (operador lógico XOR u o-exclusivo) el resultado de la función f, pasa a ser la mitad derecha.

Gráficamente:
La función f consta de: una permutación de expansión (E) - que transforma el bloque de 32 bits de la entrada en uno de 48 bits, permutando los bits que recibe y duplicando algunos de ellos -, una operación XOR con el valor de la subclave correspondiente (Ki), 8 operaciones de sustitución aplicadas a cada uno de los 8 bloques de 6 bits en los que se divide el resultado de la operación XOR anterior y otra permutación (P).

Gráficamente:
2.2.1.- La permutación de expansión (E) se realiza conforme a la posición de cada uno de los bits de entrada que se indica en la siguiente tabla:
Nótese que algunos de los bits que recibe (32 bits) se duplican para obtener una salida de 48 bits, con objeto de poder realizar la operación XOR con la subclave (Ki) correspondiente, que tiene una longitud de 48 bits.

En nuestro ejemplo, para la primera iteración (entrada R0):
2.2.2.- Operación XOR con el valor de la subclave correspondiente:
En nuestro ejemplo y para la primera ronda:
2.2.3.- Las sustituciones se realizan mediante unas tablas denominadas S-Cajas (en inglés S-Boxes, Substitution Boxes).

Para ello, en primer lugar se divide el resultado anterior en 8 bloques de 6 bits cada uno, de la siguiente manera:
Y, posteriormente, cada uno de estos bloques es la entrada a su respectiva S-Caja, cada una de las cuales determina la sustitución a realizar de la siguiente manera:

El primer y último bit de cada bloque (Bi) indican la fila de la S-Caja (Si) a seleccionar y los cuatro bits centrales determinan la columna, devolviéndose el valor (4 bits) que se encuentra en la intersección de ambas.

En nuestro ejemplo, para la primera ronda y primera S-Caja (S1):
Las tablas de las S-Cajas son las siguientes:
2.2.4.- Por último, el resultado de la función f de cada ronda se obtiene aplicando una permutación (P) a la concatenación (32 bits) de los resultados obtenidos tras realizar cada una de las sustituciones anteriores, que devuelve un bloque también de 32 bits.
Y se repite el paso 2.2. hasta completar las 16 rondas.

2.3.- Finalmente, se aplica una permutación inversa a la permutación inicial (IP-1), conforme a la posición de cada uno de los bits de la concatenación de R16 y L16 obtenidos en la última ronda:
El resultado de aplicar esta permutación final es el criptograma (C).

Para ver si lo he entendido correctamente (con tanta confusión y difusión reconozco estar yo mismo un tanto confuso y difuso :)), en el próximo post pondré el resultado completo del cifrado del ejemplo y en otro posterior su descifrado, aunque ya adelanto que para el descifrado bastará con aplicar las subclaves (Ki) en orden inverso.

Comentarios

Entradas populares de este blog

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

Hace unos días mi amigo Iñaki Regidor ( @Inaki_Regidor ), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes"  publicado en uno de los blogs de EiTB . En ese post se explican ciertos métodos clásicos para cifrar mensajes , entre ellos el cifrado de Vigenère , y , al final del mismo, se propone un reto consistente en descifrar un mensaje , lo que me ha animado a escribir este post sobre el método Kasiski  para atacar un cifrado polialfabético ( conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla ). El mensaje a descifrar es el siguiente: LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético , lo que significa que, al contrario que en un sistema de

Criptografía (XXIII): cifrado de Hill (I)

En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill , propuesto por el matemático Lester S. Hill , en 1929, y que se basa en emplear una matriz como clave  para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente . Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice  Dani , amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasat

¿Qué significa el emblema de la profesión informática? (I)

Todas o muchas profesiones tienen un emblema que las representa simbólicamente y en el caso de la  informática: " es el establecido en la resolución de 11 de noviembre de 1977  para las titulaciones universitarias superiores de informática, y  está constituido por una figura representando en su parte central  un  núcleo toroidal de ferrita , atravesado por  hilos de lectura,  escritura e inhibición . El núcleo está rodeado por  dos ramas : una  de  laurel , como símbolo de recompensa, y la otra, de  olivo , como  símbolo de sabiduría. La  corona  será la  de la casa real  española,  y bajo el escudo se inscribirá el acrónimo de la organización. ". Veamos los diferentes elementos tomando como ejemplo el emblema del COIIE/EIIEO (Colegio Oficial de Ingenieros en Informática del País Vasco/ Euskadiko Informatikako Ingeniarien Elkargo Ofiziala ) . Pero no sólo el COIIE/EIIEO adopta el emblema establecido en dicha resolución, sino que éste se adopta también como im