Desafío criptográfico: ¡Que le corten la cabeza! O no…

–¡Que le corten la cabeza! –exclamó enfurecida la Reina de Corazones.

–Bueno, bueno, querida, primero tendremos emitir cada uno nuestro voto, ¿no es así? –dijo con tranquilidad el Rey de Corazones.

–¡No! ¡Estoy harta de este sistema de votaciones que acordamos! Decidimos que para cortar una cabeza es necesario que los dos estemos a favor, ¿sabes niña? –dijo la Reina dirigiéndose a Alicia, que era la única que parecía no estar al tanto.

–¿Y cuál es el problema, Su Majestad? ¿Desea decidir usted sola? –respondió Alicia educadamente.

–No niña, ese no es el problema en absoluto, estoy de acuerdo en que lo hagamos conjuntamente. Pero el desenlace habitual es que yo voto “cortar” y el Rey “vota perdonar”, el acusado se salva y, para colmo, todo el mundo piensa que soy una persona horrible.

–¿Y no lo arreglarían votando en secreto? Cada uno de ustedes podría darle el voto en un sobre cerrado a alguien de confianza, por ejemplo, al Conejo Blanco. Cuando tuviera los dos votos en su poder, anunciaría si el acusado ha sido perdonado o no, sin revelar nada más sobre la votación.

–Pero, ¡qué ingenua eres! Alguien de confianza, dices. Ya lo hemos intentado y siempre se acaba sabiendo el voto de cada uno. No me fío absolutamente de nadie.

–Majestad, he estado dándole vueltas al asunto y creo que podría haber una solución – intervino el Sombrerero–. Podríamos intentar diseñar un nuevo Protocolo Real en el que solo intervinieran el Rey y usted. Tras llevarlo a cabo, se sabría si el acusado se salva o no. Pero usted obtendría ciertas garantías de privacidad. Si rodara la cabeza, estaría claro lo que ha votado cada uno, nada que ocultar ahí. Pero si el acusado se salvase y el Rey hubiera votado “perdonar”, lo que usted ha votado quedaría en secreto para todo el mundo, incluido el propio Rey. Así, su reputación se mantendría a salvo. Por supuesto, el Rey obtendría las mismas garantías.

–¡Ya estás con tus estúpidas ideas! Es evidente que eso es imposible. ¡Qué le corten la…! En fin, da igual, seguro que el Rey te va a perdonar.

–Con todos los respetos, Su Majestad, quizá no sea imposible –dijo tímidamente Alicia–. Una vez, en mi tierra, estuve en una conferencia en un lugar llamado Laboratorio Idea. El profesor que la impartió, Miguel, habló de un problema muy parecido al que ha planteado el Sombrerero, de hecho, yo diría que es exactamente el mismo. Bueno, no había que cortarle la cabeza a nadie, pero por lo demás era el mismo. Y además explicó una forma de resolverlo. Os podría contar lo que recuerdo, pero tengo algunas lagunas. Hacen falta seis cartas con dorsos idénticos, esto os agradará. De las seis cartas, tres han de ser iguales, por ejemplo, tres ases de corazones y las otras tres diferentes de las primeras pero iguales entre sí, por ejemplo, tres ases de picas. Usted tendría dos cartas para votar, una roja y una negra; y lo mismo para el Rey. Las dos cartas restantes se colocan en una mesa con seis espacios. Os haré un dibujo.

–Estas dos cartas se pondrían ahora bocabajo. Para votar, cada uno de ustedes pondría sus dos cartas, también bocabajo, en los espacios que les estoy indicando. Si la carta roja está a la izquierda, el voto es “Cortar”, mientras que, si está a la derecha, el voto es “Perdonar”. Aquí es donde mis recuerdos no son ya precisos. Había que dividir esas seis cartas, de alguna manera, en dos grupos de tres cartas, grupo 1 y grupo 2, e introducir cada grupo ordenadamente en un sobre cerrado. A continuación, los sobres se mezclaban para que no pudiera saberse cuál contenía las cartas de cada grupo. Se abría por tanto un sobre y se colocaban las cartas (sin alterar el orden) asumiendo que eran las del grupo 1, para hacer después lo propio con el grupo 2 y el segundo sobre. Finalmente mostrando solo cuatro de las seis cartas podía verse el resultado. Siento no recordar todos los detalles, Majestad.

–Interesante, sí, muy interesante. ¡Sombrerero! ¿Serías capaz de completar el nuevo Protocolo Real a partir de estas ideas?

La solución de este décimo y último desafío criptográfico se publicará dentro de 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.

