Siguiente: Triple DES Un nivel arriba: Data Encryption Standard (DES) Anterior: Data Encryption Standard (DES)

Presentación del método

El estándar de encriptamiento de datos, Data Encryption Standard (DES), ha sido de los más utilizados en la historia de la criptografía:

• Se desarrolló en los años 70, por IBM, principalmente.
• En 1977 se adoptó como un estándar por la Oficina Nacional de Estándares (NBS: National Bureau of Standards, en la actualidad el National Institute of Standards and Technology) del Gobierno de los EUA.
• Es de encriptamiento por bloques, con bloques de 64 bits.
• Utiliza llaves de 56 bits (dadas en 8 bytes, en cada uno de los cuales 7 bits son de la llave y el octavo es de paridad).
• Consecuentemente, el espacio de búsqueda para la llave es de tamaño 2⁵⁶ (en promedio se requiere de 2⁵⁵ pasos de búsqueda).
• El encriptamiento se hace con 16 ciclos de reiteración. En cada ciclo, los paraámetros de la función de encriptamiento dependen de los bloques de datos y de llaves, actuales y previos.
• En cada ciclo, la (sub-)llave $\mbox{\it Llave}_i$, $i=1,\ldots,16$ se construye mediante un algoritmo de preparación de llaves (key scheduling algorithm).

Dado un mensaje $\mbox{\bf m}=\mbox{\bf m}_{\mbox{\scriptsize\it Izq}}\mbox{\bf m}_{\mbox{\scriptsize\it Der}}$ de 64 bits, es decir, 8 bytes, $\mbox{\bf m}_{\mbox{\scriptsize\it Izq}},\mbox{\bf m}_{\mbox{\scriptsize\it Der}}$ de 4 bytes cada uno, se procede como sigue:

1.

Sea $\mbox{\bf m}_{\mbox{\scriptsize\it Izq}}^{(1)}\mbox{\bf m}_{\mbox{\scriptsize\it Der}}^{(1)}=\mbox{\bf m}^{(1)}= T(\mbox{\bf m})$, donde T es una permutación.

2.

Para $i=2,\ldots,16$ hágase

$$\begin{eqnarray*}\mbox{\bf m}_{\mbox{\scriptsize\it Izq}}^{(i)} &=& \mbox{\bf m}... ..._{\mbox{\scriptsize\it Der}}^{(i-1)},\mbox{\it Llave}_i\right) % \end{eqnarray*}$$

donde $\mbox{\it Llave}_i$ tiene una longitud de 48 bits.

3.

$\mbox{\bf c}= T^{-1}(\mbox{\bf m}_{\mbox{\scriptsize\it Izq}}^{(16)}\mbox{\bf m}_{\mbox{\scriptsize\it Der}}^{(16)})$.

El cálculo de $f:Z\!\!\!Z_2^{32}\times Z\!\!\!Z_2^{48} \to Z\!\!\!Z_2^{32}$, $\left(\mbox{\bf m}_{\mbox{\scriptsize\it Der}},\mbox{\it Llave}_i\right) \mapsto f\left(\mbox{\bf m}_{\mbox{\scriptsize\it Der}},\mbox{\it Llave}_i\right)$ utiliza 8 transformaciones $S_j:Z\!\!\!Z_2^{6} \to Z\!\!\!Z_2^{4}$, $j=1,\ldots,8$, llamadas S-cajas, fijadas de antemano por los estándares. f se calcula como sigue:

1.

Duplicando bits en 16 posiciones, la cadena $\mbox{\bf m}_{\mbox{\scriptsize\it Der}}$ de 32 bits se expande a una cadena $\mbox{\bf m}_{\mbox{\scriptsize\it Der}}'$ de 48 bits.

2.

Sea $\mbox{\bf r}=\mbox{\bf m}_{\mbox{\scriptsize\it Der}}'\oplus\mbox{\it Llave}_i\in Z\!\!\!Z_2^{48}$.

3.

Escríbase $\mbox{\bf r}=\left[\mbox{\bf r}_j\right]_{j=1}^8$, donde cada $\mbox{\bf r}_j\in Z\!\!\!Z_2^{6}$ es una cadena de 6 bits.

4.

Hágase $f\left(\mbox{\bf m}_{\mbox{\scriptsize\it Der}}^{(i-1)},\mbox{\it Llave}_i\righ... ...\right)\right]_{j=1}^4 P\left[S_{j}\left(\mbox{\bf r}_{j}\right)\right]_{j=5}^8$, donde P es una permutación $Z\!\!\!Z_2^{32}\to Z\!\!\!Z_2^{32}$.

