La Hormiga de Langton y la Encriptación de Imágenes

Autores: Andrés Romero-Arellano, Dr. Ernesto Moya-Albor, Dr. Jorge Brieva.

Correo Electrónico: 0228652@up.edu.mx, emoya@up.edu.mx, jbrieva@up.edu.mx

Institución: Universidad Panamericana. Facultad de Ingeniería. Augusto Rodin 498, Ciudad de México, 03920, México.

Palabras Clave: #Encriptación de Imágenes, #Hormiga de Langton, #Autómatas Celulares, #Imágenes Médicas, #Seguridad

La encriptación de imágenes es un proceso por el que se transforma una imagen para que su contenido sea ilegible por una persona sin acceso a ella, lo cual es de relevancia cuando se transmiten imágenes con información personal o confidencial. Esto se logra mediante métodos criptográficos, entre los que se incluye el uso de autómatas celulares. Por ejemplo, si imaginamos una cuadrícula parecida a un tablero de ajedrez, donde cada casilla, llamada célula, puede estar en un estado previamente definido (encendido o apagado) y cada célula tiene como vecinos a las células que están al lado o en diagonal a ella. Entonces un autómata celular consiste en un conjunto de reglas que determina cómo una célula cambia de estado a lo largo del tiempo según el estado de ella misma o de sus células vecinas. La hormiga de Langton es un autómata celular inventado en 1986 por Christopher Langton [1], la cual simula el caminar de una hormiga artificial. Se puede pensar como un juego con reglas sencillas que se desarrolla en una cuadrícula de extensión infinita compuesta por cuadrados, los cuales pueden tener dos colores: blanco y negro. Empezamos colocando una hormiga imaginaria en algún cuadro de la cuadrícula, la cual puede iniciar viendo al norte, este, sur u oeste, y caminará a través de la cuadrícula siguiendo dos reglas sencillas:

Si la hormiga se encuentra en un cuadrado negro, rotará 90 grados en sentido de las manecillas del reloj, cambiará el color del cuadrado a blanco y avanzará al cuadrado frente a ella.

Si está en un cuadrado blanco, rotará 90 grados contrarreloj, cambiará el color del cuadrado a negro y avanzará al cuadrado frente a ella.

En la Figura 1 se ilustran los primeros tres pasos de una hormiga de Langton.

Figura. 1. Los primeros 3 pasos de la hormiga de Langton sobre una cuadrícula negra con una celda blanca inicial.

Lo más común es colocar a la hormiga sobre una cuadrícula con todas sus casillas pintadas de negro. Si se deja caminar a la hormiga en esta configuración inicial, exhibe rápidamente un comportamiento caótico y desordenado, pero sorprendentemente, después de algunos miles de pasos se estabiliza y acaba atrapada en un ciclo apodado “la autopista”, como se ve en la Figura 2.

Figura 2. La hormiga de Langton (resaltada en naranja) después de 11,538 iteraciones mostrando el ciclo apodado “la autopista”.

Se ha probado otras configuraciones iniciales para la hormiga, cambiando una cantidad finita de casillas de negro a blanco, y hasta ahora no se ha encontrado ninguna configuración en la que la hormiga no llegue eventualmente al ciclo de “la autopista”.

De manera sorprendente, si se detiene a la hormiga en algún punto del proceso, se le da media vuelta, y se le deja caminar la misma cantidad de pasos que llevaba caminados, la hormiga revertirá todas las modificaciones que le hizo a la cuadrícula, por lo que es un proceso reversible.

Desde su invención, la hormiga de Langton se había mantenido principalmente como una “curiosidad matemática” sin aplicaciones directas: un juego inútil pero interesante al que se han descubierto patrones inesperados [2], pero en años recientes se le ha encontrado una aplicación en la encriptación de imágenes digitales.

Una imagen digital es una cuadrícula de pixeles compuesta por tres canales de color (rojo, verde y azul). Cada píxel en cada canal se representa con un número finito de bits, por ejemplo, usando 8 bits la menor intensidad es 0 y la mayor 255. En la Figura 3 se muestra este concepto en una imagen muy sencilla, pero este es el mismo proceso por el que una pantalla LED puede mostrar cualquier imagen. 

Figura 3. Descomposición de una imagen digital en sus canales rojo, verde y azul.