Angel L. Pérez del Pozo es profesor de Matemática Aplicada e investigador en Criptografía en la U. Rey Juan Carlos.

SOLUCIÓN AL DESAFÍO ANTERIOR

El desafío de esta semana se ha resistido un poco más (incluso a nuestros lectores más habituales y aventajados). Intuitivamente, puede parecer que la youtuber está en lo cierto cuando afirma que la probabilidad de éxito de un miembro del equipo no depende que éste conozca la clave o no. Y de hecho, está completamente en lo cierto al pensar que, como todos los miembros del equipo entran a la sala con la misma información, no pueden influirse unos a otros para amplificar su ventaja.

A pesar de todo, sí que existe una estrategia que aumenta la probabilidad de éxito del equipo que conoce la contraseña. La observación clave es la siguiente. Como no hay dos teclas que escriban el mismo carácter en pantalla, cada carácter está asociado de forma única a cada tecla. Si empezamos pulsando la tecla “1″ y aparece el carácter “x”, podemos pulsar la tecla “x”, que mostrará por ejemplo el “8″. La tecla “8″ mostrará el “k”, la “k” el “q”, etc. Esto define una secuencia que podemos describir de la siguiente manera: (1-x-8-k-q-…). Dicho de otro modo, las teclas definen una permutación, que además es aleatoria, del conjunto de 40 caracteres posibles.

Cuando definimos una permutación al azar, es improbable que podamos escribirla por completo en una sola secuencia. Por ejemplo, si resulta que tecla “q” muestra el carácter “1″, se forma la secuencia (1-x-8-k-q-1). Si pulsamos la tecla “1″, volveremos a obtener una “x” y así sucesivamente, quedando atrapados en un ciclo. Para continuar, debemos elegir una tecla distinta de las anteriores, como por ejemplo la tecla “2″, que dará lugar a otra secuencia (o ciclo) diferente. En general, necesitaremos varios ciclos de este tipo para describir la permutación al completo.

Para ilustrar la estrategia a seguir, centrémonos en el primer miembro del equipo, cuya tarea es conseguir que aparezca su carácter en la pantalla, por ejemplo, la letra “q”. Debe comenzar pulsando la tecla “q” correspondiente a su carácter, y avanzar en la secuencia anterior hasta encontrar la tecla que muestre la “q” en pantalla. Por ejemplo, (q-1-x-8-k-q), con lo que habrá encontrado la tecla que muestra la “q” (es decir, la tecla “x”) en cinco pasos. Si todos los miembros del equipo siguen esta estrategia, tendrán garantizado ganar si todos los ciclos de la permutación tienen una longitud menor que 20, que es el número de teclas que pueden pulsar. Si existe algún ciclo de longitud mayor que 20, lo más probable es que algún miembro del equipo fracase.

La probabilidad de que, dada una permutación al azar de 40 elementos, todos los ciclos sean de longitud menor que 20 es de un 32%. El problema se inspira en el conocido como “problema de los 100 prisioneros”, propuesto por Peter Bro Miltersen en 2003. Nuestro lector, Anghlar, se ha dado cuenta rápidamente. Para los más curiosos, un desarrollo matemático del problema original puede encontrarse en esta página.

Es probable que, en este punto, el lector se pregunte: ¿y cómo puedo estar seguro de que voy a encontrar mi carácter en la secuencia? La clave está en que, al empezar por la tecla correspondiente a tu carácter, te aseguras de encontrarlo al final del ciclo, en tantos pasos como la longitud del mismo. Invitamos al lector a dibujar las posibles secuencias, por ejemplo en permutaciones de números del 1 al 10, para ver este fenómeno con claridad. De hecho, esto es lo que proporciona una ventaja a los conocedores de la clave; un jugador que busque un carácter que no conoce no podrá empezar por él, y por tanto no tendrá garantizado “caer” en el ciclo que lo contiene. La probabilidad de éxito en este caso se reduce a un 50% por jugador, como planteaba la youtuber.

Con este reto, presentamos un problema en el que aparentemente la probabilidad de éxito es prácticamente nula, pero para el que existe una estrategia que permite obtener una victoria casi una de cada tres veces. Esto ilustra la importancia de realizar pruebas (matemáticas) de seguridad rigurosas para los protocolos criptográficos, pues si se diseña un protocolo que carezca de tal análisis, es posible que se den ataques devastadores.

Como curiosidad final, estrategias similares de búsqueda de ciclos dan lugar a algoritmos con aplicaciones prácticas importantes, como por ejemplo la factorización de enteros.

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