[SC] 3. One time pad pseudo-randomness tests

For this week, we had to test our one time pad keys generator.

The goal is to ensure that our generator produces enough pseudorandom keys.

To achieve that goal we need to satisfy the next requirements

- The pseudorandom numbers should be enough uniformly distributed

- The generation must be unpredictable and unreproducible.

- The keys must be uncompressible.

We must also ensure that our generator does not cause any kind of pattern.

Tomada de http://www.random.org/analysis/

In the image, we can see how the pseudorandom number generator of the function rand() from PHP have a high periodicy and the pattern thats causes a pattern, this is a very big vulnerability because, with the enough computing power, any pseudorandom generated key can be broken.

If we fulfill the requirements we can ensure that our keys are unbreakable.

Tests

To tests my pseudorandom  keys, I perform the following tests:

• Uniformity of pseudorandom integers
• Uniformity of zeros and ones
• Frequency Monobit Test
• Frequency Block Test
• Compression test

Results

1. Uniformity of pseudorandom integers.

For this tests first I generate a new set of keys, the one-time-pad to test is conformed by a set of 100 keys with length 100 each one, that means that I produce 10000 pseudorandom numbers in a range from 0 to 126, then, I store them in a matrix (only for storage, nothing special). Then, I pass the matrix to a function that calculates the frequency of each number in the range 0 to 126.

Then, with the frequencies calculated I proceed to plot them in a graph. This is the result

We can see that the integers are semi uniform, sometimes there are some high levels of recurrence, sometimes are low levels of recurrence. This is only the first part, later we can tests if really the pseudorandom keys are really random.

2. Uniformity of zeros and ones.

After calculate the frequency of each integer, I proceed to tests the uniformity of zeros and ones, so, first I need to convert my key in a long binary string, for that I followed the rule:

if(number >= 0 and number <=63) then number = 0

if(number >=64 and number <=126) then number = 1

With this method now my key matrix is a binary matrix, now I counted the amount of ones and zeros in each key and then I plot a graph with the results.

The graph looks like the previous one, we can see that the amount of ones and zeros is also semi uniform, so, we can conclude that maybe the numbers that form each key are pseudorandom.

For more confiability, I perform 2 officially tests for pseudorandom generators.

3. Frequency Monobit.

"The focus of this test is the proportion of zeroes and ones for the entire sequence. The purpose of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence. The test assesses the closeness of the fraction of ones to 1/2, that is, the number of ones and zeros in a sequence should be about the same. 
Note that if a generator fails this test then the likelihood of other tests failing is high."

Tomado de  http://www.random.org/analysis/Analysis2005.pdf

The parameter of this test is only n , the length of the key (list of ones and zeros, length 100), I pass all the matrix as parameter and I perform the tests 100 times (100 keys).

This is the results of the tests:

.......

The pictures are croped, at the final, the tests shows the amount of passed tests and failed tests.

We can conclude that our one time pad is suspicious to be a real pseudorandom keys because the 93% of the monobit tests was passed.

4. Frequency Block.

"The focus of this test is the proportion of ones within M-bit blocks. The purpose of this test is to determine whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under the assumption of randomness. 
Note that for block size M=1, this test degenerates to the Frequency (Monobit) test. 
The parameters of the tests are the length of each block (M), the length of the bit string (n),  the sequence of bits as generated by the RNG or PRNG being tested (ε). ε ≥ n. 
If the computed P-value is <0.01, then conclude that the sequence is non-random. Otherwise, conclude that the sequence is random. "

Tomado de  http://www.random.org/analysis/Analysis2005.pdf

Also, I pass all the matrix as parameter and I perform the tests 100 times (100 keys, each keys of lenght 100 with block length of  "key length / 10").

The results:

 ......

With the two tests performed we can conclude that, according to the results of the tests, our one time pad meet the requirements to be a real random keys because the 90% of the frequency block tests was passed.

Summary:

90% of the frequency block tests was passed.

93% of the monobit tests was passed.

5. Compression test.

This is an extra tests that only to measures the compression ratio of the keys, so first we take the keys matrix and pass it as parameter to the function, then, reads each key and convert it to a string, next we apply the zlib.compress() to compress the key with a level of compression of 6 (default). Then I perform a summatory of the lenght of each keys (compressed and decompressed) and finally I compare the size of all the keys compressed and decompressed.

The result was:

If I try to compress the ones-zeros matrix, the result was:

We have a little contradiction here, because, our randomness tests conclude that the keys was real random keys, but, the compression ratio is almost 50%

5. Conclusion.

