Un vídeo sobre un peculiar algoritmo para solucionar el cubo de Rubik, grafos y ataques criptográficos

Este curioso vídeo de Polylog es un curioso crossover entre dos de mis temas favoritos: el cubo de Rubik y la criptografía. Explica cómo utilizar la técnica Meet-in-the-Middle («Encontrarse a medio camino») para resolver un cubo de Rubik. Esta técnica se emplea para atacar algunos algoritmos criptográficos, y no es precisamente la ideal para resolver el cubo. Pero sirve para hacerse una idea de cómo funciona este tipo de ataques convirtiendo un ataque imposible por fuerza bruta en otros dos más pequeños que sí son factibles. El vídeo está además estupendamente ilustrado con muy buenas animaciones.

La cuestión es que enseña a ver los movimientos del Cubo como un grafo, algo que puede suceder en otras situaciones, en el que unas posiciones (vértices) llevan a otras con cada giro, en un grafo que podría ser equivalente al de una red social o al de la teoría de los seis grados de separación. Encontrar la solución sería ir de la posición A (mezclado) a la B (resuelto) recorriendo el camino óptimo que tenga menos pasos. Y eso muchas veces puede hacerse, aunque depende de la complejidad y el número de vértices y caminos.

Contamos con una ventaja: para el Cubo de Rubik tradicional de 3×3×3 sabemos que 20 es el número máximo de movimientos necesario para resolverlo de forma óptima. Ojo a los matices, que mucha gente se lía: es el número máximo para resolverlo de forma óptima, que no el mínimo –que pueden ser muchos menos si el cubo está casi resuelto– ni el máximo absoluto –que puede ser infinito si te pones a hacer el tonto girando siempre la misma cara–. El número total de posiciones distintas de un cubo se sabe desde la antigüedad que es 43.252.003.274.489.856.000 (unas 1020).

El problema es que usar la fuerza bruta para llegar a todas las posiciones no sirve porque 1020 es un número un poco inabarcable; que esto es un juguete, no un satélite espía enemigo en el que invertir millones y millones. Pero curiosamente la forma de abordarlo con la técnica Meet-in-the-Middle permite explorar todas las posiciones a las que se pueden llegar con 10 movimientos desde el cubo mezclado (unas 1010) y al mismo tiempo las 1010 posiciones a las que se pueden llegar desde el cubo resuelto. Como está demostrado que el máximo necesario son 20 movimientos, eso quiere decir que si se solapan esos grafos alguna de esas posiciones (que ocupan unos 80 GB, así que se necesita mucha RAM) coincidirá. Se toma un camino del primera grafo, otro del segundo y esa será el camino ideal a la solución. Problema resuelto. Nota: esto solo funciona si el número de posiciones crece de forma suficientemente exponencial.

Incidentalmente, resulta que así es como se atacan criptográficamente sistemas de cifrado como el DES (con una clave única de 56 bits), calculando los dos grupos de 228 bits (algo más abarcable) y solapándolos. Por esta razón se quedó obsoleto y se inventó el Triple DES que usa 168 bits (3×56).

Ya lo hemos dicho antes: este algoritmo Meet-in-the-Middle no es óptimo por poco práctico –muchas veces la fuerza bruta no lo es– pero enseña algunas cosas interesantes. El código puede verse en Github (Rubik MITM Solution) donde se cita a Cube Explorer como sitio en el que encontrar algoritmos mucho más rápidos basados en otras ideas.

En God’s Number is 20 puede leerse algo más sobre cómo se resolvió el problema del número máximo de movimientos y en un vídeo de J Perm se explica lo del conteo de las 4,3 ×1019 posiciones distintas de un cubo 3×3×3.

Relacionado:

Una forma alternativa de cronometrar cómo se resuelve un Cubo de Rubik
Un cubo de Rubik completamente funcional fabricado única y exclusivamente con piezas de Lego
Récord Guinness: resolver tres cubos de Rubik a la vez
Un cubo de Rubik que levita en el aire mientras se resuelve
Rubik’s Impossible: un cubo cuyas pegatinas cambian de color
Gregoire Pfennig, creador de cubos de Rubik y del 33 × 33 × 33
El puzle de piezas que cambian de color, de Clemens Habitcht
Un cubo de Rubik tamaño 32.768 x 32.768 x 32.768 que se resuelve (¡fácilmente!) en 7.000 millones de movimientos
VisualCube, un generador gráfico de imágenes de cubos de Rubik
Molecube, el cubo de Rubik + sudoku
Scrambled: un cortometraje de animación protagonizado por un cubo
La primera Academia Internacional del cubo de Rubik, en A Coruña
Nuevo récord resolviendo 3 cubos a la vez «haciendo malabarismos»
Feliks Zemdegs bate nuevamente el récord con 4,22 segundos
Una máquina que resuelve el cubo de Rubik en 0,38 segundos
Cubestormer 3: resuelve el cubo de Rubik en poco más de 3 segundos
El Multicuber 999: un robot de Lego que resuelve el cubo 9x9x9
Récord de Europa del cubo de Rubik 3x3x3 «a ciegas»
Esto es lo que ve un experto mientras resuelve el cubo en 9 segundos
El método Fridrich para resolver el cubo de Rubik
La segunda juventud del cubo de Rubik, artículo 30º aniversario
Resolviendo Rubiks colosales de hasta 20×20×20
Resolver el Cubo de Rubik: mi explicación en un PDF con ilustraciones y todo tipo de detalles. Es uno de los más tradicionales (primitivo e ineficiente), pero fácil de aprender. Permite resolverlo en <60 segundos

# Enlace Permanente

Deja una respuesta

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