Cómo engañar a un verificador de sudokus

La criptografía no solo consiste en descifrar mensajes ocultos. En esta segunda entrega de los desafíos criptográficos ―que la sección de Tecnología de EL PAÍS publica cada 15 días― retamos a los lectores a intentar vulnerar la seguridad de una herramienta llamada “sistema de demostración interactivo”, que sirve para demostrar que conocemos un secreto sin revelar información sobre el mismo. Tales construcciones son fundamentales, por ejemplo, para elaborar mecanismos de identificación, pues permiten que el usuario demuestre conocer una clave, sin tener que revelarla a terceros que podrían suplantarlo.

En el patio de secundaria tenían éxito los juegos de ingenio. Y Mario, Carla, Araceli y Hugo se habían aficionado a los sudokus. Algunos compañeros editaban la revista Patio de Jugones, cuya última página contenía un sudoku realmente difícil. Los cuatro abrían juntos la revista en el primer recreo de la semana y competían para ver quién era el primero en resolverlo. El resto de los recreos se los pasaban charlando sobre cómo organizar una competición de sudokus.

–En cuanto uno resuelve el sudoku, nos lo enseña a los demás, y lo comprobamos– opinó Hugo.

–Eso no puede ser, porque entonces ya vemos la solución, y se acabó la diversión– continuó Carla.

–Pues se lo enseña a cualquier otro compañero. Comprobar que un sudoku está bien resuelto es fácil, así que cualquiera valdría de verificador– se unió Araceli.

–Ya, pero lo que yo quiero es comprobar que está bien resuelto sin desvelar la solución, que los demás puedan seguir pegándose con él– insistió Carla.

–Se me ocurre una cosa– dijo Mario mientras cavilaba–. En vez de escribir números podemos usar fichas para rellenar la cuadrícula. Ponemos una ficha en cada casilla con el número de la solución. Si el número ya estaba en el enunciado, la ficha se pone boca arriba, y si es uno que ponemos al resolverlo, se pone boca abajo, para que no se vea el número. Cuando esté relleno el Sudoku, el verificador escoge la fila, columna o caja que quiera, entonces el que lo ha resuelto recogerá todas las fichas de esa fila, columna o caja, las barajará y las mostrará para que el verificador pueda comprobar que todos los números son diferentes.

–¡Me parece una idea buenísima!– exclamó Araceli entusiasmada –, pero con una fila, columna o caja no demuestras que el sudoku completo esté resuelto. Sería mejor que el verificador dijera “filas”, “columnas” o “cajas” y que se comprueben, según su elección, una a una todas las filas, columnas o cajas.

–Pero seguimos en las mismas– comentó ahora Carla–. El hecho de que las filas (o columnas, o cajas) no tengan números repetidos no garantiza que la solución sea buena, tienen que pasar las tres cosas a la vez. A mí esto me recuerda a la historia que nos contó la profe de Mates sobre una señora que decía que, si le daban a probar una taza de té con leche, podía distinguir si se había se había vertido primero el té o la leche. Un tal Fisher diseñó un experimento para comprobar si lo que decía la señora era cierto o no. La idea era que sometían a la señora a una cata a ciegas de tazas de té con leche. Después de probar cada taza, ella debía declarar si se había vertido primero el té o la leche. El experimento se repetía muchas veces y al terminar, calculaban la probabilidad de haber acertado tantas veces como ella o más, si se respondía completamente al azar. Si esa probabilidad era muy pequeña, seguramente la señora decía la verdad.

–Creo que te sigo– dijo Mario–. En nuestro caso, el verificador puede escoger “filas”, “columnas” o “cajas”. Supongamos que lo hace completamente al azar, escogerá cada uno de ellos con probabilidad 1/3. Escoja lo que escoja, si el que ha resuelto el Sudoku tiene la solución correcta, le podrá mostrar al verificador un resultado positivo (sin números repetidos en cada grupo). Pero, aunque no tenga la respuesta correcta, si no hay números repetidos en la misma estructura que haya elegido el verificador (filas, columnas o cajas), le engañará. La probabilidad de que un mentiroso acierte de antemano la estructura que va a pedir el verificador y componga los números de acuerdo con ella es 1/3… y ahora es donde entra la historia de la catadora de té. Podemos repetir el experimento. El que dice haber resuelto el Sudoku vuelve a colocar las fichas, el verificador vuelve a elegir entre filas, columnas y cajas y la probabilidad de que un mentiroso le engañe dos veces seguidas será 1/3 x 1/3 (es decir, 1/9). El proceso se puede repetir más veces y terminaremos pillando a un mentiroso.

