jueves, 30 de agosto de 2012

Criptografía factorización

Esta entrada es de un ejercicio visto en clase, donde lo buscado era hacer la comunicación entre bob y alice, en el que bob mandaba una número generado por la multiplicación de una lista de números dados, así que alice tendría que encontrar cuales era la lista.

Así que bob, mandaría 1594323 (con la lista 131*3*11*5*101*17) y alice buscaría encontrar esa lista.

¿Como alice encontraría la lista?
La respuesta es sencilla lo que hay que hacer es factorizar el número y tendremos la lista hecha por bob

Código:
Para eso generé un código que te factorice el número, aún falta optimizarlo un poco, pero te da la lista.

def factorM(num):
    b = list()
    for i in range(1, 100000): #Determinamos un alcance
        a = num % i  #Sacamos el modulo de i al numero, para saber si es 0 que es lo que buscamos
        if a == 0:
            num = num / i #Actualizamos el numero dividiendolo por el valor de i, para ir sacando los demas numero de lo contrario la lista creceria
            b.append(i)
    return b

a = float(raw_input("Dame el numero: "))
b = factorM(a)
print b

Resultado:

Así que listo, ya tenemos la lista de bob.

Diffie-Hellman hack

Para ésta entrada nos toco realizar una actividad en la que consistía tratar de sacar el mensaje y la clave emitidos por Alice & Bob.

Variables o valores a usar:
p: Es un número primo emitido por Alice & Bob (público)
g: Es un número cualquiera que pertenece a p (público)
X: Es el valor que obtiene Bob apartir de un x que el define (público)
Y: Es el valor que obtiene Alice apartir de un y que el define (público)

x: Es el valor definido por Bob (privado)
y: Es el valor definido por Alice (privado)
k: Es la clave (privada)

Fórmulas:




Actividad:
p = 29
g = 19
X = 21
Y = 6

Para ésta actividad, realice un programa en python en la cuál me devuelve el valor de x, y & k. Así que la idea para sacarlas emplie fuerza bruta buscando el valor y comprobando ésta con X o Y y una vez tenidas éstas sustitui en la fórmula.

x = g ^ (i) mod p
y = g ^ (i) mod p


e i comprobábamos que fuera igual a X & Y y una vez tenidos éstas sustituiamos en la fórmula para obtener k


Programa:
def sacarX(p,g,x):
    for i in range(p):
        newX = (g**i)%p
        if newX == x:
            print "x: "+str(i)
            return i

def sacarY(p,g,y):
    for i in range(p):
        newX = (g**i)%p
        if newX == y:
            print "y: "+str(i)
            return i

def sacarK(g,p,x,y):
    k = (g**(x*y))%p
    print "K vale: "+str(k)


p = 29
g = 19
x = 21
y = 6

x = sacarX(p,g,x)
y = sacarY(p,g,y)
sacarK(g,p,x,y)




Resultados:




Referencias:
http://es.wikipedia.org/wiki/Diffie-Hellman

miércoles, 29 de agosto de 2012

Prueba de aleatoriedad clave One Time Pad

¿Para que nos serviría hacer una prueba de aleatoriedad para la clave generada?
La respuesta, es que si nosotros (que claro que si) estamos buscando generar una clave que sea dificil de romper o descifrar, a nosotros nos interesaría hacer éste tipo de test.

¿Pero como sabríamos si es aleatoria?
No sabemos bien si un número es totalmente aleatorio entonces lo que se hace es medir las frecuencias que estamos recibiendo.
En ésto me ayudo mucho en ver de otra forma, una caricatura que encontré en random.org


Para esto hay diferentes tipos de pruebas como anderson, chi, monobit, de bloques, run, entre otras. Cada una la aplicamos dependiendo del tipo de test que estamos buscando y su número aleatorio.

Para esta entrada se genero los números aleatorios de one time pad, donde buscaremos verificar que tan aleatorio es nuestra clave.

Prueba
El tipo de prueba empleado es el monobit, el cúal su fórmula ésta dada por:

Donde E es nuestra secuencia de bits
Sn nuestra sumatoria de E (hay que indicar que nuestra, que al momento de identificar un 0 esto lo cambia a -1)
n es nuestro tamaño total de E
P-value será tomada con erfc(sobs/sqrt(2))
donde erfc es la función de error complementario.
Ya para definir si fue aleatorio, se compara con una muestra de 0.01 y si esta es mayor la prueba pasa, de lo contrario no es aleatorio.


Código nuevo:

from random import randint
from math import sqrt, erfc

def generarClaves(cantidad, nombre):
    a = 'abcdefghijklmnopqrstuvwxyz '
    largoClave = 80
    for i in range(cantidad):
        clave = list()
        for j in range(largoClave):
            letra = randint(0, len(a)-1)#Creamos nuestro numero aleatorio del tamano del arreglo
            clave.append(letra)
        pruebasRand(clave)#mandamos llamar al metodo de pruebas
        #print clave

#clave.append("\n")
        #guardarClaves(clave, nombre)
def pruebasRand(clave):
    print "Prueba Monobit"
    print "\t Resultado:"+str(pruebaMonobit(clave))

def pruebaMonobit(clave):
    s = list()
    for i in clave:
        i = convertirUnosCeros(i) #Leemos cada elemento del arreglo para sacar unos y ceros
        s.append(i)
    sobs = abs(sum(s))/sqrt(len(s)) #Aplicamos la formula propuesta
    pValue = erfc(sobs/sqrt(2)) #Aplicamos la formula propuesta
    if(pValue > 0.01): return "Prueba pasada "+str(pValue) #Comparamos
    else: return "Prueba no pasada "+str(pValue)

def convertirUnosCeros(elemento):
    elemento = elemento % 2 #Lo sacamos tomando los numero pares e impares
    if elemento == 0: return -1 #Si el elemento es 0 lo convertimos a -1 para que este afecte en la sumatoria
    else: return 1

def guardarClaves(clave, nombre):
    clave = "".join(clave)
    archivo = open(str(nombre), "a")
    archivo.write(clave)
    archivo.close()
    otro = open("copia"+str(nombre), "a")
    otro.write(clave)
    otro.close()

cantidad = int(raw_input("Dame la cantidad de claves a generar: "))
nombre = raw_input("Dame el nombre del archivo: ")
generarClaves(cantidad, nombre)

Explicamos:jninininia..

Resultados:
Así que ahora proseguimos a verificar nuestros resultados y para verificarlos que estuvieran bien, la prueba se hizo varias veces:

1 vez:

5 veces:

Así que por lo valores arrojados, podríamos decir que nuestro generador de claves es seguro y es aleatorio.

Nota:
¿Pero que pasa si al test lo aplicamos más de 5 veces? Pues sorpresa, descubrimos que nuestro generador de números aleatorios, no es del todo aleatorio. Aunque nuestros resultados digan que pasaron la prueba, podemos observar que sus resultados se van repitiendo, hasta tenemos una que otra, que no paso la prueba y sus resultados son los mismos.


Resultado: FAIL.
Ya con ésto sabemos que tristemente nuestra clave no es aleatoria, ya que se repite la frecuencia, así que el posible problema es al momento de emplear randint de python, así que para solucionar ésto, podríamos implementar un número random uniforme, obteniedo unos mejores resultados o hacer nuestro número con lo visto de simulación, así que más adelante pondré mi código mejorado.


Como podemos ver en la imágen los números generados (fueron 10000), se van repitiendo con una frecuencia, haciendo esto muy inseguro.

Referencia:
http://goo.gl/IP3Wx
http://goo.gl/ExMC6
http://www.random.org/analysis/
http://www.random.org/analysis/Analysis2005.pdf

lunes, 27 de agosto de 2012

Lógica proposicional

Introducción:
Diariamente nos topamos con preguntas simples en la cuál su respuesta es falsa o verdadera, pero no ambas, mensionando algunos ejemplos vemos como: el jueves no hay tarea, el agua es un compuesto químico, el perro es un mamifero, entre otras. A esto se le llama lógica proposicional y estudia proposiciones mas complejas.

