¿Por qué no puede trabajar hacia atrás con una clave pública para descifrar un mensaje?

Hay funciones unidireccionales en ciencias de la computación (no se ha comprobado matemáticamente, pero serás rico y famoso si prueba lo contrario). Estas funciones son fáciles de resolver de una manera pero difíciles de revertir, p. Ej. es fácil para usted calcular 569 * 757 * 911 = 392397763 en un minuto o dos en una hoja de papel. Por otro lado, si te diera 392397763 y te pidiera que encontraras los factores principales, lo pasarías muy mal. Ahora, si estos números son realmente grandes, incluso la computadora más rápida del mundo no podrá revertir la factorización en un tiempo razonable.

En la criptografía de clave pública, estas funciones unidireccionales se usan de manera inteligente para permitir que alguien use la clave pública para cifrar algo, pero hace que sea muy difícil descifrar el mensaje resultante. Debe leer el artículo de Wiki RSA cryptosystem .

Su pregunta es un poco como esta (con disculpas a Tom Stoppard ): " ¿Por qué puedo agregar la mermelada a mi arroz con leche, pero no volver a batir? "

Algunas operaciones matemáticas son tan fáciles de hacer hacia atrás como hacia adelante. Por ejemplo, puede agregar 100 a un número tan fácilmente como restar 100. Sin embargo, algunos son más difíciles de revertir. Por ejemplo, si tomo x y encuentro g(x) = a(x^5)+b(x^4)+c(x^3)+d(x^2)+ex+f , tengo que hacer simples multiplicaciones y adiciones. Pero regresar de g(x) a x es difícil (de una manera algebraica) ya que no hay una solución algebraica general para un quíntico ecuación . No es inmediatamente obvio por qué ese debería ser el caso (a diferencia de una ecuación cuadrática), pero lo es. Para un ejemplo más apropiado, si le dijera que 34129 y 105319 eran primos (lo que son), podría determinar rápidamente que su producto era 3594432151. Sin embargo, si le pidiera que encontrara los dos factores principales de 3594432151 Probablemente te resulte más difícil.

La criptografía de clave pública toma un par de claves. En general, la clave privada proporciona a los parámetros un algoritmo difícil de revertir que va en una dirección (por ejemplo, texto sin formato a texto cifrado), y la clave pública proporciona parámetros para un algoritmo difícil de revertir que va en la otra.

Entonces, la razón por la que no puedes trabajar hacia atrás es simplemente porque el algoritmo está diseñado para hacer esto difícil.

Hacer malabares es fácil: simplemente lanzas las bolas en el momento adecuado, de modo que tengas una mano libre cuando caigan. Con una o dos bolas, esto es trivial. Con tres, es bastante fácil. Con más bolas, (sorprendentemente) se vuelve más difícil. Incluso sustancialmente más difícil.

En general, el cifrado "inverso" realizado con una tecla n -bit es como hacer malabares con 2 bolas ⁿ . Con una clave de 2048 bits esto es como 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 bolas. O así.

(Por supuesto, dado que los algoritmos de clave pública utilizan una gran cantidad de estructura matemática, las mentes inteligentes han aprovechado las matemáticas para reducir ese número de bolas a 162259276829213363391578010288128, que es considerablemente menor, pero aún muy lejos del poder agregado de todas las computadoras existentes en la Tierra .)

Max, la mejor herramienta que se haya creado para pensar en la criptografía es el cubo de Rubik. Si presume que un mundo donde resolverlos es un problema no resuelto, hay análogos directos para DiffieHellmanKeyExchange, firmas RSA, cifrado RSA, etc. Puede jugar trucos escribiendo movimientos y ejecutándolos en cubos e intercambiándolos; y las ecuaciones de la teoría de grupos son las mismas para los cubos criptográficos y rubiks.

Pero hay que tener en cuenta la clave, que creo que es lo que te debe molestar: tienes razón. Es "posible" invertir todas estas operaciones. Técnicamente, tenemos f (x) y f_inverse (x), donde f (x) se ejecuta en tiempo polinomial (es decir, puede cifrar grandes números rápidamente), mientras que f_inverse (x, s) se ejecuta en tiempo exponencial (es decir: incluso medio los números no son factibles) - a menos que tenga los secretos correctos para agregarlos a f_inverse. Tales pares de funciones se llaman trampillas. Las trampas comunes son problemas de la teoría numérica, como la factorización prima y los logaritmos discretos.

Lo que debe hacer es leer sobre criptografía de clave pública. La respuesta corta es que se basa en un algoritmo que permite que una clave se cifre y la otra clave para realizar el descifrado, por lo que no puede trabajar hacia atrás.

Esa es una explicación simplificada de lo que está sucediendo. Si desea llegar al fondo del problema, puede consultar fuentes como las siguientes, pero tenga cuidado, ya que rápidamente se adentra en algunas matemáticas que pueden o no no le será fácil seguir: enlace

En este cifrado de clave pública (o en una inscripción asimétrica), para cifrar algo, haga lo siguiente:

Lleve su mensaje para transmitirlo (como un número): digamos que es 5.

Calcule 3 ^ 5 (3 elevados al "secreto") = 243

Calcule su módulo, dividido por otro número: digamos 143. Entonces, 243/143 = 100.

Ahí tienes. Tu secreto encriptado es 100.

Para encontrar el secreto, sin la clave privada, solo necesitas encontrar un número que, cuando esté dividido por 143, deje 100 como resultado, y luego encontrar su raíz cúbica.

En general, no puede trabajar al revés, de la manera obvia, porque no tiene suficiente información.

RSA depende de la dificultad de factorizar números grandes. Usted genera su módulo RSA n al multiplicar dos primos grandes, p y q. Multiplicar p por q es fácil. También puede revertir la operación calculando q = n / p (o p = n / q ). Lo que no puede hacer fácilmente es deshacerse de p y q, luego calcularlos a partir de n. Ese es un problema diferente, no una reversión de algún proceso que ya ha utilizado.

De forma similar, el cifrado RSA de un mensaje m mediante la clave de cifrado e implica el cálculo de (m ^ e) mod n . Teóricamente podría invertir m ^ e usando registros, pero sin la operación de módulo, este número sería demasiado grande para trabajar. En cualquier caso, la operación de módulo descarta parte del número, por lo que, de nuevo, no tiene toda la información que necesitaría para trabajar hacia atrás de manera trivial.