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

Título:

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

Autor:

Gallego Sagastume, Ignacio

Otros autores / Colaboradores:

 Pons, Claudia Fabiana; [ Director/a] 

Temas:

CRIPTOGRAFÍA; 

URL:

https://doi.org/10.35537/10915/47577,

Palabras clave:

cuadrados latinos, 

Nota de tesis:

Tesis (Maestría en Ingeniería de Software) - Universidad Nacional de La Plata. Facultad de Informática, 2014.

Extensión:

1 archivo (1,8 MB) : il. col.

Resumen:

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.

Puede solicitar más fácilmente el ejemplar con: TES 14/42

1. Introducción: elementos básicos de criptografía 
1.1. Introducción
1.2. ¿Qué son la seguridad y la privacidad en redes informáticas? 
1.3. Cifrado de los datos 
1.4. Algoritmos simétricos y de clave pública 
1.5. Protocolos criptograficos 
1.6. Tipos de ataques 
1.6.1. Ataque de solo texto cifrado 
1.6.2. Ataque de texto plano conocido 
1.6.3. Modelo de texto plano elegido 
1.6.4. Modelo de texto cifrado elegido 
1.6.5. Otros tipos de ataques 
1.7. Tipos de algoritmos y modos de uso 
1.7.1. Stream Cipher 
1.7.2. Block ciphers 
1.7.3. Combinadores de cuadrado Latino (CCL) 
1.8. ¿Porque interesa el problema de generar cuadrados Latinos de orden 256? 

 2. Cuadrados Latinos y otras estructuras 
2.1. Introducción
2.2. Algunas estructuras y sus relaciones
2.2.1. Otras estructuras
2.3. ¿Cómo surgieron los CLs y para que sirven? 
2.3.1. Diseño de experimentos 
2.3.2. Aplicaciones criptográficas
2.3.3. Entretenimiento
2.4. CLs ortogonales (MOLS) 
2.5. Historia 
2.5.1. Cuadrados Mágicos 
2.5.2. Cuadrados mágicos en la literatura Islámica 
2.5.3. Cuadrados Latinos 
2.5.4. Cuadrados Greco-Latinos 
2.6. El problema de contar los distinos CLs 
2.7. ¿Cómo puede usarse un CL aleatorio para cifrar o generar claves? 
2.8. El problema de generar CLs aleatorios 

 3. Trabajos relacionados 
3.1. Introducción 
3.2. Strube 
3.3. El enfoque de Jacobson & Matthews 
3.4. El enfoque de Koscielny 
3.5. El enfoque de Fontana
3.6. Bartak
3.7. O'Carroll y Selvi (et.al.) 
3.8. McKay 
3.9. Wanless 
3.10. Otras propuestas 

 4. Generación simple con backtracking 
4.1. Introducción
4.2. Generación de CLs simple por las 
4.3. Pseudo-código del algoritmo 
4.4. Cantidad de colisiones en el peor caso 
4.5. Cantidad de colisiones esperadas en el caso promedio
4.6. Tiempo de ejecución del algoritmo simple 
4.7. Generación usando producto de dos CLs más pequeños 

 5. Generación con intercambios 
5.1. Algoritmo simple con intercambios 
5.2. Algoritmo simple con intercambios cíclicos 
5.3. Algoritmo simple con intercambios aleatorios 
5.3.1. Resultados 
5.3.2. Pseudo-código resultante
5.3.3. Tiempo de ejecución del algoritmo
5.3.4. Test de uniformidad del método

 6. Generación con reemplazos 
6.1. Introducción 
6.2. Descripción del método
6.3. El pseudo-código del algoritmo 
6.4. Tiempo de ejecución del algoritmo 
6.5. Uniformidad de los resultados 

 7. Implementación del método de Jacobson y Matthews 
7.1. Introducción 
7.2. El método de Jacobson y Matthews
7.3. Descripción de los movimientos 
7.4. Implementación del método 
7.4.1. Primer implementación: clara pero no tan eficiente 
7.4.2. Implementación optimizada 
7.5. Generación paso a paso
7.6. Observaciones


 8. Resultados 
8.1. El proyecto Java publicado
8.1.1. Sobre la implementación del método simple 
8.1.2. Sobre la implementación del método con intercambios aleatorios 
8.1.3. Sobre la implementación del método con grafo de reemplazos 
8.1.4. Sobre la implementación del método de Jacobson y Matthews 
8.2. Tiempos de ejecución de los algoritmos
8.3. Uniformidad de los métodos
8.4. Trabajo futuro 
8.5. Conclusiones 

 Agradecimientos 

Bibliografía