Se realizaron pruebas estadísticas de aleatoriedad al resultado de la generación de claves de números aleatorios del programa One-time Pad [T1] (de la entrada anterior) para saber si cumple con las características de datos generados aleatoriamente:
- Unpredictable (Impredecible)
- Uncompressible (Incompresible)
- Unreproducible (Irreproducible)
Para llevar a cabo las pruebas se realizaran generadores de números aleatorios en diferentes lenguajes, para el experimento también se realizaron generadores de números pseudo-aleatorios, utilizando el Método Congruencial Mixto:
Donde se utilizaran los siguientes parámetros de entrada:
X0 = la semilla (X0 > 0), las semilla tienen que ser mayor a 0.
a= el multiplicador (a>0), estas variables preferiblemente que no tengan divisores en común.
c= constante aditiva (c>0), pueden ser por ejemplo números primos.
m= el modulo (m>X0 , m>a y m>c), el modulo preferentemente mayor a todas las variables.
Los códigos los podran ver en las siguientes ligas:
Numeros aleatorios utilizando funciones rand():
Generadores de Numeros PseudoAleatorios:
Se Utilizó la Prueba de Frecuencias entre ciertos rangos, consiste en generar N números aleatorios y agruparlos por frecuencias y estas se comparan con su valor esperado mediante la siguiente formula:
VEi=N/M
La sumatoria de las x² se compara contra el valor de la Tabla de Distribución Ji.
utilizando α = 0.05 y grados de libertad de N-1 (gld: 8).
X²=(VE-VO)²/ VO
También se realizó la prueba de Corridas, una corrida es una sucesión de eventos similares seguidos y precedidos por eventos diferentes:
1000000001 <-- Corrida de longitud k
k
donde n[i]>n[i-1]
entonces cadena[i] = '0'
de lo contrario cadena[i] ='1'
.382 .421 .126 .328 .421 .638 .431 .126 .207
cadena[]:
0 1 0 0 0 1 1 0
Longitud de Corrida:
-> 1 1 3 2 1
en la que si cadena[i]es igual a cadena[i+1]
entonces imprime cadena[i],veces++
si no son iguales veces = 0,veces++
e imprime cadena[i],veces.
ya que se tiene las longitudes de corrida en una lista de las veces que se repitió se podrá utilizar la sumatoria de los datos en el calculo de la x².
(para este ejemplo):
- k
VO13213140
valor esperado:
VE(k)=2[(k²+3k+1)N-(k³+3k²-k-4)] /(k+3)!
Para corridas de longitud k
valor de ji:
X²=(VE-VO)²/ VO
La sumatoria de las x² se compara contra el valor de la Tabla de Distribución Ji.
utilizando α = 0.05 y grados de libertad de N-1 (gld: 8).
utilizando α = 0.05 y grados de libertad de N-1 (gld: 8).
Σ x² < ValorTabla ...[Resultado Satisfactorio del Experimento]
Nota: En el ejercicio practico se realiza con muestras Grandes, en este ejemplo solo se utilizo una muestra de números aleatorios pequeña.
_________Repeat__________________________ 0 44 18 4 1 0 0 0 0 0 VE(k)=2[(k²+3k+1)N-(k³+3k²-k-4)] /(k+3)! X²=(VE-VO)²/ VO k= 1 VE= 41.75 x²=0.11505681818181818 k= 2 VE= 18.1 x²=5.555555555555714E-4 k= 3 VE= 5.147222222222222 x²=0.3290297067901234 k= 4 VE= 1.1095238095238096 x²=0.011995464852607721 Sumatoria de x²= 0.45663754538010487 Si FTablas > x² los numeros probablemente son aleatorios karenalduncin@lilalduncin:~/modelado/crypto$
Salida Completa Aqui
y aqui se muestran los archivos antes y despues de comprimirlos.
karenalduncin@lilalduncin:~/modelado/crypto/keys$ ls -l
total 24
-rw-rw-r-- 1 karenalduncin karenalduncin 1098 jul 1 04:26 c.dat
-rw-rw-r-- 1 karenalduncin karenalduncin 1060 jul 1 04:29 Genjava.dat
-rw-rw-r-- 1 karenalduncin karenalduncin 1506 jul 1 04:30 genpython.dat
-rw-rw-r-- 1 karenalduncin karenalduncin 1931 jul 1 04:26 java.dat
-rw-rw-r-- 1 karenalduncin karenalduncin 1500 jul 1 04:27 python.dat
-rw-rw-r-- 1 karenalduncin karenalduncin 1798 jul 1 04:28 ruby.dat
karenalduncin@lilalduncin:~/modelado/crypto/keys$
karenalduncin@lilalduncin:~/modelado/crypto/keys$ ls -l
total 24
-rw-rw-r-- 1 karenalduncin karenalduncin 431 jul 1 04:26 c.dat.gzcalc
-rw-rw-r-- 1 karenalduncin karenalduncin 499 jul 1 04:29 Genjava.dat.gz
-rw-rw-r-- 1 karenalduncin karenalduncin 732 jul 1 04:30 genpython.dat.gz
-rw-rw-r-- 1 karenalduncin karenalduncin 972 jul 1 04:26 java.dat.gz
-rw-rw-r-- 1 karenalduncin karenalduncin 745 jul 1 04:27 python.dat.gz
-rw-rw-r-- 1 karenalduncin karenalduncin 900 jul 1 04:28 ruby.dat.gz
karenalduncin@lilalduncin:~/modelado/crypto/keys$
Las diferencias de los archivos ya comprimidos algunas como en leguaje ruby y python y java son casi del 50% ,y en los archivos que fueron con generadores fue aun mayor el porcentaje lo que significa que no son numeros confiablemente aleatorios, en el que el porcentaje de comprimido fue aun mayor al 50% fue solamente en C.
Futuras Mejoras:
El método para sacar la longitud de corrida y pruebas de frecuencias necesita mejorarse ya que aun no funciona al 100%,
El método para sacar la longitud de corrida y pruebas de frecuencias necesita mejorarse ya que aun no funciona al 100%,
Referencias:
Valores Críticos de la Distribución Ji Cuadrada (x²), Facultad Regional Mendoza.
URL del Documento de Consulta
Carlos Marquez
Generación de Números Pseudoaleatorios U4, Febrero 2012.
URL del Documento de Consulta
Ruby Tutorial
http://rubytutorial.wikidot.com/
Chi*****... Tenía escrito un comentario bien largo y luego piqué al pastebin y desapareció. Evita capturas de pantalla con un chorro de fondo que no contribuye nada. Incrusta los códigos en la entrada siempre y cuando no sean muy largos, en cual caso incrustas solamente lo más relevante. Cuida la presentación y estructura de la entrada. 6 pts.
ResponderBorrar