Conectivas lógicas:
las conectivas lógicas son utilizadas para unir sentencias y así formar una proposicion:



Cada conectiva lógica se distigue por el valor devuelto en sus diferentes estados de valores de entrada, para esto ayuda mucho las tablas de verdad en la cuál podemos ver sus diferentes estados.


  • Negación: Resibiendo una proposicion p, y esta negando -p, es verdadera cuando p es falsa y p es falsa cuando p es verdadera.
  • Conjunción: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando ambas son verdaderas, falso en cualquier otro caso.
  • Disyunción: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando cualquiera de sus entradas sea verdadera, falso cuando ambas son falsas.
  • Condicional: Resibiendo dos proposiciones p y q, tomamos que es falso cuando viniendo de un verdadero se pase a falso.
  • Bicondicional: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando ambas entradas sean del mismo tipo como falso & falso o verdadero & verdadero.

Aplicaciones:
Dando una breve introducción y teniendo una idea mas clara, pasemos ahora a ver donde los podemos ocupar o donde son aplicados algunos ejemplos son: principalmente en la eletrónica e informática, circuitos eletrónicos/digitales, en el habla (como se mensiono en los primeros ejemplos), inteligencia artificial, criptografía, sistemas de computos, lineas de producción, etc.

Inteligencia Artificial:
Navegando por internet me encontré con una nota que me llamo la atención y me ayudo a ver y comprender mas del caso.
nota: ¿Inteligencia artificial para iluminar los semáforos del futuro? enlace es.engadget
Ya que un semáforo lo podemos ver como un sistema de automatización o línea de producción donde tenemos una secuencia, pero ¿que pasaría si a éste se le aplica inteligencia artificial?
Aquí es donde entra la lógica proposicional, que es cuando entra en la fase de reconocimiento, ya que para llegar a esto estamos evaluando posibles datos de entrada y salida, que nos llevará a una sola (semántica y sintaxis/teoría).
  
Referencia:
http://www.monografias.com/trabajos51/inteligencia-artificial/inteligencia-artificial.shtml
http://es.engadget.com/2012/08/26/estudio-semaforos-inteligencia-artificial/
http://www.educared.org/wikiEducared/L%C3%B3gica_proposicional.html
http://sp.rian.ru/images/14787/86/147878665.jpg

jueves, 23 de agosto de 2012

Interpolación de Lagrange

Este método nos sirve para construir un polinomio interpolante de grado n. Un polinomio interpolante se utiliza para encontrar un polinomio que pase por todos los puntos de un conjunto de datos (muestra). La respuesta aplicada en un problema, solo tiene una solución, ya que al tenerse otra, se debería sacar la difenrecia de éstas dos, dando un polinómio de grado k + 1.

Fórmula:
La siguiente fórmula es la que nos proporciona Wikipedia.

 

 Pero si se nos hace un poco confusa como a mí podemos sustituirla en la siguiente donde, Xn, será nuestro valor en x (nuestro puntos) y Fn nuestra interpolación.





Ejemplo propuesto:

Las densidades de sodio para tres temperaturas son dadas a continuación

i   Temperatura     Densidad
0   94°C               929kg/m3
1   205                 902
2   371                 860
       x                     y

1) Escribir la formula de la interpolación de Lagrange a los tres puntos dados.
2) Encontrar la densidad para x = 251°C con interpolación de Lagrange

Emplearemos la formula proporcionada donde sustituiremos:
n = 2 + 1 = 3 //Nos sirve para saber hasta cuantos Xn se harán a sustituir en la fórmula
x1 = 94°C
x2 = 205°C
x3 = 317°C
f(x0) = 929 kg/m3
f(x1) = 902 kg/m3
f(x2) = 860 kg/m3

A continuación les dejo una captura de pantalla de como se resuelve el problema, lo único que se hace es sustituir, lo valores por los de la fórmula:


En el problema de la pregunta 1, como se mencionó se sustituye en la fórmula planteada, obteniendo el polinomio y  en la pregunta 2, una vez que se obtiene la ecuación sustituimos 251 en x, para así obtener la densidad.

Otras aplicaciones:
La interpolación polinómica de Lagrage, también puede ser empleada en proyectores ortogolanes

Uno de los posibles problemas al implementar ésto, al momento de agregarle más números o puntos a interpolar, crece el tiempo y la complejidad de su resultado.


Link:
http://es.wikipedia.org/wiki/Interpolaci%C3%B3n_polin%C3%B3mica
http://es.wikipedia.org/wiki/Interpolaci%C3%B3n_polin%C3%B3mica_de_Lagrange

Tarea: One Pad Time

Para esta entrada, se nos encargo hacer un programa que hiciera one time pad, a continuación les dejo el código:

Generador de claves:

from random import randint

def generarClaves(cantidad, nombre):
    a = 'abcdefghijklmnopqrstuvwxyz '
    largoClave = 80
    for i in range(cantidad):
        clave = list()
        for j in range(largoClave):
            letra = a[randint(0, len(a)-1)]
            clave.append(letra)
        clave.append("\n")
        guardarClaves(clave, nombre)

def guardarClaves(clave, nombre):
    clave = "".join(clave)
    archivo = open(str(nombre), "a")
    archivo.write(clave)
    archivo.close()
    otro = open("copia"+str(nombre), "a")
    otro.write(clave)
    otro.close()

cantidad = int(raw_input("Dame la cantidad de claves a generar: "))
nombre = raw_input("Dame el nombre del archivo: ")
generarClaves(cantidad, nombre)

Encriptacion-Desencriptación:

def main(mensaje, nombreA):
    clave = convertirMensajeAnsi(leerArchivo(nombreA))
    mensaje = convertirMensajeAnsi(mensaje)
    opcion = raw_input('Escoge 1 encriptar, 2 desencriptar: ')
    if(opcion == '1'):
        enc = "".join(modulo(mensaje, clave))
        print "encriptado: "+str(enc)
    if(opcion == '2'):
        des = "".join(moduloD(mensaje, clave))
        print "desencriptdo: "+str(des)

def modulo(mensaje, clave):
    enc = list()
    for i in range(len(mensaje)):
        enc.append(encriptar(mensaje[i], clave[i]))
    return enc

def moduloD(mensaje, clave):
    enc = list()
    for i in range(len(mensaje)):
        enc.append(desencriptar(mensaje[i], clave[i]))
    return enc

def encriptar(mensaje, clave):
    enc = int((int(mensaje) + int(clave))%123)
    return chr(enc)

def desencriptar(mensaje, clave):
    enc = int((int(mensaje) - int(clave))%123)
    return chr(enc)

def convertirMensajeAnsi(mensaje):    
    a = list()
    for letra in mensaje:
        ansi = str(ord(letra))
        if(len(ansi) < 3): ansi = "0"+str(ansi) 
        a.append(ansi)
    return a

def leerArchivo(nombreA):
    archivo = open(str(nombreA), 'r+')
    linea = archivo.readline()
    raw_input()
    nuevo = "".join(archivo.readlines()[0:])
    open('b.txt', 'w+').write(nuevo)
    return linea


mensaje = raw_input("Ingresa el mensaje: ")
nombreA = raw_input("Ingresa el nombre del archivo que cont. claves: ")
main(mensaje, nombreA)

Imagen:
Les dejo una captura de una prueba que hice.


Comentarios:
Me falta pulir un poco más el código, ya que unos métodos se repiten o algunas lineas que se pueden simplificar u optimizar.

jueves, 16 de agosto de 2012

Tautología

Tautología:
La tautología en forma general lo podemos definir como hacer un enunciado obvio y que éste siempre diga lo mismo. Un ejemplo a mencionar podría ser: ‘un hombre es un hombre’, ‘así soy porque soy’, entre otros. Viendo ésto en forma lógica o en la programación, ésta se entiende como una fórmula planteada que su resultado o respuesta siempre será verdadera.

