Criptoanálisis lineal para tontos. Estándar de cifrado de datos (DES)

Han pasado más de 30 años desde la adopción del algoritmo DES como estándar de cifrado en Estados Unidos. DES es un algoritmo de cifrado con la historia más rica e interesante.

Historia de la creación del algoritmo.

Uno de los criptólogos más famosos del mundo, Bruce Schneier, en su famoso libro "Criptografía aplicada" describió los problemas de los usuarios de herramientas de seguridad de la información a principios de los años 70. Siglo XX (por supuesto, estamos hablando de usuarios al otro lado del Telón de Acero):

No existía un estándar generalmente aceptado para el cifrado de datos ni simplemente algoritmos de seguridad de la información ampliamente utilizados, por lo que la compatibilidad entre diferentes herramientas de cifrado de software o hardware estaba fuera de discusión;

Casi cualquier herramienta de cifrado era una "caja negra" con contenidos poco claros: qué algoritmo de cifrado se utiliza, qué tan fuerte es criptográficamente, si se implementa correctamente, si las claves de cifrado se crean, almacenan y utilizan correctamente, si la herramienta contiene información no documentada. capacidades insertadas por los desarrolladores, etc.: toda esta información muy importante era inaccesible para la gran mayoría de los compradores de fondos criptográficos.

La Oficina Nacional de Normas (NBS) de EE.UU. estaba preocupada por este problema. Como resultado, en 1973 se anunció el primer concurso abierto para un estándar de cifrado. NBS estaba dispuesta a examinar algoritmos candidatos que cumplieran con los siguientes criterios para seleccionar un estándar:

El algoritmo debe ser criptográficamente sólido;

El algoritmo debe ser rápido;

La estructura del algoritmo debe ser clara y precisa;

La solidez del cifrado debería depender únicamente de la clave; el algoritmo en sí no debería ser secreto;

El algoritmo debería ser fácilmente aplicable para diversos fines;

El algoritmo debe implementarse fácilmente en hardware utilizando componentes de hardware existentes.

Se suponía que las organizaciones o especialistas interesados ​​enviarían al BNE especificaciones detalladas de los algoritmos suficientes para su implementación, es decir, sin "puntos ciegos". También se suponía que el algoritmo sería certificado por la NBS para uso general y que se le eliminarían todas las restricciones de patentes y exportaciones, por lo que dicho estándar tendría que resolver todos los problemas de compatibilidad de cifrado. Además, NBS asumió la función de certificar herramientas de cifrado, es decir, las "cajas negras" deberían haber pasado a ser cosa del pasado.

De hecho, solo había un algoritmo candidato: era el algoritmo de cifrado Lucifer desarrollado por ShM. (ver sección 3.31). En el transcurso de dos años, se perfeccionó el algoritmo:

En primer lugar, la NBS, junto con la Agencia de Seguridad Nacional (NSA, National Security Agency) de Estados Unidos, llevó a cabo un análisis exhaustivo del algoritmo, que dio como resultado su revisión bastante significativa;

En segundo lugar, se tuvieron en cuenta los comentarios y críticas de todas las organizaciones y personas interesadas.

Como resultado de los esfuerzos conjuntos de IBM, NBS y la NSA, en enero de 1977 se publicó DES como un estándar estadounidense (la última versión de este estándar se encuentra en el documento) para un algoritmo para cifrar datos (excepto información altamente confidencial). El algoritmo DES fue patentado por YuM, pero NBS recibió, de hecho, una licencia gratuita e ilimitada para utilizar este algoritmo. Un nombre alternativo, pero menos utilizado, para el algoritmo es DEA (Algoritmo de cifrado de datos).

Principales características y estructura del algoritmo.

El algoritmo DES cifra información en bloques de 64 bits utilizando una clave de cifrado de 64 bits que utiliza sólo 56 bits (el procedimiento de expansión de clave se describe en detalle a continuación).

El cifrado de información se realiza de la siguiente manera (Fig. 3.56):

1. Se realiza una permutación inicial en un bloque de datos de 64 bits según la tabla. 3.16.

Tabla 3.16

La tabla se interpreta de la siguiente manera: el valor del bit de entrada 58 (en adelante todos los bits se numeran de izquierda a derecha, comenzando desde 1) se coloca en el bit de salida 1, el valor del bit 50 se coloca en el bit 2, etc.

