No existe un criptosistema cuya seguridad sea equivalente a un problema NP-hard. Ver ¿Están los problemas de descifrado involucrados en los algoritmos de criptografía asimétrica actuales NP-Complete? En particular, no se cree que la factorización de enteros sea NP-hard.
Sin embargo, hay varios problemas difíciles que se utilizan además de la factorización. El ejemplo más común es el problema de logaritmo discreto (DLP) y sus primos, los problemas de Diffie-Hellman (CDH, DDH, etc.). El problema del logaritmo discreto es más o menos: dado [matemática] g [/ matemática] y [matemática] g ^ x [/ matemática] en algún grupo (digamos, los enteros distintos de cero modulo algún primo, o una curva elíptica), para encontrar el exponente [matemáticas] x [/ matemáticas].
Los problemas de Diffie-Hellman son cosas como: dado [matemáticas] g, g ^ x, g ^ y [/ matemáticas], calcular [matemáticas] g ^ {xy} [/ matemáticas]. Los problemas de Diffie-Hellman se pueden resolver si conoce el registro discreto, y si bien esa es la mejor manera de resolverlos, no podemos demostrar que sea el mejor. Esto es algo así como que el problema RSA (encontrar un e mod raíz N ) no es lo mismo que factorizar, pero la gente dice “factorizar” porque esa suele ser la mejor manera de resolverlo.
- ¿Qué es un algoritmo de descubrimiento de ruta de ataque cibernético?
- Actualmente estoy en USACO Gold, pero apenas puedo resolver nada. ¿Qué debo hacer para ser más competente? ¿Dominar el oro es solo una cuestión de aprender toneladas de algoritmos, o necesita más que eso?
- ¿Cuándo debo comenzar a aprender algoritmos de C ++?
- ¿Cuáles son algunos problemas informáticos para los que no existe un enfoque de fuerza bruta?
- ¿Qué algoritmos gráficos (10-15, tal vez) sugeriría que hicieran bien en la programación competitiva?
Hay otros problemas para otros criptosistemas sofisticados: resolver ciertas ecuaciones en muchas variables, o encontrar los vectores más cortos que no sean cero en una red, o eliminar el ruido de ciertos tipos de sistemas de codificación. Ninguno de estos se usa ampliamente, pero pueden ser importantes si se inventa una computadora cuántica, y mientras tanto se usan en ciertos nichos.
Luego, por supuesto, están los problemas más ad-hoc, como “dado y, encuentre alguna x tal que SHA256 (x) = y”.
