jueves, 30 de agosto de 2012

[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

martes, 28 de agosto de 2012

[VERIFICACIÓN Y VALIDACIÓN] Lógica proposicional

Para la tarea de esta semana se encargó buscar ejemplos de las aplicaciones de la lógica proposicional en la vida real.

En si, la lógica proposicional estudia las proposiciones o sentencias lógicas, sus posibles evaluaciones de verdad y en el caso ideal, su nivel absoluto de verdad.

Se define una proposición como un enunciado declarativo que puede ser verdadero o falso, pero no ambos a la vez.

Sintaxis
  • Constantes lógicas verdadero (V) o falso (F).
  • Variables P, Q y R.
  • Conectivos lógicos: negación (¬), conjunción (^), disyunción (v), implicación (-->), implicación doble (<-->), etc.
  • Símbolos de puntuación: paréntesis ( ), corchetes [ ] y llaves { }.
Tabla de verdad de algunos conectivos lógicos:
Aplicaciones

En matemáticas:
  • Fundamenta las matemáticas.
  • Rama de las matemáticas.
  • Mecanización del razonamiento matemático.
En informática:
  • Base de partes de la informática con mayor futuro:
    • I.A., Sistemas expertos, 
    • Programación Lógica.
  • Primer ejemplo de construcción de un lenguaje formal o artificial.
  • Paradigma de programación.
  • Otras aplicaciones:
    • Especificación y verificación de programas.
    • Deducción automática.
    • Diseño de circuitos electrónicos.
En I.A.

Una visión muy frecuente entre los investigadores de la Inteligencia Artificial es que para que un sistema sea "inteligente", debe contener un componente que se puede entender como lingüístico tal que:
  • Contiene el conocimiento del sistema, y
  • Conduce el comportamiento inteligente del sistema
Un Agente Basado en Conocimiento (ABC) es aquel sistema que posee conocimiento de su mundo y que es capaz de razonar sobre las posibles acciones que puede tomar para cambiar el estado de su mundo. Mediante sentencias lógicas se logra el razoamiento en conjunto con su conocimiento para dar respuestas lógicas, o bien realizar cambios esperados en algún sistema.

Una lógica es un sistema formal para describir lo que esta sucediendo en un momento determinado y que consta de:

Sintaxis : Reglas que explican cómo construir oraciones o sentencias legales
Semántica : Cómo las oraciones representan hechos en el mundo.

La semántica estudia el significado de los signos lingüísticos, esto es, palabras, expresiones y oraciones. Qué signos existen y cuáles son los que poseen significación esto es, qué significan para los hablantes, cómo los designan, y por último, cómo los interpretan los oyentes.

Teoría : Reglas para inferir oraciones desde otras oraciones

Si la semántica y la sintaxis están definidas de manera precisa, se dice que el lenguaje es una lógica.

En Sistemas Expertos

Los sistemas expertos son programas que reproducen el proceso intelectual de un experto humano en un campo particular, Estos sistemas permiten la creación de máquinas que razonan como el hombre, restringiéndose a un espacio de conocimientos limitado.

Estos sistemas se diferencian de las IA's en que se especializan en un campo muy específico, por lo tanto es eficiente para lo que se diseña, es rápido y puede trabajar en ambientes peligrosos.

Un Sistema Experto está conformado por:
  • Base de conocimientos (BC): Contiene conocimiento modelado extraído del diálogo con un experto.
  • Base de hechos (Memoria de trabajo): contiene los hechos sobre un problema que se ha descubierto durante el análisis.
  • Motor de inferencia: Modela el proceso de razonamiento humano.
  • Módulos de justificación: Explica el razonamiento utilizado por el sistema para llegar a una determinada conclusión.
  • Interfaz de usuario: es la interacción entre el SE y el usuario, y se realiza mediante el lenguaje natural.
Utilizando una representación primitiva del lenguaje, permite representar y manipular aserciones sobre el mundo que nos rodea.

Mediante la lógica proposicional evalúa sentencias simples, que en conjunto se convierten en unas más complejas, con esta serie de sentencias el sistema es capaz de interactuar con su entorno para adquirir conocimiento o dar la respuesta requerida. A pesar de lo anterior, los sistemas expertos no tienen sentido común desarrollado, osea que no diferencian entre lo que es lógico o ilógico en la mayoría de los casos, a menos que se defina una sentencia para cada caso.



Fuentes

martes, 21 de agosto de 2012

[VERIFICACIÓN Y VALIDACIÓN] Lógica proposicional; formas normales

Para esta tarea buscaré una expresión que sea una tautología.

En lógica, una tautología es una fórmula bien formada de un sistema de lógica proposicional que resulta verdadera para cualquier interpretación; es decir, para cualquier asignación de valores de verdad que se haga a sus fórmulas atómicas. La construcción de una tabla de verdad es un método efectivo para determinar si una fórmula cualquiera es una tautología o no.

Comenzé con una pequeña expresión y trate de que todos sus valores sean verdaderos, la expresión con la que encontré la tautología es la siguiente:

[(A Λ B) Λ C] 

Y esta es la tabla de verdad:

Despues busqué una segunda expresión:

(C V ¬A) V ¬C

Y su tabla de verdad:

Y una ultima expresión:

¬(A Λ ¬B)

Y su tabla de verdad:

Las primeras 2 las uní con un "or", en si esta ya es una tautología:

{[(A Λ B) Λ C] V [(C V ¬A) V ¬C]}

Y su tabla de verdad:

Y esa expresión la uní a la última con otro "or":

{[(A Λ B) Λ C] V [(C V ¬A) V ¬C]} V ¬(A Λ ¬B)

Y la tabla resultante es una tautología.

Por último mencionar que si tenemos una ecuación larga, si alguna de sus expresiones es una tautología, es más facil que toda la ecuación sea una tautología.



lunes, 13 de agosto de 2012

[VERIFICACIÓN Y VALIDACIÓN] Introducción a la verificación formal


La verificación y validación es el nombre que se da a los procesos de comprobación y análisis
que aseguran que el software que se desarrolla está acorde a su especificación y cumple las
necesidades de los clientes.

Verificación:

El papel de la verificación comprende comprobar que el software está de acuerdo con su especificación. Se comprueba que el sistema cumple los requerimientos funcionales y no funcionales que se le han especificado.

Validación:

La validación es un proceso mas general. Se debe asegurar que el software cumple las expectativas del cliente. Va mas allá de comprobar si el sistema está acorde con su especificación, para probar que el software hace lo que el usuario espera a diferencia de lo que se ha especificado.

Los problemas que puede causar el no realizar una verificación y validación han provocado errores fatales tales como:
  • Un sistema de alertas, casi causa la 3ª Guerra Mundial (1983). Según el registro del fallido sistema, Estados Unidos había disparado 5 misiles. De no ser por Stanislav Petrov muchas personas habrían muerto y el rumbo de la historia habría cambiado.
  • La red de AT&T se colapsa (1990). Durante 9 horas, 75 millones de llamadas no se contestaron en Estados Unidos por un error en la actualización de un software utilizado en el sistema.
  • La explosión del Ariane 5 (1996). El cohete -de 8 mil millones de dólares-, que contenía 4 satélites valorados en 500 millones de dólares, explotó tras sufrir un fallo en su computador: el aparato saltó en pedazos a los 36,7 segundos de su lanzamiento, al tratar de convertir unos datos de formato 64 bits a formato 16 bits.
  • El Airbus A380 se retrasa por problemas de incompatibilidad de software (2006). Los aviones se hacen por partes, así que una hecha en Alemania se hizo con una versión desactualizada de un programa, mientras que en la otra -hecha en Francia- se utilizó la versión más reciente de dicho software. Hubo problemas al tratar de conectar ambas partes y el lanzamiento comercial y la producción de los aviones se retrasó un año.
  • El Mars Climate Observer se estrella por el sistema métrico (1998). Se perdió una nave de 125 millones de dólares que iba a estudiar el clima de Marte, cuando hubo un fallo en el cálculo de aterrizaje y terminó por quemarse en la atmósfera. El problema fue que una compañía subcontratada por la NASA utilizó el sistema anglosajón en lugar del sistema métrico decimal, normalmente utilizado por la agencia.



  • EDS y la Agencia de Ayuda a la Infancia (2004). La reforma de la agencia y el programa diseñado por EDS se convirtieron en un verdadero dolor de cabeza para la administración y para los presupuestos de la institución: para remediar los errores, se estaban gastando 70 céntimos por cada libra que entraba.


  • El Y2K (2000). Todo el mundo esperaba el caos cuando millones de ordenadores en el mundo no pudieran procesar los dígitos del nuevo año. Fue muchísimo dinero el que perdieron las empresas, cuando finalmente llegaron las 12 del 1/1/2000 y las máquinas desactualizadas no causaron la catástrofe.



  • La explosión de los portátiles (2006). El primero fue marca Dell y aprovechó un momento inoportuno -una feria japonesa-. Fue un problema en la batería que provocó que la compañía hiciera un recall de 4,1 millones de baterías. Pero en la saga le siguieron Matsushita, Sony, Lenovo, Acer e incluso Apple. ¡Boom!
  • Siemmens y los pasaportes ingleses (1999). Se unieron 2 causas: por primera vez, los menores de 16 años necesitaban pasaporte para viajar, y la agencia encargada de emitirlos empezó a utilizar un sistema que no se probó lo suficiente.
  • Se colapsa el Aeropuerto de Los Angeles (2007). Unas 17 mil personas se quedaron en tierra por un problema de software que provocó conflictos en una tarjeta de red que no funcionó como debía y tiraba de toda la red informática.


martes, 7 de agosto de 2012

[REDES NEURONALES] Introducción y repaso; formación de equipos

Servicio para reconocimiento de texto.

Se trata de un servicio que varias webs utilizan para extraer los caracteres (espacios, letras y números) que hay en una imagen. Algo conocido como OCR (reconocimiento óptico de caracteres).


Existen programas que ya tienen este servicio incluso librerías que ya hacen el trabajo, pero el fin de este proyecto es hacerlo desde 0.

Online OCR es un servicio web que tambien hace lo mismo.

ocropus, pytesser entre otras son librerias de reconocimento óptico de caracteres para python, pero opencv podria ser más adecuado, ademas de uso de otras librerias como pybrain.

http://es.wikipedia.org/wiki/Reconocimiento_%C3%B3ptico_de_caracteres