[SC] 6. RSA-Based Digital Signatures

For this week the homework was:

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

Implementation

The deployed web application uses a python script as CGI to serve the request, and another script named validator, to validate the written data into the forms.

The CGI implements 

• def function(x): The function that is evaluated with x, returns the value of fx.
• def fastmodexp(r, e, n): Calculates the value of y (y = r^e mod n)
• def generateResult(x, username, r): When the CGI validates the values of x, username and response, this function uses the username to get the value of e and n, then, calculates the value of fx and y, finally, compares their values and if fx and y are equals returns SUCCESS!, otherwise, returns FAILURE!. Implements a debug flag to print all the calculated values.
• def validation(): Validates that the written data in the forms has the correct format. Uses a error flag to warn to the script if something is wrong, then, prints the error messages.
• def getOption(): Gets the option of the CGI form. If option doesn't exists in the form, the normal page is printed. If option exists in the form and the value is one, the CGI generate a challenge value and print it in the challenge input. If the value is two, the CGI gets the value of the challenge, username and response inputs and send them to the validate function.
• def getUsers(): Open the text file with the users data (public keys), read the contents and parse them to a list. Return a list with all the users and keys.
• def getUserData(username): Read the list of users and extract the data of the specified username.
• def generateChallenge(): Implements random.randint to generate a challenge between a specified range.
• def printUsers(selectedUser): Prints the select input in the web page, calls the function getUsers(), gets the list of users and uses the information to generate options. Uses the parameter selectedUser to print a preselected option.
• def printHead(challenge, selectedUser, response, result): Prints all the web application. If challenge is defined, prints its value in the challenge input. If selectedUser is defined, send it to the function printUsers() to print the select input with a preselected username. If response is defined, prints its value in the response input. If result is defines, prints its contents (error messages or successful messages) in a hidden specified area below the response input.
• def main(): Gets the form, search for the option key and makes a decision to print the correct content in the window.

Also implements JQuery to control the events of the buttons and manage dynamically the form values.

Code - webapp

Script

The user has to download a script to generate the response, the script implements the functions :

• def function(x): The function that is evaluated with x, returns the value of y.
• def fastmodexp(y, d, n): Calculates the value of r (r = y^d mod n)

The user must copy and paste the response in the webapp to validate the data.

Code - script

External Tests

Cecy

Web Interface

 Script Execution

Ramon

Web Interface

Rafael

Web Interface

 Script Execution

Video

http://www.youtube.com/watch?v=qFQEJK2cZ8A

Link to the WebApp

http://jcespinosa.dyndns-web.com/~jc1/cgi-bin/cryptography/authentication.py

[VVS] 6. Principios de demostraciones de validez

Para la tarea de esta semana se eligió un ejercicio del texto http://www.logicinaction.org/docs/ch4.pdf, el ejercicio que elegí fue el siguiente:

Exercise 4.5: Rephrase "¬( X ≤ Y ∧ Y ≤ Z )" in predicate logic, using binary relations "<" for "less than" and "=" for "equal"

Ejercicio 4.5: Reformular "¬( X ≤ Y ∧ Y ≤ Z )" en lógica predicativa, usando las relaciones binarias "<" para "menor que" y "=" para "igual"

Solución

Expresión incial: 

¬( X ≤ Y ∧ Y ≤ Z )

La expresión nos dice que "no es verdad que Y es mayor o igual a X y no es verdad que Y es menor o igual a Z", en pocas palabras "Y no esta en el rango desde X hasta Z".

Debemos eliminar los símbolos de "mayor o igual que" para cumplir con lo que el ejercicio nos pide, entonces primero podemos ir reduciendo la expresión paso por paso para entender lo que vamos haciendo.

Primero, la teoría nos dice que expresiónes con las siguiente estructura:

A < B ∧ A < C   ó   A > B ∧ A > C

pueden ser reformuladas removiendo el conectivo and y quedando de la siguiente manera:

A < B < C   ó   A > B > C

Entonces nuestra expresión puede reformularse así:

¬( X ≤ Y ≤ Z )

Segundo, podemos eliminar los símbolos de "mayor o igual que" tal como nos lo recomienda el mismo ejercicio, utilizando dos relaciones binarias y uniéndolas con un conectivo lógico, así, la expresión:

A ≤ B 

puede reformularse así:

A < B ∨ A = B

y nuestra expresión queda así:

¬[ ( X < Y < Z ) ∨  ( X = Y = Z ) ]

FIN :)

[SC] 5. RSA Authentication

For this homework, we have to implement the RSA Authentication in python for a client-server system using sockets.

