La seguridad de los métodos de criptografía asimétrica se basan en la actualidad en la complejidad para la inversión de funciones de un sólo sentido. Estas funciones son funciones cuyo cálculo directo (encriptación) es fácil, poco tiempo computacional, pero sin embargo su inversión (desencriptación) es una tarea prácticamente imposible a no ser que se conozca una "trampa" que la simplifica. Tradicionalmente esa trampa es la factorización en números primos de la clave (por simplificarlo de alguna forma).

A medida que pasa el tiempo y crece la potencia de cálculo y se refinan los métodos de factorización lo que se hace es parchear el método mediante la utilización de claves mayores para evitar los ataques a fuerza bruta. Se supone que a día de hoy estos métodos sólo son vulnerables a los ataques a fuerza bruta si el tamaño de la clave no se ha elegido lo suficientemente grande, los números primos elegidos no son suficientemente robustos y el generador de números aleatorios tiene alguna tara.

Esto cómo tal es un parche ya que lo que hace es evitar los ataques a fuerza bruta, pero no evita que si se descubre un método que permita la factorización de número primos en tiempo polinomial (o el cálculo de logaritmos discretos que es otro de los métodos utilizados para asegurar que el proceso de inversión sea intratable computacionalmente) dichos métodos se vuelven completamente inútiles.

El problema reside en que nadie ha demostrado que no haya un atajo a la solución de estos problemas, ni tampoco todo lo contrario. Es decir por el momento son seguros pero no se sabe hasta cuando o si lo serán siempre con la salvedad de incrementar el tamaño de las claves cada cierto tiempo. Bueno en realidad en cuanto los ordenadores cuánticos sean una realidad estos métodos de encriptación no serán seguros.

Kurt Gödel fue un matemático que en los años 30 se ganó a pulso el "odio" de sus colegas al demostrar que las matemáticas no tienen solución para todo. Es decir, que existen problemas con solución a los que las matemáticas no pueden dar una solución. Este teorema es el Teorema de incompletitud de Gödel.

Desde un punto de vista matemático si se pudiera encontrar una función verificando que dicha función es invertible si y sólo si se dispone de la trampa el proceso de desencriptación sólo sería posible si se conociera la trampa (clave). Es decir que en caso de no disponer de dicha trampa sería imposible invertir dicha función y cuando nos referimos a la imposibilidad de inversión queremos decir que no es posible de ninguna forma, ni siquiera por un ataque a fuerza bruta.

El Teorema de incompletitud de Gödel nos asegura que dichos problemas existen, pero no que tengan un aplicación práctica para la criptografía, ni nos dice como encontrarlos.