Pruebas estadísticas de aleatoriedad [programa 1 [P1]

Tarea Realizada para la Materia de Seguridad de la información y criptografía  [programa 1 [P1]]

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)

Si los resultados de las pruebas son satisfactorios, es seguro y , si es seguro, resiste ataques, si los resultados son malos y la generación de números realmente no es aleatoria, podremos atacar nuestro propio One-Time Pad.

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():

Aleatorio.java                                            aleatorio.c 

aleatorio.py                                             aleatorio.rb

Generadores de Numeros PseudoAleatorios:

Generador.java                                        generador.py                             

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

Pruebas aplicadas a el generador de numeros pseudoaleatorios:

Prueba de Frecuencias:

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	VO
1	3
2	1
3	1
4	0

la prueba implica determinar las frecuencias de corridas de distinta longitud y comparar con sus valores esperados mediante el calculo de x²

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).

Σ 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.

y continuación se muestran las corridas cuando se le realizan con la Prueba de Corridas.

_________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%,

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/

One Time Pad [tarea intro [TI]]

Tarea Realizada para la Materia de Seguridad de la información y criptografía  [tarea intro [TI]]

'One Time Pad'  es como una libreta en la cual cada hoja solo se utiliza una vez, es decir la clave de la hoja que se utilizo para cifrar o descifrar un mensaje solo es utilizada una vez para garantizar su funcionalidad y que los mensajes no sean descifrados, en los siguientes fragmentos de código se muestran algunos métodos que se utilizaron en el programa:

Genera el PAD

'''Metodo que genera la libreta que 
   contiene claves que solo se utilizaran una vez '''
def generaPad(lineas,caracteres):
    hoja=[]#libreta/hoja
    for j in range(lineas):
        hoja.append([])#libreta con hojas
        for i in range(caracteres):
            num=randint(0,caracteres)
            hoja[j].append(num)#hojas
    return hoja

Genera el Archivo donde guarda la PAD

'''Genera el Archivo pad.dat (libreta) '''
def genArchivo(hoja):
    archivo = open('pad.dat','w')
    lineas=len(hoja)
    for i in range(lineas):
        archivo.write(str(hoja[i]))
        archivo.write('\n')
    archivo.close()

Convierte de acuerdo a sus Números o Letras Correspondientes

'''Convierte el Mensaje original
   a una lista de numeros correspondientes'''
def conversorNum(mensaje):
    x=len(mensaje)
    mclave=[]
    if x>25:
        #aun no valido esto
        print 'El mensaje es muy grande intentelo de nuevo'
        mensaje= raw_input('Mensaje (maximo 25 caracteres) :   ')
        conversorNum(mensaje)
    for i in range(x):
        if mensaje[i] in numerosdelalf:
            mclave=mensaje.index(mensaje[i])
    return mclave

'''Convierte un conjunto de numeros 
   a las Letras correspondiente'''
def conversorLet(numeros):
    x=len(numeros)
    mensaje=[]
    for i in range(x):
        if numeros[i] in numerosdelalf:
            #numero correspondiente al alfabeto
            pos= numerosdelalf.index(numeros[i])
            mensaje[i].append(alfabeto[pos])
    return mensaje            

Cifrado es mediante la suma de el mensaje y la key(clave) de la PAD, y a esa suma se le aplica el modulo de el largo del alfabeto que estamos utilizando.
Decifrado al contrario se resta el ciphertext a la key(clave) de la copia de la PAD, y a esa resta se le aplica asimismo el modulo del alfabeto en cuestion.

'''Metodo que cifra en mensaje sumando los emelentos de la key(clave) 
   y realizando a esa suma un modulo de la longitud del alfabeto '''
#para cifrar + mod(len(alfabeto))
def cifraMensaje(mensaje,key):
    cifrado=[]
    for i in range(len(mensaje)):
        result=mensaje[i]+key[i]
        result=result%(len(numerosdelalf))
        cifrado[i].append(result)#error
    return cifrado

'''Metodo que decifra el texto cifrado que recibe como parametro
   realizando una resta de la key(clave) 
   y aplicando el modulo del alfabeto'''
#para decif -  mod(len(alfabeto))
def decifMensaje(ciftext,key):
    mensaje=[]
    for i in range(len(ciftext)):
        temp=len(numerosdelalf)
        result=temp+ciftext[i]-key[i]
        result=result%(len(numerosdelalf))
        mensaje[i].append(result)
    return mensaje

Si requiere el código completo se puede ver en en este espacio: 

Ver Aqui                                                           Descargar Aqui

Salidas

Terminal_>
karenalduncin@lilalduncin:~/codigos/crypto$ python otp.py 6 25 hola
One Time Pad 
[11, 19, 2, 18, 24, 13, 1, 13, 7, 13, 15, 4, 14, 3, 2, 21, 17, 10, 2, 1, 11, 12, 19, 17, 1]
[4, 7, 2, 21, 8, 20, 20, 21, 23, 5, 22, 18, 21, 15, 5, 20, 12, 10, 10, 23, 3, 15, 20, 14, 21]
[4, 22, 16, 21, 20, 19, 11, 9, 8, 23, 18, 9, 25, 11, 10, 4, 12, 14, 21, 15, 13, 24, 18, 19, 24]
[21, 25, 5, 16, 17, 9, 25, 22, 17, 1, 7, 4, 13, 6, 22, 9, 25, 8, 19, 21, 16, 16, 3, 8, 4]
[9, 1, 2, 16, 18, 16, 0, 7, 3, 9, 9, 2, 7, 8, 0, 18, 19, 10, 24, 22, 5, 9, 1, 1, 2]
[6, 5, 14, 18, 17, 24, 0, 23, 9, 12, 25, 15, 4, 13, 23, 15, 16, 19, 18, 22, 18, 21, 14, 21, 17]
Mensaje:
hola
Mensaje Convertido:
[]
Mensaje Cifrado:
[]
Mensaje:
[]
karenalduncin@lilalduncin:~/codigos/crypto$ 

Archivo Generado:

pad.dat


Futuras Mejoras

En la ejecución el código no me muestra los cambios que sufre el mensaje, para esto se realizaran pruebas en el código para comprobar si en realidad entra en las condiciones y que el mensaje realmente puede volver a su estado original llegando del punto A que es cifrar así como al punto B en el cual se descifra, también ya que aun falta eliminar la clave que ya fue usada, esto es solo los métodos sin la ejecución del algoritmo funcionando, se subirá una entrada consecutiva a esta para solucionar estos problemas.