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 $\mathsf{NP}$ -completa sería un gran logro en criptografía, ya que $\mathsf{P} \neq \mathsf{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 $\mathsf{NP}$ et $\mathsf{coNP}$ por lo que es poco probable que $\mathsf{NP}$ -completa. Sin embargo, es obvio que en $\mathsf{NP}$ (sólo adivinar la clave privada, y descifrar).