Introduction

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 Rivest, Adi Shamir and Leonard Adleman, who first publicly described it in 1977. Clifford Cocks, an English mathematician, had developed an equivalent system in 1973, but it was classified until 1997. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message. Whether breaking RSA encryption is as hard as factoring is an open question known as the RSA problem.

From http://en.wikipedia.org/wiki/RSA_(algorithm)

The implementation consist in two parts, the key generator and the client-server system.

Key Generator

For the RSA Authentication we need two keys, a public key and a private key. The public key can be know to everyone. The private keys is only know by the user. A message encrypted with the public key can only be decrypted with the private key.

For the Key generator I followed 3 steps:

• Request an username
• Generate a key
• Save (e and n) in a file named public.txt, save (d and n) in a file named private.txt

The algorithm to generate the keys is as follows:

1. Generate two different random integers and prime numbers p and q of 4 digits
2. Calculate n = p * q
3. Calculate φn = (p - 1)(q - 1)
4. Generate a random integer e between 1 and φn-1
5. Use the Extended Euclidean Theorem to calculate GCD(e, φn) and verify if e and φn are coprimes. The Extended Euclidean Theorem returns 3 values
• x and y are values ​​that satisfy the expresion ax + by = GCD(a,b)
• a is the result of GCD(a,b)
6. If a = 1 then e and φn are coprimes and now d = x, where d ≡ e^-1 mod(φn)
7. (For some reason, sometimes the value of d is negative, a while loop convert it in positive adding φn to d )
8. At this point we have calculated e (public), d (private) and n

Code

RSA Authentication

For this part I wrote a script in python implementing sockets. The programs expect 3 parameters

• User type, could be -C to client or -S to server.
• Host direction
• Port number

The script creates a server socket and a client socket, the execution of the script is as follows.

1. Get the 3 parameters, if missing one, close and exit.
2. If the 3 parameter are defined, according to the parameter 1 the scripts creates a server socket or a client socket.
3. The server sockets binds the host and port and wait (listen) for a connection. The client takes the host and port and attempt to connect to the server.
4. If the connection between then server and the client is sucessfull, the server send to the client a random value x. The server calculates the value of F(x) and the client calculates y using the same function as the server.
5. The client request a username for the authentication. The client search for the client data in the file private.txt. If the user is in the file, the subroutine returns a list containing the username, d and n, otherwise, the routine shows an exception, returns False and the client closes the connection.
6. The client uses d and n to calculate r = y^d mod (n). The calculations involve very large number, so, I wrote a subroutine based in modular exponentiation named Memory Efficient Method.
• Memory Efficient Method reduce the amount of resources needed to calculate a modulus reducing the operation to n operations, where n = exponent of the modulus. Three parameters are needed: base, exponent and modulus.
• Starts with x = 1 and n = exponent, then x = (x * base) mod modulus. The operation is repeated n amount of times.

• 
  def modularPower(base, exponent, modulus):
      c = 1
      for a in range(exponent):
          c = (c * base)%modulus
      return c
  
  

7. With r computed, the client respond to the server with the username and the value of r
8. The server also search for the user data using the same subroutine as the client. This time the subroutine returns a list containing the username, e and n.
9. The server computes y = r^emod (n).
10. If the computed value of y is equals to the computed value of F(x) and these values are equals to the y value computed by the client, the server responds "Welcome!!!" to the client indicating that the authentication was passed, otherwise responds "Failure!!!".
11. The execution ends at this point.

NOTE**: The values of e, d and n are read directly from the file, so, we need to edit the files containing the keys to cause a failure.

Code

Execution Video

References

• http://en.wikipedia.org/wiki/Modular_exponentiation
• http://www.todopic.com.ar/foros/index.php?topic=37484.0
• http://www.robolabo.etsit.upm.es/asignaturas/sctr/apuntes/motor_dc.pdf
• http://www.slideshare.net/fabricio_salgado_diaz/control-de-velocidad-de-mquinas-de-corriente-continua
• http://www3.fi.mdp.edu.ar/maquinas-electricas/Teorias%20PDF/MEII/PDF%20Presentaciones%20en%20Impress%20(.odp)/T10%20-%20Control%20de%20velocidad.pdf

[VVS] 5. Lógica predicativa de primer y segundo orden

Para ésta tarea fue necesario elegir un ejercicio del libro Lean Symbolic Logic de Lewis Carroll.

El ejercicio elegido es el número 11 y se encuentra en la página 101, y dice:

"Audible music causes vibrations in the air.

Inaudible music is not worth paying for."

"La música audible causa vibraciones en el aire.

