RESPUESTA A LA PREGUNTA 14405 - INTERNET

Ahí te ve información sobre lo que preguntas:

1.- Se debe empezar fastidiando.
--------------------------------

  O eso debieron pensar Joan Daemen y Vincent Rijmen al elegir el nombre para
el algoritmo que iban a presentar al NIST para ser elegido posteriormente
como AES (Advanced Encription Standar, estandar de cifrado avanzado, el
sustituto del DES de toda la vida). El caso es que estos dos daneses han
sorprendido ganando un concurso en el que se presentaban competidores de
la talla de RSA y Counterpane (Bruce Sheiner para mas señas).

  Conceptualmente el Rijndael es un cifrador de bloque que acepta tamaños
de bloque de 128, 192 y 256 bits usando claves de tambien 128, 192 o 256 bits.
Segun reconocen los propios autores, el algoritmo esta influido directamente
en otro cifrador de bloques, el Square (a saber lo que significa "estar
influido directamente" ;) ).

  Como toda buena especificacion, se debe empezar por las bases matematicas
en las que se basa el algoritmo, para despues empezar a describirlo
detalladamente. Aviso que lo que viene es algebra cuasi-elemental (en el
sentido que es el tipo de algebra que se suele dar los primeros cursos
en los que hay una asignatura de algebra) y el que avisa no es traidor ;).

  A ver, un Campo de Galois (Galios Field, GF(), en lengua yanki) de un primo
'p' se define como el conjunto formado por todas las operaciones
* y +, ambas en modulo de p (mod p). Los elementos de cualquier conjunto
pueden ser representados de muchisimas maneras, desde la notacion
matematica y aseptica de los libros de analisis numerico hasta pintando
un circulito y dibujando cuadraditos como haciamos en EGB. Sea como sea,
se da el caso de que por cada potencia de un numero primo existe un unico
campo finito, y como estamos trabajando a nivel de byte (8 bits), todas
las representaciones que hagamos de GF(2^8) son isomorficas (es decir, que
la funcion q estemos usando es biyectiva: para cada valor del conjunto
inicial existe un valor unico en el final). Aprovechando estas propiedades,
los autores decidieron usar la tipica representacion en polinomios. Asi, cada
byte es representado por su polinomio unico. P.ej:

 El byte 01010111 (87 en decimal) se corresponde con el polinomio

        x^6 + x^4 + x^2 +x + 1

  Las operaciones en estos casos son las tipicas a las que un estudiante de
electronica esta acostumbrado ;). Para la suma se hace un XOR entre los
bits de los operandos. Para la multiplicacion se hace normalmente y despues
se aplica el teorema de Euclides (usando modulo X^8 + x^4 + x^3 + x + 1)
para que el resultado siga teniendo 8 bits.

  Esto es todo lo referente a los preliminares. Podria extenderme mas en el
algebra y en las representaciones usando vectores, pero la verdad es que es
un toston y tampoco tiene mucho sentido si no vamos a hacer un criptoanalisis
serio.


 2.- Especificaciones de diseño.
---------------------------------

  En el diseño del Rijndael se ha huido de usar las usuales estructuras de
Feistel (ver algun numero anterior del ezine) que se usan en muchos otro
algoritmos. Aqui, en vez de mover simplemente los bits de una posicion a otra
sin modificarlos, como es habitual en las redes de Feistel, se hace unas
transformaciones uniformes a todos y cada uno de los bits del bloque en cada
ronda. Esto de uniformes quiere decir que cada bit se trata de la misma
manera que a todos los demas, sin importar posicion, peso ni nada parecido.

  En esto se basa todo el algoritmo: se establecen tres niveles de
transformaciones con una serie de rondas en cada uno y la salida del ultimo
nivel es la salida del algoritmo. Concretamente los niveles son:

 - Nivel de mezclado lineal: Pues eso, se usan tecnicas lineales a traves de
     muchas rondas para mezclar los bits entre si.

 - Nivel no lineal: Se basa en la utilizacion de S-Box (funciones que
     reciben un byte y te devuelven otro segun una tabla interna) con
     propiedades no lineales.

 - Nivel de suma de clave: Esto se usa en la gran mayoria de los algoritmos
     actuales. Se trata de un XOR entre la clave de ronda y los bits de los
     otros estados.

  Como es usual en otros algoritmos, el ultimo nivel se ejecuta al
principio y al final de todo, porque un simple XOR es muy rapido y aumenta
considerablemente la seguridad del sistema. Tambien es de destacar que,
como en el DES, la ultima ronda del nivel de mezclado lineal es diferente
a las anteriores. La razon para eso... pues ni idea :).


 4.- Especificaciones de implementacion.
-----------------------------------------

  Vamos ya al meollo de la cuestion.

  El algoritmo usa la representacion matricial para el bloque y la clave.
Esto no es mas que coger los bytes del bloque y ponerlos en un array
de dos dimensiones. Concretamente, y como se usan tamaños de bloques
multiplos de 32, se ha decidido que los arrays tendran cuatro filas y tantas
columnas como hagan falta para hacer una matriz rectangular. Os haria un
dibujito pero es demasiado tarde para eso ;).

  Como ya hemos dicho, el algoritmo es simplemente una serie de rondas de