I think that the keys in the tested one time pad are real random keys, because the graphs shows that the numbers are generated almost uniformly, also, we pass the official test of randomness.

I think that the compression tests failed because the file is too small, maybe generating a long enough file the result will be better.

6. Code.





Referencias

• http://www.random.org/analysis/Analysis2005.pdf
• Google Docs | Statistical Testing Slides
• Google Docs | RNG Test Slides

[SC] Extra. Chinese Remainder Theorem

Congruence

To begin, a congruence is a therm used to designate two different integers that have the same remainder when they are divided by a natural number.

Mathematical Definition

"Given a, b and m, with m > 0 that belongs to the set of integers, we say that a is congruent to b mod m if m divides
exactly (a-b).
a and b are congruent module m if and only if a and b have the same residue to be divided by m, individually.

a ≡ b (mod m)

m | (a - b)

The expression is read "a is congruent to b module m" and m is considered the module of the congruence.

P.E:

• 27 ≡ 3 (mod 4), because (27 - 3) = 24, is divisible by 4 with remainder 0
• 47 ≡ 7 (mod 8), because (47 - 4) = 44, is divisible by 8 with remainder 0
• 1 ≡ -1 (mod 2), because (1 - (-1)) = 2, is divisible by 2 with remainder 0

Properties

The congruences have 3 properties:

• Reflexive:
  a ≡ a (mod m)
• Symmetric:
  IF a ≡ b (mod m) ⇒ b ≡ a (mod m)
• Transitive:
  IF a ≡ b (mod m) ∧ b ≡ c (mod m) ⇒ a ≡ c (mod m)

**NOTE: If you want to know more, please see the references at the final of the end of this post

Chinese Remainder Theorem

The Chinese Remainder Theorem is a method used in number theory to solve systems of congruences.

A system with 2 or more lineal congruences don't have necessary a solution, even if each individual congruence have one. A system of lineal congruences is denoted by:

b1x ≡ a1 (mod m1)

b2x ≡ a2 (mod m2)
bix ≡ ai (mod mi)

But, all system with 2 or more lineal congruences which individualy accepts a unique solution, also accepts a simultaneous solution if the modules are comprimes with each other.

The chinese mathematician Sun Tsu Suan-Ching pose the following problem around the 4th century b.C:

"There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?"

Problems of this kind are all examples known as the Chinese Remainder Theorem. In mathematical words the problems can be solved finding n, given its remainders of division by several numbers m1, m2, ..., mk.

Mathematical Definition

Suppose that m1, m2, ..., mk are positive integers, relatively primes each other in pairs (mi, mk) = 1, if i ≠ k. And b1, b2, ..., bk are arbitrary integers. In the system of lineal congruences:

x ≡ b1 (mod m1)

x ≡ b2 (mod m2)
...

x ≡ bk (mod mk)

All the solutions of x are congruent module m, with m = m1 * m2 * ... * mk

Proof

M = m1 * m2 * ... * mk
Mk = M/mk

So, if all the modules are taken in pairs, and they are comprimes with each other, that means that gcd(Mk, mk) = 1, applying the rule gcd(a, m) = d, then, the congruency ax ≡ b (mod m) have a solution if, and only if d | b.

Now, x = b1*M1*y1 + b2*M2*y2 + ... + bk*Mk*yk

If we considerate each term of this summatory a module of mk.
Given that Mi ≡ 0 (mod mk), if i ≠ k, we have that x ≡ bk*Mk*yk ≡ bk (mod mk).

This means that x satisfies each one of the congruences of the system

By the symetric property, if x and b are two solutions of the system, we have that x ≡ b (mod mk) for each k. And because each mk are relatively primes each other by pairs, we also have that x ≡ b (mod M).

Example

"Find the two minimal prime numbers that have remainders 2,3,2 when they are divided by 3,5 and 7 respectively.

Solution

The system can be modeled in a system of congruences:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

The solution starts:

m = 3*5*7 = 105

Then:

M1 = m/3 = 105/3 = 35
M2 = m/5 = 105/5 = 21
M3 = m/7 = 105/7 = 15

Next:

y1 = M1 (mod 3) = 35 (mod 3) = 2
y2 = M2 (mod 5) = 21 (mod 5) = 1
y3 = M3 (mod 7) = 15 (mod 7) = 1

Now, find x:

x = b1*M1*y1 + b2*M2*y2 + b3*M3*y3
x = 2*35*2 + 3*21*1 + 2*15*1
x = 140 + 63 + 30
x = 233

Now we have 233 ≡ y mod(105)

Applying the symmetry rule

y ≡ 233 mod(105)
233 mod(105) = 23

