|
Generación de Números Pseudoaleatorios usados por Sistemas Criptográficos RESUMEN
En gran parte de los sistemas criptográficos usados actualmente se hace necesario generar números aleatorios, sin embargo, es conocido que es una tarea difícil de llevar a cabo, por lo que se opta por generar números pseudoaleatorios, es decir, números que están cerca de ser aleatorios. Se dice que un dispositivo o algoritmo genera números pseudoaleatorios si contiene un proceso determinístico, el cual toma como entrada un número que se supone aleatorio, llamado semilla y tiene como salida una sucesión de números “casi” aleatoria. En lo anterior nos encontramos con dos problemas: el primero cómo generar una semilla aleatoria y el segundo cómo probar que la sucesión obtenida es “casi” aleatoria. El propósito de este artículo es proporcionarle algunas sugerencias para resolverlos. 1. Generaciòn de Semillas
Gran parte del éxito de un diseñador de sistemas criptográficos se respalda en sus generadores de números aleatorios, éstos pueden estar basados en “hardware” o en “software”. En el primer caso se toman a eventos físicos como generadores aleatorios, por ejemplo, el tiempo de emisión entre partículas radioactivas, la distribución térmica de semiconductores o resistores, la inestabilidad de un oscilador, la potencia del sonido en micrófonos o la intensidad de vídeo de una cámara, etcétera. Para garantizar que el generador aleatorio sea seguro, debe de ser ajeno a cualquier atacante. Hoy en día se han creado dispositivos VLSI basados en capacitores y osciladores. La mayor parte de dispositivos para generar una semilla aleatoria son por explicación obvia, basados en software. En este caso se requiere una vez más que el número generado cumpla las mismas condiciones que antes. Aquí también se hace uso de eventos que estén lo más alejado de la intervención humana como por ejemplo: el sistema de reloj, el tiempo entre cada activación del teclado o el ratón, el contenido de buffers de entrada o salida, entre otros. Es importante hacer notar que mientras más recursos se utilicen en la generación de las semillas es más probable que nos acerquemos a un buen generador de números aleatorios. Después que se ha decidido cuáles eventos deben de ser usados, se recomienda que la combinación de ellos sea la concatenación, ya que esto permite que los eventos sean independientes y así la posibilidad de que sea encontrado el origen por un atacante disminuya considerablemente. Lo anterior sugiere que debe de existir una medida de calidad de un generador de semillas aleatorias. En efecto, existen varias formas de probar si la calidad de este tipo de dispositivos es aceptable. Esto lo encontrará más ampliamente en la última sección. 2 Generación de números pseudoaleatorios
Sin embargo, es más fácil encontrar una forma que genere la cadena pseudoaleatoria a partir de la semilla. Se ha podido demostrar que cualquier función de un sólo sentido se puede utilizar para generar cadenas pseudoaleatorias. Podemos definir como un generador de números pseudoaleatorios a un dispositivo que recibe como entrada una semilla s , que se supone aleatoria, y da como salida una cadena de bits de longitud n . Existen varios ejemplos estándar: el propuesto en ANSI X9.17 que usa como función de un sólo sentido a DES (FIPS 186). Existen otros tipos de generadores de números pseudoaleatorios, que en la práctica son más lentos y sin embargo, cuando se resuelve el problema de la aritmética modular o en general la aritmética de un campo finito, es muy recomendable su uso. Estos generadores hacen uso de funciones del tipo RSA ([8]), o el Gamal ([3]) basando su aleatoriedad en la presunta intractabilidad de problemas como la factorización de un número, producto de dos números primos diferentes, y del problema del logaritmo discreto, por ejemplo, sobre una curva elíptica definida en un campo finito de característica 2. Veamos algunos ejemplos de este tipo de generadores: Algoritmo generador de bits pseudoaleatorio Entrada : Dos primos p,q , elegir e , tal que Una semilla Algoritmo: a) Para j =1 hasta k : a1) a2) Salida: La sucesión z 1 , z 2 , …, z k . Existen algunas variantes a este tipo de algoritmos como la de Micali-Schnorr ([7]), y la de Blum-Blum-Shub ([1]). Se puede mostrar que este tipo de generadores son criptográficamente seguros, es decir, que pasan las pruebas estadísticas sobre aleatoriedad que a continuación se describen. 3 Pruebas de aleatoriedad sobre dispositivos generadores de números pseudoaleatorios
El problema de la aleatoriedad es esencialmente teórico, sin embargo, se puede acercar la justificación de que un espacio es equiprobable probando que no se cumplen las características más claras de no-aleatoriedad, es decir, condiciones necesarias, aunque no suficientes. La práctica dice que esto basta para que la cadena pseudoaleatoria sea muy cercana a una cadena verdaderamente aleatoria.
En la literatura conocida ([4]), existen varias pruebas estadísticas que han sido utilizadas para probar la aleatoriedad de un generador de números pseudoaleatorios, estas pruebas verificaban por ejemplo, que las cadenas pseudoaleatorias tengan un número “igual” de ceros y unos. Contando en número de ceros y unos se calcula una estadística de prueba En 1990 ([5]), U. M. Maurer propone su “Universal Statistical Test for Random Bit Generators”, y demuestra que ésta detecta además todos los defectos de no aleatoriedad que detectan las anteriores pruebas. Además de ser muy simple de implementar. Enseguida se muestra en qué consiste la prueba de Maurer. Tenemos como entrada a la sucesión s= s 0 , s 1 , …, s n-1 y como salida a la estadística de prueba X que se distribuye normalmente con media Una tabla obtenida de [5], para
La estadística de prueba X se obtiene como:
Lo anterior se puede ver de la siguiente manera: para probar que un dispositivo satisface la prueba de Maurer, seguiremos los siguientes pasos: 1) En condiciones normales el dispositivo tendrá que generar una cadena aleatoria s de longitud n donde n es como mínimo alrededor 2 millones y como máximo de 66 millones. Después se verá cómo varía la longitud de esta cadena. 2) Se divide la cadena s en bloques de longitud L bits, donde L varía de 1 a 16. Se recomienda que es suficiente hacer la prueba para 3) Ahora se divide el número de bloques en dos partes: los primeros Q bloques y los restantes K bloques. Q debe ser elegido de al menos 10·2 L bloques, como existen 2 L bloques diferentes de longitud L, se supone que en una cadena de 10 veces este número aparecerá al menos un bloque de los 2 L diferentes. Q será la cadena de iniciación. 4) Los restantes K bloques serán la parte de prueba, se recomienda que Q sea al menos 1000·2 L , es decir esperando que el dispositivo genere 1000 veces cada bloque diferente.
He aquí, el algoritmo: Entrada: una sucesión s = s 1 , s 2 , …, s n . a) Desde i =1 hasta Q, asignar b) sum = 0 c) Desde i = Q+1 hasta Q+K hacer c1) sum ¬ sum + log (i-T[bi]) c2) d) X ¬ sum / K Salida: la estadística de prueba X. Ejemplo muestra:Si s = 00 11 01 10 01 11 00 1010 00 10 00 1111 00 01 00 11 1010 01 11 01 00 11 01 1010 00 En este caso L = 2, Q = 4, entonces la inicialización de la tabla queda como:
como K = 25, entonces un resumen del ciclo para obtener a X es el siguiente:
Lo que resulta de aquí es la estadística de prueba X = 0.499109, usando los parámetros antes definidos esta variable tiene una media Para finalizar este artículo mencionaremos que en la práctica real, los parámetros recomendados anteriormente implican que el generador de números pseudoaleatorios produzca una cadena de 2068480 bits al menos para L = 8 y de 66 191 360 bits en la prueba en el caso de L = 16. El pasar esta prueba el dispositivo garantizará la calidad requerida por cualquier exigencia de alta seguridad criptográfica conocida hasta el momento ([2]). Bibliografía [1] Blum, L. Blum M., Shub M. , “A simple unpredictable pseudorandom number generator” , SIAM Journal on Computing 15, pp 364-383, 1986. [2] FIPS 140, “ Security requirements for cryptographic modules ”, Federal Information Processing Standards Publication 140 – I, U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, Virginia, 1994. [3] Kaliski Jr. B. S. “Elliptic curves and cryptography: a pseudorandom bit generator and other tools” , Ph D thesis, MIT Department of Electrical Engineering and Computer Science, 1988. [4] Knuth D.E., “The Art of Computer Programming – Seminumerical Algorithms, Vol 2” , Addison Wesley Reading, 1973. [5] Maurer U.M. . “ A Universal Statistical Test for Random Bit Generators” , Advances in Cryptology CRIPTO ’90, LNCS 537, pp 409-420, 1991. [6] Menezes A.J., van Oorschot P.C., Vanstone S.A., “HandBook of Applied Cryptography” , CRC Press 1997. [7] Micali S., Schnorr C.P ., “Efficient, perfect polynomial random number generators”, Journal of Cryptology 3, pp 157-172, 1991. [8] Shamir A. “On the generation of cryptographically strong pseudorandom sequences”, ACM Transaction on Computer Systems, 1, 1983. Seguri DATA , Seguridad Privada, S.A. de C.V. Colaboración de: PERICIAS CALIGRAFICAS info@periciascaligraficas.com |
POR SER LA EDUCACION Y LA INFORMACION UN BIEN DE TODOS ESTA WEB ES ABIERTA
En este número encontrará una descripción de los rasgos más importantes sobre la generación de números pseudoaleatorios, principalmente, cuales son las condiciones que debe de cumplir un dispositivo que genera números pseudoaleatorios .
donde 
.
el menor bit significativo de x j
y finalmente se acepta la hipótesis de que la diferencia es insignificante si 
y varianza 
donde 
para 
. Entonces 
se distribuye normalmente con parámetros N (0, 1).
y 
se muestra enseguida:
. El residuo de n entre L se puede ignorar.
T[b i ] = i, donde b i es el número cuya representación binaria está en el bloque i. Posteriormente se calcula A i = i – T[b i ], que nos proporciona la estadística de prueba definida en la ecuación (1).
(Inicializa la tabla T)
, con desviación estándar que se puede calcular según las anteriores fórmulas, entonces 
y esto significa que la variable Z (normal estándar) es Z = -1.43486, lo que permite deducir que la cadena es pseudoaleatoria, con una confiabilidad del 95%, ya que -1.64 
-1.43. Termina entonces la prueba.