1 Encuentro de Investigación en IE, 25 — 26 de Marzo, 2010

Evaluación de un generador de números aleatorios M. Mejía-Carlos a, J. S. Murguía a

, G. Flores Eraña a

a, b

Instituto de Investigación en Comunicación Óptica, b

Departamento de Físico Matemáticas

Universidad Autónoma de San Luis Potosí, correo-e: [email protected], [email protected] Resumen — En este trabajo se presenta la evaluación de un generador de números aleatorios implementado numéricamente basado en la sincronización en autómatas celulares, los cuales evolucionan bajo la regla 90. Con el fin de evaluar el desempeño del generador se le aplicó el conjunto de pruebas estadísticas, NIST, obteniendo resultados favorables. Abstract — This paper presents the evaluation of a random number generator implemented numerically based on cellular automata synchronization, which evolves under rule 90. In order to evaluate the performance of the generator was applied a set of statistical rules from NIST, obtaining favorable results. Descriptores — Autómata celular, números aleatorios, pruebas estadísticas, sincronización.

L

I. INTRODUCCIÓN

OS números aleatorios son uno de los principales ingredientes para un gran número de aplicaciones en criptografía, simulación, juegos, muestreo, etcétera. Un generador de números ya sea aleatorio o pseudoaleatorio tendrá sus ventajas tales como la aperiodicidad, ser impredecible, ser independiente, con un alto nivel de seguridad, entre otras, así como sus desventajas de ser lento e ineficiente, con secuencias no reproducibles, alto costo del generador, posibilidad de manipulación, etcétera. En muchos sistemas de encriptación los generadores pseudoaleatorios son utilizados para la generación de llaves, las cuales son generadas a partir de una semilla inicial, la cual es reproducible si se utiliza la misma 

semilla. En los últimos años, se ha notado una relación interesante entre el caos y la criptografía ya que los sistemas caóticos tienen propiedades atractivas (ergodicidad, sensibilidad a condiciones iniciales, propiedades mezclantes, etc.), las cuales son útiles para los criptosistemas y la generación de números pseudoaleatorios. Actualmente existe un gran número de sistemas de encriptación, donde su principal objetivo es el de proteger información por medio de un algoritmo que hace uso de una o más llaves. Muchos de estos sistemas sacrifican el tiempo de procesamiento para tener un encriptador más confiable o viceversa, el encriptador es menos confiable pero se logra un menor tiempo en el proceso de encriptado y desencriptado, y en algunos casos la información se encripta de manera parcial. En la implementación de muchos sistemas de encriptación se han utilizado diferentes esquemas con un enfoque caótico con la finalidad de dar mayor robustez y seguridad a la información que se va a cifrar. Por ejemplo, en [1] se emplea el fenómeno de sincronización de autómatas celulares para implementar un sistema de encriptación y se prueba que el generador de llaves tiene buenas propiedades estadísticas. Con el fin de verificar el desempeño del generador de llaves, en este trabajo se presenta la evaluación de la implementación numérica del generador con la ayuda del conjunto de pruebas estadísticas establecidas de la NIST. II. TRANSFORMACIÓN DE SECUENCIAS

BINARIAS Dos sistemas dinámicos acoplados sincronizan si,

2 Encuentro de Investigación en IE, 25 — 26 de Marzo, 2010

después de un largo período de tiempo, sus comportamientos consiguen estar arbitrariamente cerca. Esto es, en cada paso de tiempo ambos sistemas evolucionan de acuerdo a la misma regla. En el caso de autómatas celulares existe la sincronización como el resultado de un acoplamiento no trivial. El acoplamiento en autómatas celulares sucede cuando un conjunto determinado de coordenadas (coordenadas acopladas) es copiada de uno de los sistemas el cual es el autómata celular manejador, al sistema de respuesta que será el autómata celular de respuesta. Esto es, en cada paso de tiempo ambos sistemas evolucionan de acuerdo a la misma regla, y las coordenadas acopladas del autómata celular manejador son copiadas a las correspondientes coordenadas del autómata celular de respuesta. En la Figura 1 se muestra un ejemplo que ilustra el acoplamiento unidireccional en autómatas celulares.

