Estudio de las cadenas pseudo aleatorias generadas por los autómatas celulares unidimensionales de dos estados, implementación y aplicaciones a criptografía

Abstract

Los autómatas celulares fueron propuestos por Jhon von Newman en el anó de 1936.Él tenia la idea de crear una máquina capaz de autoreproducirse y con la ayuda deStanislav Ulam pudo lograr su objetivo. Más adelante Jhon Conway creo “El Juegode la Vida”, tal vez el autómata celular mas famoso. Algunas configuraciones de esteautómata tienen comportamientos tan complejos como generar números primos. Hacialos anos 80, Stephen Wolfram presenta su estudio sobre autómatas celulares lineales.En 1986 el mismo Wolfram propone la utilización de sus autómatas en la criptografíacomo generadores de sucesiones de bits pseudo aleatorias. Por el lado de la criptografía el proyecto se centra en los sistemas de cifrado en flujo, estos derivan del método propuesto por Vernam, con la diferencia que la sucesióncifrante no es aleatoria sino que se genera pseudo aleatoriamente a partir de una semilla. Se presentan tres métodos de generación de suscesiones pseudo aleatorias de bits. Elprimero es una variación al propuesto por Wolfram con la diferencia que se usan vecindades de tamaño 4 en vez de 3. Este método es inseguro por cuando no presenta ningunobstaculo para evitar el criptoanálisis por clave reusada. El segundo método elimina esta debilidad añadiendo un generador de números pseudoaleatorios de tal manera que no se elige siempre la misma célula sino que permite laelección de diferentes celulas que dependen de una segunda clave llamada “nonce”. Sinembargo este segundo método es muy lento debido a que se necesitan muchas evoluciones de los autómatas para la generación de un solo bit de sucesión cifrante. Finalmente con el método 3 se solucionan los problemas de velocidad presentados elel método anterior mediante la selección de múltiples columnas para el autómata delgenerador de números pseudoaleatorios.