AES

Y resulta que me dejaron implementar AES en criptografía.

Me llevó unas cuantas horas implementar el estándar; quiero decir, la función que recibe 128 bits y la llave de 128, 192 ó 256 bits, y los cifra (y las funciones que a su vez necesita… y las inversas para descifrar). La Wikipedia fue de gran ayuda, porque los el maldito FIPS a mí se me hizo ilegible… o mejor dicho tenía hueva y el FIPS es de 51 páginas.

Y después perdí casi dos días implementando el programa que usa esas funciones que cifran y descifran, el que recibe la llave y el archivo de entrada y el archivo de salida etc. De hecho el programa también me llevó unas cuántas horas, pero cuando lo terminé era lentísimo.

Bueno, para archivos normales estaba bien, pero cifré un archivo de 350 MB, y tardó casi media hora. 350 MB es mucho, pero que tardara media hora era ridículo.

Así que pasé este par de días haciendo pruebas y tratando de entender en dónde estaba el cuello de botella, y resultó estar en la función de MixColumns. Inicialmente había copiado tal cual el código de la Wikipedia, pero como ya tenía implementadas las operaciones sobre polinomios de séptimo grado y sobre GF(2⁸), decidí utilizarlas y hacer la multiplicación de matrices. Ciertamente el código era mucho más legible y bonito.

Y lentísimo. Como 20 veces más lento.

Entonces regresé al código de la Wikipedia, pero no tenía el de la función inversa. Así que lo que hice fue que, dado que las matrices sólo utilizaban las constantes 2, 3, 9, 11, 13 y 14, generar las tablas de multiplicar de todos los elementos del campo con esas constantes. Así la multiplicación se realiza de volada (es buscar un elemento en una tabla). También realicé otras optimizaciones obvias, y cambié el programa para que leyera el archivo de entrada en bloques de 2¹⁶ bytes (y escribiera igual el de salida).

Al final, mi programa pasó de tardar 28 minutos en cifrar un archivo de 350 MB, a tardar 2 minutos 22 segundos. Lo cual está bastante chido, si está bien que yo lo diga. Además, utiliza menos de 2KB de memoria; el único otro programa que encontré específicamente para cifrar usando AES se traba estúpidamente porque trata de cargar todo el archivo de entrada en memoria. Pero con archivos más chiquitos es casi cinco veces más rápido que el mío.

Hay todavía una optimización más que podría hacer, que tal vez le permitiría a mi programa alcanzar la velocidad del otro que encontré, pero me gusta mucho cómo quedó el código y no le veo mucho sentido hacerla. No soy ingeniero; lo que realmente me interesaba era que el programa funcionara.

Sólo que media hora por un tercio de gigabyte era ridículo. Con 2 minutos 22 segundos puedo vivir.

Actualización: Por idiota, se me olvidó ponerle optimizaciones a gcc al compilar mi programa, y quitarle los símbolos de depuración. Con optimizaciones y sin símbolos de optimización, mi programa tarda 1 minuto 33 segundos; y en mi Athlon 64 X2 tarda 33 segundos (sin usar los dos cores al mismo tiempo).