Prueba de secuencias pseudoaleatorias

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de octubre de 2020; las comprobaciones requieren 5 ediciones .

La prueba de secuencias pseudoaleatorias  es un conjunto de métodos para determinar la medida de proximidad de una secuencia pseudoaleatoria dada a una secuencia aleatoria. Tal medida suele ser la presencia de una distribución uniforme , un período grande, una frecuencia igual de aparición de subcadenas idénticas, etc.

Base teórica

Principios de construcción

Una de las pruebas más ilustrativas es una prueba para una distribución uniforme de las frecuencias de aparición de cada carácter. Sea  una secuencia de longitud n y dimensión m . Entonces las frecuencias ν i deben pertenecer al intervalo . Sin embargo, la mayoría de las pruebas usan un método diferente: aceptar o rechazar la hipótesis de aleatoriedad de la secuencia usando distribuciones estadísticas.

Conociendo las propiedades probabilísticas de una secuencia verdaderamente aleatoria, uno puede usarlas para probar la hipótesis sobre qué tan similar es la secuencia generada a una secuencia aleatoria. Para hacer esto, se selecciona una estadística adecuada para cada prueba, sus valores se calculan para la secuencia ideal y generada. Si la diferencia entre estos valores supera algún valor crítico establecido de antemano, la secuencia se considera no aleatoria. Para secuencias "buenas", la probabilidad de tal evento es extremadamente pequeña (digamos ~0.001 y lo denotamos por α). Sin embargo, existe la posibilidad de que una secuencia "mala" satisfaga el criterio y se llegue a una conclusión sobre su aleatoriedad (denotamos la probabilidad de tal evento como β). En la práctica, las longitudes de secuencia n , α y β están relacionadas, se da α y se elige n para minimizar β.

Definamos el valor P como la probabilidad de que el generador ideal genere una secuencia menos aleatoria que la que se está estudiando. Entonces, si el valor P es mayor que α, entonces la secuencia estudiada se considera aleatoria y viceversa en caso contrario.

Brevemente, los pasos de las pruebas estadísticas se pueden representar en forma de tabla:

número de paso Proceso Comentarios
una Declaración de la hipótesis Suponemos que la secuencia es aleatoria.
2 Cálculo de estadísticos de la secuencia estudiada Pruebas de nivel de bits
3 Cálculo del valor P Valor p [0; una]
cuatro Comparando el valor P con α Establecer α dentro de [0.001; 0,01]; si el valor P > α, entonces se pasa la prueba

Interpretación de resultados

Sea dada una sucesión binaria s . Se requiere establecer si la secuencia dada pasa la prueba estadística o no. Para hacer esto, se utilizan varios enfoques diferentes:

Umbral

Este enfoque consiste en calcular algún valor estadístico de la secuencia binaria c(s) y compararlo con algún valor umbral. Si el valor resultante c(s) es menor que el valor umbral, entonces la secuencia s no pasa esta prueba.

Rango fijo de valores

El enfoque también consiste en calcular algún valor estadístico de la secuencia binaria c(s) como en el primer caso. Sin embargo, ahora decimos que si c(s) está fuera de algún rango de valores, entonces la secuencia s falla esta prueba.

Valor de probabilidad

