Un pilar resquebrajado en ciberseguridad

La historia cuenta que César, para intercambiar mensajes secretos con sus generales en el campo, solía rapar a sus mensajeros y escribir el mensaje en sus cueros cabelludos. Luego esperaría unos meses a que su cabello volviera a crecer y los enviaría a sus destinos. Solo sus generales de confianza conocerían este método para intercambiar mensajes, entregando así sus órdenes de forma segura (aunque con unos meses de retraso).

Este ejemplo poco práctico y bastante tonto describe de qué se trata la criptología. La criptología es la ciencia de asegurar la comunicación. El término está tomado del griego kryptós ("oculto, secreto") y lógos ("palabra"). En esencia, se trata de "ocultar palabras". Es solo un pilar en la ciencia de la ciberseguridad, pero es importante. En la base de este pilar se encuentran las subdivisiones de la criptología: Criptografía y Criptoanálisis. Los dos casi pueden verse como complementarios. Donde la criptografía es la práctica de transformar las comunicaciones en una forma que es ilegible para los espías, el criptoanálisis es la práctica de tratar de desentrañar esos mensajes transformados por un destinatario no deseado.

Y es aquí, en la base de este pilar, donde una prueba de un problema podría provocar el colapso de la Ciberseguridad.

Entonces, ingrese al Panteón, este templo de la Ciberseguridad si lo desea, y déjeme guiarlo hacia donde comienzan a mostrarse las grietas en las columnas corintias.

Hay muchos algoritmos diferentes diseñados para mantener los mensajes seguros. Les voy a contar un poco sobre algunos de esos sistemas para que quede clara la base de estos algoritmos.

Si ha leído algo sobre criptografía, es probable que haya encontrado un concepto llamado "cifrado César". Este es otro ejemplo de un método utilizado para proteger los mensajes. También se le atribuye a César, aunque este no involucra las cerraduras de un mensajero (nunca mejor dicho) para mantener el mensaje seguro. En cambio, este cifrado introduce un concepto importante en el que se basa una parte significativa de los algoritmos criptográficos: la aritmética modular.

Sé que sé. Suena aterrador, ¿verdad? ¿Y si te dijera que es tan simple que lo usas todos los días? Mira, tu reloj también se basa en aritmética modular. Cuando intenta calcular cuánto dormirá si tiene que despertarse a las 06:00, ya que está terminando ese plazo a las 23:00, sabe que no debe contar más allá de las 24:00 . El resultado siempre va a ser menos de las 24:00. Básicamente, está calculando el módulo 24. Esta es la aritmética modular y se usa ampliamente en criptografía. Sin embargo, incluso en su simplicidad, la aritmética modular guarda muchos secretos que no son inmediatamente evidentes. Muchos algoritmos criptográficos se basan en estos secretos.

El cifrado de César es un cifrado simétrico. Esto significa que ambas partes usan la misma clave. Digamos que la clave es 3. El remitente cambiaría cada letra de su mensaje por 3. Esto se llama encriptación. El receptor necesita conocer la clave y luego retrocedería cada letra en 3, obteniendo el mensaje original. Esto se llama descifrado. Compare esto con el método del mensajero calvo. El cifrado es dejar crecer el cabello del mensajero sobre el mensaje, el descifrado es afeitar al mensajero calvo.

Ahora bien, ¿es muy seguro el cifrado César? Bueno en realidad no. Cualquiera puede probar fácilmente todas las diferentes claves, de las cuales hay 26 en total, y encontrar la correcta para desentrañar el mensaje. Esto se llama ataque de fuerza bruta. Si bien el cifrado no es muy seguro, se adhiere a un principio importante al que los mensajeros calvos de César no se adhieren. El principio de Kerckhoff establece:

"Un cifrado no debería requerir secreto, y no debería ser un problema si cae en manos enemigas".

En otras palabras, el principio establece que solo la clave debe permanecer en secreto. El método puede hacerse público, pero sin la clave, el mensaje debe permanecer seguro.