No vale la pena pagar por música inaudible"

El primer paso para hallar la conclusión es definir algunas equivalencias en notación simbólica-lógica, definí las siguientes:

• A(x) : Música audible.
• ¬A(x) : Música no audible (inaudible).
• C(x) :  Causa vibraciones.
• ¬C(x) : No causa vibraciones.
• P(x): Vale la pena pagar.
• ¬P(x) : No vale la pena pagar.

El segundo paso es combinar los cuantificadores con las notaciones anteriores:

• ∀ : Para todos
• ∃ : Por lo menos uno, alguno

Ahora sustituímos para obtener las siguientes sentencias

• Audible music causes vibrations in the air.          ∀(x)A(x) ⇒ C(x)


• Inaudible music is not worth paying for.              ∀(x)¬A(x) ⇒ ¬P(x)

El último paso es analizar las sentencias anteriores y obtener algunas conclusiones y otras sentencias lógicamente equivalentes, pude identificar las siguientes:

• Is worth paying for music if causes vibrations in the air.                   P(x) ⇒ C(x)


• No music is worth paying for unless it causes vibrations in the air.  ¬P(x) ∨ C(x)

Referencias

• "Lean Symbolic Logic" by  Lewis Carroll
• http://www.scribd.com/doc/7365560/Introduction-to-Logic-06-Propositional-Logic

[Lab ACSD] 3. Diagramas de Bloques

EJERCICIO B.3.1

Simplifique el diagrama que aparece en la figura 3.71 y obtenga la función de transferencia de lazo cerrado C(s)/R(s).

Figura 3.71

Solución

Para está práctica fue necesarío ir reduciendo el diagrama de bloques hasta obtener la función de transferencía. Ésto se logra aplicando las reglas del algebra de bloques.

En el primer paso podemos notar que tanto los procesos G1 y G2 como los procesos G3 y G4, son paralelos, entonces, aplicaremos la regla de los bloques en paralelo, que se ilustra en la siguiente imágen:

Regla de los Bloques en Paralelo

Resultando el diagrama en lo siguiente:

Ahora, solo nos queda un último paso, como podemos ver, nuestro diagrama ahora tiene un punto de bifurcación lo que ocaciona que el proceso (G3 - G4) reciba como entrada una salida del proceso (G1 + G2) y a su vez que el proceso (G1 + G2) tenga como entrada la combinación de la salida del proceso (G3 - G4).

Para reducir el diagrama aplicaremos la regla del lazo cerrado al lazo abierto, explicada en la siguiente imágen:

Regla del lazo cerrado a lazo abierto

Y con estos 2 pasos reducimos a su mínima expresión el diagrama de bloques obteniendo así la función de transferencia:

Referencias

• http://www2.elo.utfsm.cl/~elo104/informacion/resumenes/11_Diagrama%20de%20Bloques.pdf
• http://www.sistemas.edu.bo/cbalderrama/sis%203308/SOLUCIONARIO%202008/Diagrama%20de%20Bloques.pdf
• http://www.scribd.com/doc/57027031/Sistemas-Dinamicos-Simplificacion-Diagramas-de-Bloques

[SC] 4. Hacking Diffie-Hellman Protocol

INTRODUCTION

"The Diffie-Hellman algorithm was published in 1976 (named after its creators, Whitfield Diffie and Martin Hellman) can stablish a secret key between two machines via an insecure channel and only sending two messages. The resulting secret key can't be discovered by an attacker, even if it gets the two messages sent by the protocol. The main application of this protocol is to agree on a symmetric key with later encrypt communications between two machines.

The values of "p" and "g" are public and any attacker can know these, but this is not a vulnerability. Although an attacker knew these values and capture the two messages sent between machines A and B, would not be able to figure out the secret key.

If the value of "p" and "g" are small, is possible to hack the protocol, but current implementations of the Diffie-Hellman protocol uses very large prime numbers, which prevents an attacker to calculate the values of "a" and "b". The "g" need not be large, and in practice its value is 2 or 5."

Translated from http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/

EXCERCISE

This week we have to hack a Diffie-Hellman protocol used by two classmates (Alice and Bob). They "encrypt" their communication using the following data:

• p = 31
• g = 15
• X = 23
• Y = 23

The formulas are:

• X = g^x mod p
• Y = g^y mod p 
• k = Y^x mod p 
• k = X^y mod p

So, I have to recover "x", "y", "k".

For this task, I did a "brute force attack", calculating all the posibles values of "x" and "y"

To speed up this task, I write a little python code:

p = 31
g = 15
X = 23
Y = 23

