FIUBA: Crypto Learning Tools Wiki

UBATIC: Herramientas de aprensizaje de algoritmos criptográficos

Brought to you by: alexmantaut, marceloruizba, matorchio, nicolasjavierp, xwing-alliance

IDEA

Authors:

Attachments

IDEA.png (43498 bytes)

IDEA_Cifrado_Ronda0.png (31796 bytes)

IDEA_Cifrado_RondaX.png (55689 bytes)

IDEA_Cifrado_Ronda_Final.png (34962 bytes)

Introducción

IDEA es un cifrador de clave simétrica por bloques de dominio público. El mismo fue diseñado por Xuejia Lai yJames L. Massey para Escuela Politécnica Federal de Zúrich y su primera publicación data del año 1991. El algoritmo es una versión mejorada del crifrado PES (Proposed encryption standard).

El cifrador opera sobre bloques de 64 bits (estos bloques son la información que se va a cifrar), cifrando el contenido usando una clave de 128 bits. La principal característica de este algoritmo es que hace uso de operaciones de tres grupos algebraicos distintos. Otra característica especial es que las operaciones tanto para cifrado como para descifrado son las mismas, solo cambiando la forma de uso de la clave (más adelante se revisará este punto).

Pasos del algoritmo

Algoritmo de cifrado

Como se mencionó, el algoritmo hace uso de tres operaciones de grupos algebraicos distintos. Las mismas son las siguientes:

XOR bit a bit de bloques de 16-bits
Suma en módulo 2¹⁶ de dos enteros de 16-bits
Multiplicación en módulo 2¹⁶+1 de dos enteros de 16-bits, ajustandose a al valor 2¹⁶ a los valores de entrada igual a cero y llevando a cero los resultados del producto que den 2¹⁶

Mediante estas tres operaciones, el algoritmo se ejecuta en 8 rondas iguales más una ronda final especial (también denominada “media ronda”) como se muestra en la siguiente figura:

idea

Las entrada con notación S_N^(M) hacen referencia a la sub-clave N de la ronda M, cuya longitud es de 16 bits.

Generación de sub-claves

En el gráfico anterior se observa que el algoritmo utiliza 6 sub-claves por ronda más 4 claves en la ronda final. Operando sobre la cantidad de claves podes mos ver que la cantidad de claves que va a hacer uso el algoritmo es de 52 (8 x 6 + 4 x 1).

El proceso para obtener las 52 claves se puede resumir en los siguientes pasos:

Se subdivide la clave original (de 128 bits) en grupos de 16 bits. De la primera subdivisión se obtienen las 6 sub-claves utilizadas en la primera ronda más las claves S₁⁽²⁾ y S₂⁽²⁾.
Para obtener las claves faltantes para la segunda ronda, las mismas se obtienen al realizar un shift a izquierda de 25 bits de la clave original. De la nueva clave de 128 bits que queda formada, se procede a extraer las cuatro claves faltantes para la segunda ronda (las otras 4 claves sobrantes se utilizan de igual forma que se utilizaron las sobrantes del primer paso).
El punto anterior se repite hasta bien haber obtenido las 52 claves que requiere el algoritmo (en el último shift van a sobrar 4 claves, estás no se utilizan y son descartadas)

Descifrado

El algoritmo necesario para realizar el descifrado es exactamente el mismo que se requirió para el cifrado. Los cambios que se producen solo están reflejados en las claves utilizadas.

Si las claves requeridas para cifrar hubiesen sido las siguientes:

N° Ronda	Sub claves
Ronda 1	S₁⁽¹⁾ S₂⁽¹⁾ S₃⁽¹⁾ S₄⁽¹⁾ S₅⁽¹⁾ S₆⁽¹⁾
Ronda 2	S₁⁽²⁾ S₂⁽²⁾ S₃⁽²⁾ S₄⁽²⁾ S₅⁽²⁾ S₆⁽²⁾
Ronda 3	S₁⁽³⁾ S₂⁽³⁾ S₃⁽³⁾ S₄⁽³⁾ S₅⁽³⁾ S₆⁽³⁾
Ronda 4	S₁⁽⁴⁾ S₂⁽⁴⁾ S₃⁽⁴⁾ S₄⁽⁴⁾ S₅⁽⁴⁾ S₆⁽⁴⁾
Ronda 5	S₁⁽⁵⁾ S₂⁽⁵⁾ S₃⁽⁵⁾ S₄⁽⁵⁾ S₅⁽⁵⁾ S₆⁽⁵⁾
Ronda 6	S₁⁽⁶⁾ S₂⁽⁶⁾ S₃⁽⁶⁾ S₄⁽⁶⁾ S₅⁽⁶⁾ S₆⁽⁶⁾
Ronda 7	S₁⁽⁷⁾ S₂⁽⁷⁾ S₃⁽⁷⁾ S₄⁽⁷⁾ S₅⁽⁷⁾ S₆⁽⁷⁾
Ronda 8	S₁⁽⁸⁾ S₂⁽⁸⁾ S₃⁽⁸⁾ S₄⁽⁸⁾ S₅⁽⁸⁾ S₆⁽⁸⁾
Ronda 9	S₁⁽⁹⁾ S₂⁽⁹⁾ S₃⁽⁹⁾ S₄⁽⁹⁾

Entonces, las requeridas para el descifrado serían las siguientes:

N° Ronda	Sub claves
Ronda 1	(S₁⁽⁹⁾)^-1 -S₂⁽⁹⁾ -S₃⁽⁹⁾ (S₄⁽⁹⁾)^-1 S₅⁽⁸⁾ S₆⁽⁸⁾
Ronda 2	(S₁⁽⁸⁾)^-1 -S₂⁽⁸⁾ -S₃⁽⁸⁾ (S₄⁽⁸⁾)^-1 S₅⁽⁷⁾ S₆⁽⁷⁾
Ronda 3	(S₁⁽⁷⁾)^-1 -S₂⁽⁷⁾ -S₃⁽⁷⁾ (S₄⁽⁷⁾)^-1 S₅⁽⁶⁾ S₆⁽⁶⁾
Ronda 4	(S₁⁽⁶⁾)^-1 -S₂⁽⁶⁾ -S₃⁽⁶⁾ (S₄⁽⁶⁾)^-1 S₅⁽⁵⁾ S₆⁽⁵⁾
Ronda 5	(S₁⁽⁵⁾)^-1 -S₂⁽⁵⁾ -S₃⁽⁵⁾ (S₄⁽⁵⁾)^-1 S₅⁽⁴⁾ S₆⁽⁴⁾
Ronda 6	(S₁⁽⁴⁾)^-1 -S₂⁽⁴⁾ -S₃⁽⁴⁾ (S₄⁽⁴⁾)^-1 S₅⁽²⁾ S₆⁽³⁾
Ronda 7	(S₁⁽³⁾)^-1 -S₂⁽³⁾ -S₃⁽³⁾ (S₄⁽³⁾)^-1 S₅⁽²⁾ S₆⁽²⁾
Ronda 8	(S₁⁽²⁾)-1 -S₂⁽²⁾ -S₃⁽²⁾ (S₄⁽²⁾)^-1 S₅⁽¹⁾ S₆⁽¹⁾
Ronda 9	(S₁⁽¹⁾)^-1 S₂⁽¹⁾ S₃⁽¹⁾ (S₄⁽⁹⁾)^-1

En donde:

“-S_N^(M)” es el complemente a 2 del valor de la sub-clave al momento de cifrar
“(S_N^(M))^-1“ es la inversa en complementa a 2¹⁶+1 de dicho número. Para obtener este valor se puede hacer uso del algoritmo euclidiano extendido.

Cálculo del inverso

Como se mencionó en el punto anterior, para lograr revertir las operaciones de multiplicación se requiere del uso del inverso multiplicativo del número utilizado inicialmente. Para tal fin, se hace uso del algoritmo euclidiano extendido. Sin embargo, antes de dar inicio a la explicación de dicho algoritmo, vamos a aclarar algunos puntos a tener en cuenta en el cálculo de inversos multiplicativos de números en módulo N.

Cuando definimos el inverso multiplicativo de un número "a" en módulo "p", en realidad estamos buscando un número "x" que cumpla:

a.x = 1 mod p

O sea, el inverso genera un número que es múltiplo de "p" sumado una unidad. Por ejemplo:

tomamos p = 17 y a = 2

a.x = 1 mod 17 = (17.n) + 1 // "n" es un número natural

Para este caso, podemos ver que x = 9 es solución. A su vez, tomando este valor de x e incrementando o decrementando el valor del módulo podemos obtener nuevos valores que funcionan como el inverso de "a". Sin embargo, x = 9 es el único inverso multiplicativo dentro del módulo p.

Según la teoría de los campos de galois (teoría que excede al presente resumen), en un conjunto de números enteros en los que esté definida las operaciones de suma y multiplicación modular, el mismo podrá lograr que exista la inversa multiplicativa de sus elementos (excepto el 0, claro está) si el módulo es en base a una potencia de un número primo.

Volviendo a las operaciones modulares de IDEA, podemos ver que el algoritmo realiza multiplicacione en módulo 2¹⁶+1, el cual es un número primo (nota de color: también es un número de Fermat) y, dado lo mencionado para los campos de galois, sabemos que todos los números menores a 2¹⁶+1 poseen un número que es su inverso multiplicativo dentro del módulo (lo cual es muy importante!! ya que nos garantiza que exista la inversa de todos los números que representamos con 16 bits, dándo una operación reversible ideal para un algoritmo de cifrado).

Entonces, pudimos ver que todos los números en módulo 2¹⁶+1 poseen un inverso multiplicativo, a excepción del número cero, el cual no puede tenerlo. Si el algoritmo no hiciera ninguna aclaración con el número cero, entonces cualquier multiplicación que involucrara a este valor desembocaría en la imposibilidad de revertir la operación. Como era de esperar, IDEA tomó en cuenta esta limitación y le asignó un inverso multiplicativo "virtual" al cero. Este inverso multiplicativo es el número 2¹⁶, lo cual no genera problema alguno con la representación numerica utilizada, ya que los datos de entrada sus valores de 16 bits (i.e. se puede representar hasta el valor 2¹⁶-1).

Algoritmo de Euclides extendido

Pseudocódigo:

EXTENDED EUCLIDES(m, b)

# (A1, A2, A3)=(1, 0, m); 
# (B1, B2, B3)=(0, 1, b);
# if (B3 == 0)
#    return A3 = gcd(m, b); //no inverse    
# if (B3 == 1) 
#    return B3 = gcd(m, b); B2 = b^–1 mod m
# Q = A3 div B3
# (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
# (A1, A2, A3)=(B1, B2, B3)
# (B1, B2, B3)=(T1, T2, T3)
# goto 2

Ejemplo de pantalla

Claves

claves

Rondas

rondas

Ronda final

final

Wiki: Home