jueves, 20 de septiembre de 2012

Tarea 3: Función de Transferencia y Diagramas de Bloques

Para la tarea 3 de laboratorio de automatización, escogí el siguiente problema:


El problema, como dice, consiste en obtener la función de transferencia del circuito eléctrico mostrado.

Para obtener las ecuaciones de dicho sistema, primero se necesita saber sobre las leyes básicas que gobiernan los circuitos eléctricos (las leyes de Kirchoff de corriente y voltaje). 
  1. La primera ley de Kirchoff( ley de la corriente, KCL) dice que la suma algebraica de todas las corrientes entrando y saliendo de un nodo es cero. Esto también se puede expresar como: "La suma de las corrientes entrando en un nodo es igual a la suma de las corrientes saliendo del mismo nodo".
  2. La segunda ley de Kirchoff( ley del voltaje, KVL) dice que en cualquier instante dado la suma algebraica de los voltajes alrededor de cualquier bucle en un circuito eléctrico es cero. Esto también puede expresarse como: "La suma de las caídas de voltaje es igual a la suma de los incrementos de voltaje alrededor de un bucle". 
Entonces podemos obtener un modelo matemático de un circuito eléctrico aplicando una o ambas de las leyes de Kirchoff a el mismo.

Mi problema
El circuito consta de resistencias (Ohms), capacitadores (Faradios) e intensidad de corriente(Amperes). Considerando ei es la entrada y e0 la salida. Las ecuacones del sistema son:


  • Tomando la primera parte, donde esta ei

  • Tomando la parte de e0



  •  Ahora, utilizando la ley de Kirchoff de los Corrientes(Suma de Corrientes = 0), podemos decir que en la otra ecuación: e0 + ei = 0, que significa:

Ahora para poder obtener la ecuación de transferencia, primero sacamos la transformada de Laplace de cada una de estas ecuaciones, como sigue:


Ahora, una opción es obtener la ecuacíón de transferencia desde estas transformadas, pero el problema especifíca que debemos obtenerla utilizando la aproximación por diagramas de bloques, por lo tanto debemos obtener el diagrama de bloques de cada ecuación, y luego combinarlos para obtener la función de transferencia.

Cambiando la ecuación 1 para poder escribirla en un diagrama de bloques:
Cuyo diagrama de bloques queda así:
(1)
También podemos modificar la ecuación 2 de la siguiente manera:

El diagrama de bloques de ésta ecuación:

(2)

La ecuación 3 podemos pasarla directamente a diagrama de bloques y queda así:

(3)

Ahora combinando los primeros tres diagramas, juntando salidas con entradas iguales y demás, podemos obtener el diagrama siguiente:


Podemos simplificar este diagrama mucho más a fondo para poder encontrar la función de transferencia, la primera simplificación sería así:

(1)
(2)
(3)
(4)

Entonces la ecuación de transferencia es:

miércoles, 19 de septiembre de 2012

5th Assignment

The fifth assignment consist on, as stated in the pdf:

"Implement a HTTP public-key repository for key exchange that employs RSA-based digital signatures"

To do this I chose python and CGI to implement the web service, because it's pretty simple to link the html form to a python script and then take the data from the form to do all the work. I also used a small javascript  function to generate random numbers from 1 to 100, because this was somewhat useful to generate the challenge number x.

Methodology:

First, for a better understanding of the situation, consider this example:

"Alice is chatting with Bob, but she thinks he may be an impostor. Bob is registered in a authentication web service, so Alice enters the web page and generates a challenge "x". Alice then sends this Challenge to bob, who will then Download a script from the web service, in order to calculate his Response "r", which should be generated using a function f(x)[which both the web service and this script should know], the Challenge and his private key. Bob will send Alice back "r", and Alice will then write r in the web service, and selecting Bob in a list. The web service will look for Bob's public key (e, n), and it will calculate its own f(x) which will then compare with r^e % n,. If the values were the same, the web service informs Alice that the authentication was successful. But if the authentication fails the web service will warn Alice that Bob is a fake."

