Un mensaje en clave napolitana oculto entre unos y ceros

Beeeeeeep… Beeeeep… Beeeeep

Domingo por la mañana. El nen no está en casa y hay un vacío extraño; por primera vez no va a estar durante unos meses; se ha ido a hacer el proyecto de fin de grado a la Universidad de Salerno, muy cerca de Nápoles.

―¿Síííí?

―Hola mamá ―dice Jordi con un tono preocupado al otro lado de la pantalla ―llevo una semana en el Departamento de criptografía pero no entiendo nada. ¿Puedes explicarme qué es eso del cifrado Vernam? ¿Y por qué el gran matemático estadounidense Claude Shannon lo llamó “perfecto”?

Paz sonríe – Ea, vamos allá. El cifrado Vernam o One Time Pad es un sistema que sirve para cifrar mensajes con claves de un solo uso. Te explico cómo funciona. Si quieres por ejemplo enviar la palabra HOLA, primero la codificas en binario, porque las cadenas de unos y ceros son más fáciles de transmitir. Bastará usar cinco bits para un alfabeto de 27 letras.

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z

Y lo harías de esta manera. Primero, asignas a cada letra un número según su orden en el alfabeto: A=0, B=1, C=2... Z=26. Luego pasas dichos números a binario, descomponiéndolos en sumas de potencias de dos (desde 1, que es 2 elevado a 0, a 16, que es 2 elevado a 4 ). Fíjate:

A=0, que en binario con cinco bits se escribe 00000, pues 0= 0x16 + 0x8 + 0x4 + 0x2 +0x1

B=1, en binario se escribe como 00001, pues 1 = 0x16 + 0 x 8 + 0x4 + 0x2 + 1x1

C=2, siguiendo el mismo método sería 00010, ya que 2 = 0x16 + 0 x 8 + 0x4 + 1x2 + 0x1

D=3, que sería 00011, puesto que 3= 0x16 + 0x8 +0x4 +1x2 +1x1

E=4, y se codificaría 00100, ya que 4= 0x16 + 0x8 + 1x4 + 0x2 + 0x1

Y así, hasta Z=26, que sería 11010, pues 26= 1x16 + 1x8 + 0x4 + 1x2 +0x1

Así, tu mensaje M =HOLA se codificaría en cuatro bloques de cinco bits, uno por cada letra. Y tomando

H=00111, 0=01111, L=01011, A=00000, nos queda:

MENSAJE ORIGINAL (M) = 00111 01111 01011 00000

Ese es el mensaje original. Pero para cifrarlo y que nadie pueda entenderlo, a parte de tu receptor, has de usar una clave de la misma longitud de bits. En este caso, una tira de 20 bits en cuatro bloques que hemos acordado previamente tú y yo. Por ejemplo:

CLAVE (K) = 01010 10101 01010 10101 (equivalente a la palabra KUKU, que es fácil de recordar)

Lo que cifras y envías será el resultado de hacer la suma del mensaje y de la clave, bit a bit. Pero ¡ojo! No es una suma convencional. Es una suma que se llama XOR, o módulo 2, para la que empleamos el símbolo ⨁ y que se hace así:

0⨁0=0

1⨁0=1

1⨁1=0

―Por tanto, ―Jordi no se puede aguantar sin intervenir― lo que enviaría en este caso sería… el siguiente mensaje cifrado:

MENSAJE ENVIADO (C) = M⨁K= 00111 01111 01011 00000 ⨁ 01010 10101 01010 10101= 01101 11010 00001 10101

―¡Exacto! Por otro lado, este método además de seguro es muy ágil: cuando yo reciba tu mensaje simplemente tengo que hacer la suma bit a bit con la clave que tenemos en común y recupero el mensaje original. Pero lo revolucionario de este método ―Paz hace una pausa teatral ― que justamente subrayó Shannon, es que una persona que intercepte el mensaje enviado no sabrá nada de él, ya que la tira de bits C podría contener dentro cualquier mensaje con ese número de letras. Imagínate que alguien intercepta el mensaje que enviamos antes y, como no tiene ni idea de la clave, prueba a ver si es, por ejemplo, K’=01100 11010 00000 10101

-Espera… sabes que soy muy rápido… obtendría que el mensaje original es:

C+K’=00001 00000 00001 00000

O sea BABA, mi dulce napolitano preferido… mmmm.

―Jajajajajaja… sabía que te gustaría. Sorprendente, ¿no? ¿Tú crees que podría salir cualquier mensaje original probando claves distintas? ¿Cuál sería el mensaje original si la clave utilizada hubiese sido esta otra, K*=01111 11010 00100 10001? Te lo dejo para que lo pienses. Y ya puestos... te propongo un reto mucho más difícil: descifrar un mensaje cuando no tienes la clave...

―Pero eso es imposible...

―No si te doy alguna pista. La clave es un testigo impagable de los tiempos, y el mensaje original está relacionado con un dios del mar; llegarás a ambos si no olvidas el lugar en el que te encuentras. El mensaje interceptado es este:

C = 00000 01111 01000 00011 10000 01100 01100

― Un testigo, mamá, ¡menuda pista! – protestó Jordi indignado – puede ser tantas cosas… un monumento, un lugar, incluso una receta de pasta… pero quizá... ¡Me pongo a ello!