2. El resultado de la operación anterior se divide en 2 subbloques de 32 bits (por

arroz. 3.56 marcado Un 0 y B 0), sobre el cual se realizan 16 rondas

las siguientes transformaciones:

Como se mencionó anteriormente, de una clave de cifrado de 64 bits, el algoritmo DES utiliza sólo 56 bits. Cada octavo bit se descarta y no se utiliza de ninguna manera en el algoritmo, y el uso de los bits restantes de la clave de cifrado en las implementaciones del algoritmo DES no está limitado de ninguna manera por el estándar. El procedimiento para extraer los 56 bits significativos de una clave de 64 bits en la Fig. 3.59 se designa como E. Además de la extracción, este procedimiento también realiza una reorganización de los bits clave según la Tabla. 3.19 y 3.20.

Tabla 3.19

Tabla 3.20

Como resultado de la permutación, se forman dos valores de 28 bits C y D. La Tabla 3.19 define la selección de bits clave para C, tabla. 3.20 - para D.

Luego se realizan 16 rondas de transformaciones, cada una de las cuales produce una de las claves de ronda Kt. En cada ronda del procedimiento de ampliación de claves se realizan las siguientes acciones:

1. Valores actuales de C y D desplazado cíclicamente hacia la izquierda un número variable de bits pag. Para las rondas 1, 2, 9 y 16 norte= 1, en las rondas restantes se realiza un desplazamiento cíclico de 2 bits.

