¿Por qué utilizan la factorización principal para el cifrado en lugar de un algoritmo que hemos demostrado que es difícil de resolver?

Necesita más que simplemente “difícil de resolver” para el cifrado. También necesita “problemas fáciles de construir”. Si fuera tan difícil de cifrar como es difícil de descifrar, entonces nunca sería capaz de cifrar nada.

Esa es la esencia de la criptografía de clave pública. Las matemáticas son fáciles de hacer en una dirección, pero difíciles de revertir a menos que sepa algo sobre el problema. El truco es encontrar alguna operación en la que puedas regalar ese “algo” sin regalar todo. Se llaman funciones unidireccionales.

La multiplicación por números primos en módulo aritmético es excelente para eso: es relativamente fácil encontrar inversos si conoce los factores, pero difícil si no los conoce. Hay otros, como logaritmos informáticos (nuevamente, en aritmética modular) y curvas elípticas (en campos finitos). Ambos se usan, pero en ambos casos, la prueba de la dificultad es, eh, difícil.

Si conoce algoritmos con las propiedades correctas y puede probarlo, consiga una patente. Sería muy valioso Pero en este momento, se cree ampliamente que los problemas clave no están en la posibilidad de factorizar fácilmente en las matemáticas ordinarias, sino en las computadoras cuánticas que podrían atacar el problema de una manera probabilística (pero no obstante extremadamente rápida).

La idea principal sobre el cifrado no se trata de elegir un algoritmo difícil de resolver.

Pero se trata de encontrar un algoritmo que sea lo suficientemente simple cuando tenga que usarlo para calcular un resultado:

• Dado un conjunto de valores de entrada, puede calcular fácilmente, en términos de tiempo u operaciones, la salida deseada.

Y dicho algoritmo debería ser muy, muy difícil de hackear:

• Dado un valor de salida, “realice ingeniería inversa” para encontrar los valores de entrada correspondientes establecidos.

Por otro lado, realmente no entiendo qué quieres decir con “algoritmo difícil de resolver”. Podría usar un algoritmo que resuelva un problema simple en la dirección [matemática] entrada \ salida de flecha [/ matemática] y al mismo tiempo produzca un problema bastante imposible en la dirección [matemática] entrada \ salida de flecha. [/ Matemática]

Por ejemplo, el algoritmo RSA resuelve un problema bastante fácil en su camino de entrada a salida (algo de potencia, módulos, etc.) y te deja con un problema muy difícil de resolver al revés (factorizando números grandes y problema RSA) .

Porque hasta hace poco la factorización funciona de manera más confiable que los problemas aparentemente más difíciles.

Criptosistema de mochila Merkle-Hellman: Wikipedia se describió en 1978, el mismo año de RSA, y se basa en un problema que es NP-hard, el problema de suma de subconjuntos, pero se rompió muy pronto, ya que el problema especial que permite un La trampilla de aumento excesivo no tiene la misma complejidad que el problema de suma de subconjuntos en el peor de los casos, y puede romperse polinomialmente por el algoritmo LLL.

El primer criptosistema demostrablemente seguro, basado en una reducción de la complejidad del caso más desfavorable al caso más desfavorable (el criptosistema Ajtai-Dwork), aún dependiendo de la suposición P ≠ NP, es mucho menos eficiente que RSA (y su seguridad ha sido cuestionada) .

Actualmente, se investigan activamente los criptosistemas basados ​​en celosía seguros y probables (según algunos supuestos estándar), y hay candidatos eficientes (alguna variante de NTRU – Wikipedia), actualmente bajo escrutinio para su adopción, en vista de la posible llegada de grandes computadoras cuánticas, eso hará que RSA, Diffie-Hellman y la criptografía de curva elíptica sean inseguros. Existe una recomendación reciente de la NSA de prepararse para cambiar pronto a la criptografía post-cuántica (es decir, protocolos criptográficos resistentes a los ataques de una computadora cuántica).

Ver criptografía post-cuántica – Wikipedia para más información.

Para ser útil para el cifrado, debe ser fácil descifrar un mensaje cuando tiene la clave. Esto significa que el “problema” de descifrado debe ser NP. Actualmente es un problema no resuelto si hay problemas de NP que son “difíciles de resolver”.

Sin embargo, hay problemas de NP que son al menos tan difíciles como cualquier otro problema de NP, como el “problema del embalaje del contenedor”. Se han diseñado esquemas criptográficos que utilizan estos problemas “NP-complete” en su lugar.