miércoles, 29 de agosto de 2012

Adecuate randomness

On my last homework, I made the one time pad, if the key are truly random, one time patd is unbreakable and if someones stole the key that's not fault in the algorithm, it is the fault in the store the key.

Cryptography secure adecuate randomness means that is officially random, don't have any patterns that anybody could use for brake the algorithm, if you are making one time pad, you have a pseudorandom generator that has patterns.

If we have patterns or periodicity we have a vulnerability in the one time pad and somebody can synchronize for have my keys that I made with the key generator, and people could get the sequence of the key.

In this report, I'm going to explain and made different test for randomness, and demonstrate if I have a secure or insecure system, at the end I'm going to make a conclusion about it.

First at all, I'm going to make a statistical test for randomness, as you need to know, randomness is a probabilistic property, so we can use different test for make sure that my data have a true random data, I made two different test, a frequency test and a Runs test, I implemented in python, this is my code that generate key using random.choice and select a 15 symbols in ascii then I translate those into integer for made an XOR in the one time pad implementation.



In the frecuency test this are the steps:

  • We need to compute the test statistic: Sobs = abs(s)/sqrt(n) where sn are sum of all the zeros in -1.
  • Then, we need to compute P-value = erfc(Sobs/sqrt(2)), where erfc is the complementary error function.
  • At the end, we need to know if P-value is small (< 0.01), accept the sequence as random

In runs test this are the steps:

  • We need to compute the pre-test proportion pi of ones in the input sequence:
    • sum_pi = SUM(number zeros-ones)/n
  • Compute the test statistic Vobs = SUM(r(k))+1
    • When r(k)=0 if the value of array of number zeros-ones it's the same that the next one, and r(k) = 1 otherwise.
  • Compute P-value = erfc( abs(Vobs-2n*sum_pi*(1-sum_pi))/2*sqrt(2n)*sum_pi*1-sum_pi)
    • If >= 0.01, accept the sequence as random

In based on Secure Telecomunication System slides[1], the recommendation for made the test is for both, Runs and frequency, has a input size minimum 100, so this are the result.


So  in both test, we don't have a good random sequence, to conclude, my implementation is insecure because it not truly random and somebody can have patterns or periodicity and synchronize and have my keys.

Then, I change the random import from python to randint from numpy, I run the same test and I have the same result, sequence are not accept as random by frequency test, as well as runs test.

Then,  I made a comparison between have a compress file with 100000 random numbers and make zip, for pass this test, they cannot be smaller because, as you know, the compress algorithm look for repeat sequence and replace long sequences with short sequences, we can look at the weight compress by kb.

This are the result:


So in the test, we don't have a good random sequence again, because we can compress the file about 46 %, we can conclude, that my implementation is insecure because it not truly random because we can compress the file.

So, for make a conclusion, we can see that in the three test, we don't have a good response and we have a one time-pad very insecure, so we need to develop with a truly random generator key for have a good implementation, only change the key generator, because in the algorithm, we don't have problem, we have problem at making the keys, we need to know that most of the computation random generators are called pseudo-random, because they use a deterministic algorithm, in most of the case is OK for make programs but, in this case, make the one time pad insecure, so, I investigate and we can use a random generate by OS like os.urandom() in python, but never we can have a truly random generator by computer, only if we can have something mechanical like random.org or maybe in the future.

Bibliography
[1] Slides of Secure Telecommunication System here.

martes, 28 de agosto de 2012

BDD

Primero que nada, inventé una expresión con las características deseadas que nos dice en la presentación, por lo que podemos ver que tiene los conectivos y las 3 variables.

Expresión:
((A ^ B)  ^ (B  ^ A)) v ¬ C )

Ahora tenemos el BDD, el cual contiene la expresión hecha en un diagrama binario de desición, tal como lo muestra en el PDF aqui. este es el resultado.

BDD:







Como podemos ver, este diagrama se puede reducir, si se fijan, tenemos salidas repetidas en los primeros 6 nodos de izquierda a derecha, tenemos 1 y 0, por lo que facilmente podemos reducirlo y obtener algo como el siguiente diagrama.

ROBDD:


En este diagrama reducido podemos ver que los 3 nodos repetidos se juntan en C, siguiendo los pasos descritos en el libro podemos decir que este es un ROBDD del primero BDD.

Saludos :)

lunes, 27 de agosto de 2012

Aplicación de la lógica proposicional.

Introducción.

