#Cómo engañar a un verificador de sudokus #noticias #2022

#Cómo engañar a un verificador de sudokus #telediario #2022

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 utensilio citación “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 adjudicatario demuestre conocer una esencia, 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 amateur a los sudokus. Algunos compañeros editaban la revista Patio de Jugones, cuya última página contenía un sudoku efectivamente 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.

Ejemplo de Sudoku publicado por EL PAÍS.  Un Sudoku es un juego matemático cuyo objetivo es rellenar una cuadrícula de 9x9 celdas dividida en cajas de 3x3 celdas con número del 1 al 9 en cada celda de tal modo que ninguna fila tenga números repetidos, ni tampoco los tenga ninguna columna ni ninguna caja. El juego debe respetar algunos números que vienen ya dispuestos de inicio.
Ejemplo de Sudoku publicado por EL PAÍS. Un Sudoku es un encaje matemático cuyo objetivo es rellenar una cuadrícula de 9×9 celdas dividida en cajas de 3×3 celdas con número del 1 al 9 en cada celda de tal modo que ninguna fila tenga números repetidos, ni siquiera los tenga ninguna columna ni ninguna caja. El encaje debe respetar algunos números que vienen ya dispuestos de inicio.

–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 posibilidad, y se acabó la diversión– continuó Carla.

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

–Ya, pero lo que yo quiero es comprobar que está aceptablemente resuelto sin desvelar la posibilidad, 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 posibilidad. Si el número ya estaba en el enunciado, la ficha se pone boca hacia lo alto, y si es uno que ponemos al resolverlo, se pone boca debajo, 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 selecció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 posibilidad sea buena, tienen que advenir 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 caucho, podía distinguir si se había se había despojos primero el té o la caucho. Un tal Fisher diseñó un indagación 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 caucho. A posteriori de probar cada taza, ella debía resolver si se había despojos primero el té o la caucho. El indagación se repetía muchas veces y al terminar, calculaban la probabilidad de favor 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 posibilidad correcta, le podrá mostrar al verificador un resultado positivo (sin números repetidos en cada colección). Pero, aunque no tenga la respuesta correcta, si no hay números repetidos en la misma estructura que haya predilecto 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 indagación. El que dice favor resuelto el Sudoku vuelve a colocar las fichas, el verificador vuelve a designar 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 proponer, 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. Por otra parte, si solo hay filas, columnas y cajas, tiene que favor alguna forma de hacer el proceso solo con tres comprobaciones.

–¡Claro!– se animó a comentar Araceli–, en punto de una ficha en cada celda, el participante pone una torrecita de tres fichas (boca hacia lo alto si son las celdas fijas y boca debajo 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 posibilidad 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 4×4 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 posibilidad 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 batallar 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 favor descifrado el enigma. Además pueden despachar sus respuestas al correo [email protected]. En cada nuevo desafío publicaremos la posibilidad del preparatorio, 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 área de Estadística de la Universidad Carlos III de Madrid.


SOLUCIÓN AL DESAFÍO ANTERIOR

La posibilidad al desafío El intriga de la carta del soldado teutónico 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 cerca de la iglesia, y retira unos vigésimo centímetros de tierra.

Para descifrar, usamos la esencia Vigenère: HIAVNDS (cogemos la primera romance de cada “verso”, tal como el soldado ha escrito el poema, que intuitivamente se ve que no tiene la métrica innovador). Varios lectores han llegado a esta esencia, 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 proponer, mediante un software informático, probando todas las claves Vigenère posibles: primero de largo 1, luego de largo 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 criptográfico es HELGA (como han hecho Joaquín o Alicia), y así calculando la secuencia de saltos utilizada en las 5 primeras literatura, para luego ir deduciendo el resto de forma similar. Ahí, de nuevo, hay que suponer que la esencia Vigénere es de largo 5, 6, etc… e ir probando saltos posibles para dar con la esencia completa. Para eso es mejor programar la búsqueda, por ejemplo, en idioma Python, como habéis usado varios.

– Usando directamente algún software habitable 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 sexo y en la supresión…

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

Texto criptográfico:

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 esencia H, luego miramos la fila 7 correspondiente a la H, buscamos la romance 0 y subimos hasta la fila 0 (de texto claro); la romance que encontramos es la H.

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

La L se ha obtenido cifrando con esencia A, luego efectivamente al abreviar no se ha transformado la romance en claro, luego la romance del texto claro es todavía una L.

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

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

Así, omlbn es el criptográfico de HELGA.

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

#Cómo engañar a un verificador de sudokus #telediario #2022

Sé el primero en comentar

Dejar una contestacion

Tu dirección de correo electrónico no será publicada.


*