 |
|
|
| .: Criptotaller
:. |
|
| |
|
| Tests
estadísticos para números pseudoaleatorios |
Resumen: los FIPS (*) 1401 y
1402 recogen una serie de tests estadísticos que se describen
en este artículo y deben cumplir los generadores de números
pseudoaleatorios.
Los FIPS 1401 (Enero 94) y 1402 (Noviembre
99) titulados "Security requirements for cryptographic modules"
que publica el NIST pretenden establecer una serie de estándares
que seguir por el gobierno federal estadounidense. En particular
los módulos criptográficos que utilicen generadores
de números pseudoaleatorios deben pasar algunos tests.
En concreto el apartado 4.9.1 "Power-Up
Tests" dice:
"En el momento de la inicialización,
los módulos criptográficos deben realizar todos
los siguientes auto-tests: test del algoritmo criptográfico,
test de integridad del software/firmware, test de funciones críticas
y tests estadísticos del generador de números aleatorios...
"
Se necesitan entonces 20.000 bits consecutivos
producidos por el generador de números aleatorios que deberán
pasar todos los siguientes tests: monobit, poker, runs y long
runs. Los tests se describen a continuación tal y como
aparecen en el FIPS 1402.
Test monobit
1.- Contar el número de bits iguales a uno en la secuencia
de 20.000 bits. Llamemos X a dicho número.
2.- El test se pasa si 9.275 < X < 10.275 (Error tipo
I de 0.0001) { FIPS 1401 menos exigente pedía 9.654 <
X < 10.346 }
1.- Dividir la secuencia de 20.000
bits en 5.000 segmentos contiguos de 4 bits. Contar y almacenar
el número de veces que ocurre cada uno de los 16 valores
posibles (0000,0001,...,1111), llamemos f(i) al número
de veces que apareció el valor i, 0<= i <= 15
2.- Evaluar la siguiente expresión
X = (16/5000) * ( f(1)2 + f(2)2
+ ... + f(15)2) - 5000
3.- El test se pasa si 2'16 < X < 46'17 (Error tipo I
de 0.0001) { FIPS 1401 pedía 1'03 < X < 57'4 }
Test de runs (rachas?)
1.- Una racha se define como una subsecuencia máxima
de bits consecutivos bien de unos bien de ceros que es parte
de la secuencia inicial de 20.000 bits. Se cuentan y almacenan
las rachas de 1 o más bits.
2.- El test se pasa si las rachar que ocurren (de longitudes
1 a 6) están en los intervalos especificados en la siguiente
tabla. Esto debe ocurrir tanto para los ceros como para los
unos, es decir que los 12 conteos deben estar en los intervalos
especificados. Para este test las secuencias de longitud superior
a 6 se consideran de longitud 6.
Intervalos requeridos para el test de rachas
| Longitud |
Intervalo requerido |
| 1 |
2.343 - 2.657 |
| 2 |
1.135 - 1.365 |
| 3 |
542 - 708 |
| 4 |
251 - 373 |
| 5 |
111 - 201 |
| 6 |
111 - 201 |
Test de long runs (rachas largas)
1.- Una racha larga se define como una racha de longitud 26
o más (tanto de ceros como de unos) para un error de
tipo I de 0.0001
2.- El test se pasa si en 20.000 bits no hay rachas largas.
Código fuente
Hay que reseñar que pasar los
tests citados, como ocurre con cualquier test estadístico
no significa que el generador sea bueno aunque no pasarlo significa
que el generador debe rechazarse. En particular estos tests no
aseguran nada sobre una cualidad necesaria para un generador de
números pseudoaleatorios criptográficamente fuerte,
a saber que dada parte o toda la secuencia de números ya
generados sea imposible predecir el siguiente número generado.
Con estas salvedades el código
fuente de fips1402.c
nos permitirá desechar generadores de números pseudoaleatorios
defectuosos.
Fuente: FIPS1401, FIPS1402 en http://www.nist.gov
Notas al pie
(*) FEDERAL INFORMATION PROCESSING
STANDARD PUBLICATION
|
|
|
|
|
|
| 
|
| Area
On-Line
|
| Todo
tipo de material, para disfrutar de él completamente On-Line, sin
necesidad de descargar archivos ni tener que andar descomprimiendo estos.
No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva.
Son de lo más interesante. |
|
