Cifrado: el juego de la vida

Hace unas tres semanas, hablé de "El juego de la vida" de Conway en este post y también propuse un pequeño acertijo en este otro post. Todo aquello me dio la idea de crear un cifrado basado en esta simulación.

Recuerda que en "El juego de la vida", las células (representadas por casillas en una cuadrícula) van modificando su estado de vivas o muertas atendiendo a unas reglas que pueden condensarse en las siguientes líneas:

• Una célula viva que tenga 2 ó 3 vecinos vivos seguirá viva en el siguiente estado. De otro modo, morirá.


• Una célula muerta que tenga exactamente 3 vecinos vivos volverá a la vida en el siguiente estado. De otro modo, seguirá muerta.

Te recomiendo que, antes de proseguir con la lectura, te familiarices un poco con el juego usando la versión interactiva que hice en JavaScript en el primer post mencionado arriba.

¿Cómo podríamos diseñar un cifrado a partir de todo esto? En primer lugar, nuestro mensaje será algo gráfico: podemos dibujar letras, números o formas. Como primera tentativa, podríamos dibujar nuestro mensaje en la cuadrícula, pasar al siguiente estado y mandar el resultado. Por ejemplo, para cifrar una línea vertical de cuatro casillas, mandaríamos su siguiente estado, como en la imagen:

Lo que debería hacer el receptor es encontrar el estado anterior del patrón que recibe. ¿Funciona este método? Por desgracia, no. Considera la siguiente figura, que también se transforma en el mismo rectángulo al aplicar las reglas del juego:

El receptor no tendría modo alguno de determinar cuál esos dos patrones es el que nosotros elegimos al principio. Y, no sólo en esta situación: en general, cualquier patrón que se genere de esta manera tendrá varios estados anteriores posibles. Tendremos que pensar en otra cosa.

Podríamos hacerlo al revés: encontramos un estado anterior a nuestro mensaje (aunque existan varios, elegimos sólo uno de ellos), lo enviamos y es el receptor el que aplica las reglas de "El juego de la vida" para recuperar el mensaje original. El receptor siempre podrá recuperar correctamente el mensaje, ya que las reglas no admiten ningún camino alternativo.

Nos resta, pues, un único problema: ¿cómo, a partir de un patrón, logramos encontrar un estado anterior? Normalmente, a ese estado anterior se le llama "padre" porque genera el que ya tenemos.

Si indagamos un poco sobre "El juego de la vida", enseguida nos encontramos con un muro que parece infranqueable: los llamados "jardines del Edén". Un jardín del Edén es un patrón que no tiene ningún padre, es decir, nadie lo genera. ¿En qué nos afecta la existencia de los jardines del Edén? Simple, si nuestro mensaje resulta que es uno de estos patrones especiales, no podremos encontrar ningún estado anterior para que sea nuestro mensaje cifrado. En este punto, pensé "Bueno... si hay muy poquitos jardines del Edén, quizás nunca nos veamos en esta situación..." Pero la mala noticia es que cuanto más grande sea el patrón, más probable es que se trate de un jardín del Edén, es decir, hay muchísimos. ¡En menudo jardín nos hemos metido!

La conclusión es evidente: no podremos cifrar cualquier cosa, tan solo algunos patrones. Tendremos que ser muy cuidadosos...

Más o menos en este punto me encontraba, intentando encontrar padres a dibujos sencillos como las letras y los números, cuando, por una absoluta y brillante casualidad, encontré este curioso post en la página de Matthew Scroggs (link AQUÍ a la página principal). Es el creador de las cruzadas de Chalkdust Magazine, que ya sabes que tanto me gustan y de las que ya he hablado en alguna ocasión. En su post, proporciona patrones padres para versiones pequeñas de las letras del alfabeto. Por ejemplo, observa esta figura:

Al aplicar las reglas del juego, se genera:

Es decir, la letra K. Hemos encontrado una manera de cifrar letras: escribimos los padres de cada una de las que queramos cifrar, dejando espacio entre cada figura para que no se afecten unas a otras, y mandamos el patrón. Por ejemplo, para cifrar LOGICA, que se traduce en el siguiente dibujo,

enviaríamos el siguiente patrón, que es uno de sus padres:

Por supuesto, ésta no es la única manera, podríamos utilizar otros modelos de letras que nos gustasen más, más grandes, más estilizadas, añadir la Ñ, incluso,... Lo único que tendríamos que hacer, como ya sabes, es encontrar un padre apropiado. Por ejemplo, para conseguir este otro modelo de G:

lo único que tenemos que dibujar es este patrón que, curiosamente, también es otra G:

Otro ejemplo que he construido, este patrón:

genera el número 170:

Puedes ser tan creativo como quieras y dibujar tus propios diseños o usar los que Matthew Scroggs propone en su post. Una vez que hayas elegido el dibujo y encontrado el patrón padre adecuado, sólo tienes que mandarlo. Y esto lo puedes hacer de varias formas. Lo más sencillo es enviar directamente la imagen, pero también puedes "convertirla" en una lista de 0's y 1's (un 0 representa una casilla blanca y un 1, una negra). O incluso puedes usar este otro cifrado que tanto me gusta. Escojas en método que escojas, el receptor debería ser capaz de volver a dibujar el patrón para, a continuación, aplicar las reglas de "El juego de la vida" y obtener el mensaje original.

Como cifrado, es interesante, aunque no muy práctico (ya sabes que mis cifrados favoritos son más bonitos que útiles). Si siempre utilizas los mismos patrones, no se diferenciará de un cifrado de sustitución corriente, fácil de romper, pero sería buena idea investigar qué ocurriría si se van usando diferentes diseños, cómo afectaría a la seguridad (asumiendo que el atacante no sabe qué reglas estamos usando). Aún así, reconozco que encontrar un patrón padre es una tarea algo tediosa (y, como hemos comentado antes, a veces, imposible).

Espero que te haya gustado este cifrado y no dudes en compartir los diseños que encuentres. Si te apetece, puedes intentar resolver este criptograma. ¡Hasta el próximo cifrado!