Para la tercera tarea de la materia de verificación y validación de software se nos pide investigar aplicaciones de la lógica proposicional y documentar uno.

Una de las formas de definir la lógica proposicional, como lo vimos en la materia, es el estudio de las formas de razonamiento donde su validación depende solamente de las propiedades verdadero o falso, es el primer paso para la definición de lo que es la lógica y el razonamiento en sí,  como por ejemplo, la siguiente proposición "si llueve, llevo mi paraguas": Llueve -> Paraguas.

El lenguaje natural y la lógica proposicional

La lógica proposicional se puede utilizar para razonar diferentes argumentos del lenguaje natural[1], podemos hacer una serie de pasos para determinar primero que nada las premisas y la conclusión de un argumento identificando las proposiciones formales, luego la lógica proposicional se emplea para determinar si la conclusión es valida según esas premisas, ahora les muestro un ejemplo, supongamos que tenemos la siguiente canción de Joan Manuel Serrat, en donde tenemos el siguiente párrafo.

Caminante son tus huellas el camino y nada más.
Caminante no hay camino, se hace camino al andar,
Al andar se hace camino y al volver la vista hacia atrás.
Se ve la senda que nunca se ha de volver a pisar.
Caminante no hay camino, hay estelas en el mar.

Entonces para poder estudiar el lenguaje natural debemos de seguir una serie de pasos [2]:

  • a) Identificar los enunciados simples: importante recalcar que solamente se formaliza las oraciones declarativas, o sea las que afirman o niegan, fijandose que hablen del mismo objeto, desechandonos de información irrelevante
  • b) Asignar a cada enunciado simple una constante proposicional.
  • d) Identificar las conectivas lógicas: verificar las conectivas no, y, o, si, si y sólo si, algunas veces algunas otras cumplen con la función, como es el caso de la coma.
  • d) Reconstruir los enunciados complejos a partir de los simples y de las conectivas.

Ahora, podemos estudiar este párrafo y encontrar los conectores para demostrar si la conclusión que esta persona que escribió este autor es verdadera, hacemos los siguiente.

Caminante son tus huellas el camino y nada más.
Caminante no hay camino, se hace camino al andar,
Al andar se hace camino y al volver la vista hacia atrás.
Se ve la senda que nunca se ha de volver a pisar.
Caminante no hay camino, hay estelas en el mar.

Los conectivos tienen una traducción en la lógica proposicional, como podemos ver en la siguiente tabla, podemos separar estas proposiciones.


Símbolo Lógica Representación
   -> Implicación        coma
    ^ AND          y
    v OR          o
    ¬ Negación         no


Ahora vamos a representar las siguientes proposiciones.
  • p: Caminante son tus huellas el camino
  • q: Caminante son tus huellas nada más
  • v: Caminante hay camino
  • s: Caminante se hace camino al andar
  • t: Caminante al volver la vista atrás
  • y: Caminante se ve la senda que se ha de volver a pisar.
  • v: Caminante hay estelas en el mar.
Ahora podemos hacer una definición formal de este párrafo.

((( p ^ q ) -> ¬ r) -> s ) -> ( s ^ t ) -> ¬ y -> ¬r -> v

Ahora con el script[3] que hacia realizado anteriormente, lo modifiqué para sacar una tabla de verdad y cuando todas son verdaderas, la definición formal arroja verdadero, cuando todas son falsas arroja que es falsa, por lo que podemos concluir que esta proposición es verdadera y tiene coherencia.

Con esto, tiene su aplicación al examinar la sintaxis y la semántica tanto de la lógica como del lenguaje natural, como lo podemos ver en el documento [4] de la Universidad de Missouri, donde utilizan lenguaje lógico proposicional para procesar el lenguaje natural, creando una relación estrecha por medio de gráfos, en donde cada nodo se representa por una conectiva y por preposiciones, y las relaciones entre ambas.

La lógica proposicional en la industria.

La lógica proposicional es de suma importancia en la industria, sobre todo en sistemas computacionales formales e inteligentes, ya que esta sienta las bases para poder tener fundamentos teóricos y formales para el modelado de sistemas al igual que el tratamiento inteligente de datos para una solución tecnológica.