transformaciones entre los bits teniendo la ultima ronda distintas a las
demas. Me vais a permitir que use la denostada tecnica del cut&paste para
poner el pseudocodigo de las operaciones ;).


   Round(State,RoundKey)
   {
     ByteSub(State);
     ShiftRow(State);
     MixColumn(State);
     AddRoundKey(State,RoundKey);
   }

lo de arriba para las rondas normales y lo siguiente para la ultima:

   FinalRound(State,RoundKey)
   {
     ByteSub(State);
     ShiftRow(State);
     AddRoundKey(State,RoundKey);
   }


  Vamos por partes:

  * ByteSub: es el nivel no lineal del asunto. Aqui se usan las S-box no
             lineales de antes. Se construye con el multiplicativo
             inverso de GF(2^8) y se aplica una transformacion a fin de
             GF(2) definida por (c&p rulez!!):

           | y0 |   | 1 00 0 11 1 1 |   | x0 |   | 1 |
           | y1 |   | 1 10 0 01 1 1 |   | x1 |   | 1 |
           | y2 |   | 1 11 0 00 1 1 |   | x2 |   | 0 |
           | y3 |   | 1 11 1 00 0 1 |   | x3 |   | 0 |
           | y4 | = | 1 11 1 10 0 0 | * | x4 | + | 0 |
           | y5 |   | 0 11 1 11 0 0 |   | x5 |   | 1 |
           | y6 |   | 0 01 1 11 1 0 |   | x6 |   | 1 |
           | y7 |   | 0 00 1 11 1 1 |   | x7 |   | 0 |

             y? es el estado final despues de la operacion y x? el inicial.


  * ShiftRow: No creo que sea necesario explicar mucho, es solamente
              mover las filas de la matriz con diferentes offset.
              Estos offset dependen de la longitud del bloque.

  * MixColumn: Un poco mas complicado. Aqui las columnas del bloque son
               representadas como los polinomios de los que hablabamos antes
               y se multiplican en modulo x^4 + 1 (00010001) con otro
               polinomio predefinido que es:

                   c(x) =  '03' x^3 + '01' x^2 + '01' x + '02'

               '03','02' y '01' son coeficientes normales. Si alguien
               encuentra una razon logica para usar esos y no otros, que me lo
               explique ;). Bueno, bromas aparte, siendo a(x) el estado
               inicial y b(x) el estado final esta operacion se podria
               definir como b(x) = c(x) XOR a(x), o sea, un simple producto
               de matrices:

              | b0 |   | 02 03 01 01 |   | a0 |
              | b1 |   | 01 02 03 01 |   | a1 |
              | b2 | = | 01 01 02 03 | * | a2 |
              | b3 |   | 03 01 01 02 |   | a3 |

               Solo se usan cuatro bits porque, como dijimos antes, el bloque
               se representa como una matriz cuadrada de 4 filas.

  * AddRoundKey: Como hemos dicho antes, esto solo es el XOR entre los bits
                 del bloque y la clave de esta ronda. Mas abajo viene como
                 sacar dicha clave.

 
  El tratamiento de la clave se basa en 2 componentes: expansion de la clave
de cifrado y la seleccion de la clave de ronda. De manera simple se puede
explicar esto como:

 1.- El numero total de bits de la clave de ronda es igual al numero de bits
     del bloque multiplicado por el numero de rondas mas 1. Por ejemplo, para
     un bloqe de 128 bits y 10 rondas, se necesitan 128 * 11 = 1408 bits.

 2.- Expansion de la clave de cifrado.

 3.- La seleccion de la clave de cada ronda es simple: se coge la clave
     expandida y se toman N bits (con N siendo la longitud de las filas del
     bloque), para la segunda se toman los siguientes N bits y asi
     sucesivamente.

  Como la expansion de la clave es simplemente una funcion matematica, no
me voy a poner a explicarla. Simplemente la pego ahi abajo para el que tenga
interes en seguirla (y para hacer bulto, para que negarlo ;) ):

 Si el numero de columnas de la matriz de la clave es <= 6:

 KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)])
 {
   for(i = 0; i < Nk; i++)
      W[i] = (Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);
   for(i = Nk; i < Nb * (Nr + 1); i++)
   {
      temp = W[i - 1];
      if (i % Nk == 0)
      temp = SubByte(RotByte(temp)) ^Rcon[i / Nk];
      W[i] = W[i - Nk] ^temp;
   }
 }

 Si es mayor:

 KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)])
 {
   for(i = 0; i < Nk; i++)
      W[i] = (key[4*i],key[4*i+1],key[4*i+2],key[4*i+3]);
   for(i = Nk; i < Nb * (Nr + 1); i++)
   {
      temp = W[i - 1];
      if (i % Nk == 0)
         temp = SubByte(RotByte(temp)) ^Rcon[i / Nk];
      else if (i % Nk == 4)
         temp = SubByte(temp);
      W[i] = W[i - Nk] ^temp;
   }
 }



Dabiz Spuch Calvar
dabizspuch@yahoo.es