En cuanto a la generación de sub-llaves, dada la llave del usuario de 56 bits, primero se transpone a sus bits, y se fracciona en dos partes de 28 bits cada una. Se va rotando a estas partes uno o dos bits a la izquierda, dependiendo del índice del ciclo, y de acuerdo con una regla fija, se compone a las partes para producir la llave $\mbox{\it Llave}_i$ de 48 bits:

1.

Sea $\mbox{\it Llave}=\left[k_i\right]_{i=1}^{64}$ una llave dada por 64 bits. Los bits k_8i, $i=1,\ldots,8$ son de paridad. Se les descarta y los restantes forman la llave de 56 bits propia del usuario.

2.

Sea $L=\mbox{\bf P}_1(\mbox{\it Llave})$ la cadena de 56 bits formada mediante la aplicación de una permutación $\mbox{\bf P}_1$, a $\mbox{\it Llave}$. Escríbasela como un par de cadenas de 28 bits, [C₀,D₀]=L.

3.

Para cada ciclo $i\leq 16$, hágase $v_i=\left\{\begin{array}{ll} 1 &\mbox{\rm si $i\in \{1,2,9,16\}$ , } \\ 2 &\mbox{\rm en otro caso. } \end{array}\right.$

En otras palabras, de acuerdo con el índice de cada ciclo se ha de rotar como se indica a continuación:

Ciclo i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Rotaciones vi	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

Sea $\gamma:Z\!\!\!Z_2^{28}\to Z\!\!\!Z_2^{28}$ la rotación consistente de ``correr un lugar hacia la izquierda''.

4.

Para cada $i=2,\ldots,16$ hágase $C_i=\gamma^{v_i}(C_{i-1})$, $D_i=\gamma^{v_i}(D_{i-1})$ y sea $\mbox{\it Llave}_i=\mbox{\bf P}_2([C_i,D_i])$ la llave de 48 bits formada mediante una permutación $\mbox{\bf P}_2$.

Para desencriptar se sigue el mismo procedimiento, pero en sentido inverso de aplicación.

Observaciones:

• Las S-cajas definen transformaciones que no son lineales ni afines. En tanto sean más complejas, la seguridad será mayor.
• Una llave es débil si $E_{\mbox{\scriptsize\it Llave}}(E_{\mbox{\scriptsize\it Llave}}(\mbox{\bf m})) = \mbox{\bf m}$.
• Propiedad de complemento. Si $\mbox{\bf c}=E_{\mbox{\scriptsize\it Llave}}(\mbox{\bf m})$ entonces $\overline{\mbox{\bf c}}=E_{\overline{\mbox{\scriptsize\it Llave}}}(\overline{\mbox{\bf m}})$.
• En la actualidad, la llave resulta pequeña.
• La implementación en hardware de las S-cajas es propiedad de IBM y no se ha publicado su diseño, el cual puede ser un elemento de vulnerabilidad.

Un posible ataque:

1.

Escójase $\mbox{\bf m}$.

2.

Obténgase los cifrados $\mbox{\bf c}_0$ de $\mbox{\bf m}$ y $\mbox{\bf c}_1$ de $\overline{\mbox{\bf m}}$, así $\mbox{\bf c}_0=E_{\mbox{\scriptsize\it Llave}}(\mbox{\bf m})$ y $\mbox{\bf c}_1=E_{\mbox{\scriptsize\it Llave}}(\overline{\mbox{\bf m}})$.

3.

Para las 2⁵⁵ llaves $\mbox{\it Llave}'$ cuyo bit más significativo es 0, revísese si $E_{\mbox{\scriptsize\it Llave}'}(\mbox{\bf m})\in \{\mbox{\bf c}_0,\mbox{\bf c}_1\}$. En tal caso, se tendrá evidencia de que $\mbox{\it Llave}=\mbox{\it Llave}'$ si $E_{\mbox{\scriptsize\it Llave}'}(\mbox{\bf m})=\mbox{\bf c}_0$ o bien de que $\mbox{\it Llave}=\overline{\mbox{\it Llave}'}$ si $E_{\mbox{\scriptsize\it Llave}'}(\mbox{\bf m})=\mbox{\bf c}_1$.

Siguiente: Triple DES Un nivel arriba: Data Encryption Standard (DES) Anterior: Data Encryption Standard (DES)