The solution is 233 ≡ 23 mod(105), and 2 minimal integers could be 23 and 233, but, if we divide (233-23)/105, the result is 2, maybe there are another number where the result is one.

1 = (x-23)/105 also 1 = 105/105

Then

105+23 = 128 and 1 = (128-23)/105

The 2 minimal integers are 23 and 128.



References

• http://mat.izt.uam.mx/notas_de_clase/congruencias.pdf
• http://www.scribd.com/doc/43526801/Teorema-Chino-de-los-Restos
• http://www.cut-the-knot.org/blue/chinese.shtml
• http://www.millersville.edu/~bikenaga/number-theory/chinese-remainder/chinese-remainder.pdf
• http://www.mat.upm.es/~pzz/docencia/grado/mtds/congruencias_sin_pause4.pdf
• http://www.trans4mind.com/personal_development/mathematics/numberTheory/chineseRemainderTheoremFormula2.htm
• Google Books | Number Theory: Congruences (Spanish)

[VVS] 3. Aplicaciones de la lógica proposicional

[1] "La Lógica Proposicional pretende estudiar las frases declarativas simples (enunciados o proposiciones) que son los elementos básicos de transmisión de conocimiento humano. 

De manera informal, una proposición se define como una frase que puede ser considerada verdadera o falsa y que no se puede descomponer en otras frases verdaderas o falsas."

[2] "Una de las razones que motivó la aparición de la lógica matemática, fue evitar la ambigüedad del lenguaje natural y transformar el pensamiento en un cálculo, según el modo de operar de las matemáticas. Simplificar o simbolizar las oraciones o juicios para poder operar con ellas, así surge el lenguaje formal."

Algunos conceptos

La lógica proposicional representa el lenguaje de una forma bastante simplificada y primitiva que nos analizar muchas deducciones sobre el mundo que nos rodea.

El objetivo principal la lógica proposicional es el razonamiento, utilizando un mecanismo que primero evalúa sentencias simples y luego sentencias complejas, formadas mediante el uso de conectivos proposicionales, por ejemplo Y (AND), O (OR). Este mecanismo determina la veracidad de una sentencia compleja, analizando los valores de veracidad asignados a las sentencias simples que la conforman.

Una proposición es una simple oración que tiene un valor asociado de verdad (V), o falso (F), pero nunca puede tener ambos, algunos ejemplos pueden ser:

• El día esta soleado
• Mañana es jueves
• Los hombres son mortales
• Jose es hermano de María

Los conectivos proposicionales utilizados juntar las oraciones son:

Nombre	Símbolo	Lenguaje Natural	Ejemplo
Conjunción	∧	... y ...	Esta nublado y esta lloviendo
Disyunción	∨	... o ...	Esta nublado o esta soleado
Negación	¬	no ...	No esta nublado
Implicación	→	si... entonces ...	Si esta nublado entonces esta lloviendo
Doble Implicación	↔	... sí y solo sí ...	Esta lloviendo si y solo si esta nublado

La sintaxis de la lógica proposicional contiene un alfabeto que esta formado por:

• Las constantes lógicas de verdad y falso (V, F)
• Los símbolos de las variables (letras del alfabeto)
• Los conectivos proposicionales (las tablas de arriba)
• Símbolos de puntuación como paréntesis, corchetes y llaves

La unión de los componentes anteriores forman una oración compuesta.

La semántica le da un significado a las expresiones del lenguaje lógico y permite interpretar cada uno de los elementos del alfabeto logico y darle a su vez un valor de verdad o falso a cada una de las proposiciones, el valor esta definido por las tablas de verdad:

Negación
P	¬P
V	F
F	V

Conjunción
P	Q	P∧Q
V	V	V
V	F	F
F	V	F
F	F	F

Disyunción
P	Q	P∨Q
V	V	V
V	F	V
F	V	V
F	F	F

Implicación
P	Q	P→Q
V	V	V
V	F	F
F	V	V
F	F	V

Doble Implicación
P	Q	P↔Q
V	V	V
V	F	F
F	V	F
F	F	V

Al terminar analizar una oración proposicional podemos toparnos con 4 posibles casos:

• Tautología o validez: Cuando todas las combinaciones de una proposición dan como conclusión verdad
• Contradicción: Cuando todas las combinaciones de una proposición dan como conclusión falso
• Contingencia: Cuando no tenemos suficiente información para obtener una conclusión y la proposición puede ser verdad o falso
• Satisfabilidad: Si una combinación de todas las posibles es verdadera

Sistemas basados en conocimientos

