top of page

Vulnerabilidades en algoritmos de criptografíapost-cuántica

En este artículo hablaremos del fenómeno físico del entrelazamiento de trenzas y de como este fenómeno matemático puede dar como resultado un sistema criptográfico muy interesante que puede ser candidato a un algoritmo resistente a ataques de computación cuántica.

La criptografía es una disciplina que se ocupa de la protección de la información mediante el uso de técnicas matemáticas y algoritmos. Una de las técnicas más interesantes y novedosas de en este campo es la criptografía basada en trenzas. Esta técnica utiliza la teoría matemática de los grupos de trenzas para cifrar y descifrar mensajes.

Entrelazamiento_de_trenzas

La teoría de las trenzas es un área de las matemáticas que estudia la geometría y la topología de las trenzas. Una trenza es un tipo de objeto matemático que se puede representar como una serie de hilos que se entrelazan entre sí. La teoría de las trenzas se utiliza en una amplia variedad de campos, desde la física y la química hasta la biología y la informática.


En este artículo nos centraremos en una aplicación mas particular, la criptografía basada en trenzas. Este tipo de criptografía utiliza la teoría de grupos, mas específicamente los grupos de trenzas para cifrar y descifrar mensajes. Este proceso de cifrado implica tomar un mensaje y transformarlo en una serie de trenzas complejas. Estas trenzas son difíciles de desenredar y de interpretar sin la clave de descifrado correspondiente.


Para cifrar un mensaje utilizando la criptografía basada en trenzas, primero se convierte el mensaje en una serie de bits. Estos bits se utilizan para construir una trenza compleja utilizando la teoría de las trenzas. Esta trenza se utiliza como clave para cifrar el mensaje original.


El proceso de descifrado implica tomar la trenza cifrada y utilizar una clave correspondiente para desenredarla y obtener el mensaje original. La clave se utiliza para realizar una serie de operaciones matemáticas que permiten descifrar la trenza y recuperar el mensaje original.


Grupos de trenzas


Para entender este fenómeno empecemos hablando de qué es un grupo de trenzas con un ejemplo. Supongamos que tenemos 5 hilos y cada uno de estos hilos se puede entrelazar con otros hilos como los que vemos en la figura 1.


Grupo_de_trenzas

En este ejemplo la primera imagen representa a la identidad del grupo donde no se ha realizado ningún entrelazamiento entre los hilos. En la segunda imagen se entrelazó la primera trenza con la segunda y luego la tercer trenza con la primera lo que correspondería al elemento σ1(σ2) −1 , la tercera corresponde a σ1(σ2) −1σ3 y así sucesivamente dependiendo de que entrelazamientos se realicen.


Este fenómeno físico da lugar a un grupo matemático particularmente útil para la criptografía.


Este grupo tiene como elementos todas las posiciones diferentes en las que pueden estar entrelazadas la trenzas (que son infinitas) y una operación sobre este grupo de trenzas consiste en realizar todos los entrelazamientos de las otras trenzas. El ejemplo de la figura 1 corresponde al del grupo B5 que es el grupo de todos los entrelazamientos de 5 trenzas y en general se utiliza el grupo Bn consistente de todos los entrelazamientos de n trenzas.


Operaciones_de_trenzas

Es fácil ver que las operaciones sobre las trenzas forman un grupo donde las operaciones son como las que vemos en la figura 3, donde una operación σ sobre el grupo de trenzas consiste en enredar dos de los hilos de esta trenza y al agregar más operaciones seguimos creando una trenza cada vez más compleja que sigue haciendo parte del grupo. Por otro lado, esta figura nos permite ver que aunque el grupo no es conmutativo algunas operaciones sobre las trenzas son equivalentes como las operaciones σ1σ3 y σ3σ1 de la imagen.


Criptografía basada en trenzas

Propiedad_de_las_trenzas

Usualmente los criptosistemas de clave pública se basan en algún problema que es muy sencillo de resolver en una dirección pero muy complicado de resolver en otra dirección. En el caso de las trenzas este es el problema de la conjugación y el problema de la palabra.



  • El problema sencillo de la palabra consiste solo en generar dos trenzas al realizar diferentes operaciones de entrelazamiento. El problema complicado sería decidir si dos trenzas que se entrelazaron de cierta manera son equivalentes. Esto puede parecer muy similar al fenómeno en la vida real; es muy sencillo enredar varias trenzas pero es muy difícil poder determinar si dos grupos de trenzas enrededadas son similares.

  • El problema de la conjugación: Dado dos grupos de trenzas entrelazados, decidir si son conjugados; es decir, dado x, x′ ∈ Bn encontrar un c ∈ Bn tal que x = cx′ c −1 . El problema sencillo estaría en generar dos trenzas x, x′ y el problema coomplicado estaría en determinar si son conjugados.

Estos son problemas sobre los cuales no se conoce una solución eficiente para todos los casos, lo que ha permitido la creación de sistemas de llave pública como los protocolos del conmutador y los protocolos de conjugado de Diffie-Hellman. Además de esto, este problema no se ha podido resolver de forma eficiente con computadores cuánticos por lo que podría ser un candidato para un protocolo de criptografía post-cuántica, sin embargo no se han hecho estudios suficientes para poder asegurar esto.


Conclusión


Vemos como un fenómeno físico como el entrelazamiento de trenzas que parece completamente aislado de la criptografía nos puede generar un conjunto de problemas matemáticos muy interesantes que pueden dar como resultado criptosistemas de llave pública que se podrían volver muy útiles con el desarrollo de la computación cuántica.







Si deseas tener siempre a la mano el artículo escrito por José Darío Flórez, te invitamos a descargarlo, compartirlo y comentarnos qué opinas al respecto.


Criptografía_basada_en_trezas
.pdf
Download PDF • 482KB


Fuentes




*La imagen inicial usada en esta nota fue tomada de tomada de https://www.google.com/url?sa=i&url=https%3A%2F%2Fli nk.springer.com%2Farticle%2F10.1007%2Fs00209-016-1630-0&psig=AOvVaw3hYd_zt-ZV_a2ujcNuaFyH&ust=169081186481 1000&source=images&cd=vfe&opi=89978449&ved=0CA4QjRxqFwoTCPDa1JvLtoADFQAAAAAdAAAAABAD.

97 visualizaciones0 comentarios

Comments


bottom of page