¿Existe un formalismo matemático para clasificar la dureza de los problemas difíciles?
En particular, me refiero al tipo de problemas difíciles que normalmente se utilizan en sistemas de cifrado; como la factorización para RSA o el método de la teoría de números utilizado en AES.
Tenga en cuenta que, por un sistema de clasificación, no me refiero a la creencia de que un problema es más difícil que el otro porque ha existido por más tiempo, estoy pidiendo un poco de formalismo.
Sí. Y no.
Las almohadillas de una sola vez son demostrablemente demostrables porque todas las soluciones son igualmente probables. También son totalmente inútiles en casi todos los casos.
RSA y AES son tan diferentes que realmente no son comparables. RSA se basa en la dificultad de ciertos cálculos, mientras que AES no usa las matemáticas en el sentido tradicional. Mezcla los bits muy directamente, por lo que el mejor ataque que tenemos es una fuerza bruta directa en la propia clave. Un ataque "ideal" implicaría encontrar una debilidad en la manera en la que se codificaron los bits, por lo que podría encontrar algún sesgo estadístico que podría ser explotado. Pero eso no es matemática en el sentido de priming factoring. No estás atacando el problema de frente, estás buscando errores sutiles.
Incluso DES, el primer cifrado "fuerte" que hemos tenido, es ininterrumpido en el sentido de que el ataque más fácil es el de fuerza bruta. Simplemente está paralizado por el hecho de que el tamaño de la clave hace que la fuerza bruta sea relativamente fácil.
Encontrar un tipo de cifrado simétrico "irrompible" no es realmente el problema.
Lea otras preguntas en las etiquetas encryption