Now I will explain how all fits together step by step in my code:
  1. Using the previous assignment programs, I generated some public and private keys. And stored the public keys somewhere where the server can find them. 
  2. Alice generates a random challenge value "x" using the web service, and selects Bob from the list. Then Alice will send "x" to Bob using a chat.
  3. To get the response, Bob will download a script(the link will be in the same page as the form) and will calculate his y = f(x), and then the response r = y^d % n with his private key. Then Bob will send back the response "r" in the chat.
  4. Alice will type "r" in the form and then when "Check" is pressed, the python script will read all the values, search for the public key of Bob, and calculate r^e % n.
  5. If the calculated value is equal to f(x) [the server should also know what f(x) is], then Bob is authenticated, otherwise he's not Bob and a warning is issued.
Python Code:

Script for Getting the Response
def f(x):
  y = x+1
  return y

def exp(x,n):
  power = 1
  while n != 0:
    if n %2 != 0:
      power *= x
      n -= 1
    x *= x
    n /= 2
  return power

if __name__ == "__main__":
  x = int(raw_input("Challenge(x):"))
  d = int(raw_input("d:"))
  n = int(raw_input("n:"))
  y = f(x) 
  r = exp(y, d) % n
  print "Your r  = %s"%r


The purpose of this script is for the user to download it and calculate its response "r". To do this the user should know his/her private key (d, n) and the challenge value "x". Giving this data as input, the program will calculate y = f(x), where this function is the same that the web service uses. The script will then calculate:
r = (y^d) % n. This r will be sent back to the person using the web service so it can be written in the form.

Python main code

#!/usr/bin/python
import cgi   

def read_public_key(user):
  f = open("users.dat", "r")
  for line in f.readlines():
    tmp_user, public_key = line.split(" ")
    if tmp_user == user:
      e, n = public_key.split(",")
      e = e.replace("(", "")
      n = n.replace(")", "")
      return (int(e), int(n))
  return -1

def f(x):
  y = x + 1
  return y

def exp(x,n):
  power = 1
  while n != 0:
    if n %2 != 0:
      power *= x
      n -= 1
    x *= x
    n /= 2
  return power

if __name__ == "__main__":
  url = "http://synnick.byethost31.com/"
  print "Content-type: text/html\n" 
  print "<html><head>"
  print ' <meta http-equiv="refresh" content="5;url=%s" />'%url
  print "<title>Redirecting...</title></head><body><center>"
  form = cgi.FieldStorage()
  x = int(form.getvalue("Challenge", "(No x value)"))
  user = form.getvalue("User", "(No user)")
  r = int(form.getvalue("y", "(No response)"))

  (e, n) = read_public_key(user)
  y = exp(r, e) % n
  if y == f(x):
    print "<h1>:)</h1>"
    print "<h2>User %s is real</h2>"%user
  else:
    print "<h1>:(</h1>"
    print "<h1>User %s is a fake!</h1>"%(user)
  print '<form method="link" action="http://synnick.byethost31.com/">'
  print '<input type="submit" value="Go Back"></form>'
  print "</center></body></html>"

The code is pretty simple. I copied some functions that I used in the previous assignment, like the exp(x, n) function to do exponentiation by squaring, which is faster than the python's default methods. I also copied my function to read the public key of a certain user from a file, but edited it a little bit.

The important part(the cgi handling) is just checking if a certain name of a form field exists, and reading its value if its not empty. This is done for the challenge value, the list with the users and the response. This data will be used by the program, first with the user name the program will read his/her public key from the users.dat file located somewhere in the server. Then with that public key, the web service will calculate y from the response and compare with the value of f(x). Should this be equal, the user is authenticated, and the program shows a happy smiley. If not then the user is not who he/she says and the program shows a sad smiley.This output is easily done printing html code.

Test to the keys:

Using the test routine that was posted in the Facebook group, I ran some tests to keys with different length, the results were:

Using a short key:
(Here the test passed, because both assertions were True)

Using a medium-sized key:
(Here the test also passed)


Using a long key:

(Here using a long key the test didn't passed)

Using a long key with the Facebook Group code:
(The test passed, which means my key generation program doesn't work with large keys)

Example Run:

First, I'll show the files with the private and public keys that I generated:

(The first file is the one I used to save all the generated keys, both public and private so I could use them while running test. The second one is the file that the web service uses to find the public key of a certain user)

Now using Lucy as an example, I generated a random value x, selected Lucy from the list, and "sent the x value to Lucy".

So the generated x was 76, now "Lucy should download the script from the provided link and use it to calculate the response r":


The calculated response value was 115, "Lucy should send this value back to me, so I can type it in the Response field". Now when I press Check, the program should compare the values and show an output depending on the results. In this case:


Now lets imagine that the response that Lucy sent back wasn't 115 but another number like 77. When I click check with this value, the web service will find a mismatch and then this will happen:


Testing Web Service with Long Keys


Using the large keys that I generated using the Facebook group code, the web service worked correctly:







So the problem with my long key generation was with my exponentiation function, which wasn't fast and good enough than the class fastmodexp function.

References:

lunes, 17 de septiembre de 2012

Tarea 6: Lógica Predicativa

Para esta tarea escogí el ejercicio 4.8 que dice:

Assume the domain of discourse to be all human beings. Translate the following sentences into predicate logic:
  1. Augustus is not loved by everyone( α : Augustus, L : Love).
  2. Augustus and Livia respect each other ( α : Augustus, l : livia, R : Respect).
  3. Livia respects everyone who loves Augustus.
Traducido: 

Asuma que el dominio del discurso son todos los seres humanos. Traduzca los siguientes enunciados en lógica predicativa:
  1. Augustus no es amado por todos (  α : Augustus, A : Amor).
  2. Augustus y Livia se respetan el uno al otro ( α : Augustus, l : livia, R : Respeto).
  3. Livia respeta a todos los que aman a Augustus.
Primero comenzaremos con la expresión (1):

(1) Augustus no es amado por todos

Aquí, considerando que  α : Augustus y A : Amor.

Simplemente sabiendo que estamos hablando de todos los seres humanos, podemos primero colocar el cuantificador ∀ para referirnos a todo el conjunto de seres humanos. Pero debido a que estamos hablando que no todos los seres humanos aman a augustus, debemos darle una negación a este cuantificador. Ya en la expresión podemos colocar Axα (x ama a Augustus, donde x es el ser humano en cuestión). De ésta forma quedaría algo así:

¬∀x ( Axα )
[ No para todo x, x ama a Augustus = Augustus no es amado por todos]

ó (utilizando la propiedad de la negación de cuantificadores)


\exists \!\, x ( ¬Axα )
[ Existe por lo menos un x, que no ama a Augustus]

Axα: x ama a Augustus

Considerando la expresión (2):

(2) Augustus y Livia se respetan el uno al otro 

Donde α : Augustus, l : livia, R : Respeto.

En este caso no son necesarios cuantificadores, debido a que solamente estamos hablando de Augustus y Livia. Este enunciado puede ser también expresado como Augustus respeta a Livia y Livia respeta a Augustus, lo que facilita su traducción a lógica predicativa:


(Rαl ^ Rlα )
[Augustus respeta a Livia y Livia Respeta a Augustus = Augustus y Livia se respetan el uno al otro]

Rαl: Augustus respeta a Livia
Rlα: Livia respeta a Augustus


Para terminar, la expresión (3):

(3) Livia respeta a todos los que aman a Augustus.

Donde α : Augustus, l : livia, R : Respeto y A : Amor.

Aquí de nuevo estamos hablando de todos los que aman a Augustus, por lo que el cuantificador en cuestión es ∀. Ahora, como estamos hablando de que solo respeta a aquellos que aman a Augustus, estamos  hablando de un bicondicional, debido a que Livia respeta a alguien sí y solo sí ese alguien ama a Augustus. Por lo tanto quedaría algo así:

x ( Rlx  Lxα)
[Para todo x, Livia respeta a x si y solo si x ama a Augustus]


Rlx: Livia respeta a x
Lxα: x ama a Augustus



Referencias:

jueves, 13 de septiembre de 2012

4th Assignment: RSA Authentication

For this week, we had to do the following:
  • Implement RSA authentication in Python for a client-server system with sockets.
For this I implemented this in two different ways:
  1. A password verifying one, where the server sends the client the public key, the client encrypts its password with that, and sends it back. Then the server deciphers it with the private key and searches in a file for a match.
  2. The method explained in class where the server sends a random number, the client calculates a function from that number and encrypts it  with its private key to send it to the server. The server will now use the host name of the client to search the public key and decipher it. If it matches, the client is authenticated, otherwise the connection closes.
RSA

RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. RSA stands for Ron RivestAdi Shamir and Leonard Adleman.[1]

So, the algorithm, as stated in the class pdf, is pretty much:
  • Generate n = p × q, where both p and q are prime.
  • (e, n) is the public key; c = m^e mod n.
  • e is to be relatively prime with ɸ(n)
  • (d, n) is the private key; m = c^d mod n.
    • Requirement: e × d ≣ 1 mod ɸ(n) (or in other words d needs to be the inverse multiplicative of e);
  • ɸ(n) = (p - 1) × (q - 1).
  • m^(e×d)≣ m mod n due to Euler’s theorem.

Method 1 (Not the one explained in class)

So initially I understood the homework differently so I did the client-server program in a different way, but because I didn't want all that time spent go to waste I'll just go ahead and explain it anyway.

For this method, I first tried to make a diagram sort-of thing to manage the interactions between the client and server, and what would each instance do.  I did it first in paper, but then to make it more easy to understand I also did it on Cacoo:

Then, the process would be:
  1. The server generates p and q, calculates n and ɸ(n).
  2. The server chooses an e which is relatively prime to ɸ(n).
  3. The server computes d, which is the inverse multiplicative of e (with the extended euclidean algorithm).
  4. The server sends the public key (n, e) to the client who wants to authenticate.
  5. The client encrypts its password with said public key, and sends the cipher text to the server.
  6. The server will now use the private key (n, d) to recover the password from the cipher text, and searches for the password in a certain file.
         6.1. If there is a match, the server authenticates the client, and the communication can begin.
I will now explain step by step how I did this on Python.
Note:  I will not explain here how the client-server communication with sockets works, because this post is dedicated to the RSA Authentication part.

Step 1. The server generates p and q, calculates n and ɸ(n).

First we need to choose a pair of prime numbers p and q, which need to be different. For security purposes, these numbers need to be random, so I did a small pair of functions, one which will verify if a determined number is prime, and another which generates two random prime numbers. Combined we should get a nice pair of p and q random primes.

Now with p and q, we calculate n = p x q, and ɸ(n) = ( p - 1) x ( q - 1).

Step 2. The server chooses an e which is relatively prime to ɸ(n).

Two numbers are said to be relative prime or co-prime if the only number that divides both of them is 1. So we need e to be relatively prime ɸ(n). To generate a valid e, I also did a simple function which checks if two numbers are co-prime. 

Step 3. The server computes d, which is the inverse multiplicative of e.

To do this,we need to use the extended euclidean algorithm. For example, if we have e = 3 and ɸ(n) = 11, first we do a table like this:
We make the first α the value of ɸ(n) (in this case 11), and the first β the value of e(3). γ will be the result of the  operation α % β, but we need to keep the values of the multiplication. The next pair of  α-β will be the previous β and the previous γ respectively.The table finishes when we reach zero.

After this, starting from 1, we need to change each multiplier in the terms of the previous residue. This means that, first we will clear 1, and then we will replace the 2 in that for the terms of the previous 2, until we're done:
Now we pair up the similar terms. To verify the equality we could apply modulo of 11 to everything,  but to find d, first we eliminate the numbers multiple of 11(equal to zero). 
 

Then we should have something like (e)(d) % 11= 1, where the e will be the value we already know, and d the multiplicative inverse of e. 

d = 4, e = 3

Step 4. The server sends the public key (n, e) to the client who wants to authenticate.

Now the server will send the public key values "n" and "e" to the client via sockets. Nothing more.

Step 5. The client encrypts its password with said public key, and sends the cipher text to the server.

The client uses "n" and "e" to encrypt his/her password, and then send that cipher text back to the server. The encryption will be done using c = (m^e) % n, where m is the password, "e" and "n" are the public key and c is the resulting cipher text.

It should be noted that, if the password is going to be a combination of words and letters, each word should be  ciphered individually but working carefully with the modulo because the password could be lost.

Step 6. The server uses the private key (n, d) to recover the password from the cipher text, and searches for the password in a certain file.

The server now uses the previously generated d, and n, as the private key to recover the message(in this case a password). So, m = (c^d) % n. This password will be searched in a file to verify if the client already exists(we could also use a host name for the client to use as an index in this search). 

Step 6.1. If there is a match, the server authenticates the client, and the communication can begin.

If the password was found in the previous step, then the server acknowledges the client as trustworthy and whatever communication was supposed to happen can now happen. Otherwise the communication can end because the password was wrong.

Example of the process:

      Calculating the Public Key


Encrypt  m:
Decipher c:
Code:

The program bellow simulates an rsa authentication using a client-server protocol. First the server generates the random primes p and q, then it calculates n and ɸ(n) with said values. Then it generates the e (coprime to  ɸ(n)). The server will send the public key (e, n) to the client, which will use it to encrypt a password. The resulting cipher text will be sent back to the server, which will decipher it and compare it with stored passwords in a file. If it matches a password, the authentication is correct, and the client is trusted. Otherwise it will terminate the communication.

The code consists of 3 files: rsa_client.py, rsa_server.py and rsa_operations.py. I did the last one to gather all the common operations needed to calculate stuff for the rsa algorithm, like the euclidean algorithm, exponentiation by squaring, simple prime verificators and such.

Client Side



Server Side
Screen Captures:

Correct Authentication




Incorrect Authentication (Wrong Password)



Password file:



Method 2:

Now the real method which was explained in class is this one. I didn't write it down from a scratch, I just modified the previous one because that way was easier (and it's my code after all). This method consists in:
  • The server generates a random number x.
    • The server sends x to a connected client.
  • The client calculates y = f(x) where this function can be pretty much anything, in my case is just 2x+1.
    • The client encrypts y using its private key (which will be generated previously in a file)
    • The client sends the encrypted y to the server.
  • The server receives the encrypted y and searches for a public key for the host name of the client.
    • If there is a match, the server retrieves the public key, deciphers the encrypted y, and compares with f(x)
    • If f(x) is equal to the deciphered y, then the client is welcomed.
      • Otherwise the communication is over.
Code:

Using the example that I explained on the previous method, I created the public key (e, n) = (7, 187) and stored in in the users.dat file for the server. I also did the same with the client, storing the private key (d, n) = (23, 187) in the emmanuel.dat file. So for any random that the server generates, the client emmanuel should be able to get authenticated.

Client Side:


Server Side:


Screen Captures: Correct Authentication
Incorrect Authentication(changing client key)
users.dat and emmanuel.dat files





References:

lunes, 10 de septiembre de 2012

Reporte 1: Función de Transferencia

El primer reporte consta de crear un modelo matemático para nuestro proyecto, en forma de una función de transferencia. Primero que nada explicaré en que consiste nuestro proyecto:

Control de ventiladores a partir de temperatura

(Simulación sencilla hecha hecha en Proteus, faltaría un microcontrolador que controle con más precisión todo el sistema)
Descripción:

El proyecto consiste en un sensor de temperatura (LM35) del cual a partir de la variación que de, pueda surgir un voltaje variable que produzca diferentes velocidades para el ventilador, o en caso de que la temperatura sea muy baja, éste permanezca apagado.

El rango de voltaje de salida en el que opera el LM35 es de 10mV por °C, por lo cual será necesario amplificar este voltaje a una cantidad mucho mayor, que pueda encender el ventilador.

Materiales:

Los materiales que tenemos contemplados de momento, pero que podrían aumentar son los siguientes:
  • Sensor LM35
  • Amplificador Operacional (LM324)
  • Algunos Leds para obtener retroalimentación visual.
  • Resistencias
  • Ventilador(VN4-012P)
  • Fuente de Poder de 12V
  • Cable para conexiones.
Modelo Matemático

Primero necesitamos dejar en claro que es un modelo matemático.

[1]Un modelo matemático es la descripción matemática de un sistema o fenómeno de la vida real. La formulación de un modelo matemático implica:
  • Identificar las variables causantes del cambio de un sistema.
  • Establecer un conjunto de hipótesis razonables acerca del sistema (leyes empíricas aplicables).
Las hipótesis de un sistema implican con frecuencia la razón o tasa de cambio de una o más variables que intervienen. El enunciado matemático de esas hipótesis es una o más ecuaciones donde intervienen derivadas, es decir, ecuaciones diferenciales.

Proceso de modelado

El proceso de modelado básicamente sigue los siguientes pasos:
  1. Identificación de variables estableciendo una notación matemática.
  2. Leyes empíricas que se pueden aplicar.
Modelo del Proyecto


Entonces según lo definido anteriormente primero identificaremos las variables que causan cambios y luego establecer algunas hipótesis:
  • Identificación de variables causantes del cambioPrimero es necesario identificar las variables que causan el cambio en el sistema, que en este caso es el control de los ventiladores. La única variable que podemos identificar es:
    • Temperatura del sensor LM35: A partir de ésta, todo el sistema actuará(si es baja, el ventilador podría mantenerse apagado o encender muy lentamente, al ir incrementando la velocidad del ventilador debería aumentar proporcionalmente hasta cierto punto).
    • Nota: podríamos considerar el voltaje debido a que este es el que marcara la velocidad del ventilador, pero al ser diferente el voltaje en respuesta a la temperatura del sensor LM35, la que en verdad esta causando este cambio es la temperatura.
  • Establecer un conjunto de hipótesis acerca del sistema
    Asumiendo que el sistema éste funcionando correctamente, podemos hacer las siguientes hipótesis:
    • "La velocidad del ventilador aumentará proporcionalmente con la temperatura, hasta un punto en el cual dejará de aumentar"
    • "La velocidad del ventilador disminuirá proporcionalmente con la temperatura hasta caer a cero"
    • "En caso de que no exista cambio de temperatura, la velocidad del ventilador permanecerá constante"
Proceso de modelado

Ahora ya para realzar el modelado matemático, primero identificamos las variables involucradas en el sistema mediante una notación matemática para después mostrar las leyes que se puedan aplicar.
  • Identificación de variables estableciendo una notación matemática
    Como sabemos, la variable causante del cambo sería la temperatura, esta haría que el sensor produjera un voltaje de salida variable de 10mV/°C, y a su vez este voltaje amplificado cambiaría la velocidad del ventilador, por lo tanto:
    • Temperatura t (en °C)
    • Voltaje V(en Volts)
    • Velocidad v (en RPM, revoluciones por minuto, debido a que trabajamos con un ventilador)
  • Leyes empíricas que se pueden aplicar.
  • Ley de Enfriamiento de Newton. Al trabajar con variaciones(diferencias) de temperatura, no es difícil darnos cuenta que todo esto se refiere a derivadas,en cuanto a temperatura la Ley de Enfriamiento de Newton podría servir de alguna manera, y ésta dice  que en un cuerpo que se está enfriando, la rapidez con que la temperatura T(t) cambia es proporcional a la diferencia entre la temperatura del cuerpo y la temperatura constante Tenv del medio que lo rodea.
 Donde r es la constante de proporcionalidad.

  • LM35
    Como ya mencioné el sensor LM35 produce 10mV/°C, lo que podemos utilizar para crear una simple ecuación que defina el voltaje que nos dará en función de la temperatura.
  • Entonces dependiendo de la temperatura que sería la entrada, podríamos encontrar el voltaje que este produciría utilizando el sensor LM35. Esta sera nuestra ecuación de entrada.
  • Amplificador No Inversor
    Nuestro circuito hace uso de un amplificador no inversor, que es necesario para amplificar la salida del sensor LM35(10mV) a algo mayor que nos pueda producir cantidades de entre 8 y 13 volts (lo que opera el ventilador), por ello para obtener la cantidad con la cual ampliaremos, necesitamos hacer uso de la siguiente función:
Nota: R2 y R1 son constantes, debido a que son resistencias que ajustaremos  para obtener una ganancia que pueda darnos un voltaje de salida entre 8 y 12V

Usando la ecuación anterior del LM35, podríamos obtener el voltaje de inicio para esta ecuación, y entonces obtener el voltaje de salida que pondría en operación el ventilador. Por lo tanto esta puede ser la ecuación de salida.

Función de Transferencia

[2]Un modelo matemático para un sistema descrito por una ecuación diferencial lineal e invariante en el tiempo. Es la transformada Laplace de la salida divido entre la transformada Laplace de la entrada.

En el caso de el problema, yo propongo como funciones de entrada y salida según lo definido anteriormente:

fin  
fout  = 

Entonces las Transformadas de Laplace de cada una son:

Por lo tanto la función de transferencia quedaría de la siguiente manera: