Recientemente, el
material fue publicado en la revista Quanta, en la cual el autor habló sobre un fenómeno que fue sorprendente desde el punto de vista de lectores inexpertos, probado por matemáticos. Su esencia es que casi todos los polinomios de cierto tipo son irreductibles, es decir, no se pueden descomponer. Esta prueba se aplica en muchas áreas de la matemática pura. Pero también esta es una buena noticia para uno de los pilares de la vida moderna: el cifrado digital.
Para el almacenamiento confiable de información digital, el cifrado utilizando el algoritmo RSA es ampliamente utilizado. Esta es una versión animada del esquema que incluso un alumno de séptimo grado puede idear para intercambiar mensajes con amigos: a cada letra se le asigna un número, que se multiplica por una clave secreta previamente acordada. Para descifrar un mensaje, simplemente divídalo en una clave secreta.
El cifrado RSA funciona de manera similar. Damos una explicación muy simplificada. El usuario aparece con un mensaje y realiza ciertas operaciones matemáticas en él, incluida la multiplicación por un número muy grande (varios cientos de dígitos). La única forma de descifrar el mensaje es encontrar factores simples del resultado *.
* *Los factores primos de un número son los números primos que deben multiplicarse para obtener ese número. Entonces, para el número 12 es 2 * 2 * 3, y para el número 495 es 3, 3, 5 y 11.
La seguridad del cifrado RSA se basa en el hecho de que las matemáticas no conocen formas rápidas de encontrar factores primos de números muy grandes. Y si el mensaje encriptado no fue destinado a usted, y no tiene una clave para descifrarlo, entonces los intentos de encontrar esta clave pueden demorar mil años. Además, esto también es cierto para las computadoras más modernas, con la ayuda de las cuales todavía no será posible seleccionar los factores simples correctos.
Pero hay una solución alternativa.
Cada número se puede representar como una ecuación algebraica única. Y, a diferencia de la búsqueda de factores primos de un número, la búsqueda de factores primos de un polinomio es mucho más fácil. Y tan pronto como el polinomio se descompone en tales factores primos, esta información se puede utilizar para buscar factores primos del número original.
Así es como funciona.
Paso uno: elige cualquier número cuyos factores primos necesites averiguar. Para simplificar, tome el número 15.
Paso dos: 15 se traduce a binario:
1111.
Paso tres: esta expresión binaria se convierte en un polinomio al traducir todos los números binarios en coeficientes del polinomio:
(Nota: este polinomio es 15 si x = 2. El número 2 es la base del sistema binario).
Cuarto paso: el polinomio se factoriza:
Paso cinco: x = 2 se sustituye en cada uno de estos factores:
Conclusión: 5 y 3 son factores primos de 15.
Sí, esta es una forma demasiado complicada de encontrar factores simples de un número pequeño como 15, que son fáciles de entender en la mente. Sin embargo, cuando se trata de números grandes que consisten en cientos de números, este método polinomial ofrece una ventaja sorprendente. Para descomponer números primos, no existen algoritmos rápidos. Pero existen tales algoritmos para descomponer polinomios grandes. Por lo tanto, tan pronto como logre convertir un número grande en un polinomio grande, puede acercarse mucho a encontrar factores simples del número.
¿Esto significa que el cifrado RSA está en riesgo? En realidad no Y un nuevo patrón recientemente probado con respecto a los polinomios está conectado precisamente con esto.
Los matemáticos
Emmanuel Brulya y
Peter Varju de la Universidad de Cambridge demostraron que a medida que los polinomios con coeficientes 0 y 1 se hacen más largos, la probabilidad de que se puedan expandir se vuelve más baja. Y si el polinomio no puede descomponerse, entonces no puede usarse para buscar factores simples del número que necesita calcularse.
La evidencia de Brull y Varju en realidad sugiere que una solución alternativa para descifrar el cifrado RSA no lleva a ninguna parte. Los números muy grandes utilizados en RSA corresponden a polinomios muy largos. Los científicos de Cambridge argumentan que es casi imposible encontrar polinomios de esta longitud que puedan descomponerse. Tanto los criptógrafos como los matemáticos han sospechado durante mucho tiempo que esto es así. Sin embargo, cuando la ciberseguridad mundial depende de la imposibilidad de utilizar alguna técnica matemática, siempre es bueno tener pruebas de que esta técnica realmente no funciona.
