Cecilia Urbina: septiembre 2012

miércoles, 19 de septiembre de 2012

RSA-based digital signatures

Homework:

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

I used Google App Engine Python for the web service, this is my app http://rsa-ds.appspot.com/.
The script to download and calculate the "r" and "y" is :

	#!/usr/bin/python
	def f(x):
	return x311*7

	def fastmodexp(x, y, mod):
	p = 1
	aux = x
	while y > 0:
	if y % 2 == 1:
	p = (p * aux) % mod
	aux = (aux * aux) % mod
	y = y >> 1
	return p

	def main():
	x = int(raw_input("x: "))
	d = int(raw_input("d: "))
	n = int(raw_input("n: "))
	y = f(x)
	r = fastmodexp(y, d, n)
	print "La r es = " + str(r)

	main()

view raw gistfile1.py hosted with ❤ by GitHub

Google app python:

	import cgi
	import webapp2
	import random
	from google.appengine.api import users
	import datetime
	from google.appengine.ext import db


	def f(x):
	"""devuelve un valor de y
	"""
	return x311*7

	def fastmodexp(x, y, mod):
	p = 1
	aux = x
	while y > 0:
	if y % 2 == 1:
	p = (p * aux) % mod
	aux = (aux * aux) % mod
	y = y >> 1
	return p


	class Usuario(db.Model):
	nombre = db.StringProperty(required=True)
	e = db.StringProperty(required=True)
	n = db.StringProperty(required=True)

	######## users test########

	a = Usuario(nombre="cecy",
	e="59",
	n="5767")
	a.put()
	b = Usuario(nombre="daniel",
	e="13",
	n="2773")
	b.put()
	c = Usuario(nombre="pedro",
	e="23",
	n="3293")
	c.put()
	d = Usuario(nombre="lupita",
	e="89",
	n="3649")
	d.put()
	############################


	class MainPage(webapp2.RequestHandler):
	"""clase principal que muestra el formulario
	"""

	def get(self):
	x = int(random.random()*100)
	self.response.out.write("""
	<html>
	<head> <link type="text/css" rel="stylesheet" href="/bootstrap/css/bootstrap.css" />
	</head>
	<body>
	<div class="container">
	<form class="form-horizontal" action="/generate" method="post">
	<legend>RSA-based digital signatures</legend>
	<div class="control-group">
	<label class="control-label">Challenge</label>
	<div class = "controls">
	<input type="text" name="x" value="%s" readonly="readonly"/>
	<a class="btn" href="http://rsa-ds.appspot.com/"><i class="icon-cog"></i>Generate</a>
	</div></div>
	""" %x)
	usuarios = db.GqlQuery("SELECT * FROM Usuario")
	self.response.out.write("""<div class="control-group">
	<label class="control-label"><i class="icon-user"></i>
	User</label>
	<div class="controls">
	<select name="usuario">""")
	for i in usuarios:
	self.response.out.write("""<option>""")
	self.response.out.write("""%s""" %i.nombre)
	self.response.out.write("""</option>""")
	self.response.out.write("""</select>
	<a class="btn" href="https://docs.google.com/open?id=0BzBiYAUF68vdNFEzMnFIaWhrcjQ">
	<i class="icon-download-alt"></i>Download script</a></div></div>
	<div class="control-group">
	<label class="control-label"><i class="icon-edit"></i>r</label>
	<div class="controls">
	<input class="input-large" type="text" name="r" placeholder="numeric value" size="10" /></div></div>
	<div class="controls">
	<button type="submit" class="btn btn-primary"><i class="icon-check icon-white"></i> Validate</button></div>
	</form>""")
	self.response.out.write("""</div></body>
	</html>""")


	class Calculo(webapp2.RequestHandler):
	def post(self):
	self.response.out.write("""<html><head>
	<link type="text/css" rel="stylesheet" href="/bootstrap/css/bootstrap.css" /></head>
	<body><div class="container">""")
	usuario = self.request.get('usuario')
	r = self.request.get('r')
	x = self.request.get('x')
	y = f(int(x))
	us = db.GqlQuery("""SELECT * FROM Usuario WHERE nombre = '%s'""" %usuario)
	for i in us:
	e = i.e
	n = i.n
	nombre = i.nombre
	try:
	y1 = fastmodexp(int(r), int(e), int(n))
	self.response.out.write("""<div class="row">User: %s</div>
	<div class="row">r: %s</div>
	<div class="row">x: %s</div>""" %(usuario, r, x))
	self.response.out.write("""<div class="row">y = f(x) = %s</div>""" %y)
	self.response.out.write("""<div class="row">Public key: (e,n) =
	(%s, %s)</div>""" %(e, n))
	self.response.out.write("""<div class="row">y1 = r^e mod n = %s</div>""" %y1)
	if y1 == y:
	self.response.out.write('<div class="row"><p class="text-success">Yes, it is correct</p></div>')
	else:
	self.response.out.write('<div class="row"><p class="text-error">Is incorrect</p></div>')
	except ValueError:
	self.response.out.write('<div class="row">r must be a numeric value</div>')
	self.response.out.write('<div class="row"><a href="http://rsa-ds.appspot.com/">Retry</a></div>')
	self.response.out.write('</div></body></html>')

	app = webapp2.WSGIApplication([('/', MainPage),
	('/generate', Calculo)],
	debug=True)