Problema planteado:
Ahora como ejercicio se buscó encontrar una tautología, con x cantidad de operaciones y x cantidad de variables.

Respuesta:
En mi resolución del problema hice digamos que un poco de trampa, ya que realicé una simple tabla buscando que sus valores sean verdaderos o falsos (al final de la operación ponemos un negado, para que sea verdadera), una vez teniendo éste la enlazamos con un OR y listo, ya cualquier sub-operación agregada nos dará positiva, hasta para hacerla más llamativa le ponemos operaciones más complejas enlazadas con el OR y listo.

Tabla Simple:


Fórmula Desarrollada:
((p & q)→p) | (-r ⊕ ((-q ↔ r) & -(r → p)))


Árbol:


Referencias:
http://etimologias.dechile.net/?tautologi.a
http://es.wikipedia.org/wiki/Tabla_de_verdad

martes, 14 de agosto de 2012

Introducción de Verificación y Validación del Software

Verificación y validación del software, es el proceso de control que asegura que un determinado software cumple con su especificación y satisface las necesidades del usuario.

Verificación: Se ocupa de controlar si el producto satisface los requerimientos del usuario.
  • Construir el sistema correctamente
  • Descubrir  y corregir errores en el sistema
  • Criterios a verificar
  • Vereficar que la información sea coherente
  • Identifica desviaciones con éstandares y requerimientos
  • Recolecta datos para mejorar el proceso
  • Verifica que el producto cumpla: 
    • Cumplan con los requerimientos
    • Cumplan con los  atributos de calidad
    • Se ajuste a las regulaciones, estándares y procedimientos definidos.

Validación: Controla que el producto cumpla su especificación inicial, la diferencia de este a verificación  es el que éste evalúa al sistema en el trancurso o al final del proceso del desarrollo.
  • Construir el sistema correcto
  • Evaluar la conformidad con la especificación de requisitos
  • Casos de test
  • Pruebas unitarias

Técnicas de control: Se dividen en dos: dinámicas y estáticas.
  • Dinámicas: Éstas también son conocidas como  testing  o prueba, así que son únicamente aplicables cuando se tiene una version ejecutable u operativa.
  • Estáticas: Son las primeras pruebas que se aplican al software, tiene como objetivo mejorar la calidad del software ayudando a arreglar defectos en etapas  tempranas, sin codificar.
    • Se basan en revisiones del código o documentación.
    • La finalidad de éste es detectar la mayor cantidad de defectos posibles 
Tipos de Pruebas:
  • Pruebas de aceptación, son desarrolladas por el cliente
  • Pruebas alfa, son realizadas por el usuario con el desarrollador como observador de un entorno controlado
  • Pruebas beta, son realizadas por el usuario en su entorno de trabajo, generalmente son utilizadas como producto final. 
Niveles de Pruebas:
  •  Pruebas unitarias
  • Pruebas de integración
  • Pruebas de sistema
Pruebas funcionales: es una prueba basada en la ejecución, revisión y retroalimentación de las funcionalidades previamente diseñadas para el software.

Desarrollo guiado por pruebas: El objetivo de éste es lograr un código limpio que funcione, la idea  de éste es que los requisitos sea traducidos a pruebas.
 Ciclo:
  • Elegir un requisito
  • Escribir un prueba
  • Verificar que la prueba falla
  • Escribir la implementación
  • Ejecutar las pruebas automatizadas
  • Eliminación de duplicación
  • Actualización de la lista de requisitos