Si el mensajero anteriormente calvo de César es interceptado por el enemigo y el interceptor es consciente del método utilizado por César, el pobre mensajero volverá a ser calvo afeitado en poco tiempo, revelando el mensaje en su cuero cabelludo. Sin embargo, con el cifrado de César, incluso si el interceptor conoce el método de cifrado, aún tendría que probar 26 claves diferentes para descubrir el mensaje.

El cifrado de César es uno de los cifrados más simples que existen, pero su simplicidad demuestra muy bien los aspectos de la aritmética modular. Otros criptosistemas simétricos comunes son DES, 3DES y AES. Esencialmente hacen lo mismo que el cifrado de César, aunque mucho más complejo y más difícil de usar la fuerza bruta. Si desea leer más sobre estos sistemas, le recomiendo leer el AES Comic .

Introduzcamos otro concepto importante. Criptografía asimétrica (o criptografía de clave pública). La diferencia es que en lugar de que las dos partes tengan la misma clave, tienen sus propias claves públicas y secretas.

Antes de sumergirnos en RSA, aquí hay un dato interesante para usted. Cuando Ron Rivest, Adi Shamir y Leonard Adleman inventaron RSA, era ilegal que exportaran el algoritmo o incluso su descripción, como parte del control de municiones en los EE. UU. RSA se consideraba tan poderoso que debía mantenerse en secreto militar. Como protesta por la libertad de expresión, usaron camisetas con el algoritmo impreso en convenciones y charlas.

RSA es el criptosistema de clave pública más popular. Es un sistema genial que ilustra perfectamente en qué se basa gran parte de la criptografía moderna. Vamos a ponernos un poco técnicos aquí, pero tengan paciencia conmigo.

El teorema fundamental de la aritmética establece que cualquier número positivo puede representarse exactamente de una forma como producto de uno o más números primos. Por ejemplo, el número 77 se puede representar mediante la multiplicación de 7 (primo) y 11 (primo). No hay otra forma de representar el 77 en números primos aparte de cambiar el orden de los números primos. Tenga esto en cuenta mientras explico RSA.

Antes de que se pueda enviar un mensaje, necesitamos hacer alguna configuración. Digamos, Bob quiere enviar un mensaje a Alice y hay un espía llamado Eve. Alicia, como receptora, elige dos números primos grandes. Ella multiplica estos dos números para obtener el resultado m, el módulo. Vamos a mantenerlo simple y pequeño en nuestro ejemplo. Alice elige 7 y 11 como números primos, lo que da como resultado el módulo 77. Publica el módulo 77 y algún exponente de cifrado elegido e. La combinación del módulo 77 y el exponente de cifrado e se denomina clave pública.

Con la clave pública de Alice, Bob puede encriptar el mensaje que quiere enviar. En este caso, el mensaje es un número x. El cifrado en RSA se realiza tomando x^e mod m. Esto da como resultado el texto cifrado y y lo envía a Alice.

Ahora, Alice puede hacer algo de magia con los factores primos 7 y 11, lo que da como resultado una información llamada d (para descifrar). Esta es la clave secreta de Alice. Todo lo que Alice tiene que hacer ahora es tomar y^d, lo que resultará en el mensaje original de Bob x.

¡Uf, eso fue mucho, pero la parte difícil ya pasó! Ahora, observe que solo Alicia conoce los factores primos 7 y 11. Esto significa que solo Alicia puede hacer ese truco de magia para obtener información d. Pero si eres agudo, no estarías de acuerdo con el mero aquí. Dirías: "Como 77 está publicado y todo el mundo tiene acceso a él, Eve puede deducir fácilmente que 77 = 7*11 y hacer el truco de magia también para obtener d, con lo que puede obtener el mensaje original x". Estaría de acuerdo contigo aquí. Entonces te diría: "¿Cuáles son los números primos del número 30142741". Lo más probable es que no puedas decirme la respuesta. Sin embargo, puedo decirle fácilmente la respuesta, ya que todo lo que hice fue tomar dos números primos y multiplicarlos para obtener 30142741. Y si le dijera esos dos números, podría verificar fácilmente que el producto es 30142741. De hecho, RSA depende de que Eve (o usted) no pueda encontrar esos dos números primos. En este caso, los primos son 6037 y 4993. ¿Ves lo difícil que es la factorización de primos, pero lo fácil que es verificar los primos correctos?

¡Eso es todo! Finalmente estamos en la base del pilar. ¿Ves las grietas? Probablemente no. Déjame aclarar.

Por lo tanto, las transformaciones que aplicamos al mensaje (cifrado) deben ser invertibles para que el receptor pueda descifrarlo. El receptor puede invertir el mensaje porque está en posesión de alguna información adicional. Mientras tanto, cualquier interceptor que no esté en posesión de esa información no podrá descifrar el mensaje. En RSA, por ejemplo, el interceptor necesitaría encontrar los dos factores primos del módulo. Encontrar los dos factores primos de un número pequeño como 77 es, por supuesto, fácil, pero la descomposición en factores primos se vuelve mucho más difícil cuando se elige un número grande. Verificar que los dos primos son factores del módulo siempre es relativamente fácil ya que solo haces multiplicaciones.

Si la factorización prima fuera fácil o si hubiera un algoritmo que pudiera resolver el problema relativamente rápido, RSA quedaría obsoleto. Se basa en que la factorización prima es difícil de resolver, pero fácil de verificar. Podemos hacer una distinción entre dos conjuntos de problemas. Hay problemas para los que conocemos una forma de encontrar la respuesta rápidamente, por ejemplo, la multiplicación o el cuadrado. Este conjunto se llama "clase P". La otra clase, "NP", es un conjunto de problemas para los que no hay formas conocidas de encontrar una respuesta rápidamente, pero cuando tiene alguna información, la respuesta es fácilmente verificable. La factorización prima pertenece a esta clase.

Pero, ¿y si hay una manera de resolver fácilmente un problema de descomposición en factores primos? Esto implicaría que la descomposición en factores primos pertenece a la clase P. De hecho, tal vez podamos probar que todos los problemas NP son en realidad problemas P. La conclusión sería que P = NP.

Esta conclusión tendría consecuencias desastrosas para la criptografía. Como hemos visto, RSA se basa en que la factorización prima es difícil de resolver. Pero RSA es solo uno de los muchos algoritmos que se basan en problemas NP y la factorización prima es solo un ejemplo de un problema NP. Otros cifrados simétricos y asimétricos utilizados para sus transacciones financieras, su comunicación por correo electrónico, etc. quedarían obsoletos.

Bitcoin y otras criptomonedas también sufrirían graves consecuencias, ya que Bitcoin se basa en el hash criptográfico, específicamente, el algoritmo hash SHA-256. Para que se acepte un nuevo bloque en la cadena de bloques, este nuevo bloque debe contener una prueba de trabajo. En resumen, la prueba es fácil de verificar para cualquier nodo de la red, pero generar el número correcto es extremadamente difícil.

La prueba de P = NP podría, por otro lado, tener consecuencias positivas para otros campos. Muchos problemas matemáticos siguen siendo difíciles de resolver. ¡Imagínese los efectos que podría tener en las matemáticas!

La prueba de P ≠ NP significaría que nuestros algoritmos criptográficos son seguros y que el título de este artículo es solo clickbait. ¡Pero al menos te ofrecí la oportunidad de ganar un millón de dólares! Esa es la recompensa que el Clay Mathematics Institute otorgará a la primera persona que resuelva el problema "P vs NP".

Entonces, ¡pruébalo! Tal vez usted podría ser el que rompa la criptografía moderna y nos haga volver a usar mensajeros calvos para nuestra comunicación diaria.

También publicado aquí