Analysis for Pseudorandomness in One-Time Keys

Seguridad de la Información y Criptografía
Homework 2

Last week we write a python program for create one-time pads for two users, and then we use one of the keys and send a encrypted message, and the other user receive that message and decrypt with the same key, and every key that we use was deleted.

In that program we use a python random function for create the one-time keys, and now we need to check if the keys are secure.

And the question is:

Are one-time pads unbreakable?
"Yes. But only if used properly. A one-time pad must be truly random data and must be kept secure in order to be unbreakable." [1]

In class we learn three characteristics of a randomness key:

• Unpredictable.
• Uncompressible.
• Unreproducible.

This three characteristics can be passed with a statistical test in the random keys, there are some tests that we can use, like Monobit Test, longest run of ones in a block, non overlapping template, and more.

In my case I use two tests that I had used in the past, monobit test and frequency block test, the next link is one of my publications in this blog, where I talk about statistical tests for pseudorandomness numbers.

Statistical tests for pseudorandomness numbers

I modify my last code for one-time pads, and in this case I add the functions for check every key with the two tests.

Note: I add a hashtag in the main function in the lines that encrypt and decrypt the message, because I only want to check the result of the test.

And here is my code:


And here is an example of an execution where I only request 4 keys, and every key was checked by the two tests.

If you check my code, in the part of the monobit test I need to change a character for a binary number (0 or 1), and in the frequency blocks I change the character for an int number.

Other important thing is that in the frecuency blocks, in my runnings ever gets a 1.0, but is because is use a little length of the key, if I change for 100000, the number change, but it takes more time for check every key.

One more thing that I used for check my one-time pads, is compressing the file with the keys and view the difference of size of the original file with the compressed file, and we can know how many is the percentage of compressing.

Pay attention in keys1 with keys1.tar.gz the compression is 16.95% less than the original, and keys22 with keys22.tar.gz the compression is the same, so if I create a file with more keys the percentage of compression don't change drastically.

ramon@pavilion:~/Documents/programas/criptologia/breakonetimepad$ ls -l
total 20672
-rwxr-xr-x 1 ramon ramon     3289 Aug 30 08:02 checkontimepad.py
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys1
-rw-rw-r-- 1 ramon ramon   831446 Aug 30 08:07 keys1.tar.gz
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys2
-rw-rw-r-- 1 ramon ramon 10010000 Aug 30 03:35 keys22
-rw-rw-r-- 1 ramon ramon  8313357 Aug 30 03:35 keys22.tar.gz

The percentage of compression isn't as bad as I think, so if the compression was more than 50%, someone can attack our keys easily, but isn't the case.

References and other pages:
[1] - One-time pad
Statistical Tests for Random Number Generators

Aplicaciones de la Lógica Proposicional

Verificación y Validación de Software
Entrada 3

En esta publicación hablaré de una de las aplicaciones de la lógica proposicional, primeramente veremos algunos términos y cosas básicas para entrar en el tema, y después hablaré del caso en específico.

Antes de empezar, cabe mencionar que la lógica proposicional es usada en muchos ámbitos, sobre todo computacionales, por lo que su uso suele ser básico en muchos sistemas. De entre varios usos aplicados que me ha tocado leer en internet son la representación del conocimiento o razonamiento con sentido común, dentro del campo de inteligencia artificial, verificación de propiedades en ingeniería de software, algoritmos de aproximación mediante teoría de la computación, verificación de protocolos criptográficos y diseño de circuitos digitales, entre muchos más.

Lógica proposicional

Definición:
"La lógica proposicional es la parte de la lógica que estudia la formación de proposiciones complejas a partir de proposiciones simples, y la inferencia de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples." [1]

Sintaxis usada en la lógica proposicional

Variables proposicionales (P): p, q, r, s, t...
(Se puede usar cualquier letra del abecedario, pero normalmente se usan letras a partir de la "p")

Conectivos lógicos: ¬, ∨, ∧, →, ↔
(Los conectivos anteriores suelen ser los que se usan, pero existen simbologías diferentes)

Símbolos de puntuación: (, )
(Se usan paréntesis para separar expresiones y evitar confusión, tal y como se hace en álgebra, y también puede ser usados corchetes y llaves)

Es importante saber que cada variable proposicional es una entidad completa y que no se puede dividir, y que solamente puede tomar uno de dos diferentes valores: verdadero (1) o falso (0).

Tablas de conectivas lógicas

Nombre	Lenguaje natural	Ejemplo	Símbolo
Negación	no	No hace frío	¬
Conjunción	y	Hace frío y está nublado	∧
Disyunción	o	Hace frío o hace calor	∨
Condicional	si-entonces	Si hace frío, entonces uso abrigo	→
Bicondicional	si y sólo si	Está nublado si y sólo si hay nubes visibles	↔

Para cada una de estas conectivas lógicas existen tablas de verdad, que me imagino ya hemos visto en algún momento dentro de nuestras clases, les dejo aquí una imagen con las tablas de verdad de los conectivos anteriores, obtenida de Wikipedia y que compare con algunos apuntes, para verificar que están correctas.

Uso de la lógica en computación

"Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Álgebra de Boole. El Álgebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicos puede realizarse con rapidez." [2]

Todo lo anterior son nociones básicas que ya debemos de saber, y es solo una breve introducción, para poder entrar en el caso particular.

Diseño de circuitos

La realización del diseño de un circuito puede involucrar la creación de un sistema electrónico complejo, como el de una placa madre de una computadora, o circuitos menos complejos como el de un sistema integrado.

Cuando son diseños "pequeños" es fácil que una sola persona pueda hacerlos, pero cuando se habla de algo complejo, se requiere a un equipo de personas que hagan un diseño con enfoque sistemático y del cuál se puedan hacer pruebas mediante un simulador, antes de la fabricación del mismo.

La etapa del diseño del circuito, es donde se genera el esquema del circuito integrado, y se considera una etapa media entre el diseño lógico (donde se dice qué debería de hacer el circuito en base a que entradas) y el diseño físico (parte en la que se estructura el diseño del circuito a imprimir a una placa).

[Al hablar de un circuito impreso en una placa me refiero a algo como en la siguiente imagen]

[http://www.arqhys.com/contenidos/diseno-circuitos.html]

Un circuito lógico es aquél que interpreta la información y hace una operación en base a el voltaje de entrada, que puede ser "alto" (1) o "bajo" (0).

El circuito ejecutará una serie de funciones lógicas, a través de puertas lógicas como los conectivos NOT, AND y OR, así como de combinaciones de las mismas como XOR.

Puertas lógicas

En seguida imagen con las puertas lógicas mencionadas. Estas no son todas las existentes.

[http://blogpumaagl.blogspot.mx/2010/10/circuitos-logicos.html]

Como podemos observar cada puerta tiene dos valores de entrada, a excepción del NOT, y solamente pueden tener un valor de salida 0 o 1, y para cada una de ellas existe una tabla de verdad, las mismas que en los conectivos lógicos correspondientes mencionados en la primer parte de esta publicación.

Ejemplo de diseño de un circuito

Para realizar un circuito lo primero que necesitamos es saber las especificaciones del cliente, es decir, saber que es lo que se quiere que el circuito de como resultado.

Enseguida les comparto un ejemplo de mis apuntes de sistemas digitales, donde podemos aplicar el diseño de un circuito.

"Diseñar un circuito que indique al operador de la torre de control de un aeropuerto cuando un avión Jumbo 747 puede aterrizar. Se tienen 3 pistas en el aeropuerto (p, q y r), y cuando una de ellas esta disponible, se obtiene una entrada lógica de 1. Además este tipo de avión solo puede aterrizar cuando existen dos pistas contiguas disponibles."

Ahora sabemos que lo que se desea es un indicador para el operador de la torre, este puede ser un led que encienda cuando es posible aterrizar. Se enciende cuando la salida del circuito es 1, se mantiene apagado cuando la salida es 0. Como entrada tenemos 0 si la pista no esta disponible, y 1 cuando si lo esta.

Creamos una tabla de verdad con las salidas que necesitamos.

p	q	r	Salida
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

La tabla queda así, porque solo cuando tenemos dos unos contiguos en las entradas (dos pistas contiguas disponibles), significa que la salida sera 1 (puede aterrizar el Jumbo 747).

Ahora mediante mapas de Karnaugh, obtendremos la proposición de salida.

r \ pq	00	01	11	10
0	0	0	1	0
1	0	1	1	0

Con esto podemos obtener la función lógica del circuito.
S = qr + pq
S = (q^r) ∨ (p^q)

Y el diseño de este circuito usando puertas lógicas quedaría así:

Podemos simplificar:
S = q(r + p)
S = q^(r ∨ p)

[Imágenes creadas desde http://www.circuitlab.com/editor]

Con este circuito podemos dar solución al problema planteado, y básicamente los pasos que seguí son los que se utilizan para el diseño de circuitos.

Verificación y pruebas del diseño de un circuito

"Una vez que el circuito ha sido diseñado, debe ser a la vez verificado y probado. La verificación es el proceso de pasar a través de cada etapa de diseño y asegurando que va a hacer lo que la especificación exige que haga. Esto es frecuentemente un proceso altamente matemático y puede involucrar a gran escala simulaciones por ordenador del diseño. En cualquier diseño complejo que es muy probable que los problemas se encuentran en esta etapa y puede implicar una gran cantidad del trabajo de diseño de hacerse de nuevo con el fin de solucionarlos." [3]

Referencias y documentos consultados:
[1] y [2] Lógica proposicional
[3] Circuit design
Lógica proposicional - PDF
Diseño de circuitos lógicos - PDF

Forma Normal Disyuntiva - DNF

Verificación y Validación de Software
Agregado 1

Como tarea extra realice un ejemplo pequeño de una proposición y que lo pasaré a la forma normal disyuntiva, que se denota por DNF por sus siglas en inglés.

La idea de esto es inventar cualquier proposición, y mediante leyes de equivalencia, como las leyes de Morgan, hagamos que nuestra proposición quede expresada únicamente con los operadores de negación y disyunción, que se denota así {¬, ∨}.

Entonces la proposición simple que invente es.

(¬c → b)^(c → ¬a)

Y ahora vamos a cambiar los operadores usados para que quede, como ya dije, con operadores de negación y disyunción.

Por si tienen duda de las leyes de equivalencia, yo encontré en la siguiente página las más básicas y que me ayudaron en la realización de esta tarea.

Leyes de equivalencia

Entonces tenemos que:

(¬c → b) ^ (c → ¬a)
Primero pasamos a eliminar los operadores condicionales que están dentro de los paréntesis, con la ley de Implicación Material.

(¬¬c ∨ b) ^ (¬c ∨ ¬a)
Simplificamos la parte del doble operador negativo.

(c ∨ b) ^ (¬c ∨ ¬a)
Luego para eliminar la conjunción, usamos las leyes de Morgan.

¬[¬(c ∨ b) ∨ ¬(¬c ∨ ¬a)]

Y ahora ya tenemos la proposición expresada solo con operadores de negación y de disyunción. Ahora vamos a probar si la original, con esta última nos dan como resultado la misma tabla de verdad.

Para ahorrar tiempo use el mismo programa que había creado para verificar si una proposición era una tautología, y probé estas dos proposiciones.


Entonces para (¬c → b) ^ (c → ¬a) el siguiente resultado.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
conjuncion(condicional(negacion(C),B) , condicional(C,negacion(A)))
a b c  S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y para ¬[¬(c ∨ b) ∨ ¬(¬c ∨ ¬a)] se obtuvo.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
negacion(disyuncion(negacion(disyuncion(C,B)),negacion(disyuncion(negacion(C),negacion(A)))))
a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y como podemos observar, en las dos tablas de verdad obtenemos los mismos valores en la salida S.

Ahora con mapas de Karnaugh

También es posible obtener la proposición en DNF, mediante códigos de Gray y mapas de Karnaugh.

Para esto partimos de la proposición original (¬c → b) ^ (c → ¬a) y obtenemos sus valores de salida junto con los códigos Gray, en una tabla de verdad.

a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y ahora usando mapas de Karnaugh obtendremos la forma normal disyuntiva (DNF).

c \ ab	00	01	11	10
0	0	1	1	0
1	1	1	0	0

Y los mapas nos dan la proposición a'c + bc', que podemos escribir también como (¬a^c) ∨ (b^¬c), y en base a la definición de wikipedia de "una fórmula está en forma normal disyuntiva (DNF) si corresponde a una disyunción de cláusulas conjuntivas" [1], sabemos que lo que esta entre paréntesis son las cláusulas conjuntivas, y hay una disyunción entre los dos.

Con el programa volvemos a probar con esta nueva fórmula, y vemos que la tabla de verdad sigue dando los mismos resultados de salida.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
disyuncion(conjuncion(negacion(A),C),conjuncion(B,negacion(C)))
a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Recursos consultados:
[1] Forma normal disyuntiva - Wikipedia
Leyes de equivalencia

One-time Pads

Seguridad de la Información y Criptografía
Homework 1

This is the first homework for the cryptography class, and the topic is One-Time Pads. We make a program where we create two files with the same list of keys and a function to encrypt and decrypt a message or text with a size less or equal than the key.

At the end of this post I embed my complete code, but in the next part I try to explain how my code works.

What is an One-time pad?

"In cryptography, the one-time pad is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting in a ciphertext."

If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key. So, the only bad thing about this method is if we don't be careful how the list of keys are saved or where, it can be insecure, but is better that the last time when we only encrypt a text rotating the alphabet or changing the position of the alphabet.

My code

First of all, I create a function where the program open two different files, "keys1" and "keys2", then choose a random number between 32 and 126, for convert that number into a ASCII char character, and write a line of characters with a length defined in the beginning of the code (KEY_SIZE).

def create_files_with_keys(n):
  file1 = open('keys1', 'w')
  file2 = open('keys2', 'w')

  for i in range(n):
    key = ''
    for j in range(KEY_SIZE):
      key = key + chr(int(random.uniform(32,126)))
    key = key + '\n'
    file1.write(key)
    file2.write(key)

  file1.close()
  file2.close()

In this image I show what happens when I run my program. In the main function I call to "create_files_with_keys(n)", and the files were created.

And in this case I only create 4 keys, that I defined in the beginning of the code with a global variable. Check that the same keys were written in the two files.

Now for encrypt a message I read line by line in the file with the keys and save it in an array, then write again the keys in the file less the first that we need to use for the encryption.

I use the module for encrypt the message. And for debug print the message, the current key, and the ciphertext.

def encrypt(message):
  keys_file = open('keys1', 'r')
  ciphertext = ''
  residue = []

  for line in keys_file:
    residue.append(line.strip('\n'))
  keys_file.close()

  keys_file = open('keys1', 'w')
  for i in range(len(residue)-1):
    line = residue[i+1] + '\n'
    keys_file.writelines(line)

  message = message.zfill(KEY_SIZE)
  alphabet = map(chr, range(32,126))

  for i in range(KEY_SIZE):
    suma = alphabet.index(message[i]) + alphabet.index(residue[0][i])
    mod = suma%94
    ciphertext = ciphertext + alphabet[mod]

  print 'Message to encrypt: ' + message
  print 'Key used to encrypt: ' + residue[0]
  print 'Message encrypted: ' + ciphertext
  return ciphertext

For this time I use the file "keys2" to get the first key and can decrypt the message.

For debug I print the ciphertext, the key used (it must be the same for encrypt), and the message decrypted.

def decrypt(ciphertext):
  keys_file = open('keys2', 'r')
  message = ''
  residue = []

  for line in keys_file:
    residue.append(line.strip('\n'))
  keys_file.close()

  keys_file = open('keys2', 'w')
  for i in range(len(residue)-1):
    line = residue[i+1] + '\n'
    keys_file.writelines(line)

  alphabet = map(chr, range(32,126))

  for i in range(KEY_SIZE):
    suma = alphabet.index(ciphertext[i]) - alphabet.index(residue[0][i])
    mod = suma%94
    message = message + alphabet[mod]

  print 'Message to decrypt: ' + ciphertext
  print 'Key used to decrypt: ' + residue[0]
  print 'Message decrypted: ' + message.lstrip('0')
  return message.lstrip('0')

And finally the main function, where I used the number of keys created in the files for receive the same quantity of messages to encrypt and decrypt.

def main():
  create_files_with_keys(N_KEYS)
  print '\n'
  for i in range(N_KEYS):
    message = raw_input('Write a message: ')
    print '\n'
    ciphertext = encrypt(message)
    print '\n'
    message = decrypt(ciphertext)
    print '\n'
  print '\n'

Here's an example of how I write a message, the message is encrypted, the key in one files is deleted, then send the message to the function for decrypt, use the first key in the other file, delete the key and decrypt the message.

Complete code

References
One-Time Pad - Definition

Tutorial Octave

Automatización y Control de Sistemas Dinámicos
Laboratorio: Entrada 1

¿Qué es Octave?

GNU Octave es un lenguaje de alto nivel destinado para el cálculo numérico. Provee una interfaz sencilla, orientada a la línea de comandos, que permite la resolución de problemas numéricos, lineales y no lineales, además permite la ejecución de scripts.

Octave posee una gran cantidad de herramientas que permiten resolver problemas de álgebra lineal, cálculo de raíces de ecuaciones no lineales, integración de funciones ordinarias, manipulación de polinomios, integración de ecuaciones diferenciales ordinarias y ecuaciones diferenciales algebraicas. Sus funciones también se pueden extender mediante funciones definidas por el usuario escritas en el lenguaje propio de Octave.

Ir a la página principal de Octave.

Características de Octave:

• La sintaxis es similar a la utilizada en MATLAB, por lo que se le considera precisamente la versión libre de MATLAB.
• Es un lenguaje interpretado.
• No permite punteros.
• Se pueden generar scripts.
• Soporta gran parte de las funciones de la biblioteca estándar de C.
• El lenguaje está pensado para trabajar con matrices y provee mucha funcionalidad para trabajar con éstas.

Instalación

Usando Ubuntu como sistema operativo, Octave puede ser instalado desde el instalador de paquetes synaptic o desde línea de comandos con apt-get. El nombre del paquete a instalar se llama octave3.2, en una de sus versiones más estables.

esteban@presario:~$ sudo apt-get install octave3.2

Correr octave

Para hacer uso de octave, abrimos una terminal o consola de comandos, y escribimos octave.

esteban@presario:~$ octave

Esto nos desplegará información de la versión que tenemos instalada actualmente en nuestra computadora y así entramos a la consola de octave, muy parecida a la usada en python, y es aquí donde empezaremos a escribir cálculos matemáticos para nuestro primer ejemplo.

GNU Octave, version 3.2.4
Copyright (C) 2009 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  For details, type `warranty'.

Octave was configured for "i686-pc-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/help-wanted.html

Report bugs to  (but first, please read
http://www.octave.org/bugs.html to learn how to write a helpful report).

For information about changes from previous versions, type `news'.

octave:1>

Salir de octave

Para salir de la línea de comandos dentro de octave, basta con escribir quit o exit y presionar enter.

octave:1> exit

esteban@presario:~$ 

Nociones básicas

Lo siguiente es una sesión simple que realice en octave. En ella podemos ver como es posible asignar valores a las variables, hacer operaciones fundamentales sencillas, uso de vectores, y multiplicación básica de un vector, así como ver de nuevo el valor que tenemos en una variable y como es posible cambiar su valor.

Pero todo esto lo explico más a detalle en las siguientes secciones.

octave:1> a = 2*3
a =  6
octave:2> b=[1 2 3 4]
b =

   1   2   3   4

octave:3> c = a*b
c =

    6   12   18   24

octave:4> d = c/2
d =

    3    6    9   12

octave:5> a
a =  6
octave:6> a = a*5
a =  30
octave:7> quit

Cambe mencionar que cuando salimos de octave, todas las variables usadas son liberadas, por lo que al entrar de nuevo, no se habrá guardado nada de nuestra sesión anterior.

Guardar una sesión

Octave almacena los comandos ejecutados previamente por el usuario, incluso órdenes ejecutadas en sesiones anteriores, el archivo donde se guarda el historial se encuentra en el directorio home del usuario y lleva el nombre de .octave_hist. Gracias a esta característica podemos buscar un comando ejecutado previamente.

Pero al salir de Octave se perderán todas las variables que se han creado. Para eso existen los comandos save y load, que sirven para guardar una sesión y así recuperar las variables que ya teníamos asignadas.

Enseguida podemos ver la asignación de algunas variables, y como al terminar de usarlas se guardan en una sesión llamada "prueba".

octave:1> a = 5
a =  5
octave:2> b = 3
b =  3
octave:3> c = a*b
c =  15
octave:4> save prueba
octave:5> quit

Si en una siguiente ocasión regresamos a octave, si queremos ver alguna variable que habíamos usado anteriormente, vemos que esta ya no existe y se lanza un error. Pero después de cargar la sesión "prueba", previamente guardada, podemos recuperar todas las variables usadas.

octave:1> c
error: `c' undefined near line 1 column 1
octave:1> load prueba
octave:2> c
c =  15
octave:3>

También es posible recuperar específicamente alguna o algunas variables.

octave:1> load prueba a c
octave:2> a
a =  5
octave:3> b
error: `b' undefined near line 3 column 1
octave:3> c
c =  15
octave:4>

Vemos que solo recuperamos la variable "a" y "c", por lo tanto "b" lanza error, ya que no esta definida aún.

Operaciones aritméticas y cosas útiles

En la siguiente sesión de octave muestro el uso de operaciones aritméticas comunes. Agregue el signo "#", usado para comentarios, para explicar lo que se hace en cada línea.

octave:1> # Se respetan las reglas para el orden de operaciones
octave:1> 4 + 10 / 5 - 3
ans =  3


octave:2> # Es buena practica usar paréntesis para evitar conflictos
octave:2> (4 + 10) / (5 - 3)
ans =  7


octave:3> # Para calcular potencias existen dos formas
octave:3> 2^8
ans =  256
octave:4> 2**8
ans =  256


octave:5> # Negación de una variable
octave:5> a = 4
a =  4
octave:6> -a
ans = -4


octave:7> # Para ocultar la respuesta de salida se usa ";" al final
octave:7> a = 2^3
a =  8
octave:8> a = 2^3;


octave:9> # Podemos crear vectores
octave:9> v = [3 1 7 9]
v =

   3   1   7   9



octave:10> # Para obtener la transpuesta
octave:10> v.'
ans =

   3
   1
   7
   9



octave:11> # Octave es bueno para operar con matrices
octave:11> m = [1 2 3;4 5 6;7 8 9]
m =

   1   2   3
   4   5   6
   7   8   9

octave:12> m.'
ans =

   1   4   7
   2   5   8
   3   6   9



octave:13> # Podemos introducir varios comandos en una misma línea
octave:13> base=10, altura=4, A=(base*altura)/2
base =  10
altura =  4
A =  20


octave:14> # Podemos ocultar algunas operaciones
octave:14> base=10; altura=4; A=(base*altura)/2
A =  20


octave:15> # También podemos liberar una variable
octave:15> A
A =  20
octave:16> clear A
octave:17> A
error: `A' undefined near line 17 column 1


octave:17> # Variables predefinidas

octave:17> 1.2*4.4
ans =  5.2800
octave:18> # ans muestra el último resultado
octave:18> ans
ans =  5.2800


octave:19> pi
ans =  3.1416


octave:20> e
ans =  2.7183


octave:21> Inf
ans = Inf


octave:22> # Secuencias de números
octave:22> 1:9
ans =

   1   2   3   4   5   6   7   8   9



octave:23> # Secuencias con paso entre números
octave:23> 1:0.5:4
ans =

    1.0000    1.5000    2.0000    2.5000    3.0000    3.5000    4.0000

Funciones matemáticas y trigonométricas

Octave incluye una serie de funciones matemáticas y trigonométricas que nos ayudan a simplificar algunos cálculos, la siguiente tabla muestra algunas de ellas.

sqrt(x)	Raíz cuadrada de x
abs(x)	Valor absoluto de x
log(x)	Logaritmo neperiano de x
log2(x)	Logaritmo en base a 2 de x
log10(x)	Logaritmo en base a 10 de x
exp(x)	Exponente
pow2(x)	Para cada elemento de x, calcula 2^x
rem(x,y)	Resto entre la división de x e y (módulo)
round(x)	Redondeo de x al entero mas cercano
ceil(x)	Redondeo al entero superior de x
floor(x)	Redondeo al entero inferior de x
sin(x)	Devuelve el seno de x
cos(x)	Devuelve el coseno de x
tan(x)	Devuelve el tangente de x
sec(x)	Devuelve el secante de x
csc(x)	Devuelve el cosecante de x
ctg(x)	Devuelve el cotangente de x
gcd(x,y)	Calcula el máximo común divisor entre x e y
lcm(x,y)	Calcula el mínimo común múltiplo entre x e y
x(n)	Regresa el n-ésimo elemento del vector x
x(n,m)	Regresa el elemento que se encuentra en la fila n y columna m.
x(n,:)	Devuelve todos los elementos de la fila n
rand(n,m)	Crea una matriz aleatoria uniformemente distribuida de n×m, si se invoca con un solo escalar crea una matriz aleatoria cuadrada de n elementos
zeros(n,m)	Crea una matriz n×m con sus elementos iguales a 0, si se invoca con un solo escalar crea una matriz cuadrada de n elementos
ones(n,m)	Crea una matriz n×m con sus elementos iguales a 1, si se invoca con un solo escalar crea una matriz cuadrada de n elementos
sum(x)	Devuelve la suma de los elementos del vector x o la suma de los elementos de cada columna de la matriz x
max(x)	Devuelve el máximo para cada columna de la matriz x o el máximo de los elementos del vector x
min(x)	Devuelve el mínimo elemento del vector x o el mínimo elemento para cada columna de la matriz x
sort(x)	Ordena de menor a mayor los elementos del vector x

Sistemas de ecuaciones

Para la solución de ecuaciones lineales usamos a\b.

3x+2y+z=1
5x+3y+4z=2
x+y-z=1

octave:1> a=[3,2,1; 5,3,4; 1,1,-1]
a =

   3   2   1
   5   3   4
   1   1  -1

octave:2> b=[1;2;1]
b =

   1
   2
   1

octave:3> a\b
ans =

  -4.00000
   6.00000
   1.00000

Lo que se interpreta como "x = -4", "y = 6" y "z = 1".

Crear scripts y funciones

Bueno como ya vimos octave es una gran herramienta para hacer cálculos matemáticos y es muy bueno en el manejo de matrices, pero hasta ahora solo hemos hecho algunas cosas simples desde línea de comandos, lo cual no suele ser algo viable cuando se necesita crear un procesamiento un poco más complejo.

Por lo que tenemos la opción de poder escribir el código en un archivo, y darle la extensión .m reconocida por octave, en la cual podemos escribir todas las operaciones, además de hacer uso de ciclos y condiciones, al escribir de forma continua las operaciones tal y como las haríamos desde línea de comandos, lo llamamos script, y aquí tenemos un ejemplo.

Es un ejemplo tal vez un poco tonto o sin sentido, pero la idea es poner de ejemplo el uso de la sentencia for y los if else. Lo que hace es crear un vector de 7 elementos, y mediante el ciclo for pasamos de elemento por elemento, si el número es mayor a 0.5 escribe "Alto" y en caso contrario "Bajo".


Desde línea de comandos dentro de octave, basta con escribir el nombre del archivo donde escribimos nuestro código y veremos su ejecución.

octave:1> simplescript
0.766650 = Alto
0.778489 = Alto
0.651956 = Alto
0.715153 = Alto
0.389429 = Bajo
0.608944 = Alto
0.429080 = Bajo
octave:2>

Y también podemos crear nuestras propias funciones, que reciban parámetros y que den como salida algún resultado, o que al llamarlas hagan alguna acción, en este caso recibe el nombre de un archivo y un número N, crea el archivo y hace una lista de N filas enumeradas desde 0 a N y coloca un número aleatorio.


Es importante saber que los archivos deben de estar en la carpeta desde donde se ejecuta "octave" para poder hacer uso de las funciones, en otro caso tendría que ponerse la ruta para llegar al archivo del script o la función.

Gráficas 2D y 3D

Y como ya alargue demasiado esta entrada, ya no me extiendo mucho en la creación de gráficas desde Octave, ya que en realidad ocuparía una entrada del largo de esta para hacer cosas buenas, pero veamos esta gran utilidad que nos provee con unos simples ejemplos escritos desde la línea de comandos y la gráfica que resulta de cada una.

octave:1> x = rand(30,1);
octave:2> plot(x)

La siguientes líneas las obtuve de un tutorial mencionado al final en referencias, y dan como resultado la creación de una gráfica tridimensional.

octave:1> x=[-2:0.1:2];
octave:2> [xx,yy]=meshgrid(x,x);
octave:3> z=sin(xx.^2 - yy.^2);
octave:4> grid
octave:5> mesh(x,x,z)

Fue un poco extensa la entrada, pero trate de abarcar todos los aspectos fundamentales de octave, y espero les sea de ayuda.

Referencias:
Introducción a GNU Octave
Octave Ubuntu
GNU Octave - Wikipedia
Manual de Octave
Tutorial rápido de Octave

Tautología

Verificación y Validación de Software
Entrada 2

¿Qué es una Tautología?

Tautología es una fórmula de un sistema que resulta verdadera para cualquier interpretación. En otras palabras, se trata de una expresión lógica que es verdadera para todos los posibles valores de verdad de sus componentes atómicos.

Determinar si una fórmula es una tautología

Para determinar si una fórmula cualquiera es una tautología, basta con considerar todas las posibles interpretaciones de las fórmulas atómicas, y calcular el valor de verdad del todo. Esto se logra mediante una tabla de verdad.

Tarea

Encontrar por nosotros mismos una fórmula que resulte ser una tautología. Esta debe contener por lo menos 3 variables y 4 conectivos, que pueden ser operadores de negación, disyunción y conjunción.

Solución

La forma en que logre encontrar una tautología fue en un inicio a "prueba y error", ya que lo que estaba haciendo era escribir una fórmula cualquiera, creada con operadores al azar y luego probar mediante una tabla de verdad si esta daba como resultado siempre un valor "verdadero" o 1, pero resultaba ineficiente ya que era tardado probar con las 8 diferentes entradas de valores posibles, representadas en una tabla de verdad.

Entonces para no perder tiempo en verificar cada fórmula creada, decidí hacer un programa en python que me ayudara a verificar más rápidamente si mi fórmula daba verdadero para todas las diferentes y posibles entradas, según una tabla de verdad.

Programa tatutologia.py


Entonces lo que se hace es escribir mediante funciones, en el apartado de la variable formula, los operadores lógicos de la fórmula que se desea probar.

Una de las fórmulas que probé fue la siguiente:
F(A,B,C) = (A|¬B)^(C|¬C)

La cual escrita en el programa cambiaba la variable formula por:
formula = bool(conjuncion(disyuncion(A, negacion(B)) , disyuncion(C, negacion(C))))

Y el resultado que arrojo no fue una tautología ya que en más de una entrada dio como resultado False.

Luego hice unos cambios en la fórmula, y me resulto una tautología, y la fórmula usada fue:
F(A,B,C) = ((A|¬A) | ¬B) ^ (C|¬C)

Cuya fórmula escrita en mi programa es:
formula = bool(conjuncion(disyuncion(disyuncion(A, negacion(A)), negacion(B)) , disyuncion(C, negacion(C))))

Y la captura de pantalla de la ejecución donde se muestra que para la tabla de verdad dada, siempre da como resultado un True.

Árbol

P = ((A|¬A) | ¬B) ^ (C|¬C)

Tabla de verdad

Para comprobar con la tabla de verdad que todos los valores dan Verdadero, hacemos paso por paso, tal y como se desglosa en el árbol y vemos que obtenemos como resultado en la última columna los valores de 1 o Verdadero.

Nota: En el programa mostrado también se incluyeron funciones para comprobar fórmulas donde se incluyen el operador condicional y bicondicional, pero solo fueron para probar algunos ejemplos de tautologías encontradas en internet, y así verificar que el programa estaba haciendo lo correcto.

Referencias:
Definición de Tautología

Ciphertext

Seguridad de la Información y Criptografía
Agregado 1

In the cryptography class, we have to create a program that we can use to encrypt and decrypt a message, we must publish a ciphertext, that can be decrypted by our classmates, and I can try decrypt the ciphertext of someone else. The person who decrypts a messaje, earns one extra point.

Here's my ciphertext:

6mct1RlAct6mqUmN1RlAqUJQ5SqUjJ1RctFT1RlActIbCMlAweOI,hIbOIMX8CT0sOIbCMlAweOIlAXWOIlAbdwe8C.zIbhwIblAhwwelAivXWwe8C8CT0lA,h.zWD.z!s-PlA:7T0CMlAOIT0WDweCMlAweCMbdT0,h.zT0!sweCMlA8Cwe0,we!shwweCMlAT0MXT0,hT0OIhwIblAhwweCMhwwelAXWOIT0lA0,T0CMwelAIb,hXW!sMXT0PZlAv.T0OIlA!sIbiv8CT0hwIblACMXWlAbd8C.zsOwe8CT0lAWD.z,hMXIb8C.zT0lA,hIbOIMX8CT0lAwe!slAsOT0!sWDT0hwIblAa}sObdwe8C.zIblAKgT0!sT0,hMX.z,hIb-PlAGqXW8CT0OIMXwelA!sT0lA0,T0MXT0!s!sT0PZlA!sIbCMlAweCMbd.zT0CMlA8Cwe0,we!shwweCMlAv.T0OIlA,hIbOICMweivXW.zhwIblAT0bdIbhwwe8CT08CCMwelAhwwelA!sIbCMlAbd!sT0OIIbCMlACMwe,h8CweMXIbCMlAhwwe!slAT08CsOT0lAMXIbMXT0!slAVLlAhwweei.zOI.zMX.zWDT0lAhwwe!slAa}sObdwe8C.zIb3YlA!sT0lAqUCMMX8Cwe!s!sT0lAhwwelA!sT0lA7cXWwe8CMXwePZlAXWOIT0lAweCMMXT0,h.zIbOIlAweCMbdT0,h.zT0!slAT0,hIb8CT0LlT0hwT0lA,hIbOIlAbdIbMXweOI,h.zT0!slACMeiXW,h.zweOIMXwelAbdT08CT0lAhwweCMMX8CXW.z8ClAXWOIlAbd!sT0OIweMXT0lAweOIMXwe8CIb-PlA5Swe8CCMweivXW.zhwT0lAbdIb8ClA!sIbCMlACM.zOI.zweCMMX8CIbCMlAT0ivweOIMXweCMlAhwwe!slAa}sObdwe8C.zIbPZlA!sT0lAbd8C.zOI,hweCMT0lA:7we.zT0lAWDXWwe!sT0lAv.T0,h.zT0lACMXWlAbdT0MX8C.zT0lAT0lA0,Ib8ChwIblAhwwelACMXWlAOIT0WDwelAweCMbdT0,h.zT0!slA!s!sweWDT0OIhwIblA,hIbOICM.zivIblA!sIbCMlAbd!sT0OIIbCMlA8CIb0,T0hwIbCMlAd8XWwelAbdIbhw8CT0OIlACMT0!sWDT08ClAT0lACMXWlAbdXWwe0,!sIblAVLlAhwweWDIb!sWDwe8ClA!sT0lA!s.z0,we8CMXT0hwlAT0lA!sT0lAivT0!sT02V.zT0-P

Ejemplo de Fracciones Parciales

Automatización y Control de Sistemas Dinámicos
Agregado 1

El método de las fracciones parciales consiste en descomponer un cociente de polinomios en una suma de fracciones de polinomios de menor grado.

Es utilizado como procedimiento intermedio en la resolución de algunas integrales.

Fracciones Parciales

Yo cree el documento, tratando de explicar el procedimiento, tomando en cuenta que ya se tiene un conocimiento previo en la resolución de estos problemas.

Enlaces relacionados:
Integración de funciones racionales, por fracciones parciales

¿Qué es la Verificación y Validación de Software?

Verificación y Validación de Software
Entrada 1

Es un conjunto de 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.

Los objetivos de las actividades de verificación y validación son valorar y mejorar la calidad de los productos del trabajo generados durante el desarrollo y modificación del software.

Los atributos de la calidad deben ser la corrección, la perfección, la consistencia, la confiabilidad, la utilidad, la eficacia, el apego a los estándares y la eficacia de los costos totales.

Hay dos tipos de verificación: formal y del ciclo de vida. Esta última consiste en el proceso de determinar el grado de los productos de trabajo de una fase dada del ciclo de desarrollo cumplen con las especificaciones establecidas durante las fases previas. La verificación formal es una rigurosa demostración matemática de la concordancia del código fuente con sus especificaciones.

La validación es la evaluación del software al final del proceso de desarrollo del software para determinar su conformidad con los requisitos IEEE.

La verificación y validación implican la valoración de los productos de trabajo para determinar el apego a las especificaciones, incluyen las especificaciones de requisitos, la documentación del diseño, diversos principios generales de estilo, estándares del lenguaje de instrumentación, estándares del proyecto, estándares organizacionales y expectativas del usuario, al igual que las meta especificaciones para los formatos y notaciones utilizadas en la especificación de productos diversos.

¿Qué es verificación?

La verificación se enfoca más al proceso de evaluación del sistema o componentes ya que permite determinar si los productos de una determinada fase del desarrollo satisfacen las condiciones impuestas en el inicio de la etapa.

¿Qué se debe tener en la verificación?

• Consistencia: vigilar que la información sea coherente.
• Precisión: corrección de la sintaxis.
• Completitud: lagunas en capacidad deductiva.

Lo que se hace en la verificación:

• Identifica desviaciones con estándares y requerimientos.
• Recolecta datos para mejorar el proceso.
• Verifica que el producto:
  - Cumpla con los requerimientos.
  - Cumpla con los atributos de calidad.
  - Se ajuste a las regulaciones, estándares y procedimientos definidos.
  

¿Qué es validación?

La validación también es una evaluación del sistema o de componentes, solo que es en el transcurso o al final del proceso del desarrollo, donde se determina si cumple con lo especificado.

Aspectos en la validación:

• Construir el sistema correcto.
• Evaluar la conformidad con la especificación de requisitos.

Métodos formales de verificación

Entre los métodos de verificación más utilizados, se encuentran:

• Aserciones E/S: El programa, en lógica de Hoare, se especifica mediante aserciones que relacionan las entradas y salidas del programa. Se garantiza que si la entrada actual satisface las restricciones de entrada (precondiciones) la salida satisface las restricciones de salida (poscondiciones).
• Precondición más débil: Consiste en dada una poscondición POST, encontrar, operando hacia atrás, un programa S tal que la precondición se satisfaga en un amplio conjunto de situaciones.
• Inducción estructural: La inducción estructural es una técnica de verificación formal que se basa en el principio de inducción matemática.

Ejemplos de grandes pérdidas por errores de software

El desorbitado Mars Climate en 1998

Después de un viaje de 286 días desde la tierra, la nave "Mars Climate Orbiter" encendió sus motores para ponerse en órbita alrededor de Marte. Al llegar a Marte, la sonda debía modificar su trayectoria y reducir su velocidad, de forma que se mantuviera orbitando alrededor del planeta. Los motores arrancaron, pero el ingenio entró demasiado en la atmósfera del planeta, provocando que se estrellara en su superficie.

La causa fue que el software que controlaba los propulsores del Mars Orbiter usaban unidades imperiales (libras de fuerza) en lugar de unidades métricas (Newtons), como especificaba la NASA.

Pérdida: 125 millones de dólares.

Apagón de 2003 en Norteamérica

Privó de electricidad a un estimado de 50 millones de personas. El apagón se debió a un error en el software de monitoreo basado en Unix de General Electric, que impidió que los operadores se dieran cuenta de un corte local de energía. El efecto dominó de la falla afectó a ocho estados de Estados Unidos y a Ontario, en Canadá.

Problema del año 2000

El problema del año 2000, también conocido como efecto 2000 o por el numerónimo Y2K, es un bug o error de software causado por la costumbre que habían adoptado los programadores de omitir la centuria en el año para el almacenamiento de fechas, asumiendo que el software sólo funcionaría durante los años cuyos nombres comenzaran con 19. Lo anterior tendría como consecuencia que después del 31 de diciembre de 1999, sería el 1 de enero de 1900 en vez de 1 de enero de 2000.

Por ejemplo los programas que cuentan el número de años a través de la sustracción de las fechas, obtendrían una cantidad de años negativa. Si una persona nació en 1977, la edad de esta persona en 2000 sería: 00-77 = -77 años.

Y relacionado con este último ejemplo les dejo la primer parte del capítulo de Dilbert donde se enfrentan al problema del año 2000.

Fuentes consultadas:
Introducción a la verificación y validación
Métodos formales
Los errores informáticos más costosos
Problema del año 2000

Aplicación de una Red Neuronal

Redes Neuronales
Reporte 1

Reconocimiento de personas mediante voz

"Un sistema de reconocimiento de voz es una herramienta computacional capaz de procesar la señal de voz emitida por el ser humano y reconocer la información contenida en ésta, convirtiéndola en texto o emitiendo órdenes que actúan sobre un proceso."

Los sistemas de reconocimiento de habla diseñados para dar órdenes a un computador se llaman control por comandos. Estos sistemas reconocen un vocabulario muy reducido, lo que incrementa su rendimiento.

La idea es crear un programa para reconocimiento de personas mediante la voz, la cual puede ser usado en varios panoramas, en mi caso la idea es usarlo específicamente en una casa inteligente, la cual el sistema pida que diga alguna frase a la persona que llegue a la casa y esta identifique cuál de los habitantes es el que ha llegado, y así crear acciones inmediatas que frecuentemente hace esta persona, como el encender las luces del cuarto o encender la computadora.

Una de las librerías que puede ser utilizada para el preprocesamiento de la voz es python-pocketsphinx.

Identificar texto en imágenes

"Proceso dirigido a la digitalización de textos, los cuales identifican automáticamente a partir de una imagen símbolos o caracteres que pertenecen a un determinado alfabeto, para luego almacenarlos en forma de datos, asi podremos interactuar con estos mediante un programa de edición de texto o similar."

Existen en el mercado de aplicaciones móviles varias opciones que nos permiten tomar fotografías a un póster o libro, y luego se busca en la imagen la incidencia de texto el cual puede ser traducido directamente en la imagen o procesado para copiarlo directo a un archivo de texto. Entonces la idea es hacer mediante una red neuronal el reconocimiento de caracteres para esta obtención de texto.

Podía ser algo redundante y de lo cual ya hay muchas aplicaciones que lo hacen o incluso librerías que facilitan este reconocimiento, pero lo importante es aprender a hacerlo.

Para esto existe una herramienta que podría ser de gran ayuda con el nombre de PyTesser.

Páginas consultadas:
PyTesser
Reconocimiento de voz
Reconocimiento de caracteres