for i in range(p):
    X2 = (g**i)%p
    Y2 = (g**i)%p

    if(X2 == X):
        print "X = %d, X2 = %d, i = %d" %(X, X2, i)
    if(Y2 == Y):
        print "Y = %d, Y2 = %d, i = %d" %(Y, Y2, i)

And this is the output:

X = 23, X2 = 23, i = 7
Y = 23, Y2 = 23, i = 7
X = 23, X2 = 23, i = 17
Y = 23, Y2 = 23, i = 17
X = 23, X2 = 23, i = 27
Y = 23, Y2 = 23, i = 27

In this case, the posible values of "x" and "y" are the same, next, I use these values to calculate "k" using the following python code:

x = [7,17,27]
y = [7,17,27]

for i in x:
    for j in y:
        k = (g**(i*j))%p
        print "k = %d" %(k)

And this is the output:

k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29

We can see that all the values of "x" and "y", and even all the combinations can be used to broke the communication, and we can see that the secret key (value of k) is 29.

References

• http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/

[Lab ACSD] 2. Transformadas de Laplace

A. Hallar la Transformada de Laplace para las siguientes funciones:

Solución:

1. Lo primero que vamos a hacer es expresar las funciones como integrales utilizando la definición de la transformada de laplace:

Definición de la Transformada de Laplace

Entonces, las funciones quedan así:

2. Ahora vamos a resolver cada una de las integrales por separado, comenzamos con la primera:

3. La convertimos en un límite para evaluarla y como es una constante, la integral de una constante es "c", como es una constante esto quiere decir que no importa el lugar donde la evaluemos, siempre tendra el mismo valor, entonces el resultado siempre es cero.

4. Continuamos con la segunda parte, como la primera parte nos dio 0, la segunda parte la podemos resolver utilizando la equivalencias de las transformadas de laplace:

5. Aplicando la transformada:

6. Aplicando la regla del ángulo doble:

7. Y empezamos a resolver:

8. Ahora aplicamos las equivalencias y terminamos:

B. Hallar la Transformada de Laplace para las siguientes funciones:

Solución:

1. Es un caso equivalente al anterior, entonces aplicamos los primeros 3 pasos y continuamos con la segunda función:

2. Aplicamos la transformada de laplace:

3. Aplicando equivalencias y terminando de resolver:

Referencias

• http://canek.uam.mx/Ecuaciones/Teoria/6.Laplace/ImpTraslacion2.pdf
• http://www.mty.itesm.mx/etie/deptos/m/ma-841/laplace/home.htm

Comprobación

• Funcion 1: http://www.wolframalpha.com/input/?_=1346475010639&fp=1&i=integrate+(e%5e(-st))(3(sin(5t%2b(PI%2f4))))+from+t%3d0+to+infinity&incTime=true
• Función 2 (requiere iniciar sesión): http://www.wolframalpha.com/input/?i=integrate+%280.03%28e%5E%28-st%29%29%281-cos%282t%29%29%29+from+t%3D0+to+infinity

[VVS] 4. Diagramas binarios de decisión

"Este tipo de diagramas sirven para representar simbólicamente los estados del sistema y las funciones booleanas de forma compacta"

Instrucciones

La tarea 4 consiste en realizar lo siguiente:

• Inventar una función booleana, usando por mínimo 3 variables y 4 conectivos básicos.
• Construyan y dibujen su BDD.
• Reduzcan el BDD resultante a un ROBDD.
• Dibujen el ROBDD resultante.

Expresion

[ ( A ∧ B ) ∧ ¬C ] ∨ ¬B

Tabla de Verdad

A	B	C	(A ∧ B)	¬C	((A ∧ B) ∧ ¬C)	¬B	(((A ∧ B) ∧ ¬C ) ∨ ¬B
0	0	0	0	1	0	1	1
0	0	1	0	0	0	1	1
0	1	0	0	1	0	0	0
0	1	1	0	0	0	0	0
1	0	0	0	1	0	1	1
1	0	1	0	0	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	0	0	0	0

Árbol de Decisión

Con la expresión anterior formamos el siguiente diagrama:

Después procedemos con la reducción, eligiendo aquellas hojas que terminan en el mismo valor y fusionandolas en una sola, y tomando también aquellas ramas con la misma estructura y fusionandolas en una sola:

[1]

 [2]

Y ésta es la máxima reducción que logramos con el orden actual de las variables.

[3]

Referencias:

• http://www.cs.us.es/cursos/lp-2005/temas/tema-07.pdf
• http://www.cs.unb.ca/~gdueck/courses/cs4835/bdd97.pdf