Los algoritmos de encriptación de imágenes alteran los valores de los píxeles para ocultar la información visual de la imagen, siguiendo alguna regla que pueda revertirse para recuperar la imagen original a través de una clave secreta. Más recientemente, se planteó la idea de aprovechar indirectamente el comportamiento caótico de la hormiga de Langton para generar números aleatorios que se usarían para revolver los píxeles de una imagen y encriptarla [3]. 

Pero en 2021, se desarrolló un método para usar la hormiga de Langton de manera directa en la encriptación de imágenes, colocando a la hormiga sobre los píxeles de la imagen para que estos se alteren con el caminar de la hormiga [4].

Debido a que la hormiga de Langton está situada originalmente en una cuadrícula con cuadrados con dos colores posibles, en [4] se modificó el planteamiento de la hormiga de la Figura 1 para adaptarla a una cuadrícula con más de dos estados. En particular, se coloca a la hormiga sobre el canal rojo de una imagen. La hormiga se seguirá moviendo mediante las dos reglas mencionadas anteriormente, pero modificadas ligeramente. En lugar de revisar si un cuadrado es negro o blanco, la hormiga analizará si el cuadrado en el que está actualmente tiene un valor par o impar. Siguiendo estas dos reglas:

Si la hormiga se encuentra en un cuadrado par, rotará 90 grados en sentido de las manecillas del reloj, sumará, un número entero impar definido con anterioridad, al valor del cuadrado (transformándolo en impar) y avanzará al cuadrado frente a ella.

Si está en un cuadrado impar, rotará 90 grados contrarreloj, sumará el mismo número entero impar al valor del cuadrado (transformándolo en par) y avanzará al cuadrado frente a ella.

Debido a que sólo hay 256 valores posibles de intensidad para el canal rojo, es posible que algún cuadrado aumente en valor a un valor superior al permitido. Si esto sucede, se restará 255 al valor para continuar desde el inicio, generando un ciclo. Otro factor a tomar en cuenta es que en el planteamiento original la hormiga “vive” en una cuadrícula de extensión infinita en cualquier

dirección, mientras que la cuadrícula de una imagen es finita. Por lo tanto, se deben dar instrucciones a la hormiga en caso de que llegue a un borde: si es necesario que la hormiga cruce un borde, reaparecerá por el lado opuesto de la cuadrícula, en una forma muy similar al comportamiento de los pasillos laterales del juego Pacman. Es decir que, si en el borde derecho debe moverse aún más a la derecha, llegará al borde izquierdo y viceversa. Lo mismo ocurrirá para el borde superior y el inferior. Esta modificación al mundo de la hormiga evitará que quede atrapada en el ciclo de “la autopista” como se mostró en la Figura 2.

Una vez que la hormiga ha caminado la cantidad de pasos que le hayamos pedido, podemos hacer este mismo procedimiento sobre el canal verde y el canal azul (ver Figura 3). Finalmente, juntamos los tres canales para obtener una imagen final, la cual exhibirá las modificaciones generadas por la hormiga de Langton. Si la hormiga realiza una gran cantidad de pasos sobre los canales de la imagen, la modificará tanto que ocultará su información visual y se le podrá considerar como una imagen encriptada. Se deberá recordar la ubicación y orientación final de la hormiga en cada uno de los canales de la imagen y la cantidad de pasos que dio, para que así se pueda colocar la hormiga en su última posición, se rote su orientación en 180 grados, y se deje caminar la misma cantidad de pasos que dio para encriptar (restando el número entero impar a cada casilla por la que pase en lugar de sumarlo), lo que revertirá todos los cambios hechos por la hormiga y generará la imagen original. Por lo tanto, diremos que la ubicación final, orientación final y cantidad de pasos que la hormiga dio en cada cuadrícula será nuestra clave de encriptación. En la Figura 4 se puede observar con detalle el efecto de la hormiga sobre una imagen con pocos píxeles, mientras que en la Figura 5 se muestra un ejemplo del algoritmo de encriptación y desencriptación aplicado a una imagen de prueba de mayores dimensiones. En particular, esta última imagen es una de otras tantas imágenes que comúnmente se usan para probar y comparar los algoritmos de procesamiento de imágenes. En ambos casos se colocó a la hormiga en el centro de la imagen en los tres canales y tomando a 47 como el entero impar.

Figura 4. Encriptación de una imagen de 20×20 píxeles usando la hormiga de Langton 

con distintas cantidades de pasos.

Figura 5. Encriptación y desencriptación de una imagen de 256×256 píxeles usando la hormiga de Langton con distintas cantidades de pasos. Imagen “Mandrill (a.k.a. Baboon)” (volumen “Miscellaneous”) del conjunto de datos de imágenes público “The USC-SIPI Image Database” [6].

