Análisis de algoritmos para generación de cuadrados latinos aleatorios para criptografía

Abstract

Existen estructuras algebraicas aplicables en seguridad informática, como los Latin squares (cuadrados Latinos o CLs), con ciertas propiedades que los hacen muy convenientes para implementar protocolos de comunicación seguros y otras aplicaciones criptográficas como algoritmos de cifrado. En particular, son difíciles de adivinar o calcular por fuerza bruta y sirven como claves de un algoritmo de cifrado simétrico. Los CLs aleatorios de orden 256 son de particular importancia, porque permiten cifrar y decifrar cualquier caracter de la tabla ASCII, utilizando un recorrido secuencial a la manera "Off the grid" de Gibson. En un contexto de una aplicación criptográfica como las anteriormente mencionadas (protocolos o algoritmos de cifrado), se debe generar un CL cada cierta cantidad de tiempo o datos transmitidos. Esto no debe representar una sobrecarga de tiempo o recursos, es decir, que el algoritmo de generación debe ser lo más eficiente posible. Es por esto que en el presente trabajo, se analizan distintos algoritmos para generar CLs aleatorios con distribución aproximadamente uniforme. En la primera parte del trabajo, se hace una introducción a la criptografía aplicada, para revisar conceptos que constituyen el contexto de los algoritmos implementados. En el segundo capítulo, se hace una introducción a los CLs y otras estructuras, su historia y problemas relacionados, como el de generar MOLS (Mutually Orthogonal Latin Squares) o generar Sudokus. En el capítulo 3, se estudian diversos enfoques y trabajos relacionados existentes al problema de la generación de CLs aleatorios con distribución uniforme. En el capítulo 4 se desarrolla un método simple de generación secuencial con backtracking que servirá como base para el algoritmo con intercambios aleatorios desarrollado en el capítulo 5. En el capítulo 6 se muestra otro algoritmo con reemplazos. Estos dos últimos algoritmos se comparan luego con una implementación del método más aceptado para resolver el problema de generación de CLs uniformemente distribuidos, el método de Jacobson y Matthews. En el capítulo 7 se estudia una implementación de este último método y se muestra también una implementación en OpenGL que se utiliza para graficar las estructuras de datos del algoritmo de Jacobson y Matthews, la cual puede ser utilizada con fines didácticos. Por último en el capítulo 8 se analizan los resultados obtenidos, trabajo futuro y algunas conclusiones.