Criptografía con autómatas celulares y protocolo de cero conocimiento

Abstract

RESUMEN: En la actualidad la criptografía forma parte de nuestra vida cotidiana. Fue el uso de las computadoras y el nacimiento de las primeras redes que las conectaban las que impulsaron la expansión de los servicios criptográficos. Cada vez que realizamos una recepción o envío de datos por internet, se pone en riesgo la confidencialidad de nuestros datos personales. En este trabajo de tesis se propone y desarrolla un sistema de autenticación de una entidad y posteriormente un cifrado y descifrado de datos; usando como herramientas autómatas celulares de una y dos dimensiones, protocolo de cero conocimiento y problemas NP-completo. Para el servicio de autenticación se propone una prueba de cero conocimiento interactivo (ZKIP), la cual tiene como secreto compartido dos grafos con la propiedad de ser 3-coloreables. La salida de dicho algoritmo será un vector que servirá como la llave para el cifrado-descifrado de archivos. En el cifrado y descifrado de datos se hace uso de una matriz que tiene como datos el vector obtenido de la autenticación, repetido $n$ veces, un autómata celular de dos dimensiones, y el archivo que se quiere cifrar-descifrar. La salida del algoritmo será el archivo cifrado-descifrado respectivamente, las cabeceras de los archivos son cifradas lo que origina la pérdida de la identidad del archivo original. La robustez del sistema se encuentra en que la salida del sistema de autenticación forma parte de la entrada del sistema de cifrado y, la intratabilidad computacional de los secretos compartidos dado que son NP-completos. Por último dado que los autómatas celulares son sensibles a las condiciones iniciales, es necesario conocer la configuración inicial del sistema para poder obtener la llave con la que se cifraron los datos y las veces que fue evolucionado.

ABSTRACT: Nowadays the cryptography is a recurrent tool in our daily life. The expansion of cryptographic services was boosted by the use of computer and the creation of a new network which connect them. Every time when we send or receive data on internet, the confidentiality of our personal data is on risk. In this thesis is proposed and developed an entity authentication system, subsequently a data encryption and decryption. These are use as cellular automaton of 1-D and 2-D, zero knowledge protocol and NP-complete problems. For the authentication system, a Zero-Knowledge Interactive Proof (ZKIP) is proposed, which has, two graphs three-coloring as a shared secret. The output of this algorithm will be a vector which will be use as a key for the encryption-decryption of files. In the data encryption and decryption is use a matrix which have as data the value of the vector obtained in the authentication repeated $n$-times, one cellular automaton of 2-D and the file to be encrypted-decrypted. The output of the algorithm will be the file encrypted-decrypted respectively. The headers of the files are encrypted what provoke the lost of the original file. The robustness of the system is on the output of authentication system which is the entry of encryption and decryption system and the computational intractability of the shared secrets due these are NP-complete problems. Finally, due the cellular automaton are susceptible to initial conditions, it is necessary to know the initial configuration of the system to obtain the key which will encrypt the data and the times that the times that was evolving.