–¡Vaya método más complicado!– se quejó Hugo–. Como nos pongamos muy tiquismiquis, vamos a terminar con 10 rondas para darnos por satisfechos. Además, si solo hay filas, columnas y cajas, tiene que haber alguna manera de hacer el proceso solo con tres comprobaciones.

–¡Claro!– se animó a comentar Araceli–, en lugar de una ficha en cada celda, el participante pone una torrecita de tres fichas (boca arriba si son las celdas fijas y boca abajo si son las que hay que rellenar) y luego el verificador va cogiendo y agrupando fichas colocadas en las celdas de cada fila, cada columna y cada caja en el orden que quiera. Se barajan las de cada uno de esos grupos, se voltean las fichas y se comprueba que no hay números repetidos, en cuyo caso, la solución sería correcta.

–¡No necesariamente!– dijo Carla.– Esta técnica conseguirá detectar muchísimos fraudes, pero no es infalible. Por simplificar las cosas, pensad en un sudoku 4x4 como éste.

Conviene resolverlo primero. Y luego (y ese es el desafío) hay que intentar encontrar alguna forma de colocar las tres fichas en cada casilla que no dé una solución correcta al sudoku, pero que, con suerte pueda engañar al verificador.

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.

Ignacio Cascos Fernández es doctor en Matemáticas y profesor del departamento de Estadística de la Universidad Carlos III de Madrid.

SOLUCIÓN AL DESAFÍO ANTERIOR

La solución al desafío El misterio de la carta del soldado alemán es: Helga, las joyas de los abuelos están todas enterradas bajo el abedul, en el huerto de las higueras. Sitúate de espaldas al tronco, mirando hacia la iglesia, y retira unos veinte centímetros de tierra.

Para descifrar, usamos la clave Vigenère: HIAVNDS (cogemos la primera letra de cada “verso”, tal como el soldado ha escrito el poema, que intuitivamente se ve que no tiene la métrica original). Varios lectores han llegado a esta clave, pero no todos a partir del poema. Estas son algunas de las estrategias que nos han contado por correo electrónico:

- Usando “fuerza bruta”, es decir, mediante un programa informático, probando todas las claves Vigenère posibles: primero de longitud 1, luego de longitud 2, etc. La “fuerza bruta” que algunos habéis hecho manualmente habrá sido muy tediosa, pero habéis sido muy ingeniosos seleccionando claves posibles (Tomás, nos ha encantado que probases “TELEFUNKEN”).

- Asumiendo que la primera palabra del texto cifrado es HELGA (como han hecho Joaquín o Alicia), y así calculando la secuencia de saltos utilizada en las 5 primeras letras, para luego ir deduciendo el resto de manera similar. Ahí, de nuevo, hay que suponer que la clave Vigénere es de longitud 5, 6, etc… e ir probando saltos posibles para dar con la clave completa. Para eso es mejor programar la búsqueda, por ejemplo, en lenguaje Python, como habéis usado varios.

- Usando directamente algún programa disponible en internet para descifrar Vigènere (como Julio o Manu, que han utilizado Cryptii.com y Vigenere Solver. Esto es un poquito trampa, pero, ya se sabe, en el amor y en la guerra…

Detallamos ahora los primeros pasos del proceso de descifrado (el resto son análogos):

Texto cifrado:

omlbn, osz rotnv vl ton nemlton rvlhv tjqdk lvtzeuskis wnmg lt awrgms, mn zy kmlztj qh dha hdtxwyis. nvwmhbe yr hkwilynv ss brjafg, tqrvagg oicdn os polzfls, f zeovus bvon ihaube xrqlpueoerk km tdrujh.

La 0 se ha obtenido cifrando con clave H, luego miramos la fila 7 correspondiente a la H, buscamos la letra 0 y subimos hasta la fila 0 (de texto claro); la letra que encontramos es la H.

La M se ha obtenido cifrando con clave I, luego miramos la fila 8 correspondiente a la I, buscamos la letra M, y subimos hasta la fila 0, obteniendo la letra E.

La L se ha obtenido cifrando con clave A, luego realmente al cifrar no se ha transformado la letra en claro, luego la letra del texto claro es también una L.

La B se ha obtenido cifrando con clave V, luego miramos la fila 21 correspondiente a la V, buscamos la B, subimos a la columna 0 y encontramos la letra correspondiente, la G.

La N se ha obtenido con clave N, luego justo encima, en la fila 0 encontramos su correspondiente en claro: la A.

Así, omlbn es el cifrado de HELGA.

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