En psicología, por ejemplo, la cognitiva del ser humano hace énfasis en que tenemos cada uno de nosotros una complejidad en cuestión del aprendizaje por lo que se concluye que nosotros representamos el contenido por estados mentales y representaciones, por ejemplo Newell y Simon [5] en 1972 realizaron un estudio sobre el aprendizaje modelando la mente humana como un sistema de procesamiento de información, planteando que el pensamiento es el hecho de procesar mucha información manipulando símbolos, entonces los estados mentales del ser humano se empezaron a comprar con sistemas de signos organizados en un lenguaje en donde se deben de conocer las reglas, en este caso estas reglas utilizan la lógica proposicional para describir las representaciones mentales.

Todo esto nos lleva a que la lógica proposicional ayuda de una forma matemática a aplicar computacionalmente representaciones mentales y obtener inteligencia la cual no proviene de un ser humano, si no que, es artificial dentro de una computadora, es aquí en donde la lógica proposicional tiene cabida, con el hecho de que muchas aplicaciones con lo que actualmente interactuámos, tiene inteligencia artificial, el hecho de jugar un videojuego con la computadora hace que estemos relacionándonos con una inteligencia que no es de un ser.

Espero que esta tarea ayude a comprender la importancia de la lógica proposicional.

Bibliografía

[1] Applications of Propositional Calculus, Mathematical Approaches to Software Quality, Gerard O' Regan, Springer.

[2] La formalización del lenguaje natural, Universidad de Granda

[3] Tarea de tautología: liga
[4] A logical Language for Natural Language Processing, Syed S. Ali

[5] L'apprentissage organisationnel, Frédéric LEROY liga



jueves, 23 de agosto de 2012

Residue en Octave

En esta primera entrada para el labortorio voy a explicar una función de suma importancia en Octave para la clase de Automatización y control de sistemas dinámicos, se pretende que al leer esta entrada se pueda comprender el uso de la herramienta Octave para poder sacar los residuos.

¿Qué son las Fracciones Parciales?
En álgebra, la descomposición en fracciones parciales es un procedimiento que se utiliza para poder reducir el grado ya sea del numerador o del nominador de una función racional, existen diferentes casos en donde debemos descomponer en factores, de tal manera que se nos facilite la solución de algún problema.

Entre los casos que podemos mencionar los siguientes:

Caso 1. Factores lineales distintos.
A cada factor lineal (ax + b) le corresponde una fracción de la forma:


Caso 2. Factores lineales repetidos.
A cada factor lineal repetido (ax + b)^k le corresponde la suma de k fracciones parciales de la forma:

Caso 3. Factores cuadráticos distintos.
A cada factor cuadrático (ax^2+bx+c) le corresponde una fracción de la forma:

Caso 4. Factores cuadráticos repetidos.
A cada factor cuadrático repetido (ax^2+bx+c)^k le corresponde la suma de k fracciones parciales de la forma:

Existen más casos, pero estos son los más comunes.


¿Qué es la función residue en Octave?

Existen un número de funciones en Octave con el fin de manipular los polinomios entre ellas esta la función residue en donde se encuentran los siguientes parámetros:

[R, P, K, E] = residue(a, b)

  • a = vector que incluye los coeficientes de los polinomios en la parte superior.
  • b = vector que incluye los coeficientes de los polinomios en la parte inferior
Si ambos son vectores con coeficientes de los polinomios, se calcula el residuo de expansión de fracción parcial correspondiente a la relación de los dos polinomios.

Teniendo como resultado 3 parámetros R, P y K.

  • R = vector que contiene los términos de residuos.
  • P = contiene los valores de los polos.
  • K = contiene los términos independientes
Como parámetro opcional se puede definir un tercer valor a la función residue para agregar la toleracia, en donde por default es .001 y regresar el vector E que contiene las potencias de los denominadores en los terminos de las fracciones parciales.


¿Cómo funciona esta función?


Suponiendo que tenemos la siguiente función:

Podemos utilizar la función residue de Octave para sacar sus fracciones parciales de una manera muy sencilla, vamos a capturar en un vector los coeficientes de la parte del numerador y del denominador de la siguiente manera: [1, 14],[1,3,3,1]

Estos son los valores que entran en la función residue, como saben ponemos en el terminal, octave y luego ponemos la función de este modo: [R, P, K] = residue([1,14],[1,3,3,1])

Obtenemos el siguiente resultado:

Como dijimos anteriormente, obtenemos el residuo (R), los polos (P) y los términos independientes (K).
Ahora hace falta construir las fracciones parciales con estos valores, por lo que tendríamos algo como esto.


En donde decimos que:
Y tenemos como fracciones parciales.


