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.

¨D?S¨ª¨ª¨ª¨ª?

¨DHola mam¨¢ ¨Ddice Jordi con un tono preocupado al otro lado de la pantalla ¨Dllevo 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 ¨C 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

¨DPor tanto, ¨DJordi no se puede aguantar sin intervenir¨D 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

¨D?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 ¨DPaz hace una pausa teatral ¨D 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.

¨DJajajajajaja¡­ 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...

¨DPero eso es imposible...

¨DNo 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

¨D Un testigo, mam¨¢, ?menuda pista! ¨C protest¨® Jordi indignado ¨C 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) ¨Dpuesto que es la tablilla del pacificador¨D 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.