Un tercer enfoque para determinar si una secuencia binaria s pasa una prueba estadística implica contar no solo la estadística c(s) sino también su correspondiente valor de probabilidad p . Por lo general, una estadística particular se calcula de tal manera que sus valores grandes implican una naturaleza no aleatoria de la secuencia s . Entonces p es la probabilidad de que c(s) sea mayor o igual que c(s') calculada para una secuencia verdaderamente aleatoria s' . Por tanto, valores pequeños de la probabilidad p (normalmente p < 0,05 o p < 0,01) pueden interpretarse como evidencia de que s no es aleatorio. Así, si para algún valor fijo a el valor de probabilidad p < a , entonces la secuencia binaria s no pasa esta prueba. Por regla general, a toma valores del intervalo [0.001;0.01].

Pruebas gráficas

Esta categoría incluye pruebas, cuyos resultados se muestran en forma de gráficos que caracterizan las propiedades de la secuencia estudiada. Entre ellos:

  • histograma de la distribución de elementos de secuencia; le permite evaluar la uniformidad de la distribución de caracteres en la secuencia y determinar la frecuencia de repetición de cada carácter;
  • distribución en el avión; diseñado para determinar la relación entre los elementos de la secuencia;
  • verificación en serie; le permite determinar la uniformidad de los caracteres individuales en la secuencia, así como la uniformidad de la distribución de series de k bits;
  • verificar la monotonicidad; sirve para determinar uniformidad a partir del análisis de subsecuencias no crecientes y no decrecientes;
  • función de autocorrelación ; diseñado para evaluar la correlación entre copias desplazadas de secuencias y subsecuencias individuales;
  • perfil de complejidad lineal; la prueba evalúa la dependencia de la complejidad lineal de la secuencia con su longitud;
  • prueba espectral gráfica; le permite evaluar la uniformidad de la distribución de bits de la secuencia en función del análisis de la altura de los valores atípicos de la transformada de Fourier .

Los resultados de las pruebas de gráficos son interpretados por un ser humano, por lo que las conclusiones basadas en ellos pueden ser ambiguas.

Pruebas estadísticas

A diferencia de las pruebas gráficas, las pruebas estadísticas brindan una característica numérica de la secuencia y le permiten decir sin ambigüedades si se pasó la prueba. Los siguientes paquetes de software de pruebas estadísticas son los más conocidos:

No. Nombre Autor Organización
una Pruebas NIST [1] Andrew Rujin, et. Alabama. NIST ITL
2 PRUEBA-U01 [2] P. L'Ecuyer y otros. Universidad de Montreal
3 CRIPTA-X [3] Helen Gustafson et al. Universidad Tecnológica de Queensland
cuatro El proyecto pLab [4] Pedro Hellekalek Universidad de Salzburgo
5 INCORRECTO [5] Jorge Marsaglia Universidad Estatal de Florida
6 Más intransigente [6] Roberto G Brown Universidad de Duke
7 ENT [7] Juan caminante autodesk , inc.
ocho El arte de la programación informática vol. 2 Algoritmos Semiméricos [8] donald knuth Universidad Stanford
9 Manual de Criptografía Aplicada [9] Alfred Menezes y otros. CRC Press, Inc.

Pruebas DIEHARD

Las pruebas DIEHARD fueron desarrolladas por George Marsaglia a lo largo de varios años y se publicaron por primera vez en un CD-ROM dedicado a los números aleatorios. Se consideran uno de los conjuntos de pruebas más rigurosos que se conocen.

Pruebas de D. Knuth

Las pruebas de Knuth se basan en una prueba estadística . El valor calculado de las estadísticas se compara con los resultados tabulares y, según la probabilidad de ocurrencia de dichas estadísticas, se llega a una conclusión sobre su calidad. Entre las ventajas de estas pruebas se encuentran su reducido número y la existencia de algoritmos de ejecución rápida. La desventaja es la incertidumbre en la interpretación de los resultados. Aquí hay un resumen de estas pruebas:

  • Comprobación de series no vinculadas . La secuencia se divide en m series no superpuestas y se construye una distribución para las frecuencias de ocurrencia de cada serie posible.
  • Consultar intervalos . Esta prueba comprueba la uniformidad de la distribución de caracteres en la secuencia estudiada mediante el análisis de las longitudes de las subsecuencias, cuyos elementos pertenecen todos a un cierto intervalo numérico.
  • Comprobación de combinaciones . La secuencia se divide en subsecuencias de cierta longitud y se examinan series que consisten en varias combinaciones de números.
  • Prueba de coleccionista de cupones . Sea  una secuencia de longitud n y dimensión m . Se investigan subsecuencias de cierta longitud que contienen cada número de m dígitos.
  • Comprobación de permutaciones . Esta prueba comprueba la uniformidad de la distribución de caracteres en la secuencia estudiada mediante el análisis de la disposición mutua de números en subsecuencias.
  • Compruebe la monotonicidad . Se utiliza para determinar la uniformidad a partir del análisis de subsecuencias no crecientes y no decrecientes.
  • Comprobación de correlación . Esta prueba comprueba la independencia mutua de los elementos de una secuencia.

Pruebas NIST

La diferencia entre estas pruebas y otras modernas es la apertura de los algoritmos. Entre las ventajas también se encuentra una interpretación inequívoca de los resultados de las pruebas. Tabla de características generales:

No. Nombre de la prueba Defecto definido
una prueba de frecuencia Demasiados ceros o unos
2 Comprobación de importes acumulados Demasiados ceros o unos al principio de la secuencia
3 Comprobación de "agujeros" en subsecuencias Desviación en la distribución de secuencias de unidades
cuatro Comprobación de "agujeros" Un número grande (pequeño) de subsecuencias de ceros y unos indica que la fluctuación del flujo de bits es demasiado rápida (lenta)
5 Comprobación de los rangos de las matrices Desviación de la distribución de rangos de matrices de la distribución correspondiente para una secuencia verdaderamente aleatoria, asociada con la periodicidad de las secuencias
6 Prueba espectral Propiedades periódicas de una secuencia
7 Comprobación de patrones que no se superponen Los patrones no periódicos son demasiado comunes
ocho Comprobación de patrones de intersección Secuencias de m bits demasiado comunes de unos
9 Prueba estadística universal de Maurer Compresibilidad (regularidad) de una secuencia
diez Comprobación de desviaciones aleatorias Desviación de la distribución del número de ocurrencias de subsecuencias de cierto tipo
once Una variación de la verificación de desviaciones aleatorias Desviación de la distribución del número de ocurrencias de subsecuencias de cierto tipo
12 Comprobación de la entropía aproximada Distribución desigual de palabras de m bits. Valores pequeños significan alta repetibilidad
13 Comprobación de la serie Irregularidad en la distribución de palabras de m bits
catorce Compresión usando el algoritmo Lempel-Ziv Mayor compresibilidad que una verdadera secuencia aleatoria
quince Complejidad lineal Desviación de la distribución de complejidad lineal para longitud de subcadena finita

Aplicaciones prácticas

Los generadores de números aleatorios y pseudoaleatorios son el eslabón de la seguridad de la información . En cierto sentido, estos son componentes fundamentales de los algoritmos y protocolos criptográficos. Dado que dichos generadores se utilizan en muchos problemas criptográficos, por ejemplo, la formación de parámetros aleatorios y claves de sistemas de cifrado, los requisitos para ellos son bastante altos. En particular, uno de los criterios para una secuencia binaria absolutamente arbitraria obtenida a la salida del generador es la imposibilidad de predecirla en ausencia de cualquier información sobre los datos suministrados a la entrada del generador. Por tanto, en la práctica, se realizan pruebas estadísticas para comprobar el carácter aleatorio de una secuencia binaria generada por un generador de números aleatorios o pseudoaleatorios. Lo que a su vez le permite identificar generadores que cumplan con los requisitos de un problema criptográfico específico de antemano.

Concurso AES

Para aprobar el nuevo Estándar de Cifrado Avanzado , el Instituto Nacional de Estándares y Tecnología , con el apoyo del gobierno de los EE. UU., realizó una competencia durante la cual se probaron 15 algoritmos solicitantes. Uno de los criterios utilizados en la evaluación de algoritmos fue su idoneidad como generadores de números aleatorios. La prueba de dichos generadores para la formación de secuencias binarias aleatorias con buenas propiedades estadísticas se llevó a cabo utilizando el conjunto de pruebas estadísticas del NIST .

Durante la primera ronda de AES, las pruebas se realizaron con claves de 128 bits. Solo 9 algoritmos de 15 algoritmos pudieron pasar las pruebas estadísticas [10] .

Según los resultados de la primera ronda, se seleccionaron 5 algoritmos de cifrado como finalistas de AES: MARS , RC6 , Rijndael , Serpent y Twofish . En la segunda ronda de la competencia AES, se evaluó la idoneidad de estos 5 algoritmos como generadores de números aleatorios en base a claves de 192 bits y 256 bits. La duración de las pruebas estadísticas del NIST fue de varios meses, con cálculos realizados en numerosas estaciones de trabajo Sun Ultra . Todos los datos se generaron y procesaron en línea. Como resultado de la segunda ronda se demostró que cada uno de los cinco finalistas genera una secuencia binaria aleatoria con buenas propiedades estadísticas y por lo tanto se puede utilizar como generador de números pseudoaleatorios, pudiendo utilizar claves con tamaños: 128 , 192 y 256 bits [11] .

Véase también

Notas

  1. ↑ Kit de herramientas criptográficas del NIST . Consultado el 8 de mayo de 2010. Archivado desde el original el 17 de agosto de 2011.
  2. ↑ PruebaU01 . Fecha de acceso: 8 de mayo de 2010. Archivado desde el original el 23 de julio de 2010.
  3. ↑ Crypt-X Archivado el 22 de septiembre de 2008 en Wayback Machine . El Centro de Investigación de Seguridad de la Información.
  4. ↑ El proyecto pLab (enlace descendente) . Consultado el 21 de noviembre de 2009. Archivado desde el original el 14 de noviembre de 2009. 
  5. ↑ The DIEHARD Test Suite Archivado el 25 de enero de 2016.
  6. ↑ Dieharder: un conjunto de pruebas de números aleatorios . Consultado el 8 de mayo de 2010. Archivado desde el original el 10 de junio de 2010.
  7. ↑ ENT . Consultado el 8 de mayo de 2010. Archivado desde el original el 15 de mayo de 2010.
  8. ↑ Donald E. Knuth. The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms Archivado el 4 de septiembre de 2008 en Wayback Machine / 3.ª ed. Addison Wesley, 1998
  9. ↑ Alfred Menezes y otros Handbook of Applied Cryptography Archivado el 7 de marzo de 2005 en Wayback Machine .
  10. ↑ NIST IR 6390 Randomness Testing of the Advanced Encryption Standard Candidate Algorithms Archivado el 6 de noviembre de 2010 en Wayback Machine . 
  11. ↑ Prueba de aleatoriedad NIST IR 6483 de los candidatos finalistas del estándar de cifrado avanzado. Archivado el 27 de mayo de 2010 en Wayback Machine . 

Literatura

  • Donald E. Knuth . Capítulo 3. Números aleatorios // El arte de la programación informática. - 3ra ed.- M .: Williams , 2000. - V. 2. Algoritmos obtenidos. — 832 pág. — ISBN 5-8459-0081-6 .
  • M. A. Ivanov, I. V. Chugunkov. Capítulo 4. Metodología para evaluar la calidad de generadores de PSS // Teoría, aplicación y evaluación de la calidad de generadores de secuencias pseudoaleatorias. - M. : KUDITS-OBRAZ, 2003. - 240 p. — ISBN 5-93378-056-1 .

Enlaces