Figura 1. Ejemplo de un acoplamiento unidireccional. Considerando está sincronización con autómatas celulares en [5] se implementó una unidad encriptadora de la cual se construyen 2 familias de permutaciones, Ψ y Φ, de palabras binarias de longitud finita de 2k − 1 , k ∈ ¢ . Estas permutaciones son usadas para encriptar y desencriptar N bloques de longitud 2k − 1 , k ∈ ¢ . Tal fenómeno de sincronización nos permite la construcción de la función llamada función h, la cual se utiliza para la generación de llaves. La Figura 2 muestra la unidad encriptadora (cuadro formado con líneas punteadas), mediante la cual se definen las permutaciones Ψ, Φ y la función h. Se puede observar la evolución de la unidad a partir de las coordenadas acopladas x00 y x N0 + 1 , identificando las palabras x, y, m, c y t.

Figura 2. Unidad encriptadora cuya regla local es AL ( xi − 1 , xi , xi + 1 ) = ( xi − 1 + xi + 1 ) mod 2 , la cual corresponde a la regla 90 de autómatas celulares. Para generar la función t = h( x, y ) , la cual denominaremos también como función h, se hace evolucionar el autómata hacia atrás, utilizando como entradas las palabras x y y. En [2] se hace uso leyes y teoremas del álgebra booleana para reducir estas funciones a un algoritmo de un solo tiempo de manera que cada ciclo de reloj se ejecute una función completa, y no una vez la regla del autómata. La Figura 3 muestra la transformación de secuencias utilizando la función h. La transformación funciona como un generador de llaves pseudoaleatorias, donde se empieza programando las semillas iniciales Semilla 1 de 15 bits y Semilla 2 de 16 bits generando la primer llave x0 de 15 bits. A partir de este valor se inicia la generación de manera recursiva, donde x0 pasa a ser el valor de la entrada x y el primer valor de x, que en este caso es la Semilla 1, pasa a ser la parte menos significativa del siguiente valor de y. Ya que el valor anterior de x es de 15 bits, el bit más significativo del valor actual de y es completado con el bit menos significativo del valor anterior de y. Con estos nuevos valores se genera la siguiente llave, y así sucesivamente utilizando xk + 2 = h( xk + 1 , xk ) .

3 Encuentro de Investigación en IE, 25 — 26 de Marzo, 2010

propósitos, como un buen generador de números pseudoaleatorios. Por otra parte, la Figura 6 nos muestra la relación entre los números en el instante n y los números un instante anterior n-1. El número de datos a considerar fue de 100000, pero para propósitos de visualización se muestran solo 35000. Se puede apreciar que no se tiene correlación entre las muestras debido a que se tiene una distribución uniforme. En caso de existir una correlación, se tendría una agrupación de los datos asemejándose a una recta.

Figura 3. Ilustración del generador de llaves. III. EVALUACIÓN DEL GENERADOR La implementación numérica del generador de llaves se realizó bajo el ambiente de LabVIEW, facilitando la generación de archivos con diferentes números de llaves con diferentes semillas iniciales, tanto en modo texto como en binario. Debido a que el generador de llaves es prácticamente la principal parte de un sistema de encriptación, se le realizaron algunas pruebas con el fin de establecer que la versión del generador considerado no sea computacionalmente predecible. En un principio al generador se le aplicaron algunas pruebas como la determinación del histograma en una dimensión para observar la distribución de los datos, la correlación entre los datos y la transformada de Fourier para ver sus propiedades espectrales.

Figura 5. Histograma de una secuencia de 1 millón de enteros y su respectivo perfil. La Figura 5 muestra el histograma en el rango 10 - 60 y el perfil del histograma de una secuencia de un millón de enteros de 15 bits cada uno. Se puede apreciar que su distribución de los datos es una dispersión del tipo gaussiana, lo cual podemos considerar, para nuestros

Figura 6. Distribución de los números en los instantes n y n – 1. Por otra parte, se calculó la transformada de Fourier a la misma secuencia de 100000 muestras, donde la Figura 7 muestra la transformada de Fourier normalizada de la secuencia considerada y su respectivo perfil. Se puede observar que los datos tienen un espectro extendido, es decir, están distribuidos en todas las frecuencias de manera uniforme y no se repiten en alguna frecuencia en particular. Los mismos cálculos se realizaron para un número mayor de muestras obteniendo resultados similares. Por lo que se puede decir que las secuencias generadas con esta versión tienen un buen comportamiento aleatorio, cuya distribución de datos es uniforme, sin correlación y no se repiten en alguna frecuencia en particular.