Una ventaja de este algoritmo de encriptación es que nos permite recuperar por completo la imagen original. Esta característica es de gran importancia para determinadas imágenes, por ejemplo, en el manejo de imágenes médicas, pues la menor diferencia entre la imagen original y la desencriptada puede afectar en la detección y diagnóstico de enfermedades. Por esta razón, en el trabajo presentado en [4] el algoritmo se enfocó en la encriptación de imágenes médicas, en particular de retinografías, fotos de la retina usadas para el diagnóstico de diferentes enfermedades que afectan a la retina, y se combinó con otros métodos de encriptación para dar una mayor seguridad al algoritmo. De esta manera, el método resultante demostró tener un alto nivel de seguridad y se mostró competitivo frente a otros algoritmos recientes de encriptación reportados en el estado del arte [4]. En la Figura 6 se puede observar el resultado de aplicar la hormiga de Langton a una retinografía usando distintas cantidades de pasos. En [7] se puede conocer más sobre la hormiga de Langton, su extensión a varios colores, más de dos dimensiones y múltiples hormigas, así como algunos simuladores en línea.

A manera de conclusión, es común cuestionarse sobre la aplicación de las matemáticas en el mundo real, pero recordemos que, inicialmente, el estudio de los números primos fue de interés exclusivo de los matemáticos y fue hasta siglos después que se convirtieron en la base de gran parte de la criptografía moderna. La idea misma de los números imaginarios y complejos fue controversial en sus inicios por su aparente relación nula a cualquier fenómeno físico, y hoy son de gran importancia para la ingeniería. Y ahora la hormiga de Langton sirve como un ejemplo más de que nunca se sabe la potencial aplicación e impacto que podrá tener una “curiosidad matemática”. 

Referencias

[1] C.G. Langton, “Studying artificial life with cellular automata,” Physica D: Nonlinear Phenomena, vol. 22, no. 1-3, pp. 120-149, 1986.

[2] A. Gajardo, A. Moreira and E. Goles., “Complexity of Langton’s Ant,” Discrete Applied Mathematics, vol. 117, no. 1-3, pp. 41-50, 2002.

[3] X. Wang and D. Xu, “A novel image encryption scheme using chaos and Langton’s Ant cellular automaton,” Nonlinear Dynamics, vol. 79, pp. 2449-2456, 2015.

[4] A. Romero-Arellano, E. Moya-Albor, J. Brieva, I. Cruz-Aceves, J.G. Avina-Cervantes, M.A. Hernandez-Gonzalez and L.M. Lopez-Montero, “Image Encryption and Decryption System Through a Hybrid Approach Using the Jigsaw Transform and Langton’s Ant Applied to Retinal Fundus Images,” Axioms, vol. 10, 2021.

[5] E. Decencière, X. Zhang, G. Cazuguel, B. Laÿ, B. Cochener, C. Trone, P. Gain, J.R. Ordóñez Varela, P. Massin, A. Erginay, B. Charton and J.C. Klein, “Feedback on a publicly distributed image database: The Messidor database,” Image Analysis and Stereology, vol. 33, no. 3, pp. 231-234, 2014.

[6] University of Southern California. (1981). The USC-SIPI Image Database [Online]. Disponible en: http://sipi.usc.edu/database. Consultado 27 de enero de 2023.

[7] Wikipedia, The Free Encyclopedia. (2023, March 29). Langton’s ant [Online]. Disponible en: https://en.wikipedia.org/w/index.php?title=Langton%27s_ant. Consultado 27 de abril de 2023.

ANEXO

Resumen: La hormiga de Langton es un autómata celular que durante años careció de ninguna aplicación práctica, teniendo a lo mucho un papel indirecto en encriptación de imágenes al ser usada para generar números aleatorios. Recientemente se ha encontrado una aplicación directa de este autómata en el área de encriptación de imágenes, en particular imágenes médicas, en la que se deja caminar a la hormiga sobre los pixeles de una imagen para encriptar la información visual.

Declaración de importancia: Se presenta un algoritmo de encriptación de imágenes médicas basado en un concepto matemático sin aplicaciones directas previas.

Disciplina principal: Matemáticas.

Áreas de aplicación: Criptografía, ciberseguridad, ingeniería. Industria mayormente relacionada: Seguridad en imágenes médicas.