Con los anteriores conceptos aterrizados, llegamos a otros 2 conceptos que ya son las bases de los sistemas basados en conocimientos:

• Inferir: Es tomar una decisión a partir de algo que ya conocemos, y asi llegar a una conclusión.
• Razonar: Es pensar con coherencia y lógica para establecer inferencias.

Existen 3 tipos de razonamiento:

• Deducción: Razonar algo de lo conocido a lo desconocido, comenzando con algo general a algo específico. Siempre se usan inferencias correctas lo que concluye en una conclusión verdadera.
• Abducción: Razonamiento que comienza con una conclusión e intenta hacer a la conlusión válida. No siempre garantiza que la conclusión sea verdadera.
• Inducción: Razonamiento que comienza con casos individuales para obtener una conclusión general. El conocimiento esta basado en éste método y permite el aprendizaje.

Asi pues "[3] un sistema basado en conocimiento (ABC) es aquel sistema que posee conocimiento de su mundo y es capaz de razonar sobre las posibles acciones que puede tomar para cambiar el estado de su mundo"

Razonamiento y conocimiento son importantes para estos sistemas pues son la base de su comportamiento exitoso.

Éstos sistemas constan de 3 partes importantes:

• Base de conocimiento que es un conjunto de oraciones que representan hechos del mundo real. Cada hecho es una oración. Por lo general hechos para los que fue programado el sistema de un tema específico. 
  Estos sistemas realizan 2 tareas importantes:
  • Decir para agregar conocimiento
  • Preguntar para obtener conocimiento y qué acción realizar ante una situación. (Cada pregunta se responde mediante el razonamiento lógico.)
• Motor de Inferencia que es el que deduce nuevas oraciones a partir de la base de conocimiento y de las nuevas oraciones almacenadas despues del proceso de aprendizaje. Aqui se utilizan teorías, que son las reglas que se deben seguir para inferir oraciones desde otras oraciones.
• Base de hechos que es una pseudo-memoria a largo plazo donde se almacenan las conclusiones correctas.

Tomada de http://www.monografias.com/trabajos12/inteartf/inteartf2.shtml

Estos sistemas también tienen percepción que es la manera en la que entran los datos

La importancia de la lógica proposicional en el tema no es mínima, digamos que la lógica proposicional juega un papel importante en el lenguaje de representación de conocimiento, que junto con la lógica del predicado y lógica temporal forman lo que se conoce como lógica formal.
El lenguaje de representación de conocimiento se utiliza para representar los hechos que el sistema procesará y unn ejemplo lenguaje de representación de conocimiento es PROLOG

Los sitemas basados en conocimientos que pueden en un futuro convertirse en sistemas para toma de decisiones o sistemas con inteligencia artificial.

[4] "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.

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

Los componentes de un lenguaje de representación de conocimiento son:

• Predicados: Son los atributos de los elementos.
• Elementos: Son las proposiciones.
• Constantes: Son una identidad completa, como un objeto o individuo.
• Variables Lógicas: Son binarias (V,F) y son aquellas que vamos evaluar.
• Variable anónima: Es una variable sin nombre y referenciada
• Operadores: Son los mismos que los operadores proposicionales.
• Hechos: Son relaciones entre los predicados y elementos
• Reglas: Son las condiciones entre los hechos y por lo general son implicaciones.

Referencias

• [1] http://www.cs.buap.mx/~iolmos/propeLogica/1_LP1.pdf
• [2] http://www.educared.org/wikiEducared/L%C3%B3gica_proposicional.html#Lenguaje_formal
• [3] http://www.slideshare.net/leopoldocapa/agentes-lgicos-presentation
• [4] http://www.monografias.com/trabajos51/inteligencia-artificial/inteligencia-artificial.shtml
• http://www.slideshare.net/leopoldocapa/agentes-lgicos-presentation
• http://www.monografias.com/trabajos/iartificial/pagina4_1.htm
• http://www.fismat.iteso.mx/pag_def/estructura/matematicas/asignaturas/logicamatematica2004/apoyos/proposicional3.pdf
• www.nebrija.es/~cmalagon/ia/transparencias/representacion_del_conocimiento_prolog.pdf

[Lab ACSD] 1. Métodos Numéricos: Método Runge-Kutta

El método de Runge-Kutta es un método genérico de resolución numérica de ecuaciones diferenciales. El método de Runge-Kutta no es sólo un único método, sino una importante familia de métodos iterativos, tanto implícitos como explícitos, para aproximar las soluciones de ecuaciones diferenciales ordinarias (E.D.O´s); estas técnicas fueron desarrolladas alrededor de 1900 por los matemáticos alemanes Carl David Tolmé Runge y Martin Wilhelm Kutta.

