Tecnologia

Las Redes Substituci´n-Permutaci´n o o y el AES(Advanced Encryption Standard)
Jaime Guti´rrez e

1.

Introducci´n o

Los algoritmos de cifrado sim´trico m´s modernos son una combinaci´n de los cifradores e a o de substituci´n y de transposici´n o permutaci´n (ver [10], [15]), que se corresponden con o o o los conceptos de confusi´n y difusi´n introducidos por Claude Shannon. El principalobjeo o tivo de la confusi´n es esconder la relaci´n entre el texto claro, el texto cifrado y la clave o o y, el de la difusi´n trata de propagar la informaci´n real en el mensaje cifrado. La aplio o caci´n sucesiva de un cierto n´mero de tales criptosistemas simples puede dar origen a un o u sistema criptogr´fico iterado (cifrador producto) suficientemente seguro. La mayor´ de los a ıacriptosistemas se basan en diferentes capas de substituciones y permutaciones, estructura denominada SPN (Substitution-Permutation Networks), redes de substituci´n-permutaci´n o o y, en particular el AES (Advanced Encryption Standard).

2.

Producto de Criptosistemas

Otra de las innovaciones de Shannon presentada en su famoso art´ ıculo [14] de 1949 es la de combinar criptosistemas formando su producto.Esta idea ha sido de importancia fundamental en el dise˜o de los cripsotistemas de hoy en d´ como el DES(Data Encrypn ıa, tion Standard) y el AES que ser´n analizados posteriormente. En esta secci´n definimos a o formalmente este concepto. Por simplicidad en la presentaci´n, supondremos que el espacio del texto claro M y del o texto cifrado C coinciden, es decir, M = C que son denominadoscriptosistemas endom´rficos. o Sean S1 = (C, C, K1 , E1 , D1 ) y S2 = (C, C, K2 , E2 , D2 ) dos criptosistemas endom´rficos. o El criptosistema producto S1 y S2 , denotado por S1 × S2 es: S1 × S2 = (C, C, K1 × K2 , E, D). Una clave del criptosistema producto tiene la forma K = (K1 , K2 ) donde K1 ∈ K1 y K2 ∈ K2 . Las transformaciones de cifrado y descifrado est´n definidas como sigue: a EK (x) = EK2 (EK1(x)), DK (y) = DK1 (DK2 (y)).

Las Redes substituci´n-permutaci´n y el AES o o

87

Se tiene que DK (EK (x)) = x, para cada x ∈ C y para cada K ∈ K1 × K2 . A continuaci´n se muestra un ejemplo muy simple de un criptosistema producto. Defino imos el cifrador S1

r Sean r y N enteros mayores que 2. Sea M = C = ZN y sea K = {r × r matrices inversibles sobre ZN }. Para cada K ∈ K, definimos EK (x)= xK, DK (y) = yK −1 .

Ahora, definimos el cifrador S2 :

r Sean r y N enteros mayores que 2. Sea M = C = ZN y sea r K = {b = (b1 , . . . , br ) ∈ ZN }. Para cada b ∈ K, definimos EK (x) = x + b, DK (y) = y − b.

Precisamente el producto de estos dos criptosistemas es el c´digo matricial ([10], [15]). o

3.

Redes de Substituci´n-Permutaci´n o o

Una red de substituci´n-permutaci´n SPNes un cifrador iterado. La idea general de o o estos cifradores consiste en dividir el mensaje en bloques de bits, generalmente del mismo tama˜o fijo, y aplicar un n´mero Nr (rondas o vueltas) de substituciones y permutaciones n u a cada bloque. Cada cifrador requiere la funci´n ronda; la clave K, que generalmente es o una cadena aleatoria de bits y una funci´n de expansi´n EK de la clave K,proporcionando o o (1) (Nr +1) una lista de claves EK(K) = (K , . . . , K ) y que ser´ construida con un algoritmo a p´blico. u En una SPN intervienen dos permutaciones: πS , denominada S-caja, (la letra S proviene de la palabra substituci´n) y, πP la cual permuta los bits de cada bloque. Sean l y m enteros o positivos. Consideramos las permutaciones πS : {0, 1}l → {0, 1}l y πP : {1, . . . , lm} → {1,. . . , lm}.

88

Jaime Guti´rrez e

Dado el texto claro x = (x1 , . . . , xlm ), como un bloque de longitud lm, podemos interpretar x como una concatenaci´n de m cadenas de bits, cada una de ellas con l bits, o x = (x(1) , . . . , x(m) ) donde cada x(i) = (x(i−1)l+1 , . . . , xil ). Finalmente, dada la salida (K 1 , . . . , K Nr +1 ) de la funci´n expansi´n EK de la clave K ∈ o o {0,...