Fases del desarrollo del software: Expresa como a progresado el desarrollo del software y cuanto puede requerir, cada versión importante en la que se le agregan nuevas características o se corrigen errores.
  • Alpha: Es la primera versión del programa, también es enviada a los testers para verificarla, este generalmente es un producto inestable
  • Beta: Representa generalmente la primera versión del sistema, también en ésta fase también el producto es un poco inestable.
  • Version candidata a definitiva(RC): Comprende un producto final, listo para publicarse como version definitiva  al menos que aparezcan errores que lo impidan. También en ésta fase se le puede asociar como el producto final, pero que aún esta en pruebas.
  • Versión de disponibilidad general(RTM): Es un producto en versión final, normalmente es casi idéntica a la version candidata, a diferencia que en ésta hay cambios de último minuto, ésta versión también es tomada como libre de errores y estable..
 
Análisis estático:
Su función es analizar sintácticamente el texto del progrma y tratar de descubrir posibles condiciones erróneas

Defectos: Es un procedimiento de un determinado producto en el cuál son incorrectos

Fallos: Es la imposibilidad de realizar determinada acción de parte del producto

Importancia:
La importancia del hacer uso de verificación y validación es el ahorro de costs y tiempo, que son vitáles en el desarrollo de un determinado producto.
Mensionando algunos ejemplos de casos donde se puede aplicar o donde se han aplicado son los siguientes:
    • Una determinada empresa, firmo un importante convenio en la cual se le pidio elaborar 850,000 piezas de un mecánismo para un nuevo modelo de un carro. Ya obteniendo el producto final con las 850,000 piezas la empresa se da cuenta que la pieza no coincidían con la especificación dada.
      • Problema: La posible falla de ésto pudo ser que al personal que se le pidio elaborar el producto en el software que lo desarrolla, tomaron diferentes las coordenadas o las medidas no fueron las indicadas.
    • Otro de los problemas comunes podemos encontrarlo en los bugs de los videojuegos, alguno de los casos famosos es el videojuego para gameboy, pokemon donde en un nivel más avanzado aparecía un personaje llamado missingNo, el cuál éste era producto de un error de programación donde al momento de buscar un determinado personaje no era encontrado en el arreglo, devolviendo ésto como un missing number.
    • Prototipos nazis, una de los acontecimientos mas mencionados podría ser la fascinación de los nazis por hacer pruebas con los prototipos finales físicos, algunos ejemplos a mencionar podrían ser los prototipos de aeronaves, como supuestos platillos voladores, en las cuales verificaban la aerodinámica del producto entonces hacían pruebas fisicas con la aeronave, pero al final había un fallo por la estabilidad de éste por diferentes condiciones climáticas, volteando la aeronave o haciendo que se golpeara bruscamente que en ocasiones producía la perdida total o perdida del piloto.

Tips o Datos de interés:
Generalmente los desarolladores usan nombre claves para los nombres de las versiones de un producto, con el fin de no confundir el producto o que se tenga un poco más de incógnito del producto para otros usuarios.

Link:
http://www.slideshare.net/FARIDROJAS/validacion-y-verificacion-presentation-632946
http://clases3gingsof.wetpaint.com/page/Verificaci%C3%B3n+y+Validaci%C3%B3n
http://es.wikipedia.org/wiki/Pruebas_de_validaci%C3%B3n
http://www.sqs.es/es/services/validation.php

martes, 7 de agosto de 2012

Automatizacion y Control de Sitemas Dinamicos

BlaBlablaaalblabblaa...

Verificación y Validación de Software

Blablaaabblablalblaa..

Idea para Desarrollar con Redes Neuronales

Mi idea o propuesta es la toma de decisión en acciones, si es bueno invertir o vender acciones.


Porque?
Actualmente, las acciones de una determinada empresa, pueden subir o caer insesperadamente, dando esto a perdidas millonarias o ganancias millonarias.

Beneficios:
A quien no le gustaría ganarse una feria o salvarse de una mala inversión.
Ayudar a accionistas en puntos críticos.

Idea:
La posible idea de como funcionaría ésta, sería tener un previo historial de las acciones, así como algunos datos actuales de como se mueven otras acciones, para poder predecir un posible quiebre.



Links:
http://ciberconta.unizar.es/Biblioteca/0004/SerGall96.html
http://www.ciberconta.unizar.es/leccion/redes/180.HTM