view raw gistfile1.py hosted with ❤ by GitHub

Database:

Screenshots:

Script:

App:

Result:

Script:

App:

Result:

App:

Result:

App:

Result:

domingo, 16 de septiembre de 2012

Función de transferencia de la ecuación de estado

B.3.10 Considere el sistema descrito mediante:

Obtenga la función de transferencia del sistema.

Para resolver esto tenemos la siguiente teoría obtenida del libro "Sistemas de Control Moderno" de Richard C. Dorf:

"y" es la única entrada y "u" la única salida y sus transformadas de Laplace son:

en donde B es la matriz de nx1, ya que u es una sola entrada. No se incluyen condiciones iniciales, porque se busca la función de transferencia. Y reordenando la ecuación se obtiene:

Como

tenemos:

Y ahora sustituimos X(s) en la ecuacion Y(s) y tenemos:

Entonces la funcion de transferencia:

es:

Ahora si estamos listos para resolver el problema planteado:

Tenemos que obtener la función de transferencia

Entonces lo primero que hice es obtener la matriz Identidad multiplicada por s:

Después le resto la A:

Ahora obtenemos Phi(s):

Para obtener la matriz inversa se sigue la formula:

Entonces:

que es igual a:

y simplificamos la parte de abajo de la fracción:

Entonces ahora tenemos Phi(s)

El siguiente paso es obtener :

Sustituimos:

Lo siguiente es multiplicar las matrices, con esto obtendremos una sola matriz de 2x1:

Entonces nuestra X(s) queda:

Ahora nuestra C es igual a la y que nos da el problema por las formulas ya vistas antes entonces tenemos que la C es:

Y la manera de obtener la función de transferencia G(s) es:

Sustituimos valores:

Como podemos ver fácilmente la multiplicación de matrices será "s" , entonces tenemos:

La función de transferencia final es:

Y ahora si ya para terminar y por no quedarme con la duda me puse a investigar como podría hacer esto en octave, y encontré una función que se llama "ss2tf" en octave que lo que hace es que a partir de la variable de estados obtenemos la función de transferencia. Para esto lo primero que hay que hacer es instalar el paquete "signal" lo descargamos de la página oficial de octave, sin embargo al querer instalar este nos damos cuenta que tiene dependencias a otros paquetes que aun no están instalados:

Entonces igual descargo uno a uno los paquetes y instale primero el paquete "image" sin problemas, después el "specfun" también sin problemas y por último el "optim" con este si tuve que instalar otra vez otras dependencias:

También las descargo de la página de octave, y ahora si instalo "optim" y el paquete "signal" porfin.

Ahora en octave cargamos el paquete con "pkg load signal" y les dejo una captura con la solución de mi problema, primero cargamos las matrices de estado:

Y ahora resuelve y obtenemos el mismo resultado que encontramos a mano:

Referencias

Dorf, Richard C., and Robert H. Bishop. Sistemas de control moderno. 10th ed.
Matriz inversa

Octave, ejemplo

Principios de demostraciones en validez