Espero que con este ejemplo puedan desintegrar fácilmente cualquier función racional, ya que con esto ayudamos a derivar e integrar con términos más simples.

Esto sería todo para la primera entrada del laboratorio.

miércoles, 22 de agosto de 2012

ONE-TIME PAD -- Python

This is my intro homework implementing ONE-TIME PAD, I made two different script, one for make the keys and save it into file, and then a simulation script, those are the codes.

This code generate keys, using choice and library string

This code made a simulation that take the keys and erase from the file, that's exactly how works one-time pad.
This is the sample out of how works my code.


Robertomtz-2:Desktop roberto$ python genera_key.py
<open file './Roberto/key_1.txt', mode 'w' at 0x10e1e4ae0>
<open file './Ramon/key_2.txt', mode 'w' at 0x10e1e4b70>


463763421315310488663110378560176982

396445231729019104983631110994544205
417134473902073172990551648684034887
354461120138371425565563466647161416
406749964060333827409156118218752342


<closed file './Roberto/key_1.txt', mode 'w' at 0x10e1e4ae0>

<closed file './Ramon/key_2.txt', mode 'w' at 0x10e1e4b70>


Robertomtz-2:Desktop roberto$ python OTP_sim.py

Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1

Escribe el mensaje a enviar a Roberto

>> Hola amigo

Llave usada por Ramon = 463763421315310488663110378560176982
Mensaje codificado 463763421314970161502469700003374137
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 463763421315310488663110378560176982
Mensaje decodificado Hola amigo
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2

Escribe el mensaje a enviar a Ramon

>> Como estas

Llave usada por Roberto = 396445231729019104983631110994544205
Mensaje codificado 396445231728711576779657101873915710
Recibido por Ramon
Ahora Ramon lo va a decodificar
Llave usada por Ramon = 396445231729019104983631110994544205
Mensaje decodificado Como estas
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1

Escribe el mensaje a enviar a Roberto

>> bien y tu

Llave usada por Ramon = 417134473902073172990551648684034887
Mensaje codificado 417134473902072616769792045078101810
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 417134473902073172990551648684034887
Mensaje decodificado bien y tu
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2

Escribe el mensaje a enviar a Ramon

>> bien tambien

Llave usada por Roberto = 354461120138371425565563466647161416
Mensaje codificado 354461109587947668995530738586365734
Recibido por Ramon
Ahora Ramon lo va a decodificar
Llave usada por Ramon = 354461120138371425565563466647161416
Mensaje decodificado bien tambien
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1

Escribe el mensaje a enviar a Roberto

>> me da gusto        

Llave usada por Ramon = 406749964060333827409156118218752342
Mensaje codificado 406749964015467211724918636957414713
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 406749964060333827409156118218752342
Mensaje decodificado me da gusto
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2

Ya no existen llaves

sábado, 18 de agosto de 2012

martes, 14 de agosto de 2012

Introducción a la validación y verificación de software

Como una pequeña introducción para la materia, estuve investigando sobre la validación y verificación de software para así comprender para que sirven estos métodos formales y en el futuro comprenderlos para implementarlos en sistemas que lo requieran.

Para empezar, podemos decir que la validación de software es el saber si nuestro sistema hace lo que nosotros buscamos que haga, esto quiere decir que si construimos el sistema de manera correcta, no es simplemente ver el código, si no que existen métodos formales que tiene cierta dificultad para determinar si se hace lo correcto, según lo que el usuario o el cliente en realidad necesita o requiere, podemos decir que contesta a la pregunta ¿Estamos haciendo el sistema correcto? [1].


Por otra parte, podemos decir que la verificación de software es saber si el sistema que estamos desarrollando hace de manera funcional y no funcional lo que nosotros especificamos en algún análisis previo a implementarlo y compararlo utilizando métodos formales, podemos decir que contesta a la pregunta ¿Estamos haciendo el sistema correctamente? [1].



Por lo tanto, podemos decir que cuando nosotros tenemos un sistema, por ejemplo, que involucre conceptos de sistemas distribuidos, paralelos, necesitemos entradas o salidas de sensores, no existe una manera sencilla de saber que todas las combinaciones posibles funcionen correctamente dependiendo de los eventos ocurridos, la unica manera de poder realizar esto es con métodos formales, expresando toda la especificación del sistema en un lenguaje matemático lógico, examinando que no existan cuestiones en el sistema que no deberían de pasar, esto quiere decir que no vamos a correr el sistema en sí, si no que se va  estudiar con estos métodos para saber si la especificación es correcta.


Es importante recalcar que nunca vamos a tener un sistema el cual no tenga errores o defectos, pero este tipo de métodos nos sirven para reducir el porcentaje de defectos y tener un producto mejor al momento de usarlo.

En conjunto, podemos utilizar la validación y la verifiación del software como un proceso para analizar si el sistema en desarrollo o final, cumple con los requisitos del cliente y se encuentra conforme con la especificación del mismo.


Buscando en la web, encontré algunas empresas en México que se dedican o manejan como alguno de sus servicios la verificación y validación de software, entre ellas se encuentran: IRQADNV, Epicor, entre otras.

La razón por la que esta materia es importante es que estudios como por ejemplo de la empresa Compuware, en donde revela que después de un análisis, las empresas que tienen un fallo por medio de software alcanzan hasta los 7.5 millones de euros en una hora [2], este sector, incluyendo por ejemplo a los trabajadores sin actividad de hasta 140 horas anuales o suspension de total de ventas.

Por listar algunos errores de software [3] que se pudieron haber evitado con una buena implementación de validación y verificación son:

  • Un error en el código de control del producto Therac-25 fue la responsable de al menos 5 muertes en la decada de los 80, produciendo cantidades exageradas de rayos X [4].
  • El Ariane 5 fue destruido 40 segundos después del despegue debido a un error de software a borde, causando perdidas de millones de dólares [5].
  • El error de software de MIM-104 Patriot hacia que su reloj del sistema estuviera a la deriva en un tercio de segundo, llevando al fracaso el interceptar un misil [6].

Bibliografía

[1]  Software Engineering: A Practitioner’s Approach, 7/e  (McGraw-Hill 2009).
[2]  Los fallos informáticos suponen pérdidas, Computing.es (2012) Liga.
[3]  List of software bugs, Wikipedia Liga.
[4]  An investigation of the Therac-25 Accidents, Nancy Leveson, University of Washington (1993) Liga
[5]  ARIANE 5 Report, Inquiry Board (1996) Liga.
[6]  Patriot Missile Software Failure, Aly Farahat, Slides (2009) Liga.

jueves, 9 de agosto de 2012

Cryptography exercises

(`)t|<s(|x<^<(|"<_xQ=__$<)^<_^|l<|<^)s<:t_x^)tiQ=__%:<t_x<(+<s(+xs+:<:t_^:+:Q:t+|^:(})l<=`<s(+]|%=<_t|<:l+$<_x^Q^:_t<|<:l__(<_x:<l_t+^<:t_x^)&Q^:_i<]|l(`:<:+x<:t|_}<t_x^|-QQ<t`)<-)<_%ll+&<_x^<(+<_:`)x<t`)Q^__t^:<t`)<-)<_%ll+&<_x^<(+<_:`)x<t`)QQ)`t<x)`:_<+(<^x_<&+ll%_<)-<)`t<:^t__^Q)`t<x)`:_<+(<^x_<&+ll%_<)-<)`t<QQ)`t<x)`:_<+^<x|:<|<"t)}lQ^x_t_:<|%}|]:<:)&_^x+(s<x|==_(+(sQ|(l<+^:<`:`|%%]<?`+^_<%)`lQ)`t<&`&<:x_:<:)<x)`:_<=t)`lQ()^x+(s<_{_t<:%)}:<x_t<l)}(Q|(l<|<&_::<+:<()^<|%%)}_lQ

martes, 7 de agosto de 2012

Automatización y control de sistemas dinámicos

Automatización y control
de sistemas dinámicos

Verificación

Roberto

Proyecto de redes neuronales

Reconocimiento de voz para desbloquear

 Realizar un sistema con una red neuronal en el cual al momento de hablarle a la computadora pueda reconocer tu timbre de voz para poder desbloquear la computadora, esto seria útil para aquellas personas.

















Poder medir por medio de algunos indicadores el procesamiento de voz, existen algunas librerias las cuales hacen ese procesamiento y me gustaria implementar.

 Ligas interesantes

Reconocimiento de frutas para supermercado

Realizar un sistema el cual por medio de alguna camara detecte una fruta y a partir de ese pueda saber cual es la fruta, para asi las cajeras no tengan que teclear el código, el cual las frutas y verduras no tienen, y puedan utilizar una red neuronal.
 

















Poder medir por medio de algunos indicadores la imagen por medio de OpenCV y luego procesarlas para entrenar la red.

Ligas interesantes