He oído opiniones y afirmaciones diferentes de distintos profesores y fuentes sobre si "se cree" que descifrar RSA está en NP, o si se sabe que es un problema NP-completo. ¿Puede alguien arrojar luz sobre esta discrepancia? ¿cuál es, o lo sabemos?
Respuesta
¿Demasiados anuncios?Demostrar que romper cualquier criptosistema es NP -completa sería un gran logro en criptografía, ya que P≠NP es probablemente la hipótesis de dureza más "estándar" que existe. En el caso de RSA, la seguridad del sistema se basa en la dureza del problema de factorización de enteros. Este problema se encuentra en la intersección de NP et coNP por lo que es poco probable que NP -completa. Sin embargo, es obvio que en NP (sólo adivinar la clave privada, y descifrar).