Los desafíos criptográficos se publicarán cada 15 días. Los lectores pueden dejar sus soluciones y debatir sobre el problema en los comentarios de esta página, por lo que se recomienda a quien quiera resolverlo por sí mismo no leerlos hasta haber descifrado el enigma. También pueden enviar sus respuestas al correo desafioscriptograficos@gmail.com. En cada nuevo desafío publicaremos la solución del anterior, acompañada de un comentario con algunas ideas originales o inspiradoras que hayamos recibido.

Germán Sáez Moreno es investigador del grupo MAC y profesor de Matemática Aplicada en la Universitat Politècnica de Catalunya.

SOLUCIÓN AL DESAFÍO ANTERIOR

Necesitamos rellenar 7 casillas, incluyendo la (1,1,1) ―puesto que es la tablilla del pacificador― de modo que se defina un conjunto crítico, es decir, que nos lleve a un único cuadrado latino posible partiendo de:

La secuencia correcta es a secuencia es T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }, que rellena el cuadrado parcialmente de esta forma:

Cualquier otro conjunto de 7 tablillas tomadas de las 8 posibles no define un conjunto crítico, es decir, puede rellenarse dando lugar a varios cuadrados latinos. Con las nuestras, el único cuadrado latino completo que sale es:

Observación: Este cuadrado latino contiene a la “tribu maldita”, la tablilla (1,5,5), que, sin embargo, tenemos que quitar si queremos que nuestra secuencia solución defina un conjunto crítico.

RESOLUCIÓN DETALLADA:

El cuadrado latino que perseguimos completar ha de contener siete de las posiciones descritas en las tablillas de cerámica:

T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5)

Además, para conseguir un conjunto crítico es imprescindible incluir al (1,1,1), que para eso es la tablilla del sacerdote pacificador.

Hay por tanto 7 conjuntos posibles (los que hay eliminando una terna de las 8 posibles si mantenemos siempre la (1,1,1) ). Veamos caso a caso:

- C1 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico. Si nos ponemos a resolver el sudoku, no hay una única solución. En este caso, salen dos cuadrados latinos compatibles

- C2 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico, salen siete cuadrados latinos compatibles

- C3 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico, salen cuatro cuadrados latinos compatibles

- C4 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

Esto es un conjunto crítico. El sudoku solo tendría una solución.

- C5 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico, salen 14 cuadrados latinos compatibles

- C6 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico, salen ocho cuadrados latinos compatibles

- C7 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

No es un conjunto crítico, salen 6 cuadrados latinos compatibles

Así pues, la secuencia correcta es la que determina el conjunto C4, que es el único conjunto crítico.

C4 = { T1=(4,3,5) T2=(3,5,4) T3=(4,2,3) T4=(1,5,5) T5 = (5,3,2) T6=(1,1,1) T7=(2,5,3) T8=(5,1,5) }

Hay herramientas disponibles en internet para hacer los cálculos sin necesidad de resolver todos sudokus, por ejemplo esta: https://www.dcode.fr/latin-square

Varios lectores, como Joaquín, han encontrado a la tribu maldita con un razonamiento más sencillo, al darse cuenta de que la ficha (1,5,5) es innecesaria: al suprimirla, y rellenar el cuadrado con el resto de tablillas, no queda otra opción que poner un 5 en la posición 1-5 (de hecho, como el conjunto que forman las otras tablillas es crítico, cualquier otra casilla del tablero queda determinada, pues nunca habrá más de una solución). Este método, sin embargo, no sirve para identificar en general conjuntos críticos (pues podría haber elementos que sobren sin ser “deducibles” partiendo exclusivamente del resto de las que forman el conjunto).

ACERCA DE LOS ESQUEMAS DE COMPARTICIÓN DE SECRETOS

Este reto está basado en un esquema de compartición de secretos publicado en el trabajo Secret sharing schemes arising from latin squares, de Joan Cooper, Diane Donovan y Jennifer Seberry.

Los esquemas de compartición de secretos son diseños criptográficos tremendamente útiles, sobre todo en escenarios en los que es importante fragmentar información y obligar a los receptores potenciales a agruparse según una cierta política de acceso a la información. Un ejemplo muy actual de uso es el de control de acceso a través de contraseñas. Supongamos que los usuarios de un sistema se identifican a través de una contraseña. Si la lista de contraseñas válidas se guarda en un único servidor (aunque sea ligeramente enmascarada) es evidente el peligro que existe si dicho servidor llega a ser controlado por una entidad maliciosa externa. Sin embargo, si se fragmenta dicha lista repartiéndola entre varios servidores, de modo que cada acceso sea validado por ellos de manera colaborativa, las contraseñas estarán protegidas cuando un único servidor sea atacado.

Los esquemas de compartición de secretos fueron introducidos por Adi Shamir en su artículo How to share a secret y George Blakey (Safeguarding cryptographic keys). Ambos autores propusieron además el esquema más utilizado hasta la fecha, que se basa en interpolación polinomial.

Puedes seguir a EL PAÍS TECNOLOGÍA en Facebook y Twitter o apuntarte aquí para recibir nuestra newsletter semanal.