Aún recuerdo cuando en la escuela aprendíamos las primeras técnicas para resolver problemas, y cómo algunas veces, cuando no nos las sabíamos bien, empleábamos ese infalible método conocido como "la cuenta de la vieja" (o fuerza bruta, como ustedes prefieran) para encontrar las soluciones. Por ejemplo, si se te pedía calcular la raíz cuadrada de 169 y no te acordabas del famoso algoritmo, probabas a calcular el cuadrado de diez, el de once, el de doce... y ¡bingo!

En Criptografía siempre se puede descifrar un mensaje por la cuenta de la vieja, sin necesidad de conocer la clave. Obviamente, basta con probarlas todas, una por una. Incluso si el algoritmo empleado para cifrar es irrompible según el criterio de Shannon esto puede lograrse, aunque en este último caso resulte imposible saber cuál de las soluciones candidatas es la correcta, ya que todos los mensajes descifrados imaginables podrán ser obtenidos si probamos con todas las claves posibles. Cuando existe algún método para descifrar un mensaje con menos esfuerzo que el que requeriría la cuenta de la vieja, se le denomina "ataque". Evidentemente, un ataque no tiene por qué servir para nada en la práctica, ya que puede resultar tan impracticable como la fuerza bruta, pero en cualquier caso representará un atajo que debe ser tenido en cuenta.

La mente humana es muy imaginativa, pero a veces se queda corta. Uno de los problemas más frecuentes con los que me encuentro en mi labor docente es la dificultad de asimilación que para los alumnos presentan algunas cantidades astronómicas. Por ejemplo, me he encontrado en más de una ocasión con la afirmación de que cierto algoritmo puede ser roto fácilmente en la práctica con solo probar... ¡2^512 claves! Esto, que a primera vista parece incluso razonable, demuestra la dificultad que tenemos para hacernos una idea perceptual de lo que representa ese número aparentemente tan inocente. Supongamos que asignamos la tarea de examinar cada una de esas claves a un átomo del Universo, y que cada átomo se toma una milésima de segundo en llevar a cabo su trabajo, quedando luego libre para comenzar con otra clave. Pues bien, si ponemos a trabajar -ahí es nada- a todo el Universo en paralelo, necesitaríamos más de 10^19 años para finalizar la tarea. Teniendo en cuenta que la edad estimada actual del Universo es de 10^10 años -mil millones de veces menos de lo que necesitaríamos-, y que carecemos de tecnología para hacer que los átomos individuales del Universo resuelvan nuestro problema, ¿a alguien le queda alguna duda de que esta tarea no puede ser llevada a cabo hoy por hoy en la práctica?

Pues todavía queda gente que se empeña en afirmar que, como no hay que recorrer todas las posibilidades, se puede tener suerte y encontrar la solución relativamente pronto, si se tiene la suficiente cantidad de suerte. Pero, ¿cuánta suerte es necesaria? Vamos a poner otro ejemplo: imagínense cien mil ordenadores trabajando en paralelo, cada uno de los cuales capaz de examinar un millón de claves por segundo, y que queremos encontrar la solución en, digamos, menos de un año. La red completa examinaría -redondeando hacia arriba- 2^62 claves en dicho tiempo. Eso significa que podríamos verificar únicamente.. ¡una de cada 2^450 posibles soluciones! Incluso si nuestro problema se redujera a buscar entre 2^200 soluciones posibles -un número enormemente inferior-, solo habríamos recorrido una de cada 2^138.

Si recordamos que la probabilidad aproximada, según la Mecánica Cuántica, de que una persona salte contra un muro y lo atraviese de forma espontánea -sin que ninguno de sus átomos colisione- es de 2^-100, vemos que resulta más fácil que saltemos contra un muro, ¡y que aparezcamos al otro lado totalmente ilesos, sin haber chocado contra él! No sé ustedes, pero yo no estoy dispuesto a hacer la prueba...

Lo cierto es que, salvo que aparezcan nuevas técnicas revolucionarias -¿tal vez la Computación Cuántica?-, se puede afirmar que hemos alcanzado los límites de la fuerza bruta. El venerable DES era susceptible a la cuenta de la vieja simplemente porque el número de claves posibles era demasiado pequeño, pero los nuevos estándares, como por ejemplo AES, escapan con mucho a los límites brutos de cálculo de nuestro Universo. Habrá que seguir buscando atajos.

Manuel Lucena
http://wwwdi.ujaen.es/~mlucena

Sacado de Kriptópolis << Altamente recomendable, si te gusta la croptografía.