El acertijo de la c¨¢mara secreta

Jorge y Clara trabajaban desde hac¨ªa meses como arque¨®logos en una pir¨¢mide precolombina al sur del Yucat¨¢n. Llevaban semanas intentando entrar en una c¨¢mara secreta. Pero para hacerlo deb¨ªan resolver un acertijo que podr¨ªa conducirles al ¨¦xito o a la muerte.

Ocho tribus se hab¨ªan disputado el poder en regi¨®n. Un sacerdote pacificador, jefe de una de las tribus, consigui¨® establecer una alianza que firmaron siete de ellas, que pasaron a custodiar la pir¨¢mide. La octava tribu se consider¨® maldita. Cada tribu aparec¨ªa en distintos restos arqueol¨®gicos representada a trav¨¦s de una figura cuadrada, que conten¨ªa una terna de s¨ªmbolos. Por ejemplo, esta era la tablilla de una de las tribus:

La puerta de la c¨¢mara en la que quer¨ªan entrar ten¨ªa en el suelo una especie de tablero dibujado, con filas y columnas indexadas exactamente por esos s¨ªmbolos, en la que pod¨ªa encajarse, para cada posici¨®n de fila y columna, una ¨²nica piedra con la forma de uno de los cinco s¨ªmbolos distintos que se hab¨ªan encontrado. Por anteriores excavaciones, se sab¨ªa que hab¨ªa que interpretar los tres s¨ªmbolos de cada tablilla como fila-columna-s¨ªmbolo. La tablilla citada m¨¢s arriba, por ejemplo, encajar¨ªa as¨ª en el tablero.

Jorge y Clara sab¨ªan que si completaban correctamente el tablero, esto es, dejando solo vac¨ªa la casilla correspondiente a la tribu maldita, se activar¨ªa un resorte que abrir¨ªa la puerta a la c¨¢mara secreta. Si, por el contrario, introduc¨ªan la piedra asociada a la tribu maldita, ser¨ªan atravesados por los dardos preparados para ahuyentar a los saqueadores de pir¨¢mides.

As¨ª pues, su plan era rellenar la tabla usando primero las figuras que indicaban las tablillas correspondientes a las tribus aliadas, para luego seguir a?adiendo s¨ªmbolos de alguna forma, hasta solo dejar una casilla sin figura. Dos eran, pues, las cuestiones a resolver:

- Hab¨ªa una tribu maldita entre las ocho, y era crucial excluir su tablilla¡­pero, ?c¨®mo identificarla?

- Suponiendo descartada la tablilla maldita y una vez incluidas las siete casillas elegidas ?ser¨ªan capaces de rellenar el resto de las casillas del tablero?

Insertando los s¨ªmbolos de las ocho tablillas correspondientes a las ocho tribus, dibujaron el tablero parcialmente relleno en una pizarra.

La primera casilla del tablero se correspond¨ªa con la tablilla de la tribu del sacerdote pacificador; as¨ª que, al menos, esa estar¨ªa bien colocada.

- Esa tablilla se queda ¨C dijo Jorge taxativo. ¨C Ahora a ver qu¨¦ pasa con las dem¨¢s. Y, para hacerlo m¨¢s f¨¢cil, usemos los n¨²meros del uno al cinco, en vez de los s¨ªmbolos:

De ese modo, a?adiendo las ocho tablillas y usando la codificaci¨®n num¨¦rica, les qued¨® en la pizarra una especie de sudoku:

Jorge parec¨ªa cada vez m¨¢s preocupado.

- ?Qu¨¦ tablilla descartamos, Clara? Una equivocaci¨®n resultar¨ªa fatal¡­.

Clara se puso a buscar en internet informaci¨®n sobre ¡°sudokus precolombinos¡±, con escaso ¨¦xito. Pero encontr¨® una p¨¢gina muy interesante que hablaba de algo llamado cuadrados latinos.

- F¨ªjate en esto, Jorge ¨C le dijo- un cuadrado latino es una tabla con igual n¨²mero de filas que de columnas, que se rellena con los n¨²meros enteros {1,2,¡­,N} cumpliendo que en cada fila y en cada columna aparece cada uno de los n¨²meros {1,2,¡­,N} exactamente una vez.

- Y a¨²n hay m¨¢s. Los cuadrados latinos sirven para compartir secretos. Hay algo llamado ¡°conjuntos cr¨ªticos¡±, que son justamente conjuntos de posiciones que s¨®lo pueden completarse de una manera para formar un cuadrado latino, igual que el sudoku de un peri¨®dico solo tiene una soluci¨®n. As¨ª, se puede repartir un conjunto cr¨ªtico entre varias personas oblig¨¢ndoles a colaborar para reconstruir el cuadrado porque, adem¨¢s, los conjuntos cr¨ªticos son minimales: si se tiene s¨®lo una parte del conjunto cr¨ªtico, resulta que hay m¨¢s de una manera de completar el tablero, con lo que no se sabe cu¨¢l es la soluci¨®n correcta.

