[CRIPTOGRAFÍA] Análisis OTP

En esta entrada se hará un análisis a los resultados arrojados por el OTP de la tarea 1, en este caso utilizaré el código de mi compañero Emmanuel ya que no lo tengo de la primera tarea.

El análisis consiste en realizar pruebas estadísticas a las llaves generadas. Existen varias pruebas, yo utilizaré el Test Monobit.

Generé 10 llaves utilizando los caracteres "abcdefghijklmnopqrstuvwxyz,.;: ", en el texto a encriptar se eliminaron caracteres no pertenecientes a los ASCII, y se utilizaron minúsculas.

Empecé buscando la frecuencia con la que aparecen ciertos caracteres en las distintas llaves, en las imágenes siguientes se muestran las frecuencias con la que aparecen los caracteres "abcdefghijklmnopqrstuvwxyz,.;: " en ese orden. Fueron tomadas 4 llaves para la prueba.

Hay una gran cantidad de caracteres que se repiten varias veces como desde la "e" a la "k", mientras que otros ni aparecen.

Código para obtener frecuencias:

def frecuencia(file):
    text = open(file,"r").read()
    abc = "abcdefghijklmnopqrstuvwxyz,.;: "
    cadena = ""
    x=0
    for element in abc:
        print element, 
        for character in text:
            if character == element:
                x+=1
        print x
        cadena+=str(element)+" "+str(x)+"\n"
        x = 0
    return cadena

for i in range(10):
    archivo = open("frecuencia_"+str(i)+".txt", "w")
    archivo.write(frecuencia("cifrado_"+str(i)+".txt"))

Para analizar más profundamente se realizó un test de frecuencias Monobit basado en trabajos anteriores. Los resultados fueron los siguientes:

Al parecer el generador de llaves no es completamente random.











Código para frecuencias Monobit

from math import sqrt, erfc, fabs

def monobit(texto):
    suma = 0
    for letra in texto:
        if letra == "0":
            suma += 1
        else:
            suma -= 1
    sobs = fabs(suma)/sqrt(len(texto))
    p = erfc(sobs/sqrt(2))
    if(p > 0.0001):
        print "RANDOM! :D " + str(p)
    else:
        print "NO RANDOM :C " + str(p)

for i in range(10):
    file = open("binario_"+str(i)+".txt", "r").read()
    monobit(file)

Despues de las pruebas decidi hacerlas de nuevo pero esta vez con un texto más pequeño, mi primer texto era:

en un lugar de la mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivia un hidalgo de los de lanza en astillero, adarga antigua, rocin flaco y galgo corredor. una olla de algo mas vaca que carnero, salpicon las mas noches, duelos y quebrantos los sabados, lantejas los viernes, algun palomino de anadidura los domingos, consumian las tres partes de su hacienda. el resto della concluian sayo de velarte, calzas de velludo para las fiestas, con sus pantuflos de lo mesmo, y los dias de entresemana se honraba con su vellori de lo mas fino. tenia en su casa una ama que pasaba de los cuarenta, y una sobrina que no llegaba a los veinte, y un mozo de campo y plaza, que asi ensillaba el rocin como tomaba la podadera. frisaba la edad de nuestro hidalgo con los cincuenta anos; era de complexion recia, seco de carnes, enjuto de rostro, gran madrugador y amigo de la caza. quieren decir que tenia el sobrenombre de quijada, o quesada, que en esto hay alguna diferencia en los autores que deste caso escriben; aunque, por conjeturas verosimiles, se deja entender que se llamaba quejana. pero esto importa poco a nuestro cuento; basta que en la narracion del no se salga un punto de la verdad. es, pues, de saber que este sobredicho hidalgo, los ratos que estaba ocioso, que eran los mas del ano, se daba a leer libros de caballerias, con tanta aficion y gusto, que olvido casi de todo punto el ejercicio de la caza, y aun la administracion de su hacienda. y llego a tanto su curiosidad y desatino en esto, que vendio muchas hanegas de tierra de sembradura para comprar libros de caballerias en que leer, y asi, llevo a su casa todos cuantos pudo haber dellos; y de todos, ningunos le parecian tan bien como los que compuso el famoso feliciano de silva, porque la claridad de su prosa y aquellas entricadas razones suyas le parecian de perlas, y mas cuando llegaba a leer aquellos requiebros y cartas de desafios, donde en muchas partes hallaba escrito: la razon de la sinrazon que a mi razon se hace, de tal manera mi razon enflaquece, que con razon me quejo de la vuestra fermosura. y tambien cuando leia: ...los altos cielos que de vuestra divinidad divinamente con las estrellas os fortifican, y os hacen merecedora del merecimiento que merece la vuestra grandeza.

Pero decidi cambiarlo por:

en un lugar de la mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivia un hidalgo de los de lanza en astillero, adarga antigua, rocin flaco y galgo corredor.

Los resultados fueron los siguientes:

Aunque sus frecuencias siguen manteniendose grandes de la "d" a la "g", estas bajaron. El resultado de el test fue:

Parece que al haber llaves pequeñas reduce las coincidencias entre 0's y 1's, esto es porque seguramente las repeticiones son más largas que el mensaje corto. En cambio las del mensaje largo son suficientemente largas para hacer notar la repeticion de ciertos patrones generados.









Fuentes:

Pruebas de Aleatoridad
Valor P
Statistical Testing of Randomness
Pruebas estadisticas para números pseudoaleatorios