Para esta semana el ejercicio lo obtuve del pdf http://www.logicinaction.org/docs/ch4.pdf y la manera de resolverlo también ya que venían ejemplos muy parecidos, es el siguiente:

Exercise 4.3 Translate the following sentences into predicate logical formulas:
(1) If John loves Mary, then Mary loves John too.
(2) John and Mary love each other.
(3) John and Mary don’t love each other.
(4) If John and Peter love Mary then neither Peter nor Mary loves John.

Ejercicio 4.3 Transforma las siguientes oraciones a formas lógicas predicativas:
(1) Si John ama a Mary, entonces Mary ama a John también.
(2) John y Mary sea aman uno al otro.
(3) John y Mary no se aman uno al otro.
(4) Si John y Peter aman a Mary entonces ni Peter ni Mary aman a John.

Podemos definir que X ama a Y con la siguiente y única expresión que necesitamos para transformar nuestros enunciados :
A(X, Y)

1. Si John ama a Mary, entonces Mary ama a John también. Entonces definimos con nuestra funcion A(X, Y) que recibe dos argumentos el primero la persona que hace la acción y el segundo quien la recibe. Al decir que John ama a Mary esto queda así: A(J, M) y como agregamos "entonces" osea una consecuencia de la primera agregamos el símbolo -> para ahora decir que Mary ama a John: A(M, J). Que queda como sigue:

A(J, M) ⇒ A(M, J)

2. John y Mary se aman uno al otro. En esta expresión a diferencia de la primera es que una cosa no es consecuencia de la otra lo que podemos agregar el conector lógico and para unir las nos funciones, una que exprese que John ama a Mary A(J, M) y otra que Mary ama a John A(M, J).

A(J, M) ^ A(M, J)

3. John y Mary no se aman uno al otro. Es muy parecida a la anterior pero hay que negar las dos funciones, y las seguimos uniendo con un and.

¬(A(J, M) ^ A(M, J))

4. Si John y Peter aman a Mary entonces ni Peter ni Mary aman a John. Para expresar este enunciado en lógica predicativa tenemos que dividirlo en dos primero escribir que "John y Peter aman a Mary" con la expresión: A(J, M) ^ A(P, J) y después "ni Peter ni Mary aman a John" con la expresión:

¬A(P, J) ^ ¬A(M, J), y ahora si unirlas con el conector -> que expresa que Si John y Peter aman a Mary entonces ni Peter ni Mary aman a John:

(A(J, M) ^ A(P, M)) ⇒ (¬A(P, J) ^ ¬A(M, J))

jueves, 13 de septiembre de 2012

RSA

For this week, the homework is to implement the RSA, I followed the next steps:

(the names of my variables are different than those we saw in class because I based the variable names on the book "Discrete Mathematics, Richard Johonsonbaugh"
)

Create 3 scripts, one that generate public and private keys, another that is client.py and one for the server.py.

For keys first generate a list of primes where I chose the p and q
After, the n in my program is part of the public key. I chose the prime number as n. I noticed that phi is not a multiple of n.
Immediately implements the Euclidean algorithm to get the s(private key)
and finally create two key files, one public.txt and one private.txt
I create the client.py and server.py and follow the next steps:

RSA:

	#!/usr/bin/python
	import random

	def genera_primos():
	"""hago una lista de los primero 10 numeros primos
	para despues de ahi elegir p,q, y n
	"""
	numero = 2
	total = 0
	primos = list()
	while total <= 10:
	div = 0
	cont = 1
	while cont <= numero:
	res = numero % cont
	if res == 0:
	div = div + 1
	cont = cont + 1
	if div <= 2:
	total = total + 1
	primos.append(numero)
	numero = numero + 1
	return primos

	def escoge_p_q():
	"""eligo p y q al azar decidi que no se repitieran
	"""
	primos = genera_primos()
	p = random.choice(primos)
	primos.remove(p)
	q = random.choice(primos)
	return p, q

	def escoge_n(o):
	"""escogo n al azar de la lista de numeros primos
	la escogo prima para que pueda cumplir mas facil las caracteristicas
	de ser coprima con o=(p-1)(q-1)
	"""
	primos = genera_primos()
	n = random.choice(primos)
	if o%n == 0 or n>o:
	return escoge_n(o)
	return n

	def euclides(n, o):
	"""en esta funcion obtengo la s,
	que hace que (s*n mod o) sea igual a 1
	"""
	a = n
	b = o
	s, t, s1, t1 = 1, 0, 0, 1
	while b != 0:
	q = a/b
	r = a%b
	a, s, t, b, s1, t1 = b, s1, t1, r, s-(s1q), t-t1q
	s = s%o
	return s

	def escribo_clave_publica():
	usuarios = ['cecy', 'lupita', 'pedrito']
	f = open("claves_publicas.txt", "w")
	datos = {}
	for i in usuarios:
	p, q = escoge_p_q()
	print "La p y la q son:"
	print p, q
	z = p * q
	print "La z es:"
	print z
	o = (p-1)*(q-1)
	print "La o es:"
	print o
	n = escoge_n(o)
	print "La n es:"
	print n
	clave_publica = z, n
	print "La clave publica es:"
	print clave_publica
	f.write(""+str(i)+", "+str(n) + ", "+str(z)+"\n")
	datos[i] = [p, q, z, o, n]
	f.close()
	return datos

	def escribo_clave_privada(datos):
	usuarios = ['cecy', 'lupita', 'pedrito']
	f = open("claves_privadas.txt", "w")
	for i in datos:
	numeros = datos[i]
	print numeros
	p = numeros[0]
	q = numeros[1]
	z = numeros[2]
	o = numeros[3]
	n = numeros[4]
	s = euclides(n, o)
	print "La s encontrada es:"
	print s
	x = int(random.random()*100)
	print "la x es:"
	print x
	f.write(""+str(i)+", "+str(s) + ", "+str(z)+"\n")


	def main():
	datos = escribo_clave_publica()
	print datos
	escribo_clave_privada(datos)
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Server:

	#!/usr/bin/python
	import socket
	import random

	def f(x):
	y = x*29
	return y

	def leer_claves():
	f = open("claves_publicas.txt")
	usuarios = {}
	for l in f.readlines():
	linea = l.split("\n")[0]
	linea = linea.split(",")
	#print linea
	usuarios[linea[0]] = [linea[1], linea[2]]

	return usuarios

	def main():
	usuarios = leer_claves()
	socket_1 = socket.socket()
	socket_1.bind(("localhost", 9999))
	print "Servidor iniciado"
	socket_1.listen(1)
	socket_2, addr = socket_1.accept()
	x = int(random.random()*100)
	socket_2.send(str(x))
	datos = socket_2.recv(512)
	datos = datos.split(",")
	print datos
	usuario = datos[0]
	r = int(datos[1])
	if usuario in usuarios:
	print usuario
	clave = usuarios[usuario]
	n = clave[0]
	z = clave[1]
	y = (int(r)**int(n))%int(z)
	if f(x) == y:
	print "Bienvenido al sistema"
	else:
	print "Algo esta mal con las igualdades"
	else:
	print "Algo esta mal con el nombre"
	socket_1.close()
	socket_2.close()
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Client:

	#!/usr/bin/python
	import socket

	def leer_claves():
	f = open("claves_privadas.txt")
	usuarios = {}
	for l in f.readlines():
	linea = l.split("\n")[0]
	linea = linea.split(",")
	usuarios[linea[0]] = [linea[1], linea[2]]
	return usuarios

	def f(x):
	y = x*29
	return y

	def main():
	usuarios = leer_claves()
	socket_c = socket.socket()
	socket_c.connect(("localhost", 9999))
	print "Servidor iniciado"
	x = socket_c.recv(512)
	x = int(x)
	y = f(x)
	usuario = raw_input("Usuario: ")
	print usuario
	if usuario not in usuarios:
	print "Algo esta mal"
	socket_c.close()
	return
	datos = usuarios[usuario]
	s = int(datos[0])
	z = int(datos[1])
	r = (y**s)%z
	enviar = ""+usuario+","+str(r)
	socket_c.send(enviar)
	socket_c.close()

	main()

view raw gistfile1.py hosted with ❤ by GitHub

Corrects users and keys:

Incorrect user:

Extra points