http://es.wikipedia.org/wiki/Método_de_Runge-Kutta

El método de Runge-Kutta de cuarto orden es el más utilizado para resolver numéricamente problemas de ecuaciones diferenciales ordinarias con condiciones iniciales,ya que proporciona un pequeño margen de error con respecto a la solución real del problema y es fácilmente programable en un software para realizar las iteraciones necesarias.

Recordemos que las ecuaciones diferenciales ordinarias son las ecuaciones donde todas las funciones y sus derivadas dependen de solo una variable independiente, es decir:

y = f(x)

El método de Runge-Kutta se utiliza para resolver ecuaciones diferenciales en su forma forma explícita: 

[1]

o en su forma implícita:

[1]

Y es sumamente útil para casos en los que la solución no puede hallarse por los métodos convencionales (como separación de variables). Hay variaciones en el método de Runge-Kutta de cuarto orden pero el más utilizado es el método en el cual se elige un tamaño de paso h y un número máximo de iteraciones n.

El método RK4 esta dado por la ecuación:

[1]

Para i=0,…,n-1. La solución se da a lo largo del intervalo (xo,xo+hn), donde:

[1]

El tamaño de paso (h) se define como el incremento de tiempo entre los sucesivos puntos tn y tn+1.

Así, el siguiente valor (yi+1) es determinado por el presente valor (yi) más el producto del tamaño del intervalo (h) por una pendiente estimada.

La pendiente es un promedio ponderado de pendientes:

• k1 es la pendiente al principio del intervalo
• k2 es la pendiente en el punto medio del intervalo, usando k1 para determinar el valor de y en el punto xi + h/2.
• k3 es otra vez la pendiente del punto medio, pero ahora usando k2 para determinar el valor de y
• k4 es la pendiente al final del intervalo, con el valor de y determinado por k3

Se promedian las 4 pendientes y se le asigna mayor peso a las pendientes en el punto medio:

[1]

Ejemplo

Las imágenes yo las hice, me apoye en LibreOffice para poder escribir las ecuaciones.

Como el programita se basa en iteraciones, lo que hice fue programar las fórmulas en python y correrlo hasta obtener el resultado final.

Código

Ejecución

Podemos asi comprobar que la primera iteracion hecha a mano es consistente con los resultados obtenidos con la programación.
Finalmente, obtenemos en la quinta iteración el resultado aproximado:

y(0.5) = 1.284025

Comprobación

Podemos ver que el error es mínimo, de solo 0.000005+, lo cual es una excelente aproximación al resultado real.

Espero les haya servido mi explicación, cualquier duda por favor dejen un comentario.

Saludos

Referencias

• [1] Fotografia tomada de http://fisica.udea.edu.co/~lab-gicm/Curso%20de%20Instrumentacion/2011_RungeKutta.pdf
• http://canek.uam.mx/Ecuaciones/Teoria/7.MetodosNumericos/ImpRungeKutta.pdf
• http://portalevlm.usal.es/Portal/e_books/guiaalumno/Chapter10SG_Spanish.pdf
• http://www.itmorelia.edu.mx/electrica/Notas/Lino_Coria/Metodos_Numericos/METODOS_DE_RUNGE_KUTTA.pdf
• http://delta.cs.cinvestav.mx/~mcintosh/comun/rodolfo/node11.html#deri
• http://users.salleurl.edu/~oscarg/resources/dinam0/dpja1.html
• http://fisica.udea.edu.co/~lab-gicm/Curso%20de%20Instrumentacion/2011_RungeKutta.pdf

[SC] 2. One-time-pad Encryption

In cryptography, the one-time pad (OTP) 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 (or pad) 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.
The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos show captured KGB pads that fit in the palm of one's hand,[7] or in a walnut shell.[8] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose.

http://en.wikipedia.org/wiki/One-time_pad

For the first activity of this class, we have to write a python script implementing one time pad encryption.
For my script I used the technique of modular addition to cipher and decipher. The steps of my script are:

1. Generate the pads: Execute the file oneTimePad.py -G to generate the pads. The cipher pad name and the decipher pad name are requested before, also the number of keys to generate and the length of each key. Whole process happens silently and very fast.
   
   
   
   
   Basically, my pad generation function opens/creates the pad file, then, initialize a list of the same size that the lenght of a key, the list is filled with random integer numbers between 0 and 126 (the basic ascii code), that's means that my alphabet lenght is 127.
   When the list is full, I use the python join() function to convert it to a string and write it in the pad file. This is repeated until the specified amount of keys are created.
   Finally, I use the module shutil and import the function shutil.copy() to create a copy of the pad. One is the cipher pad and the other one is the decipher pad.
   
   
   
   
   Original message:
   
   
   
   
   



