Algoritmos de cifrado DES y AES. Esquema de cifrado del algoritmo DES
- Tutorial
¡Hola %nombredeusuario%!
Mucha gente sabe que el algoritmo DES se considera desde hace mucho tiempo el estándar predeterminado en el campo del cifrado simétrico. El primer ataque exitoso a este algoritmo imposible de eliminar se publicó en 1993, 16 años después de su adopción como estándar. El método, que el autor llamó criptoanálisis lineal, en presencia de 2 47 pares de texto plano/cifrado, permite abrir la clave secreta del cifrado DES en 2 43 operaciones.
Debajo del corte intentaré esbozar brevemente los puntos principales de este ataque.
Criptoanálisis lineal
El criptoanálisis lineal es un tipo especial de ataque a cifrados simétricos, cuyo objetivo es recuperar una clave de cifrado desconocida a partir de mensajes simples conocidos y sus correspondientes textos cifrados.En general, un ataque basado en criptoanálisis lineal se reduce a las siguientes condiciones. El atacante tiene una gran cantidad de pares de texto plano/texto cifrado obtenidos utilizando la misma clave de cifrado K. El objetivo del atacante es recuperar parte o la totalidad de la clave K.
En primer lugar, el atacante examina el cifrado y encuentra el llamado análogo estadístico, es decir una ecuación de la siguiente forma, que se cumple con probabilidad P ≠ 1/2 para un par de texto público/privado arbitrario y una clave fija:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
donde P n, C n, K n son los enésimos bits del texto, texto cifrado y clave.
Una vez encontrada dicha ecuación, el atacante puede recuperar 1 bit de información clave utilizando el siguiente algoritmo
Algoritmo 1
Sea T el número de textos para los cuales el lado izquierdo de la ecuación (1) es igual a 0, entonces
Si T>N/2, donde N es el número de textos claros conocidos.
Supongamos que K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (cuando P>1/2) o 1 (cuando P<1/2).
De lo contrario
Supongamos que K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (cuando P>1/2) o 0 (cuando P<1/2).
Es obvio que el éxito del algoritmo depende directamente del valor de |P-1/2| y del número de pares de textos abiertos/cerrados disponibles N. Cuanto más difiere la probabilidad P de igualdad (1) de 1/2, menor es el número de textos abiertos N necesarios para el ataque.
Hay dos problemas que deben resolverse para que el ataque tenga éxito:
- Cómo encontrar una ecuación efectiva de la forma (1).
- Cómo utilizar esta ecuación para obtener más de un bit de información sobre la clave.
Descripción de DES
Pero primero, describamos brevemente cómo funciona el algoritmo. Ya se ha dicho bastante sobre DES. Puede encontrar una descripción completa del cifrado en Wikipedia. Sin embargo, para explicar mejor el ataque necesitaremos una serie de definiciones que es mejor introducir con antelación.Entonces, DES es un cifrado de bloques basado en la red Feistel. El cifrado tiene un tamaño de bloque de 64 bits y un tamaño de clave de 56 bits. Consideremos el esquema de cifrado del algoritmo DES. 
Como puede verse en la figura, al cifrar texto, se realizan las siguientes operaciones:
- Permutación de bits inicial. En esta etapa, los bits del bloque de entrada se mezclan en un orden determinado.
- Después de esto, los bits mezclados se dividen en dos mitades, que se envían a la entrada de la función Feistel. Para DES estándar, la red Feistel incluye 16 rondas, pero existen otras variantes del algoritmo.
- Los dos bloques obtenidos en la última ronda de transformación se combinan y se realiza otra permutación en el bloque resultante.
En cada ronda de la red Feistel, los 32 bits menos significativos del mensaje pasan a través de la función f: 
Veamos las operaciones realizadas en esta etapa:
- El bloque de entrada pasa a través de la función de extensión E, que convierte un bloque de 32 bits en un bloque de 48 bits.
- El bloque resultante se suma a la clave redonda K i .
- El resultado del paso anterior se divide en 8 bloques de 6 bits cada uno.
- Cada uno de los bloques recibidos Bi pasa a través de la función de sustitución S-Box i, que reemplaza la secuencia de 6 bits con un bloque de 4 bits.
- El bloque de 32 bits resultante se pasa a través de la permutación P y se devuelve como resultado de la función f.
De mayor interés para nosotros desde el punto de vista del criptoanálisis de cifrado son los bloques S, diseñados para ocultar la conexión entre los datos de entrada y salida de la función f. Para atacar DES con éxito, primero construiremos análogos estadísticos para cada una de las S-boxes y luego los extenderemos al cifrado completo.
Análisis de bloque S
Cada S-box toma una secuencia de 6 bits como entrada y para cada secuencia se devuelve un valor fijo de 4 bits. Aquellos. Hay un total de 64 opciones de entrada y salida. Nuestra tarea es mostrar la relación entre los datos de entrada y salida de los bloques S. Por ejemplo, para la tercera caja S del cifrado DES, el tercer bit de la secuencia de entrada es igual al tercer bit de la secuencia de salida en 38 de 64 casos. Por lo tanto, encontramos el siguiente análogo estadístico para la tercera S. -caja:S 3 (x) = x, lo cual se cumple con probabilidad P=38/64.
Ambos lados de la ecuación representan 1 bit de información. Por lo tanto, si los lados izquierdo y derecho fueran independientes entre sí, la ecuación tendría que satisfacerse con una probabilidad de 1/2. Por tanto, acabamos de demostrar la relación entre la entrada y la salida de la tercera caja S del algoritmo DES.
Consideremos cómo podemos encontrar un análogo estadístico de la S-box en el caso general.
Para una caja S S a, 1 ≤ α ≤ 63 y 1 ≤ β ≤ 15, el valor NS a (α, β) describe cuántas veces de 64 posibles bits de entrada XOR S a superpuestos a los bits α son iguales a los bits de salida XOR superpuestos a los bits α β, es decir:
donde el símbolo es lógico Y.
Los valores de α y β para los cuales NS a (α, β) es más diferente de 32 describen el análogo estadístico más eficiente de la S-box S a.
El análogo más eficaz se encontró en la quinta caja S del cifrado DES para α = 16 y β = 15 NS 5 (16, 15) = 12. Esto significa que se cumple la siguiente ecuación: Z=Y ⊕ Y ⊕ Y ⊕ Y, donde Z es la secuencia de entrada de la S-box e Y es la secuencia de salida.
O teniendo en cuenta el hecho de que en el algoritmo DES, antes de ingresar al S-box, los datos se agregan módulo 2 con una clave redonda, es decir Z = X ⊕ K obtenemos
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, donde X e Y son los datos de entrada y salida de la función f sin tener en cuenta permutaciones.
La ecuación resultante se ejecuta en todas las rondas del algoritmo DES con la misma probabilidad P=12/64.
La siguiente tabla muestra una lista de efectivos, es decir. teniendo la mayor desviación de P=1/2, análogos estadísticos para cada bloque s del algoritmo DES. 
Construcción de análogos estadísticos para múltiples rondas de DES
Mostremos ahora cómo podemos combinar los análogos estadísticos de varias rondas de DES y, en última instancia, obtener un análogo estadístico para todo el cifrado.Para hacer esto, considere una versión de tres rondas del algoritmo:
Usemos un análogo estadístico eficiente de la quinta s-box para calcular ciertos bits del valor X(2).
Sabemos que con probabilidad 12/64 la igualdad se cumple en la función f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, donde X es el segundo bit de entrada de la quinta S-box, es esencialmente el bit 26 de la secuencia obtenida después de expandir los bits de entrada. Analizando la función de expansión, podemos establecer que el bit 26 es reemplazado por el bit 17 de la secuencia X(1).
De manera similar, Y,..., Y son esencialmente los bits 17, 18, 19 y 20 de la secuencia obtenida antes de la permutación P. Al examinar la permutación P, encontramos que los bits Y,..., Y son en realidad bits Y (1), Y(1), Y(1), Y(1).
El bit clave K involucrado en las ecuaciones es el bit 26 de la subclave K1 de la primera ronda y luego el análogo estadístico toma la siguiente forma:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Por eso, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) con probabilidad P=12/64.
Conociendo 3, 8, 14, 25 bits de la secuencia Y(1), puedes encontrar 3, 8, 14, 25 bits de la secuencia X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) o teniendo en cuenta la ecuación (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) con una probabilidad de 12/64.
Encontremos una expresión similar usando la última ronda. Esta vez tenemos la ecuación.
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Porque
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
entendemos eso
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4)
con una probabilidad de 12/64.
Igualando los lados derechos de las ecuaciones (3) y (4) obtenemos
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 con probabilidad (12/64) 2 +(1-12/64) 2 .
Teniendo en cuenta el hecho de que X(1) = PR y X(3) = CR obtenemos un análogo estadístico
CL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
el cual se ejecuta con probabilidad (12/64) 2 + (1-12/64) 2 =0.7.
El análogo estadístico descrito anteriormente se puede representar gráficamente de la siguiente manera (los bits en la figura están numerados de derecha a izquierda y comenzando desde cero): 
El atacante conoce todos los bits del lado izquierdo de la ecuación, por lo que puede aplicar el algoritmo 1 y descubrir el valor de K1 ⊕ K3. Vamos a mostrar cómo, utilizando este análogo estadístico, es posible abrir no 1, sino 12 bits de la clave de cifrado K.
Ataque de texto plano conocido en DES
Presentemos un método mediante el cual puede expandir el ataque y obtener inmediatamente 6 bits de la primera ronda de conexión.Al componer la ecuación (5), tomamos en cuenta el hecho de que no conocemos el valor de F1(PR, K1). Por lo tanto, utilizamos su análogo estadístico K1 ⊕ PR.
Devolvemos el valor F1(PR, K1) en lugar de la expresión K1 ⊕ PR y obtenemos la siguiente ecuación:
CL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , que se ejecutará con probabilidad 12/64. La probabilidad ha cambiado desde que dejamos solo el análogo estadístico de la tercera ronda, todos los demás valores son fijos.
Ya hemos determinado anteriormente que el valor de F1(PR, K1) está influenciado por los bits de entrada de la quinta S-box, es decir, los bits clave K1 y los bits del bloque PR. Vamos a mostrar cómo, teniendo sólo un conjunto de textos abiertos/cerrados, puedes restaurar el valor de K1. Para hacer esto, usaremos el Algoritmo 2.
Algoritmo 2
Sea N el número de pares de texto abiertos/cerrados conocidos antes del ataque. Luego, para abrir la clave, debe seguir los siguientes pasos.
Para (i=0; yo<64; i++) do
{
Para(j=0; j
si(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) entonces
T yo =T yo +1
}
}
Como secuencia probable K1 se toma un valor de i tal que la expresión |T i -N/2| tiene el valor máximo.
Dado un número suficiente de textos claros conocidos, el algoritmo tendrá una alta probabilidad de devolver el valor correcto de los seis bits de la subclave K1 de primera ronda. Esto se explica por el hecho de que si la variable i no es igual a K1, entonces el valor de la función F1(PR j, K) será aleatorio y el número de ecuaciones para dicho valor de i para el cual el lado izquierdo es igual a cero tenderá a N/2. Si la subclave se adivina correctamente, el lado izquierdo será igual al bit fijo K3 con una probabilidad de 12/64. Aquellos. habrá una desviación significativa de N/2.
Habiendo recibido 6 bits de la subclave K1, puede abrir de manera similar 6 bits de la subclave K3. Todo lo que necesitas hacer es reemplazar C con P y K1 con K3 en la ecuación (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
El algoritmo 2 devolverá el valor K3 correcto porque el proceso de descifrado del algoritmo DES es idéntico al proceso de cifrado, solo que se invierte la secuencia de claves. Entonces, en la primera ronda de descifrado se usa la clave K3 y en la última ronda se usa la clave K1.
Habiendo recibido 6 bits de las subclaves K1 y K3, el atacante recupera 12 bits de la clave común del cifrado K, porque Las claves redondas son la permutación habitual de la clave K. El número de textos claros necesarios para un ataque exitoso depende de la probabilidad del análogo estadístico. Para descifrar una clave DES de 12 bits y 3 rondas, son suficientes 100 pares de texto público/privado. Para descifrar 12 bits de una clave DES de 16 rondas, se necesitarán alrededor de 244 pares de textos. Los 44 bits restantes de la clave se abren mediante fuerza bruta normal.
DES(Estándar de cifrado de datos): un algoritmo de cifrado simétrico en el que se utiliza una clave para cifrar y descifrar datos. DES fue desarrollado por IBM y aprobado por el gobierno de EE. UU. en 1977 como estándar oficial (FTPS 46-3). DES tiene bloques de 64 bits y una estructura de red Feistel de 16 ciclos; utiliza una clave de 56 bits para el cifrado. El algoritmo utiliza una combinación de transformaciones no lineales (S-boxes) y lineales (permutaciones E, IP, IP-1). Se recomiendan varios modos para DES:cifrado de bloque
Los datos de entrada para un cifrado de bloque son un bloque de n bits y una clave de k bits. La salida, después de aplicar la transformación de cifrado, es un bloque cifrado de n bits, y pequeñas diferencias en los datos de entrada suelen provocar un cambio significativo en el resultado. Los cifrados de bloques se implementan aplicando repetidamente ciertas transformaciones básicas a bloques de texto fuente.Transformaciones básicas:
Transformaciones por la Red Feistel
Esta es una transformación sobre vectores (bloques) que representan las mitades izquierda y derecha del registro de desplazamiento. El algoritmo DES utiliza una transformación directa de la red Feistel en el cifrado (ver Fig. 1) y una transformación inversa de la red Feistel en el descifrado (ver Fig. 2).
Esquema de cifrado del algoritmo DES
El texto fuente es un bloque de 64 bits. El texto cifrado es un bloque de 64 bits.
El proceso de cifrado consta de una permutación inicial, 16 ciclos de cifrado y una permutación final.
Veamos el diagrama detallado del algoritmo DES:
L i R i =1,2\ldots.mitades izquierda y derecha del bloque de 64 bits L i R i
k i - claves de 48 bits
f - función de cifrado
IP - permutación inicial
IP -1 - permutación final. 
Según la tabla, los primeros 3 bits del bloque resultante IP(T) después de la permutación inicial de IP son los bits 58, 50, 42 del bloque de entrada T, y sus últimos 3 bits son los bits 23, 15, 7 del bloque de entrada. A continuación, el bloque IP(T) de 64 bits participa en 16 ciclos de transformación de Feistel.
16 ciclos de transformación de Feistel:
Divida IP(T) en dos partes L 0 ,R 0 , donde L 0 ,R 0 son los 32 bits más significativos y los 32 bits menos significativos del bloque T0 IP(T)= L 0 R 0 , respectivamente.
Sea T i -1 = L i -1 R i -1 el resultado de (i-1) iteración, luego se determina el resultado de la i-ésima iteración T i = L i R i:
L yo = R yo - 1 La mitad izquierda de Li es igual a la mitad derecha del vector anterior Li - 1 R i - 1 . Y la mitad derecha de R i es la suma de bits de Li - 1 y f(R i - 1, k i) módulo 2.
En la transformada de Feistel de 16 ciclos, la función f desempeña el papel de cifrado. Veamos la función f en detalle.
Los argumentos para la función f son el vector de 32 bits R i - 1, la clave de 48 bits k i, que son el resultado de convertir la clave de cifrado original k de 56 bits.
Para calcular la función f, se utilizan la función de expansión E, la transformación S, que consta de 8 transformaciones de caja S, y la permutación P.
La función E expande el vector de 32 bits R i - 1 al vector de 48 bits E(R i - 1) duplicando algunos bits de R i - 1, mientras que el orden de los bits del vector E(R i - 1 ) se indica en la Tabla 2. 
Los primeros tres bits del vector E(R i - 1) son los bits 32, 1, 2 del vector R i -1. La Tabla 2 muestra que los bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 están duplicados. Los últimos 3 bits del vector E(Ri - 1) son los bits 31, 32, 1 del vector Ri - 1. El bloque E(R i -1) obtenido después de la reordenación se suma módulo 2 con claves k i y luego se presenta en forma de ocho bloques consecutivos B 1 , B 2 ,...B 8 .
mi(R yo - 1) = segundo 1 segundo 2 ... segundo 8
Cada B j es un bloque de 6 bits. A continuación, cada uno de los bloques B j se transforma en un bloque B" j de 4 bits usando transformaciones S j. Las transformaciones S j están determinadas por la Tabla 3. Supongamos que B 3 = 101111 y queremos encontrar B" 3. El primer y último bit de B 3 son la representación binaria del número a, 0. El valor de la función f(R i - 1,k i) (32 bits) se obtiene mediante la permutación P aplicada al bloque B de 32 bits. " 1 B " 2 ... B " 8. La permutación P viene dada por la Tabla 4. 
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Según la Tabla 4, los primeros cuatro bits del vector resultante después de la acción de la función f son los bits 16, 7, 20, 21 del vector B" 1 B" 2 ...B" 8
Generando claves k i .
Las claves k i se obtienen de la clave inicial k (56 bits = 7 bytes o 7 caracteres ASCII) de esta forma. Se añaden a la clave k ocho bits, ubicados en las posiciones 8, 16, 24, 32, 40, 48, 56, 64, de modo que cada byte contenga un número impar de unos. Esto se utiliza para detectar errores en el intercambio y almacenamiento de claves. Luego se realiza una permutación para la clave extendida (excepto los bits agregados 8, 16, 24, 32, 40, 48, 56, 64). Esta permutación se define como en la Tabla 5. 
Esta permutación está definida por dos bloques C 0 y D 0 de 28 bits cada uno. Los primeros 3 bits de C0 son los bits 57, 49, 41 de la clave extendida. Y los primeros tres bits de D 0 son los bits 63, 55, 47 de la clave extendida. C i ,D i i=1,2,3… se obtienen a partir de C i - 1 ,D i - 1 mediante uno o dos desplazamientos cíclicos hacia la izquierda según la Tabla 6. 
La clave k i , i=1,…16 consta de 48 bits seleccionados de los bits del vector C i D i (56 bits) según la Tabla 7. El primer y segundo bits k i son los bits 14, 17 del vector C i yo 
La permutación final IP - 1 actúa sobre T 16 y se utiliza para restaurar la posición. Es lo inverso a la permutación de IP. La permutación final está determinada por la Tabla 8. 
Modos de uso de DES DES se puede utilizar en cuatro modos.
El algoritmo de cifrado simétrico más común y conocido es DES (Estándar de cifrado de datos). El algoritmo fue desarrollado en 1977 y adoptado por el NIST (Instituto Nacional de Estándares y Tecnología, EE. UU.) como estándar en 1980.
DES es una red Feishtel clásica con dos sucursales. Los datos se cifran en bloques de 64 bits utilizando una clave de 56 bits. El algoritmo convierte una entrada de 64 bits en una salida de 64 bits en varias rondas. La longitud de la clave es de 56 bits. El proceso de cifrado consta de cuatro etapas. El primer paso es una permutación inicial (IP) del texto fuente de 64 bits (blanqueamiento), durante la cual los bits se reordenan según una tabla estándar. La siguiente etapa consta de 16 rondas de la misma función, que utiliza las operaciones de cambio y sustitución. En la tercera etapa, se intercambian las mitades izquierda y derecha del resultado de la última (16.ª) iteración. Finalmente, la cuarta etapa realiza una permutación IP-1 del resultado obtenido en la tercera etapa. La permutación IP-1 es la inversa de la permutación inicial.
Fig.4. algoritmo DES
La figura muestra un método que utiliza una clave de 56 bits. Inicialmente, la clave se suministra a la entrada de la función de permutación. Luego, para cada una de las 16 rondas, la subclave K i es una combinación de desplazamiento circular hacia la izquierda y permutación. La función de permutación es la misma para cada ronda, pero las subclaves Ki para cada ronda son diferentes debido al desplazamiento repetido de los bits de la clave.
La permutación inicial y su inversión están determinadas por una tabla estándar. Si M son 64 bits arbitrarios, entonces X = IP(M) son los 64 bits reorganizados. Si aplicamos la función de permutación inversa Y = IP-1 (X) = IP-1 (IP(M)), obtenemos la secuencia de bits original.
Descripción de la ronda des
Veamos la secuencia de transformaciones utilizadas en cada ronda.
Fig.5. Ilustración de una ronda del algoritmo DES
Un bloque de entrada de 64 bits pasa por 16 rondas, y cada iteración produce un valor intermedio de 64 bits. Los lados izquierdo y derecho de cada valor intermedio se tratan como valores separados de 32 bits, denominados L y R. Cada iteración se puede describir de la siguiente manera:
R yo = L yo -1 F(R yo -1 , K yo)
Por lo tanto, la salida de la mitad izquierda Li es igual a la entrada de la mitad derecha R i-1. La salida de la mitad derecha de Ri es el resultado de aplicar una operación XOR a Li-1 y una función F que depende de Ri-1 y Ki.
Veamos la función F con más detalle. R i , que se suministra a la entrada de la función F, tiene una longitud de 32 bits. Primero, R i se expande a 48 bits usando una tabla que especifica la permutación más la expansión de 16 bits. La expansión se produce de la siguiente manera. Los 32 bits se dividen en grupos de 4 bits y luego se expanden a 6 bits agregando los bits más externos de dos grupos adyacentes. Por ejemplo, si parte del mensaje de entrada
Efgh ijkl mnop . . .
entonces el resultado de la expansión es el mensaje
Defghi hijklm lmnopq. . .
Luego se aplica XOR al valor de 48 bits resultante con la subclave K i de 48 bits. El valor resultante de 48 bits luego se introduce en la función de sustitución, lo que da como resultado un valor de 32 bits.
La sustitución consta de ocho cajas S, cada una de las cuales recibe 6 bits como entrada y produce 4 bits como salida. Estas transformaciones están definidas por tablas especiales. El primer y último bit del valor de entrada del S-box determinan el número de fila en la tabla, los 4 bits del medio determinan el número de columna. La intersección de una fila y una columna determina la salida de 4 bits. Por ejemplo, si la entrada es 011011, entonces el número de fila es 01 (fila 1) y el número de columna es 1101 (columna 13). El valor en la fila 1 y la columna 13 es 5, es decir la salida es 0101.
Luego, el valor de 32 bits resultante se procesa utilizando la permutación P, cuyo propósito es reordenar los bits tanto como sea posible para que en la siguiente ronda de cifrado, sea probable que cada bit sea procesado por una S-box diferente.
La clave para una ronda individual Ki consta de 48 bits. Las claves K i se obtienen utilizando el siguiente algoritmo. Para la clave de 56 bits utilizada como entrada para el algoritmo, primero se realiza una permutación de acuerdo con la tabla Permuted Choice 1 (PC-1). La clave de 56 bits resultante se divide en dos partes de 28 bits, denominadas C0 y D0, respectivamente. En cada ronda, Ci y Di se desplazan cíclicamente independientemente hacia la izquierda 1 o 2 bits, dependiendo del número de ronda. Los valores resultantes son la entrada para la siguiente ronda. También son la entrada a Permuted Choice 2 (PC-2), que produce un valor de salida de 48 bits que es la entrada a la función F(R i-1, K i).
El proceso de descifrado es similar al proceso de cifrado. La entrada al algoritmo es texto cifrado, pero las claves Ki se utilizan en orden inverso. Se usa 16d en la primera vuelta, 1d se utiliza en la última vuelta. Sea la salida de la i-ésima ronda de cifrado L i ||R i . Entonces la entrada correspondiente de la (16-i)-ésima ronda de descifrado será R i ||L i .
Después de la última ronda del proceso de descifrado, las dos mitades de la salida se intercambian de modo que la entrada de la permutación final IP-1 sea R 16 ||L 16. El resultado de esta etapa es texto sin formato.
Lo que ANSI llama algoritmo de cifrado de datos DEA (Algoritmo de cifrado de datos) e ISO lo llama DEA-1, se ha convertido en un estándar mundial en 20 años. A lo largo de los años de su existencia, ha resistido el embate de diversos ataques y, con ciertas limitaciones, todavía se considera criptorresistente.
DES es un cifrado de bloques que cifra datos en bloques de 64 bits. Se ingresa un bloque de texto sin formato de 64 bits en un extremo del algoritmo y se genera un bloque de texto cifrado de 64 bits en el otro extremo. DES es un algoritmo simétrico: se utilizan el mismo algoritmo y clave para el cifrado y descifrado (excepto por pequeñas diferencias en el uso de la clave). La longitud de la clave es de 56 bits. (Una clave normalmente se representa como un número de 64 bits, pero cada octavo bit se usa para la paridad y se ignora. Los bits de paridad son los bits menos significativos de los bytes de la clave). La clave, que puede ser cualquier número de 56 bits. , se puede cambiar en cualquier momento.
La fuerza criptográfica está completamente determinada por la clave. El componente fundamental de DES es la combinación de sustituciones y permutaciones.
DES consta de 16 ciclos.
Vista general del ciclo de conversión:
Si L i y R i son las mitades izquierda y derecha resultantes de la i-ésima iteración, K i es la clave de 48 bits para el bucle i, y f es una función que realiza todas las sustituciones, permutaciones y XOR en la clave, entonces uno El bucle de conversión se puede representar como:
Teniendo en cuenta la sustitución F i (*) y la permutación T (*), el ciclo de transformación se puede representar como se muestra en la Fig.
Se puede ver que cada ciclo DES es un cifrado de composición con dos transformaciones secuenciales: sustitución F i (*) y permutación T (*) (con la excepción del último ciclo decimosexto, donde se omite la permutación).
Sustitución:
(L yo, R yo) = (R yo −1, L yo −1) ⊕ f (R yo −1, K)
F yo (F yo (L yo −1, R yo −1)) = F yo (R yo −1, L yo −1) ⊕ (f (R yo −1, K i))) = (R yo − 1, L yo −1 ⊕(f (R yo −1, K i)) ⊕ (f (R yo −1, K i))) = (L yo −1, R yo −1)
una sustitución
T (L i ′, R i ′) = (R i ′, L i ′),
También es una involución, ya que
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Si denotamos las permutaciones inicial y final como (IP) y (IP) − 1, entonces la transformación DES directa (cifrado) implementa la función:
DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,
y la transformación DES inversa (descifrado) implementa la función:
DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).
Por lo tanto, DES es un cifrado de Feistel y está diseñado para cumplir la útil propiedad de que se utiliza el mismo algoritmo para el cifrado y descifrado. La única diferencia es que las claves deben usarse en orden inverso.
Es decir, si durante el cifrado se utilizaron las claves K 1, K 2, K 3, ..., K 16, entonces las claves de descifrado serán K 16, K 15, K 14, ..., K 1. El algoritmo utiliza únicamente operaciones lógicas y aritméticas estándar de 64 bits, por lo que puede implementarse fácilmente en hardware.
DES opera en un bloque de texto plano de 64 bits. Después de la mezcla inicial, el bloque se divide en mitades derecha e izquierda de 32 bits cada una. Luego se realizan 16 transformaciones (función f) en las que se combinan los datos con la clave. Después del decimosexto ciclo, las mitades derecha e izquierda se combinan y el algoritmo finaliza con una permutación final (lo contrario del original). En cada ciclo (ver figura), los bits clave se desplazan y luego se seleccionan 48 bits de los 56 bits clave. La mitad derecha de los datos se expande a 48 bits usando permutación de expansión, se aplica XOR con los 48 bits de la clave desplazada y permutada, se pasa a través de 8 S-boxes para formar 32 bits nuevos y se permuta nuevamente. Estas cuatro operaciones las realiza la función f.
Luego, el resultado de f se combina con la mitad izquierda usando otro XOR. Como resultado de estas acciones, aparece una nueva mitad derecha y la antigua mitad derecha se convierte en una nueva mitad izquierda. Estos pasos se repiten 16 veces, lo que da como resultado 16 ciclos de DES.
Estándar ruso - GOST 28147-89
GOST 28147-89 es un cifrado de bloques con una clave de 256 bits y 32 ciclos de conversión, que funciona en bloques de 64 bits.
El algoritmo criptográfico también utiliza una clave adicional, que se analiza a continuación. Para el cifrado, el texto sin formato primero se divide en mitades izquierda y derecha L y R.
En el i-ésimo ciclo, se utiliza la subclave K i:
L yo = R yo −1 ,
R yo = L yo −1 ⊕ (f (R yo −1, K yo)).
La función f se implementa de la siguiente manera. Primero, se agregan la mitad derecha y la i-ésima subclave módulo 2 32.
- El resultado se divide en ocho subsecuencias de 4 bits, cada una de las cuales se introduce en su propia S-box. GOST utiliza ocho S-boxes diferentes, los primeros 4 bits van al primer S-box, los segundos 4 bits al segundo S-box, etc. Cada S-box es una permutación de números del 0 al 15. Por ejemplo, La caja S podría verse así: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. En este caso, si la entrada de la S-box es 0, entonces la salida es 7. Si la entrada es 1, la salida es 10, etc. Las ocho S-box son diferentes, en realidad son material clave adicional. Las salidas de las ocho S-boxes se combinan en una palabra de 32 bits, luego la palabra completa se gira 11 bits hacia la izquierda. Finalmente, se aplica una operación XOR al resultado con la mitad izquierda para crear una nueva mitad derecha, y la mitad derecha se convierte en la nueva mitad izquierda. Para generar subclaves, la clave original de 256 bits se divide en ocho bloques de 32 bits: k 1, k 2, ..., k 8. Cada ciclo utiliza su propia subclave.
- El descifrado se realiza de la misma manera que el cifrado, pero el orden de las subclaves k i se invierte. El estándar no especifica cómo se generan las S-boxes.
- Principales diferencias entre DES y GOST
- Las principales diferencias entre DES y GOST son las siguientes:
- DES utiliza un procedimiento complejo para generar subclaves a partir de claves.
Un ataque contundente a GOST es absolutamente inútil. GOST utiliza una clave de 256 bits y, si tenemos en cuenta las S-boxes secretas, la longitud de la clave será aún mayor. GOST parece ser más resistente al criptoanálisis diferencial y lineal que DES. Aunque las cajas S GOST aleatorias, si se les da alguna opción, no garantizan una alta solidez criptográfica en comparación con las cajas S DES fijas, su secreto aumenta la resistencia de GOST al criptoanálisis diferencial y lineal. Además, la eficacia de estos métodos criptoanalíticos depende del número de ciclos de conversión: cuantos más ciclos, más difícil será el criptoanálisis. GOST utiliza el doble de ciclos que DES, lo que posiblemente provoque que falle el criptoanálisis diferencial y lineal.
GOST no utiliza la permutación de extensión existente en DES.
Eliminar esta permutación del DES lo debilita al reducir el efecto de avalancha; Es razonable suponer que la ausencia de dicha operación en GOST tiene un impacto negativo en su solidez criptográfica. Desde el punto de vista de la solidez criptográfica, la operación de suma aritmética utilizada en GOST no es peor que la operación XOR en DES.
La principal diferencia parece ser el uso de desplazamiento cíclico en lugar de permutación en GOST. La reorganización del DES aumenta el efecto de avalancha. En GOST, cambiar un bit de entrada afecta a una S-box de un ciclo de conversión, que luego afecta a dos S-box del siguiente ciclo, luego a tres bloques del siguiente ciclo, etc. Se necesitan ocho ciclos antes de que cambiar un bit de entrada afecte a cada bit de la salida; en DES esto requiere sólo cinco ciclos.
Sin embargo, GOST consta de 32 ciclos y DES de sólo 16.
Los desarrolladores de GOST intentaron lograr un equilibrio entre solidez criptográfica y eficiencia. Utilizando el diseño de Feistel como base, desarrollaron un algoritmo criptográfico que es más adecuado para la implementación de software que DES. Para aumentar la solidez criptográfica, se introdujo una clave extralarga y se duplicó el número de ciclos. Sin embargo, la cuestión de si los esfuerzos de los desarrolladores se vieron coronados por la creación de un algoritmo más criptográfico que DES sigue abierta. DES
Vorobyova E., Lukyanova A.
Algoritmo
Las principales ventajas del algoritmo DES:
· sólo se utiliza una clave con una longitud de 56 bits;
· habiendo cifrado un mensaje usando un paquete, puedes usar cualquier otro para descifrarlo;
DES cifra bloques de datos de 64 bits utilizando una clave de 56 bits. El descifrado en DES es la operación inversa del cifrado y se realiza repitiendo las operaciones de cifrado en orden inverso (a pesar de lo aparentemente obvio, esto no siempre se hace. Más adelante veremos cifrados en los que el cifrado y descifrado se llevan a cabo utilizando diferentes algoritmos). .
El proceso de cifrado consta de una permutación inicial de los bits de un bloque de 64 bits, dieciséis ciclos de cifrado y, finalmente, una permutación inversa de los bits (Fig. 1).
Cabe señalar de inmediato que TODAS las tablas proporcionadas en este artículo son ESTÁNDAR y, por lo tanto, deben incluirse en la implementación del algoritmo sin cambios. Los desarrolladores seleccionan todas las permutaciones y códigos de las tablas de tal manera que el proceso de descifrado sea lo más difícil posible seleccionando una clave. La estructura del algoritmo DES se muestra en la Fig. 2.
Fig.2. Estructura del algoritmo de cifrado DES
Deje que se lea el siguiente bloque T de 8 bytes del archivo, que se transforma utilizando la matriz de permutación inicial IP (Tabla 1) de la siguiente manera: el bit 58 del bloque T se convierte en el bit 1, el bit 50 se convierte en el bit 2, etc., lo que dé el resultado: T(0) = IP(T).
La secuencia de bits resultante T(0) se divide en dos secuencias de 32 bits cada una: L(0) - bits izquierdos o de orden superior, R(0) - bits derechos o de orden inferior.
Tabla 1: Matriz de permutación inicial de IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Luego se realiza el cifrado, que consta de 16 iteraciones. El resultado de la i-ésima iteración se describe mediante las siguientes fórmulas:
R(i) = L(i-1) xor f(R(i-1), K(i)) ,
donde xor es la operación O EXCLUSIVA.
La función f se llama función de cifrado. Sus argumentos son la secuencia de 32 bits R(i-1), obtenida en la (i-1)ésima iteración, y la clave de 48 bits K(i), que es el resultado de convertir la clave de 64 bits K. En detalle, a continuación se describe la función de cifrado y el algoritmo para obtener las claves K(i).
En la 16.ª iteración, se obtienen las secuencias R(16) y L(16) (sin permutación), que se concatenan en una secuencia de 64 bits R(16)L(16).
Luego, las posiciones de los bits de esta secuencia se reordenan de acuerdo con la matriz IP -1 (Tabla 2).
Tabla 2: Matriz de permutación inversa IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Las matrices IP -1 e IP están relacionadas de la siguiente manera: el valor del primer elemento de la matriz IP -1 es 40, y el valor del elemento 40 de la matriz IP es 1, el valor del segundo El elemento de la matriz IP -1 es 8 y el valor del octavo elemento de la matriz IP es igual a 2, etc.
El proceso de descifrado de datos es inverso al proceso de cifrado. Todos los pasos deben realizarse en orden inverso. Esto significa que los datos descifrados primero se reorganizan según la matriz IP-1 y luego se realizan las mismas acciones en la secuencia de bits R(16)L(16) que en el proceso de cifrado, pero en orden inverso.
El proceso de descifrado iterativo se puede describir mediante las siguientes fórmulas:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .
En la 16.ª iteración, se obtienen las secuencias L(0) y R(0), que se concatenan en una secuencia L(0)R(0) de 64 bits.
Luego, las posiciones de bits de esta secuencia se reordenan según la matriz IP. El resultado de tal permutación es la secuencia original de 64 bits.
Consideremos ahora la función de cifrado f(R(i-1),K(i)). Se muestra esquemáticamente en la Fig. 3.
Fig.3. Cálculo de la función f(R(i-1), K(i))
Para calcular el valor de la función f, se utilizan las siguientes funciones matriciales:
E - extensión de una secuencia de 32 bits a 48 bits,
S1, S2, ..., S8: conversión de un bloque de 6 bits a uno de 4 bits,
P: permutación de bits en una secuencia de 32 bits.
La función de expansión E se define en la Tabla 3. Según esta tabla, los primeros 3 bits de E(R(i-1)) son los bits 32, 1 y 2, y los últimos son 31, 32 y 1.
Tabla 3: Función de extensión E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 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 01
El resultado de la función E(R(i-1)) es una secuencia de 48 bits que se suma módulo 2 (operación xor) con la clave de 48 bits K(i). La secuencia resultante de 48 bits se divide en ocho bloques de 6 bits B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). Eso es:
E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .
Las funciones S1, S2, ..., S8 se definen en la Tabla 4.
Tabla 4
A la tabla 4. se requiere mayor aclaración. Sea la entrada de la función matricial Sj un bloque de 6 bits B(j) = b1b2b3b4b5b6, entonces el número de dos bits b1b6 indica el número de fila de la matriz y b2b3b4b5 el número de columna. El resultado de Sj(B(j)) será un elemento de 4 bits ubicado en la intersección de la fila y columna especificadas.
Por ejemplo, B(1)=011011. Entonces S1(B(1)) está ubicado en la intersección de la fila 1 y la columna 13. En la columna 13 de la fila 1 el valor es 5. Esto significa S1(011011)=0101.
Aplicando la operación de selección a cada uno de los bloques de 6 bits B(1), B(2), ..., B(8), obtenemos la secuencia de 32 bits S1(B(1))S2(B(2 ))S3(B(3))...S8(B(8)).
Finalmente, para obtener el resultado de la función de cifrado, se deben reordenar los bits de esta secuencia. Para ello se utiliza la función de permutación P (Tabla 5). En la secuencia de entrada, los bits se reorganizan de modo que el bit 16 se convierta en el bit 1, el bit 7 se convierta en el bit 2, y así sucesivamente.
Tabla 5: Función de permutación P
De este modo,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Para completar la descripción del algoritmo de cifrado de datos, queda presentar el algoritmo de obtención de claves de 48 bits K(i), i=1...16. En cada iteración, se utiliza un nuevo valor de clave K(i), que se calcula a partir de la clave inicial K. K es un bloque de 64 bits con ocho bits de paridad ubicados en las posiciones 8,16,24,32,40,48, 56. 64.
Para eliminar los bits de control y reorganizar el resto se utiliza la función G de la preparación inicial de la clave (Tabla 6).
Tabla 6
Matriz G de preparación inicial de claves
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
El resultado de la transformación G(K) se divide en dos bloques de 28 bits C(0) y D(0), y C(0) constará de los bits 57, 49, ..., 44, 36 de la clave. K, y D(0 ) consistirán en los bits 63, 55, ..., 12, 4 de la clave K. Después de definir C(0) y D(0), C(i) y D(i), i= 1...16, se determinan recursivamente. Para hacer esto, aplique un desplazamiento cíclico hacia la izquierda de uno o dos bits, dependiendo del número de iteración, como se muestra en la Tabla 7.
Tabla 7
Tabla de turnos para cálculo de claves
| Número de iteración | Cambio (bits) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
El valor resultante se “mezcla” nuevamente de acuerdo con la matriz H (Tabla 8).
Tabla 8: Matriz de finalización de claves H
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
La clave K(i) estará formada por los bits 14, 17, ..., 29, 32 de la secuencia C(i)D(i). De este modo:
K(i) = H(C(i)D(i))
El diagrama de bloques del algoritmo de cálculo clave se muestra en la Fig. 4.
Fig.4. Diagrama de bloques del algoritmo para calcular la clave K(i)
La restauración del texto original se realiza mediante este algoritmo, pero primero se utiliza la clave
K(15), luego K(14) y así sucesivamente. Ahora deberías entender por qué el autor recomienda insistentemente utilizar las matrices dadas. Si te vuelves rebelde, es posible que acabes con un código muy secreto, ¡pero no podrás descifrarlo tú mismo!
Modos de funcionamiento del algoritmo DES.
Para cumplir al máximo con todos los requisitos de los sistemas de cifrado comerciales, se implementan varios modos de funcionamiento del algoritmo DES. Los modos más utilizados son:
· libro de códigos electrónico (Libro de códigos electrónico) - BCE;
· cadena de bloques digitales (Cipher Block Chaining) - CBC;
· retroalimentación digital (Cipher Feedback) - CFB;
· retroalimentación externa (Output Feedback) - OFB.
En este modo, el archivo fuente M se divide en bloques de 64 bits (8 bytes cada uno): M = M(1)M(2)...M(n). Cada uno de estos bloques se cifra de forma independiente utilizando la misma clave de cifrado (Fig. 5). La principal ventaja de este algoritmo es su facilidad de implementación. La desventaja es que es relativamente débil frente a criptoanalistas expertos.
