El futuro de la criptografía
kub0x:
Hace tiempo que no escribo para este subforo, todavía queda gente interesada en la criptografía e intento participar en las conversaciones. Creo que es útil explicar un poquito para donde está llendo el estudio pues en unos años el que no se renueva ahorá tendrá que hacerlo.
En la década de los 70 se descubrió el concepto de PKC (criptografía de clave pública), destacando el algoritmo de intercambio de claves de Diffie-Hellman y el hecho por Merkle en acertijos o puzzles (está tecnica se sigue utilizado en protocolos de commitment). Más tarde vino RSA, DSA, ElGamal y un poquito más tarde las curvas elípticas. Hoy día entendemos bastante bien el problema del logaritmo discreto en grupos cíclicos, pues un generador de estos grupos tiene un periodo/orden que está estrechamente relacionado con la factorización del orden del grupo. Lo mismo sucede con los residuos cuadráticos, estos permiten la factorización.
Entonces logaritmo discreto y factorización son equivalentes. El problema de la factorización se ha estudiado bastante durante la historia, genios como Gauss, Euler, Fermat, Riemann... dedicaron tiempo a ello y en el s.XX con la llegada de las máquinas, muchos otros a destacar Pollard y Shor se han dedicado a ello también, desde la parte computacional, es decir, como optimizar una máquina para buscar factores de un número. Con la llegada del ordenador cuántico esta tarea es factible para los tamaño de claves utilizados hoy día. Si nosotros aumentasemos el tamaño de la clave el doble, entonces sería resistente. Es decir, un ordenador cuántico de 2048 qubit puede factorizar un semiprimo de 1024 bits utilizado en RSA, si utilizamos un entero de 2048 bit entonces necesitaremos 4096 qubit. No sabemos si en el futuro la capacidad de aumentar qubits es factible, pero vemos que aparentemente existe una relación del doble. Lo mismo pasaría con Diffie-Hellman y derivados.
Con las curvas elípticas sucede que son más veloces a la hora de computar por ser de 128-256 bit. Un ordenador cuántico necesitaria 6 veces más qubit es decir para una de 256 pues 1530 qubits. Vemos incluso que es más factible romper una curva que resolver la factorización.
Desde los 90 se propusieron nuevas variantes del concepto de clave pública, por ejemplo: la criptografía de clave pública no conmutativa, la criptografía de clave pública multivariada, lattices, curvas elípticas supersingulares, criptografía basada en código (code-based). De esta forma, se intenta crear nuevos protocolos y criptosistemas basados en problemas matemáticos existentes o no. Analizando la complejidad de reducir el problema a otro o bien de resolverlo directamente, podemos establecer si el criptosistema/protocolo es seguro y plantear su uso futuro. Suponemos que los anteriormente dichos son resistentes a ataques en ordenadores cuánticos porque no tenemos ninguna solución para ellos, o la que tenemos no es factible ni en un clásico ni en un cuántico.
Estos campos son muy jóvenes, cada vez reciben más atención por parte de la comunidad y empresas como Google, Amazon, Microsoft, CloudFlare, Apple y guvernamentales como la NSA están ya contribuyendo a la implementación de estos. Se espera que para el año 2023 y antes de la década del 2030 anden funcionando dentro del protocolo TLS como cipher suite. El problema que los tamaños de las claves públicas son bastante más grandes que los clásicos ECC, DH, RSA.. pero hoy día la tecnología es capaz de manejarlos rápidamente sin verse afectada, y ya no te digo en el futuro...
Una conclusión bastante aparente es que la información que está siendo intercambiada, la cual es generada por la inmensa mayoría de librerías criptográficas, será legible en un futuro relativamente cercano cuando la cuántica se torne realidad. Evidentemente, la información confidencial se trata de distinta forma, y con tamaños de clave pública que por el momento retrasarían los ataques en máquinas cuánticas, pero es cuestión de tiempo.
Entonces, todo apunta a una transición en la criptografía de clave pública, un plan renove que busca asegurar los tres principios básicos de cara al futuro: confidencialidad, integridad y autenticación.
Para acabar, guste o no, nuestra capacidad de romper y descifrar en criptografía depende enteramente de nuestra habilidad para entender los problemas matemáticos subyacentes. Es imposible crear o destruir sin conocer las herramientas que te lo permiten. Puede que la criptografía sea un campo incomprendido, marginado por la mayoría de instituciones de nuestro país, pero si no estamos a la vanguardia del cambio, será imposible entenderlo, e iremos aun más por detrás.
P.D: El tema va sobre el futuro de la crypto, no cabe mención para el espionaje, backdoors y criptoanálisis realizado de forma indiscriminada por ciertas entidades.
Saludos a todos.
warcry.:
Enigma: un sofisticado sistema con 1.252.962.387.456 combinaciones
Cita de: kub0x en 23 Abril 2020, 14:10 pm
problemas matemáticos subyacentes.
Principio fundamental de la criptografia, y a la vez talón de aquiles, luego el futuro es el mismo que cuando existía la maquina enigma.
obviamente, para que haya una encriptacion y después una desencriptacion tiene que existir un resultado optimo al problema, y por tanto en los modelos matemáticos de criptografia se reduce al tiempo de procesar todas las opciones posibles contra el algoritmo de cifra.
PD: Se agradece leer algo fuera del offtopic
ace99:
Hablando de enigma... Hay una película sobre enigma y Alan Turing muy interesante. Es bastante famosa, e imagino que la mayoría la conoceréis pero no está de más dejar un link al tráiler.
El título es "The imitation game" y está protagonizada por Benedict Cumberbatch.
La podéis encontrar en diversas plataformas como por ejemplo Netflix.
Siento desviarme del tema.
Muchas gracias por leerme. Un saludo
@XSStringManolo:
Pues enigma no fue de lo más eficaz en su día. Debido a que los Alemanes usaban una clave única cada día había días que los ingleses por probabilidad craqueaban la nueva clave bien tempranito y escuchaban todas las comunicaciones cifradas de los alemanes por el resto del día hasta que al día siguiente cambiaban la clave. Por no decir que todas las claves estaban en una libreta por lo que algún alemán podría vendérsela a los ingleses y descifrar las comunicaciones día sí y día también.
Aquí un artículo bastante extenso sobre el tema. http://home.bt.com/tech-gadgets/cracking-the-enigma-code-how-turings-bombe-turned-the-tide-of-wwii-11363990654704
kub0x:
Es bien cierto que Enigma fue un rompecabezas para algunos. Pero hay que tener en cuenta que la matemática en el siglo XIX estaba bien avanzada en teoría de grupos y permutaciones. Enigma es reversible por el poseedor del diseño, la máquina y la configuración, es decir, eres capaz de descifrar con la clave o la configuración de la máquina Enigma, en este caso.
Siempre hago hincapié en la misma frase, pero no sabeís lo importante que es: "Todo criptosistema se puede escribir como un conjunto de ecuaciones lineales o multivariadas (sobre un campo/cuerpo finito)". En este caso, lo mismo sucedió con Enigma. El principio de Kerchoff nos dice que el atacante conoce el criptosistema, pero es seguro pues no tiene vulnerabilidades aparentes. Bueno, una vez los aliados se hicieron con unas cuantas máquinas, manuales y configuraciones, los criptólogos hicieron su trabajo:
Citar
In December 1932, the Bureau provided Rejewski with some German manuals and monthly keys. The material enabled Rejewski to achieve "one of the most important breakthroughs in cryptologic history"[46] by using the theory of permutations and groups to work out the Enigma scrambler wiring.[47][48]
Rejewski could look at a day's cipher traffic and solve for the permutations at the six sequential positions used to encipher the indicator. Since Rejewski had the cipher key for the day, he knew and could factor out the plugboard permutation. He assumed the keyboard permutation was the same as the commercial Enigma, so he factored that out. He knew the rotor order, the ring settings, and the starting position. He developed a set of equations that would allow him to solve for the rightmost rotor wiring assuming the two rotors to the left did not move.[49]
Vamos, que cuando quería recuperar el plaintext para otra configuración, sólo tenía que modificar el sistema de ecuaciones. Resulta que nosotros utilizamos teoría de grupos y permutaciones, entre otros, para hallar el recorrido de la trapdoor-permutation. De esta forma, por ejemplo, en el logaritmo discreto, podemos recuperar el exponente o clave privada. Existe un paper que publiqué el año pasado donde concluyo que el log discreto depende del degree o grado del grupo, el cual, es gigante por lo tanto mi método sólo vale para estudio y/o recreación. Pero es aplicable a cualquier cifrado, o estructura algebraíca cíclica, pues todo grupo es linearizable hacía un algebra lineal mediante la teoría de la representación.
Hoy día, todo esto es ampliamente tenido en cuenta, pues tu puedes hacer un cifrado "que te cagas" y tener una estructura de permitutación débil, pudiendo recuperar el input. Os dejo esta pregunta que respondí en crypto.SE no hace mucho en la que ilustro una forma de encontrar el input de una función sin tener que hacer todo el recorrido, sino sólo trabajando en un ciclo:
https://crypto.stackexchange.com/questions/77970/if-you-iterate-a-cryptographic-permutation-long-enough-will-you-map-the-input-to/77976#77976
Saludos.
Navegación
[#] Página Siguiente