2. Encrypt a message: Execute the file oneTimePad.py -C to cipher a message file. The name of the original message file, the name of the output file (encrypted message) and the name of the cipher pad file are requested.
   
   
   
   
   This function opens the input file (original message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the cipher pad file and read the first line to get the cipher key, also, converts the line into a list. Then, checks if the length of the message is less than or equal to the length of the key, if is lesser, punctuation marks are appended to the message list, if is equal nothing is done, if is greater, an error is raised and the script finish the execution. After the verification, the message is encypted character by character according the formula:
   
   (int(key[a]) + ord(message[a])) % alphabetLength
   
   Where a corresponds to the index of an element in the lists.
   The characters are converted first in their corresponding ascii codes, then, the corresponding value of the key is added, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the cipher pad file is opened and the first line is removed.
   
   
   
   
   Encrypted message:
   
   
   
   
   



3. Decrypt a message: Execute the file oneTimePad.py -D to decrypt an encrypted message file. The name of the encrypted message file, the name of the output file (decrypted message) and the name of the decipher pad file are requested.
   
   
   
   
   This function opens the input file (encrypted message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the decipher pad file and read the first line, also, converts the line into a list. Then, checks if the length of the message is equal to the length of the key, if is lesser or greater an error is raised and the script finish the execution. After the verification, the message is decrypted character by character according the formula:
   
   (alphabetLength + int(message[a]) - int(key[a])) % alphabetLength
   
   Where a corresponds to the index of an element in the lists.
   The characters are converted first in their corresponding ascii codes, then, the alphabet length is added and the key value is substracted, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the decipher pad file is opened and the first line is removed.
   
   
   
   
   Decrypted message:
   
   
   

We can see how punctuation marks was added at the final of the file. This was because the key length was greater than the length of the message.

Code

References

• http://en.wikipedia.org/wiki/One-time_pad

[VVS] 2. Lógica proposicional; formas normales

Después de un pequeño recordatorio sobre matemáticas discretas y lógica proposicional, la tarea 2 consistío en armar una tautología.

Aterrizando el concepto:

"Una tautología es aquella fórmula lógica que es cierta para cualquier valoración de los símbolos proposicionales que contiene."

Sin embargo, la tautología a elaborar debía tener las siguientes caracteristicas:

• 3 variables
• 4 conectivos lógicos
• Por lo menos 1 disyunción, 1 conjunción y 1 negación

La tarea fue sencilla, no llevo mucho tiempo, los pasos que segui fueron:

1. Armar una tabla de verdad para las 3 variables
2. Agregar el primer conectivo, una conjunción y resolver
3. Agregar el segundo conectivo, una disyunción y resolver
4. Agregar el tercer conectivo, una implicación y resolver para la conjunción y la disyunción, elegí la implicación por el resultado de los anteriores conectivos, se ve que se puede obtener una tautología antes.
5. Aplicar un cuarto conectivo, la negación a la tercer variable.
6. Agregar el quinto conectivo, una disyunción, elegí este conectivo para obtener con seguridad una tautología al final ya que es el único que me da el resultado que busco.

Ésta es la tabla de verdad con todo el procedimiento:

p	q	r	(p ∧ q)	(p ∨ q)	((p ∧ q) -> (p ∨ q))	¬r	(((p ∧ q) -> (p ∨ q)) ∨ ¬r)
V	V	V	V	V	V	F	V
V	V	F	V	V	V	V	V
V	F	V	F	V	V	F	V
V	F	F	F	V	V	V	V
F	V	V	F	V	V	F	V
F	V	F	F	F	V	V	V
F	F	V	F	V	V	F	V
F	F	F	F	F	V	V	V

Éste es el árbol correspondiente a la tautología que arme:

Segundo Intento

Edito la entrada, pues no debí haber usado la implicación, entonces, partiendo del mismo procedimiento modifico del paso 4 en adelante:

1. Tabla con 3 variables
2. 1 conjunción
3. 1 disyunción
4. Negar la conjunción
5. Unir la conjunción negada y la disyunción con otra disyunción adicional

Ésta es la tabla de verdad con todo el procedimiento:

p	q	r	(p ∧ q)	(p ∨ q)	(¬(p ∧ q))	((¬(p ∧ q)) ∨ (p ∨ q))
V	V	V	V	V	F	V
V	V	F	V	V	F	V
V	F	V	F	V	V	V
V	F	F	F	V	V	V
F	V	V	F	V	V	V
F	V	F	F	F	V	V
F	F	V	F	V	V	V
F	F	F	F	F	V	V

Éste es el árbol correspondiente a la nueva tautología:

[RNA] 1. Pronostico de Patrones de Delincuencia

Tomada de http://blog.analyticstraining.in/archives/260

OBJETIVO

Utilizar una red neuronal para predecir actividad delictiva en una zona o en un lugar mediante reconocimiento de patrones.

PROCEDIMIENTO

La información de entrada sera una serie de tiempo, de le ensenara a la red neuronal el historial en un tiempo determinado, y se obtendrá una salida. Los resultados se convertirán en información pasada la cual pasara a ser ahora la entrada de la red neuronal y así obtendremos nuevos datos sucesivamente

• Lenguaje de programación Python

RESULTADO

Generar mapas de calor que permitan visualizar los resultados.

Tomada de http://supermodelcity3.blogspot.mx/2011/07/interesting-graphic-for-traffic-flow.html

REFERENCIAS

• How can Neural Networks be used for forecasting?
• Neural Forecasting Tutorials

[SC] 1. Texto Cifrado

Que tal a todos, este es mi texto cifrado, solo mencionaré que utilicé un método mixto. Saludos

[VVS] 1. La Verificación y Validación de Software

DEFINICIÓN

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.

OBJETIVO

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. Debemos corregir todo posible fallo y alcanzar cierto grado de perfección, asi mismo, debemos garantizar la consistencia, confiabilidad, utilidad, eficacia y el apego a los estándares del desarrollo de software.

Para ello es necesario encontrar defectos en el sistema que estamos desarrollando y asegurarnos que el sistema será útil para el entorno de trabajo requerido.

VERIFICACIÓN Y VALIDACIÓN

Ambos conceptos suelen tratarse como sinónimos, sin embargo, se refieren a cosas completamente distintas:

• La verificación se enfoca más al proceso de evaluación del sistema o de los componentes, permite determinar si los productos de una determinada fase del desarrollo satisfacen las condiciones impuestas en el inicio de la misma. Responde la pregunta ¿Estamos construyendo el producto correctamente?, entonces el software debería ajustarse a sus especificaciones iniciales.
• La validación también es una evaluación del sistema o componentes, pero solo se efectúa en el transcurso o al final del proceso del desarrollo para determinar si cumple con lo especificado. Responde la pregunta ¿Estamos construyendo el producto correcto?, entonces el software debería hacer lo que el cliente realmente quiere que haga.

Es importante resaltar que nunca se va a poder demostrar que el software está completamente libre de defectos, la verificación y validación mas crítica es realizada por los clientes finales.

TÉCNICAS DE VALIDACIÓN Y VERIFICACIÓN

Para aplicar estas técnicas siempre en necesario modelar cierto tipo de pruebas (tests) específicas, las pruebas son actividades en las cuales un sistema o uno de sus componentes se ejecuta en circunstancias previamente especificadas, los resultados se observan y registran y se realiza una evaluación de algún aspecto.

Varias pruebas juntas con un fin especifico constituyen un caso de pruebas donde un conjunto de entradas, condiciones de ejecución y resultados esperados son desarrollados para un objetivo particular.

Las pruebas deben centrarse en dos objetivos:

• Probar si el software no hace lo que debe hacer.
• Probar si el software hace lo que no debe hacer, es decir, si provoca efectos secundarios.

Se clasifican en 2 grandes grupos:

• Inspecciones de Software: analizan y comprueban las representaciones del sistema (los diagramas de diseño, el código fuente del programa). Se aplica a todas las etapas del proceso de desarrollo y se complementan con algún tipo de análisis automático del texto fuente y documentos asociados. Son técnicas de verificación y validación estáticas, no requieren que el sistema se ejecute.
• Pruebas de Software: consisten en comparar datos teóricos con los resultados del software utilizando series de datos de prueba, se examinan los resultados del software y su comportamiento operacional para comprobar que se desempeñe conforme a lo requerido. Es una técnica dinámica de la verificación y validación ya que requiere disponer de un prototipo ejecutable del sistema.

Lo que buscamos descubrir con ambos tipos de pruebas son:

• Defectos (bug): un defecto en el software como, por ejemplo, un proceso, una definición de datos o un paso de procesamiento incorrectos en un programa.
• Fallos (failure): La incapacidad de un sistema o de alguno de sus componentes para realizar las funciones requeridas dentro de los requisitos de rendimiento especificados.

Los errores mas comunes son:

• División por cero
• Ciclo infinito
• Problemas aritméticos como desbordamientos (overflow) o subdesbordamientos (underflow).
• Exceder el tamaño del array
• Utilizar una variable no inicializada
• Acceder a memoria no permitida (access violation)
• Pérdida de memoria (memory leak)
• Desbordamiento o subdesbordamiento de la pila (estructura de datos)
• Desbordamiento de búfer (buffer overflow)
• Bloqueo mutuo (deadlock)
• Indizado inadecuado de tablas en bases de datos.

Después de que hemos realizado ambas pruebas y que han sido localizados errores, es necesario especificar un proceso de depuración .

El proceso de depuración localiza y corrige los errores descubiertos durante la verificación y validación. Es un proceso complicado pues no siempre los errores se detectan cerca del punto en que se generaron. Para este paso„ se utilizan herramientas de depuración, que facilitan el proceso. Algunos ejemplos de herramientas de depuración para diferentes plataformas son:

• GDB (GNU Project Debugger) para C jdb - The Java Debugger
• JDB (Java Debugger) para JAVA
• JUnit (Java Unit Testing), suite de pruebas unitarias para JAVA , existen versiones para JavaScript.
• PDB (Python debugger), suite de pruebas unitarias para JAVA

Después de reparar el error, hay que volver a probar el sistema (pruebas de regresión)pues la solución del primer fallo puede dar lugar a nuevos fallos.

IMPORTANCIA

La importancia de los procesos de validación se puede entender mejor si analizamos las consecuencias de no realizarlos, hay varios ejemplos famosos: : El Cohete Mariner 1, en una investigación espacial destinada a Venus, se desvió de su trayectoria de vuelo poco después de su lanzamiento. El control de la misión destruyó el cohete pasados 293 segundos desde el despegue. Causa: Un programador codificó incorrectamente en el software una fórmula manuscrita, saltándose un simple guión sobre una expresión. Sin la función de suavizado indicada por este símbolo, el software interpretó como serias las variaciones normales de velocidad y causó correcciones erróneas en el rumbo que hicieron que el cohete saliera de su trayectoria.

• Desastre: Cohete Mariner 1 
  Descripción: investigación espacial destinada a Venus, se desvió de su trayectoria de vuelo poco después de su lanzamiento. El control de la misión destruyó el cohete pasados 293 segundos desde el despegue. 
  Causa: Un programador codificó incorrectamente en el software una fórmula manuscrita, saltándose un simple guión sobre una expresión. Sin la función de suavizado indicada por este símbolo, el software interpretó como serias las variaciones normales de velocidad y causó correcciones erróneas en el rumbo que hicieron que el cohete saliera de su trayectoria.


• Desastre: Mars Climate Orbiter 
  Descripción: El satélite se estrello en la superficie marciana. 
  Causa: error en la programación del sistema de navegación hizo que al entrar en su atmósfera este se desintegrara, esto pasó porque al introducir los cálculos no se hicieron en el Sistema Métrico Internacional lo que provocó un fallo en la medición de la altitud sobre el planeta.


• Desastre: Ariane 5 
  Descripción: El cohete se desvía se su curso debido a un error en los datos procesados. El intento posterior de enderezar la trayectoria fue demasiado brusco y el cohete finalmente se destruyó a los 37 sg. 
  Causa: el software de control realizó una conversión de un valor flotante de 64 bits en un entero de 16 bits sin comprobar que se produjeran desbordamientos.

Todos los desastres anteriores pudieron haber sido evitados si la causa de los mismos hubiera sido corregida mediante sencillas pruebas y evaluaciones.

Como podemos suponer, este tipo de experimentos tienen un alto costo para las instituciones que los realizan, un error en el sistema puede resultar en la perdida de millones de dolares, aunque en la actualidad son mas serios los errores que tienden a corromper o suprimir la información o datos guardados de los usuarios.

Siempre hay que darle importancia a estas pruebas y destinar los recursos necesarios a las mismas, no solo por las perdidas y el costo de repararlos en una etapa posterior, sino por nuestra propia ética profesional, un error de este tipo puede dejar a un Ingeniero en Software sin trabajo de por vida, entonces, es necesario ver las técnicas de validación y verificación de software como un proceso obligado en el desarrollo de software.

REFERENCIAS

• http://www.oscargallardo.com/wp-content/uploads/2011/04/CIISA_IS2_V_V2.ppt
• http://clases3gingsof.wetpaint.com/page/Verificación+y+Validación
• http://www.ctr.unican.es/asignaturas/Ingenieria_Software_4_F/Doc/M7_09_VerificacionValidacion-2011.pdf