2. C y D se combinan en un valor de 56 bits, al que se aplica la permutación de compresión CP, cuyo resultado es una clave redonda K (. La permutación de compresión se realiza de acuerdo con la Tabla 3.21.

Tabla 3.21

Al descifrar datos, puede utilizar el mismo procedimiento de expansión de claves, pero aplique las claves redondas en orden inverso. Hay otra opción: en cada ronda del procedimiento de expansión de claves, en lugar de un desplazamiento cíclico hacia la izquierda, realice un desplazamiento cíclico hacia la derecha de n bits, donde rc' = 0 para la primera ronda, u' = 1 para las rondas 2, 9, 16 y n = 2 para las rondas restantes. Este procedimiento de expansión de claves proporcionará inmediatamente las claves redondas necesarias para el descifrado.

Vale la pena decir que la capacidad de realizar la expansión de la clave "sobre la marcha" (especialmente si esta posibilidad existe tanto durante el cifrado como durante el descifrado) se considera una ventaja de los algoritmos de cifrado, ya que en este caso la expansión de la clave se puede realizar en paralelo con el cifrado. y no desperdiciar memoria almacenando las claves de otras rondas distintas a la actual.

• 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 que se encuentra 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.

Consideremos la solución a estos problemas utilizando el cifrado DES como ejemplo.

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:

1. Permutación de bits inicial. En esta etapa, los bits del bloque de entrada se mezclan en un orden determinado.
2. 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.
3. 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:

1. 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.
2. El bloque resultante se suma a la clave redonda K i .
3. El resultado del paso anterior se divide en 8 bloques de 6 bits cada uno.
4. 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.
5. 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 los 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

Aquí tienes una forma de ampliar el ataque y obtener 6 bits de la primera ronda a la vez.
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 abrir 12 bits de una clave DES de 16 rondas, se necesitarán alrededor de 2 44 pares de textos. Los 44 bits restantes de la clave se abren mediante fuerza bruta normal.

El estándar DES está diseñado para proteger contra el acceso no autorizado a información confidencial pero no clasificada en organizaciones comerciales y gubernamentales de EE. UU. El algoritmo subyacente al estándar se difundió con bastante rapidez y ya en 1980 fue aprobado por el Instituto Nacional de Estándares y Tecnología de EE. UU. A partir de este momento, DES se convierte en un estándar no sólo de nombre, sino también de hecho. Aparecen software y microcomputadoras especializadas que están diseñadas para cifrar y descifrar información en redes de transmisión de datos.

Hasta la fecha, DES es el algoritmo más común utilizado en los sistemas de seguridad de la información comercial. Además, la implementación del algoritmo DES en tales sistemas se convierte en un signo de buena forma.

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;

· la relativa simplicidad del algoritmo garantiza una alta velocidad de procesamiento de la información;

· estabilidad suficientemente alta del algoritmo.

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 bits de un bloque de 64 bits, dieciséis ciclos de cifrado y, finalmente, una permutación inversa de bits (Figura 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.

Arroz. 2.

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 resulta en: 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 reorganizan 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 de acuerdo con 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 de 64 bits L(0) R(0).

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.

Arroz. 3.

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 está determinada por 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 están definidas en la tabla. 4.

Tabla 4

a la mesa 4. Se requieren aclaraciones adicionales. 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 una 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 claves K. Después de determinar 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)

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 de claves se muestra en la Fig. 4.

Arroz. 4.

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!

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. 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 de 48 bits resultante se introduce luego 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.

A continuación, 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 utiliza 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.

Anotación: Uno de los sistemas criptográficos de clave privada más famosos es el DES (Estándar de cifrado de datos). Este sistema fue el primero en recibir el estatus de estándar estatal en el campo del cifrado de datos. Y aunque el antiguo estándar americano DES ha perdido su estatus oficial, este algoritmo todavía merece atención en el estudio de la criptografía. Esta conferencia también explica qué es el doble DES, un ataque de encuentro en el medio, y cómo mitigarlo. Esta conferencia también analiza brevemente el nuevo estándar estadounidense para cifrados de bloques, el algoritmo Rijndael.

Propósito de la conferencia: introduce al estudiante en la información básica sobre el algoritmo de cifrado DES.

Lo esencial

Uno de los sistemas criptográficos de clave privada más famosos es DES – Estándar de cifrado de datos. Este sistema fue el primero en recibir el estatus de estándar estatal en el campo del cifrado de datos. Fue desarrollado por especialistas de IBM y entró en vigor en Estados Unidos en 1977. Algoritmo DES ampliamente utilizado para almacenar y transmitir datos entre varios sistemas informáticos; en sistemas postales, sistemas de dibujo electrónico e intercambio electrónico información comercial. Estándar DES Fue implementado tanto en software como en hardware. Empresas de diferentes países han lanzado la producción en masa de dispositivos digitales utilizando DES para el cifrado de datos. Todos los dispositivos se sometieron a una certificación obligatoria para el cumplimiento de la norma.

A pesar de que este sistema no tiene el estatus de estándar gubernamental desde hace algún tiempo, todavía se usa ampliamente y merece atención al estudiar cifrados en bloque con clave privada.

Longitud de clave en el algoritmo DES es de 56 bits. Es con este hecho que la principal controversia respecto a la capacidad de DES resistir varios ataques. Como usted sabe, cualquier cifrado de bloque con una clave privada se puede descifrar probando todas las combinaciones de claves posibles. Con una longitud de clave de 56 bits, son posibles 2 56 claves diferentes. Si una computadora busca entre 1.000.000 de claves en un segundo (lo que es aproximadamente igual a 2.20), entonces le tomará 2.36 segundos o un poco más de dos mil años buscar entre las 2.56 claves, lo cual, por supuesto, es inaceptable para atacantes.

Sin embargo, son posibles sistemas informáticos más caros y más rápidos que ordenador personal. Por ejemplo, si es posible combinar un millón de procesadores para cálculos paralelos, entonces el tiempo máximo de selección de clave se reduce a aproximadamente 18 horas. Este tiempo no es demasiado largo y un criptoanalista equipado con un equipo tan costoso puede descifrar fácilmente datos cifrados con DES en un período de tiempo razonable.

Al mismo tiempo, se puede observar que el sistema DES Se puede utilizar en aplicaciones pequeñas y medianas para cifrar datos de poco valor. Para cifrar datos de importancia nacional o que tengan un valor comercial significativo, el sistema DES Por supuesto, no debería utilizarse en la actualidad. En 2001, después de una competencia especialmente anunciada, se adoptó en los Estados Unidos un nuevo estándar de cifrado en bloque, llamado AES (Estándar de cifrado avanzado), que se basó en el cifrado Rijndael, desarrollado por especialistas belgas. Este cifrado se analiza al final de la conferencia.

Parámetros básicos DES: tamaño de bloque 64 bits, longitud de clave 56 bits, número de rondas – 16. DES es una red Feishtel clásica con dos sucursales. El algoritmo convierte un bloque de datos de entrada de 64 bits en un bloque de salida de 64 bits en varias rondas. Estándar DES construido sobre el uso combinado de permutación, sustitución y gamma. Los datos cifrados deben estar en formato binario.

Cifrado

Estructura general DES mostrado en la Fig.

1. 4.1. El proceso de cifrar cada bloque de datos sin procesar de 64 bits se puede dividir en tres etapas:
2. preparación inicial de un bloque de datos;
3. 16 rondas del "ciclo principal";

procesamiento final de un bloque de datos. En la primera etapa se lleva a cabo permutación inicial

Bloque de texto fuente de 64 bits, durante el cual los bits se reorganizan de una manera específica. En la siguiente etapa (principal), el bloque se divide en dos partes (ramas) de 32 bits cada una. La rama derecha se transforma usando alguna función F y la correspondiente, obtenido de la clave de cifrado principal mediante un algoritmo de conversión de clave especial. Luego se intercambian datos entre las ramas izquierda y derecha del bloque. Esto se repite en un ciclo 16 veces.

Finalmente, la tercera etapa reorganiza el resultado obtenido después de dieciséis pasos del bucle principal. Esta permutación es la inversa de la permutación inicial.

Arroz. 4.1.

Echemos un vistazo más de cerca a todas las etapas de la conversión criptográfica según el estándar. DES.

En la primera etapa, el bloque de datos fuente de 64 bits sufre una permutación inicial. En la literatura, esta operación a veces se denomina "blanqueamiento". Durante la permutación inicial, los bits del bloque de datos se reorganizan de cierta manera. Esta operación añade algo de "caótico" al mensaje original, reduciendo la posibilidad de utilizar criptoanálisis mediante métodos estadísticos.

Simultáneamente con la permutación inicial del bloque de datos, se realiza una permutación inicial de los 56 bits de la clave. De la Fig.

4.1. Se puede observar que en cada una de las rondas se utiliza la correspondiente clave parcial K i de 48 bits. Las claves K i se obtienen mediante un algoritmo específico, utilizando cada bit de la clave inicial varias veces. En cada ronda, la clave de 56 bits se divide en dos mitades de 28 bits. A continuación, las mitades se desplazan uno o dos bits hacia la izquierda, según el número redondo. Después del desplazamiento, 48 de los 56 bits se seleccionan de cierta manera. Dado que esto no sólo selecciona un subconjunto de bits, sino que también cambia su orden, esta operación se denomina "permutación por compresión". Su resultado es un conjunto de 48 bits. En promedio, cada bit de la clave original de 56 bits se usa en 14 de las 16 subclaves, aunque no todos los bits se usan la misma cantidad de veces.

A continuación se realiza el ciclo de transformación principal, organizado mediante la red Feishtel y que consta de 16 rondas idénticas. En este caso, en cada ronda (Fig. 4.2) se obtiene un valor intermedio de 64 bits, que luego se procesa en la siguiente ronda.

Arroz. 4.2.

Primero, el lado derecho del bloque Ri se expande a 48 bits usando una tabla que especifica la permutación más la expansión en 16 bits. Esta operación hace coincidir el tamaño de la mitad derecha con el tamaño de la clave para realizar una operación XOR. Además, al realizar esta operación, la dependencia de todos los bits del resultado de los bits de los datos de origen y la clave aumenta más rápidamente (esto se denomina "efecto avalancha"). Cuanto más fuerte sea el efecto de avalancha al utilizar uno u otro algoritmo de cifrado, mejor.

Después de realizar la permutación de expansión, el valor de 48 bits resultante se aplica mediante operación XOR con la subclave K i de 48 bits. Luego, el valor resultante de 48 bits se envía a la entrada del bloque de sustitución S (del inglés. Sustitución - sustitución), resultado que es un valor de 32 bits. La sustitución se realiza en ocho bloques de sustitución u ocho cajas S. Al hacer esto, DES parece bastante complicado en el papel, ¡y mucho menos su implementación de software! Desarrollar un programa que funcione correcta y óptimamente de acuerdo con DES Probablemente sólo los programadores experimentados puedan hacerlo. Surgen algunas dificultades al implementar software, por ejemplo, permutación inicial o permutación con expansión. Estas dificultades están relacionadas con lo que originalmente se planeó implementar. DES hardware solamente. Todas las operaciones utilizadas en el estándar se realizan fácilmente mediante unidades de hardware y no surgen dificultades de implementación. Sin embargo, algún tiempo después de la publicación del estándar, los desarrolladores de software decidieron no quedarse de brazos cruzados y emprender también la creación de sistemas de cifrado. En el futuro DES Se implementó tanto en hardware como en software.