Prueba de aleatoriedad clave One Time Pad

¿Para que nos serviría hacer una prueba de aleatoriedad para la clave generada?
La respuesta, es que si nosotros (que claro que si) estamos buscando generar una clave que sea dificil de romper o descifrar, a nosotros nos interesaría hacer éste tipo de test.

¿Pero como sabríamos si es aleatoria?
No sabemos bien si un número es totalmente aleatorio entonces lo que se hace es medir las frecuencias que estamos recibiendo.
En ésto me ayudo mucho en ver de otra forma, una caricatura que encontré en random.org

Para esto hay diferentes tipos de pruebas como anderson, chi, monobit, de bloques, run, entre otras. Cada una la aplicamos dependiendo del tipo de test que estamos buscando y su número aleatorio.

Para esta entrada se genero los números aleatorios de one time pad, donde buscaremos verificar que tan aleatorio es nuestra clave.

Prueba
El tipo de prueba empleado es el monobit, el cúal su fórmula ésta dada por:

Donde E es nuestra secuencia de bits
Sn nuestra sumatoria de E (hay que indicar que nuestra, que al momento de identificar un 0 esto lo cambia a -1)
n es nuestro tamaño total de E
P-value será tomada con erfc(sobs/sqrt(2))
donde erfc es la función de error complementario.
Ya para definir si fue aleatorio, se compara con una muestra de 0.01 y si esta es mayor la prueba pasa, de lo contrario no es aleatorio.


Código nuevo:

from random import randint
from math import sqrt, erfc

def generarClaves(cantidad, nombre):
    a = 'abcdefghijklmnopqrstuvwxyz '
    largoClave = 80
    for i in range(cantidad):
        clave = list()
        for j in range(largoClave):
            letra = randint(0, len(a)-1)#Creamos nuestro numero aleatorio del tamano del arreglo
            clave.append(letra)
        pruebasRand(clave)#mandamos llamar al metodo de pruebas
        #print clave

#clave.append("\n")
        #guardarClaves(clave, nombre)
def pruebasRand(clave):
    print "Prueba Monobit"
    print "\t Resultado:"+str(pruebaMonobit(clave))

def pruebaMonobit(clave):
    s = list()
    for i in clave:
        i = convertirUnosCeros(i) #Leemos cada elemento del arreglo para sacar unos y ceros
        s.append(i)
    sobs = abs(sum(s))/sqrt(len(s)) #Aplicamos la formula propuesta
    pValue = erfc(sobs/sqrt(2)) #Aplicamos la formula propuesta
    if(pValue > 0.01): return "Prueba pasada "+str(pValue) #Comparamos
    else: return "Prueba no pasada "+str(pValue)

def convertirUnosCeros(elemento):
    elemento = elemento % 2 #Lo sacamos tomando los numero pares e impares
    if elemento == 0: return -1 #Si el elemento es 0 lo convertimos a -1 para que este afecte en la sumatoria
    else: return 1

def guardarClaves(clave, nombre):
    clave = "".join(clave)
    archivo = open(str(nombre), "a")
    archivo.write(clave)
    archivo.close()
    otro = open("copia"+str(nombre), "a")
    otro.write(clave)
    otro.close()

cantidad = int(raw_input("Dame la cantidad de claves a generar: "))
nombre = raw_input("Dame el nombre del archivo: ")
generarClaves(cantidad, nombre)

Explicamos:jninininia..

Resultados:
Así que ahora proseguimos a verificar nuestros resultados y para verificarlos que estuvieran bien, la prueba se hizo varias veces:

1 vez:

5 veces:

Así que por lo valores arrojados, podríamos decir que nuestro generador de claves es seguro y es aleatorio.

Nota:
¿Pero que pasa si al test lo aplicamos más de 5 veces? Pues sorpresa, descubrimos que nuestro generador de números aleatorios, no es del todo aleatorio. Aunque nuestros resultados digan que pasaron la prueba, podemos observar que sus resultados se van repitiendo, hasta tenemos una que otra, que no paso la prueba y sus resultados son los mismos.

Resultado: FAIL.
Ya con ésto sabemos que tristemente nuestra clave no es aleatoria, ya que se repite la frecuencia, así que el posible problema es al momento de emplear randint de python, así que para solucionar ésto, podríamos implementar un número random uniforme, obteniedo unos mejores resultados o hacer nuestro número con lo visto de simulación, así que más adelante pondré mi código mejorado.

Como podemos ver en la imágen los números generados (fueron 10000), se van repitiendo con una frecuencia, haciendo esto muy inseguro.

Referencia:
http://goo.gl/IP3Wx
http://goo.gl/ExMC6
http://www.random.org/analysis/
http://www.random.org/analysis/Analysis2005.pdf