4 Encuentro de Investigación en IE, 25 — 26 de Marzo, 2010

15.-

Figura 7. Transformada de Fourier y su respectivo perfil de una muestra de 5000 datos en el intervalo 5500060000.

The Random Excursions Variant Test

Para las pruebas estadísticas, se generaron 100 muestras de 106 secuencias de bits, donde cada secuencia se genero a partir de una semilla aleatoria. Para cada prueba se calculo la proporción de secuencias que pasaron la prueba, en el cual la proporción debe estar arriba del valor de 0.960150. La Figura 8, parte izquierda, muestra gráficamente los resultados obtenidos de la NIST. Por otra parte, la parte derecha de la Figura 8 muestra los resultados de la distribución uniforme que presentan las secuencias, donde P-value ≥ α=0.001.

Para complementar la evaluación, se aplicaron las pruebas del conjunto de pruebas estadísticas de la NIST (National Institute of Standard and Technology) [4]. Aunque varios tipos de pruebas estadísticas han sido propuestas, nos enfocaremos en el conjunto de la NIST debido a las atractivas propiedades que posee. De hecho, las pruebas no se describen ampliamente en este trabajo debido a que los programas y su respectiva documentación están disponibles en Internet. El conjunto de pruebas de la NIST está conformado por 15 reglas, las cuales se muestran en la Tabla I. Para cada regla estadística, un conjunto de P-values se genera, el cual corresponde al conjunto de secuencias. Cada secuencia se dice ser un suceso si el valor correspondiente P-value satisface la condición P-value ≥ α, en caso contrario se dice ser un fracaso. Para un nivel de importancia α, 100α % de P-values se esperan indicar fracaso. Para interpretar los resultados de las pruebas, la NIST considera la proporción de secuencias exitosas y la uniformidad de la distribución de los Pvalues [4]. TABLA I. LISTA DE PRUEBAS ESTADÍSTICAS DE LA NIST 1.2.3.4.5.6.7.8.9.10.11.12.13.14.-

The Frequency (Monobit) Test Frequency Test within a Block The Runs Test Tests for the Longest-Run-of-Ones in a Block The Binary Matrix Rank Test The Discrete Fourier Transform (Spectral) Test The Non-overlapping Template Matching Test The Overlapping Template Matching Test Maurer's “Universal Statistical” Test The Linear Complexity Test The Serial Test The Approximate Entropy Test The Cumulative Sums Test The Random Excursions Test

Figura 8. (Izquierda)Proporción de secuencias exitosas. (Derecha) Uniformidad de la distribución de los Pvalues. IV. CONCLUSIONES En este trabajo se realizó la evaluación de un generador de números aleatorios, el cual está basado en autómatas celulares. Se realizaron las pruebas que comprenden el conjunto de pruebas de la NIST para determinar su aleatoriedad, las cuales muestran resultados favorables. En base a los resultados obtenidos, el generador de

5 Encuentro de Investigación en IE, 25 — 26 de Marzo, 2010

llaves considerado puede aplicarse favorablemente en aplicaciones de criptografía y otro tipo de aplicaciones. REFERENCIAS [1] Mejía Carlos, M., “Encriptación por Sincronización

[2]

[3]

[4]

[5]

en Autómatas Celulares”, Tesis de Doctorado, 2001. Mejía, M., and Urías, J., “An Asymptotically Perfect Pseudorandom Generator”, Discrete and Continuous Dynamical Systems, Vol. 7, pp. 115126, 2001. Patidar, V., and Sud, K. K., “A novel Pseudo Random Bit Generator Based on Chaotic Standard Map and its Testing”, Electronic Journal of Theoretical Physics, 6, pp. 327-344, 2009. Rukhin, A., et al., “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications”, NIST (Revised: August 2008). http://csrc.nist.gov/rng/. Urías, J., Ugalde, E., and Salazar, G., “A cryptosystem based on cellular automata”, Chaos, Vol. 8, (4), pp. 819–822, 1998.