- Clara, no estoy seguro de estar entendiendo todo ¨C se impacient¨® Jorge ¨C t¨² ay¨²dame a decidir c¨®mo eliminar una tablilla y m¨¢s vale que no nos equivoquemos. Escribamos de nuevo la codificaci¨®n num¨¦rica de las tablillas -

Clara no se hizo de rogar.

- Esto es lo que tenemos:

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)

- El desaf¨ªo consiste en eliminar una de las ocho figuras de la posici¨®n inicial, que se corresponder¨¢ con la tribu maldita. Y rellenar el resto de la tabla¡­ - a Clara ahora le brillaban los ojos- s¨¦ que nos jugamos la vida, pero creo que funcionar¨¢ el m¨¦todo que se me acaba de ocurrir¡­

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.

Mar¨ªa Isabel Gonz¨¢lez Vasco es catedr¨¢tica de Matem¨¢tica Aplicada de la Universidad Rey Juan Carlos e integrante de la Junta de Gobierno de la Real Sociedad Matem¨¢tica Espa?ola.

SOLUCI?N AL DESAF?O ANTERIOR

Las funciones hash son aplicaciones que asignan a cada valor de un cierto conjunto de salida un valor resumen que (t¨ªpicamente) pertenece a un conjunto mucho m¨¢s peque?o. Formalmente, de hecho, se definen como aplicaciones que toman una cadena binaria (de ceros y unos) de cualquier longitud y la resumen en una cadena de longitud fijada. Dicha longitud final se incluye en las implementaciones como parte del nombre de la propia funci¨®n hash (ver, por ejemplo, el caso de las funciones de la familia SHA o BLAKE ). A menudo se utilizan para realizar comprobaciones r¨¢pidas (verificar si dos valores coinciden, mirando si sus res¨²menes lo hacen) pero su papel fundamental es proporcionar pruebas de integridad, es decir, ayudan a detectar modificaciones en mensajes o c¨®digo. Por ejemplo, en esta imagen vemos la p¨¢gina desde la que puede descargarse un programa para estudiar criptograf¨ªa, donde se incluyen los res¨²menes para cada descarga usando la funci¨®n hash SHA256.

De este modo, un usuario que se baja, por ejemplo, el programa Cryptool 1.4.42 en Espa?ol, deber¨ªa comprobar (ejecutando SHA256 en su ordenador) que el resumen del c¨®digo obtenido coincide con la cadena de bits que aparece en la p¨¢gina (escrita en hexadecimal):

62f0681356e9b3a9cb32a13eccd8a61d9deb0a108ce17c8914668e7460601eab

Para que una funci¨®n hash sea criptogr¨¢ficamente ¨²til, se exigen dos condiciones:

- Eficiencia: los res¨²menes han de ser f¨¢ciles y r¨¢pidos de calcular con m¨ªnimos recursos computacionales (un m¨®vil, un ordenador de sobremesa, etc.)

- Resistencia a colisiones: no debe ser posible calcular eficientemente dos valores iniciales con el mismo resumen. Esto, en particular, tambi¨¦n implicar¨¢ que es dif¨ªcil calcular un valor con el mismo resumen que otro dado, o revertir la aplicaci¨®n de la funci¨®n (dado un resumen, calcular un valor inicial asociado)

En el anterior reto, la funci¨®n hash propuesta realiza una sencilla operaci¨®n; quedarse con el resto al dividir cada n¨²mero entre 1024. Hay 1024 restos posibles {0,¡­, 1023}. Es una funci¨®n realmente mala, con lo que respecta a la resistencia a colisiones. Como s¨®lo hay 1024 res¨²menes, a lo sumo, se encontrar¨ªa una repetici¨®n cuando entr¨® el espectador 1025 (y, como m¨ªnimo, tuvieron que entrar dos espectadores en el recinto para que se produjese una colisi¨®n entre sus res¨²menes).

Respondamos ahora a las dem¨¢s preguntas; si queremos saber cu¨¢ntas entradas, dentro del aforo permitido, ten¨ªan como resumen el mismo que el n¨²mero 4410, tenemos que contar los n¨²meros de la forma 4410 + K(1024), con K un entero, que est¨¦n entre 1 y 10900. Sirve tomar K = {-4,¡­, 6}, luego hay 11 entradas, que en concreto son:

En cuanto al n¨²mero de entradas con id¨¦ntico identificador pero menores que 99999, ser¨ªan, razonando igual, todos los n¨²meros de la forma 4410 + K(1024) , con K un entero, que est¨¦n entre 1 y 99999. Podemos por tanto tomar K= {-4,¡­,93}, luego hay 98.

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