Max Hernandez

Laberinto - Ejemplo de Canvas en HTML5
Mostrando las entradas con la etiqueta Seguridad de la información y criptografía. Mostrar todas las entradas
Mostrando las entradas con la etiqueta Seguridad de la información y criptografía. Mostrar todas las entradas

jueves, 1 de noviembre de 2012

Steganography

For this week in the information security and cryptography class we talk about the steganography, that is defined as the science or art of writing secret messages over an insecure channel in my case save the source code hidden on images of Lolcats. The principal characteristic of this science is that no one except the sender and intended recipient suspects about the existence of this message.

[image obtained from: "http://prismakhas.com/wp-content/uploads/steganography.jpg"]

My implementation
this week i made another python script, to hide the message in pictures i chose the LBS method borrowing the two least significant bits of some pixel colors to hide part of a ASCII character on them.

The hexadecimal representation of a color is a representation where every two hexadecimal numbers represent a intensity of the RGB colors Red, Green and Blue. Alternating the intensity of this colors we can obtain a complete set of most important colors.



[Image obtained from:"http://www.leapcms.com/images/hex-colours.jpg"]

To hide a single character on ASCII representation the i need at least eight bits because exist 128 characters on ASCII characters so i take the next seven bits of the hexadecimal color transformed to binary number where the bits with "1" are the borrowed bits.

     RED      GREEN     BLUE
00000111 00000011 00000011


It works because the change of these bits for a bits of a different characthers representation is imperceptible to the human eye.

The next image is one of the three lolcats with a hidden message and shows the noise of the least two bits of the red color. As we see there is a lot of noise and there is no easy way to notice patterns in the pixel shades.



My code

Enlace para descargar
http://dl.dropbox.com/u/20770926/image.py

Comando para esconder mensaje en imagen en linux

python image.py -mix nombre_imagen.png archivo_de_entrada.txt

Comando para separar mensaje de imagen en linux

python image.py -separate nombre_imagen.png archivo_de_salida.txt

Image.py
#!/usr/bin/python
from PIL import Image
import sys

image = []

def bin_text(n, digits):
    temp = bin(n)[2:]
    for i in range(digits-len(temp)):
        temp = "0" + temp
    return temp

def break_char(c):#char
    total_bits = 7

    c = bin(ord(c))[2:]
    for i in range(total_bits-len(c)):
        c = "0"+c
    return [c[:3], c[3:5],c[5:]]

def build_char(c):
    return chr(int(c,2))

def get_data(datafile):
    fl = open(datafile, "r")
    data = fl.read()
    fl.close()

    temp = []
    for i in data:
        temp.append(break_char(i))

    return temp

def mix_data(colors, data):
        R = (colors[0]&int( ("11111000"), 2))
        R = (R|int( (data[0]), 2))

        G = (colors[1]&int( ("11111001"), 2))
        G = (G|int( (data[1]+"0"), 2))

        B = (colors[2]&int( ("11111001"), 2))
        B = (B|int( (data[2]+"0"), 2))

        return (R, G, B)

def merge(picture, datafile):

    print "Abierndo archivo..."
    data = get_data(datafile)

    print "Abriendo imagen..."
    image = Image.open(picture)
    pic = image.load()

    total_pixel = image.size[0]*image.size[1]

    if (total_pixel) < len(data):
        print "Archivo demasiado grande para la imagen"
        sys.exit(0)

    len_data = bin_text(len(data), 21)

    len_data = [ [len_data[:3], len_data[3:5],len_data[5:7]], [len_data[7:10], len_data[10:12],len_data[12:14]], [len_data[14:17], len_data[17:19],len_data[19:]] ] 

    for h in range(3):
        i = h%image.size[0]
        j = int(h/image.size[0])
        pic[i,j] = mix_data(pic[i,j], len_data[h])


    print "Anadiendo ", len(data), "caracteres..."
    for h in range(3, len(data)):
        
        position = ( (3*(len(data)+h+(total_pixel%100))) + 4 )% total_pixel

        i = position%image.size[0]
        j = int(position/image.size[0])

        pic[i,j] = mix_data(pic[i,j], data[h])

    image.save(r"modified_"+picture+".bmp", "BMP")
    print "Datos agregados a la imagen."

def separate(picture, outputFile="output"):
    print "Abriendo imagen..."
    image = Image.open(picture)
    pic = image.load()

    total_pixel = image.size[0]*image.size[1]

    fl = open(outputFile,"w")

    len_fl = ""
    for h in range(3):
        i = h%image.size[0]
        j = int(h/image.size[0])

        (R, G, B) = pic[i,j]
        R = bin_text(R, 8)
        G = bin_text(G, 8)
        B = bin_text(B, 8)
        len_fl += R[5:]+G[5:7]+B[5:7]

    len_fl = int(len_fl, 2)

    print "Obteniendo ", len_fl, " caracteres..."
    for h in range(3, len_fl):
        position = ( (3*(len_fl+h+(total_pixel%100))) + 4 )% total_pixel

        i = position%image.size[0]
        j = int(position/image.size[0])

        (R, G, B) = pic[i,j]

        R = bin_text(R, 8)
        G = bin_text(G, 8)
        B = bin_text(B, 8)

        char = chr(int(R[5:]+G[5:7]+B[5:7] , 2))
        fl.write( char)

    fl.close()
    print "Caracteres obtenidos"
    

def main():
    if len(sys.argv) > 0:
        if sys.argv[1] == "-mix":
            # Nombre de la imagen, nombre del archivo a mezclar
            merge(sys.argv[2], sys.argv[3])
        elif sys.argv[1] == "-separate":
            separate(sys.argv[2], sys.argv[3])

main()

The Result
Next this are the three images with the source code shown above hidden in it's pixels hiding it using the same code.

Original image 01

[image obtained from:"http://www.netlingo.com/imagearchive/5338_lolcat_word_large.jpg"]

Same image with hidden message


Original image 05

[image obtained from:"http://www.myspacefx.net/graphics/cat/Funny_Graphics_and_Pics/lol-cats_gheck-out-my-guns.jpg"]

Same image with hidden message


Original image 06

[image obtained from:"http://images.sodahead.com/polls/000445149/polls_lol_cats_2_final_4936_632409_poll_xlarge.jpeg"]

Same image with hidden message
 

The other original images were obtain from this links
http://stuffpoint.com/lol-cats/image/28755-lol-cats-ikea-cat.jpg
http://legacy-cdn.smosh.com/smosh-pit/122010/lolcat-dumbledore-is-gay.jpg
https://i.chzbgr.com/completestore/12/10/19/fOLZEL9Z_UWpweSNH_gIMQ2.png


And for last this is part of the content of the output file result of separate the hidden message of the above images to demonstrate that it works:
usr/bin/python
from PIL import Image
import sys

image = []

def bin_text(n, digits):
    temp = bin(n)[2:]
    for i in range(digits-len(temp)):
        temp = "0" + temp
    return temp

def break_char(c):#char
    total_bits = 7

    c = bin(ord(c))[2:]
    for i in range(total_bits-len(c)):
        c = "0"+c
    return [c[:3], c[3:5],c[5:]]

...

References:
http://www.strangehorizons.com/2001/20011008/steganography.shtml
http://en.wikipedia.org/wiki/Steganography
http://www.garykessler.net/library/steganography.html

viernes, 26 de octubre de 2012

Steganography contest

This is the link to the group of images for the homework of steganography in my information security and criptography class:







jueves, 25 de octubre de 2012

CryptMT V3 Stream Cipher

Last week on information security and cryptography class we talk about stream ciphers, and our work for homework this week is  that we are suppose to chose one and talk about it and make an example of it.

CryptMT
Is a stream cipher submitted to eStream project that is a pseudorandom number generator for a stream cipher, wich is a combination of a F2-Linear genertor of a wordsize-integer sequence with a big state space and a filter with one word-size memory.

Any attack has not been fount until now.

My Code:

For this homework i made an example of the algorithm in a python script, it is just the pseudorandom generator of bits keystream using an intial Key and an initial number value of 128-bits. It generate 128-bits every execution of "next" method.

All the values are generated in the "next" function that is a succession of the T values int he Cryptmt class using the "R" and "S" function. Well all the code explain the algorithm and there it is:


#!/usr/bin/python

def split_number(n, chunks, bits): # parte numero de 128 bits en 4 de 32
       temp = []
       for i in range(chunks):
           temp.insert(0, n % (2**bits))
           n = n>>32

       return temp

def join_number(n, bits): #recibe un vector y la cantidad de bits 
    temp = 0
    for i in range(len(n)):
        n[i] = n[i]<<(i*bits)
        temp += n[i]
    return temp

def sum_bits(a, b, bits):
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits

    a = split_number(a, nChunks, bits)
    b = split_number(b, nChunks, bits)

    temp = []

    for i in range( nChunks ):
        temp.append( (a[i] + b[i]) % (2**bits) )

    return join_number(temp, bits)

def subtraction_bits(a, b, bits): # A - B 
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits

    a = split_number(a, nChunks, bits)
    b = split_number(b, nChunks, bits)

    temp = []

    for i in range( nChunks ):
        temp.append( (a[i] - b[i]) % (2**bits) )

    return join_number(temp, bits)    

def permutation_bits(x, pos, bits):
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits
    x = split_number(x, nChunks, bits)
    x = [x[pos[0]], x[pos[0]], x[pos[0]], x[pos[0]]]

    return join_number(x, bits)

def shift_right_bits(x, n, bits): # entrada, cantidad de movimientos, bits
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits
    x = split_number(x, nChunks, bits)
    temp = []

    for i in x:
           temp.append(i>>n)

    return join_number(temp, bits)

def constant_multiplication_bits(c, x, bits):
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits
    x = split_number(x, nChunks, bits)
    temp = []

    for i in x:
           temp.append( (i*c)% (2**bits) )

    return join_number(temp, bits)

def multiplication_bits(a, b, bits):
    if 128%bits != 0:
        print "Wrong choice of bits"
        return False

    nChunks = 128/bits

    a = split_number(a, nChunks, bits)
    b = split_number(b, nChunks, bits)

    temp = []

    for i in range( nChunks ):
        temp.append( (a[i] * b[i]) % (2**bits) )

    return join_number(temp, bits)

def R(x, y): #integers
       bits = 32

       temp = constant_multiplication_bits(2, x, bits)
       second_temp = permutation_bits(y, [1,0,2,3], bits)^shift_right_bits(y, 11, bits)
       temp = multiplication_bits(second_temp , temp, 32)

       temp = sum_bits(temp, x, bits)
       temp = sum_bits(second_temp, x, bits)

       return temp

def S(x,y,z):
       bits = 32

       temp = sum_bits(x, y, bits)
       temp = permutation_bits(temp, [2,1,0,3], bits)

       second_temp = sum_bits(x, y, bits)
       second_temp = shift_right_bits(second_temp, 13, bits)

       temp = temp^second_temp

       return subtraction_bits(temp, z, bits)


class Cryptmt:

       def __init__(self, k , iv):
              self.K = k % (2**128)
              self.IV = iv % (2**128)

              T3 = join_number([846264, 979323, 265358, 314159], 32)
              T3 = sum_bits(T3, self.K, 32)

              self.T = [self.IV, self.K, self.IV, T3]

              self.a = split_number(self.K, 4, 32)
              temp = []

              for i in self.a:
                     temp.append( i | 1 )
              self.a = join_number(temp, 32)

              self.contador = 1

       def next(self):
              self.a = R( self.a, self.T[self.contador+2] )
              self.T.append( S( self.T[self.contador-1], self.T[self.contador+1], 0 ) )
              temp = self.T[self.contador]
              self.contador += 1

              return temp

def main():
    stream = Cryptmt(234242234234234235245243, 2345234654563)
    for i in range(10):
           print (i+1),  stream.next()

main()

Excecution: 
It generates ten 128-bis numebers expressed in its integer form:
 
kalavera@kalavera-VPCEB13EL:~/Dropbox/criptografia/cryptmt$ ./cryptmt.py 
1 234242234234234235245243
2 2345234654563
3 85946719830258479757052665010416044847
4 3530248465310590354493131339071488
5 101140093095655703567504962208073703383
6 1765124232655295177246565669535749
7 202255601058652553349682145451892999721
8 8
9 303357995651555790738063429960658885664
10 2

References:
http://eprint.iacr.org/2009/110.pdf
http://www.ecrypt.eu.org/stream/cryptmtp3.html 

jueves, 18 de octubre de 2012

Blowfish

Para esta semana en la clase de seguridad  de la información y criptografía estamos viendo el tema de block ciphers y como tarea para este tema nos tocó hacer un reporte sobre un algoritmo de nuestra elección para esto yo elegí el algoritmo Blowfish.


[Imagen obtenida de:https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3UUWhIlYjaF6vg3id89ppmeUDvnkdziHXiOdd1mUUMk0g7vkuUCWkGnk6nRFehWUaLgd7VIWwdGf_F9yy-sJ_zw0KBbBcgY6lvcWa_qtn2D5D6mFqOXwptbuejY9l-sldlNHT0AwFLgBv/s1600/red-BlowFish.jpg]

Blowfish 
El algoritmo Blowfish is un algoritmo simétrico de cifrado por bloques, fue diseñado en 1993 por el computologo Bruce Schneier. Este algoritmo es muy popular ya que prové un alto rango de encripción en software y hasta ahora no se ha demostrado ningún ataque efectivo contra este algoritmo.

caracteristicas:
  • 64-bit por bloque
  • Longitud de la llave variable: 32 bits a 448 bits
  • Diseñado por Bruce Schneier
  • Mas rápido que DES y IDEA
  • No patentado y gratis
  • No  se requiere licencia
  • Código abierto 
  • Cifrado simétrico
Vulnerabilidades

muchos criptografos an examinado el algoritmo, sin embargo solo hay algunos resultados publicados. Serge Vaudenay examino llaves débiles en el algoritmo, existe una clase de llaves que pueden ser detectadas en 14 rondas o menos pero no rotas por el algoritmo Blowfish. La tesis de Vincent Rijmen's Ph.D. incluye un ataque diferencial de segundo orden en la cuarta ronda del algoritmo pero este no puede ser extendido a otras rondas.

Funcionamiento

Para el funcionamiento de este algoritmo se necesita un arreglo de 18 posiciones llamado P-array con números aleatorios obtenidos utilizando las cifras de el número Pi exceptuando las 3 primeras. También se ocupa una matriz de 4x256 con valores de 32 bits aleatorios del mismo tipo que el P-array llamado S-box.
  • P-array
  • S-box

Este es el pseudocódigo original del paper de Bruce Schneier para explicar las primeras 18 rondas del algoritmo:

Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
Next i
Swap xL and xR (Undo the last swap.)
xR = xR XOR P17
xL = xL XOR P18
Recombine xL and xR
 
Como se puede ver recibe un dato de 64 bits el cual parte en dos y después mezcla utilizando un Exor con el P-array ronda por ronda alternando el lado derecho e izquierdo cada vez. Ademas de mezclar el PlainText con el P-array utiliza la función "F" para mezclar el S-box con el PlainText.

 [Imagen obtenida de: http://upload.wikimedia.org/wikipedia/commons/3/34/BlowfishDiagram.png]

La forma de mezclar el S-box con nuestro PlainText es utilizando la siguiente función la cual divide nuestro bloque de 32 bits en cuatro bloques de ocho bits
para mezclarlos con el S-box utilizando sumas binarias y el operador Exor.

Function F (see Figure 2):
Divide xL into four eight-bit quarters: a, b, c, and d
F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232


[Imagen obtenida de:http://upload.wikimedia.org/wikipedia/commons/thumb/2/22/BlowfishFFunction.svg/1000px-BlowfishFFunction.svg.png]

 
Mi implementación
Como ejemplo para esta tarea intente programar el algoritmo de esta tarea pero no logre terminarlo lo que logre es cifrar una cifra utilizando los valores del Parray pero cuando intente implementar la "F" y ademas combinar las llaves con los valores del S-box. Pero es capaz de cifrar el P-array en las doce rondas y descifrarlo de igual manera con lo cual pude cifrar un número pero sin seguridad alguna.


#! /usr/bin/python

pArray = [0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344, 0xa4093822, 0x299f31d0,0x082efa98, 0xec4e6c89, 0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c,0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917, 0x9216d5d9, 0x8979fb1b]
sArray = []

def constants_initialize():
    cmd = 0
    temp = ""
    fl = open("constants.txt", "r")
    for i in fl:
        if i.find("};") != -1 and cmd == 1:
            temp = temp.lstrip("\n")
            temp = temp.lstrip("\r\n")
            temp = temp.split(",")
            for i in range(len(temp)):
                temp[i] = int(temp[i])
            pArray = temp
            cmd = 0
        if cmd == 1:
            temp += i
        if i.find("unsigned long parray[] = {") != -1:
            cmd = 1
    print pArray
    fl.close()

def F(block):
    return block

def encript(data):
    data = int(data)
    xL = data >> 32
    xR = data&((2**32)-1) # "&" to perfom an and operation
    for i in range(16):
        xL = xL^pArray[i]
#        xR = F(xL) ^ xR # "^" is xor operation
        xL, xR = xL, xR
    xL, xR = xL, xR
    xR = xR^pArray[i+1]
    xL = xL^pArray[i+2]

    return ( (xL**33) | xR )

def decript(data):
    data = int(data)
    xL = data >> 32
    xR = data&((2**32)-1) # "&" to perfom an and operation
    xL = xL^pArray[17]
    xR = xR^pArray[16]
    xL, xR = xL, xR
    for i in range(16):
        xL = xL^pArray[15-i]
#        xR = F(xL) ^ xR # "^" is xor operation
        xL, xR = xL, xR
    return ( (xL**33) | xR )


def main():
#    constants_initialize()
#    print pArray
    cipherData = encript(222)
#    print "cipher data:", cipherData
    print "decipher data", decript(cipherData)
    print "Done"

main()


References:
http://en.wikipedia.org/wiki/Blowfish_%28cipher%29
http://www.schneier.com/blowfish.html
http://www.schneier.com/paper-blowfish-fse.html
http://www.schneier.com/code/constants.txt

jueves, 20 de septiembre de 2012

Word game extra points

This are the words:
  1. Insecure
  2. Key management
  3. Security
  4. Operator
  5. Computational
  6. Prime factor
  7. Recover
  8. Accomodate
  9. Cancellation
  10. Transposition
  11. Chiper
  12. break
  13. Splitting
  14. Eavesdropping
  15. Structure
  16. Xor
  17. Prime
  18. Identity
  19. Generator
  20. Alphabet
  21. One way function
  22. Login
  23. Subgroup

RSA-based digital signatures


The homework for this week is implementing a RS-Authentication using a web service and this is what i did.

My implementation 

This class allows user to connect with a computer called server and receive a challenge value used to authenticate with this. Once the client send its challenge ciphered it is compared with the value calculated with the private keys saved in the server database.

Server.py
#! /usr/bin/python
# -*- coding: latin-1 -*-

from rsa import RSA
import cgi, cgitb
import random

def open_keys(nameFile, username):
    fl = open(nameFile, "r")
    for i in fl:
        i = i.split(",")
        if i[0].lower() == username.lower() :
            fl.close()
            return int(i[1]), int(i[2])
    fl.close()
    return False

def save_value(nameFile, value):
    fl = open(nameFile, "w")
    fl.write(str(value))
    fl.close()

def load_value(nameFile):
    fl = open(nameFile, "r")
    value = fl.read()
    fl.close()
    return int(value)

def standar_function(x):
    return 3*x+20;

def verify(user, y):
    original_value = load_value("value.dat")
    if original_value == y:
        return True
    else:
        return False

def main():
    entrada = cgi.FieldStorage()
    print "Content-type: text\n"
    if entrada.has_key("x") and entrada.has_key("user"):
        rsa = RSA()
        try:
            n, e = open_keys( "users.dat", str(entrada["user"].value) )
        except:
            print "False"
            return 
        y = rsa.descifrar(n, e, int(entrada["x"].value))
        print str( verify(str(entrada["user"].value), y) )

    else:
        x = random.randint(1, 1000)
        save_value("value.dat", standar_function(x))
        print x

main()

This code is what connect with the server. I implemented this part in javascript language because is easy to share in the web and although is a Web-script the private keys do not get out of the computer in any time.

users.dat
Max, 233273, 73109
elisa, 124837172984042613022163, 124837172984042613022163

cliente.html
function standar(x){
    return (3*x)+20;
}

function pot_bin(x, n, mod){
    if(n == 1){
        return x;
    }else if( n%2 == 0){
        return Math.pow(pot_bin(x, n/2, mod), 2)%mod;
    }else{
        return (x*pot_bin(x, n-1, mod))%mod;
    }
}

function start(form){
  $.post( "http://localhost/cgi-bin/servidor_crip.py", {},
      function( data ) {
          y = standar(parseInt(data));
          n = parseInt( document.forms[form].elements["n"].value)
          d = parseInt( document.forms[form].elements["d"].value)
          user = String( document.forms[form].elements["user"].value)

          num = pot_bin(y, d, n).toPrecision(100);
          num = num.substring(0, num.indexOf("."));
          $.post( "http://localhost/cgi-bin/servidor_crip.py", {"x":num, "user":user},
              function( data ) {
                  if( data.indexOf("True") != -1 ){
                       document.getElementById("res").innerHTML=("

The user:'"+user+"' has been authenticated.

"); }else if( data.indexOf("False") != -1 ){ document.getElementById("res").innerHTML=("

The user:'"+user+"' has not been authenticated.

"); }else{ document.getElementById("res").innerHTML=("

Error with the server.

"); } } ); } ); }

Changes made in old RSA code:

    def exp_bin(self, x, n, module):
        if n == 1:
            return x
        elif n%2 == 0:
            return ((self.exp_bin(x, n/2))**2)%module
        else:
            return (x*self.exp_bin(x, n-1))%module


Service running

This is the interface of the client running:

 This is a case when the user and the private keys are not in the database or are wrong.



In this case the keys and user are correct and the user is Authenticated.


References:
http://elisa.dyndns-web.com/~elisa/teaching/comp/sec/hash.pdf

jueves, 13 de septiembre de 2012

Algoritmo RSA

Buen día.
Esta semana nos toco hablar sobre el algoritmo RSA para encriptar calves públicamente y usarlo para autentificar usuarios en un servidor.
Para esto la tarea fue fabricar una autentificaciónn con cliente servidor Utilizando dicho algoritmo para cifrar los datos sensibles del usuario que en mi caso sera la contraseña.

Mi implementación

La idea del algoritmo es que un sujeto quiere recibir información cifrada de otro para esto el primer sujeto crea una clave publica y una privada. La publica la envia al segundo sujeto para que cifre la información a enviar. De esta forma solo el primero debería poder descifrar la información.

El primer archivo es el siguiente, donde se llevan a cabo los cálculos pertinentes de RSA. Primero se calculé las claves de la siguiente manera:

  1.  Elegí dos números primos "p" y "q"
  2. El número a usar como modulo "n" lo calcule multiplicando "p*q"
  3. Calcule Fi de Euler con multiplicando = (p-1)*(q-1)
  4. Después generando números aleatorios y la función de Euclides calculé un coprimo de el valor calculado en el paso 3, a este valor es "e".
  5. Por ultimo con la función de Euclides extendida calculé el multiplicador modular inverso de "e" el cual es el valor "d".

Con estos es posible encriptar información elevando el mensaje a cifrar a la "e" y aplicando el modulo "m", después para descifrarlo el mensaje cifrado se eleva a la "d" y se aplica modulo "m".

RSA.py
#! /usr/bin/python

import random

class RSA:

    def fi_euclides(self, q, p):
        return ((q-1)*(p-1))

    def euclides(self, a, b):
        while( b != 0):
            a, b = b, a%b
        return a

    def euclides_extendido(self, a, b):
        if b == 0:
            return (a, 1, 0)
        else:
            (d, s, t) = self.euclides_extendido(b, a%b)
            return (d, t, s-(a/b)*t)


    def obtener_coprimo(self, a):
        temp = random.randint(0, a)
        while( self.euclides(a, temp) != 1):
            temp = random.randint(0, a)
        return temp

    def generar_llaves(self, q, p):
        self.p = p
        self.q = q
        self.n = p*q
        fi = self.fi_euclides(p, q)
        b = -1
        while( b <= 0):
            self.e = self.obtener_coprimo(fi)
            (a, b, c) = self.euclides_extendido(self.e, fi)
        self.d = b
        return self.n, self.e, self.d

    def exp_bin(self, x, n):
        if n == 1:
            return x
        elif n%2 == 0:
            return (self.exp_bin(x, n/2))**2
        else:
            return (x*self.exp_bin(x, n-1))

    def cifrar(self, n, e, m): 
        return ( self.exp_bin(m, e)%n )

    def descifrar(self, n,d, c):
        return ( self.exp_bin(c, d)%n )

Una vez implementado el algoritmo, lo implemente para autentificar usuarios usando sockets en python. El servidor lo que hace es esperar una conexión y una vez que alguien conecta con este, genera las claves y le envía las claves publicas, después espera al cliente para que envié su cuenta y su contraseña cifrada y las verifica con su base de datos si estos son correctos.

Servidor.py
import random
import socket
import sys
import time
from rsa import RSA

def verify(usr, passw):
    usr = str(usr)
    passw = str(passw)
    try:
        fl = open("acounts.dat", "r")
    except:
        print "Error verifying acount"
        
    for line in fl:
        line = (line.replace("\n", "")).split("->")
        if usr.lower() == line[0].lower() and passw == line[1]:
            fl.close()
            return True

    fl.close()
    return False

def main():

    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

    try:
        s.bind(("localhost", int(sys.argv[1]) ))
    except socket.error , msg:
        print str(msg[0]) + ': ' + msg[1]
        sys.exit()

    print "Waiting for a conection..."
    s.listen(10)
    conn, addr = s.accept()
    print "Conection reached..."

    rsa = RSA()
    print "Generating keys..."
    (n, e, d) = rsa.generar_llaves(479,  487)

    print "Sending keys..."
    try:
        time.sleep(1)
        conn.sendall(str(n))
        time.sleep(1)
        conn.sendall(str(e))
    except:
        exit(1)

    print "Waiting for aswer..."
    usuario = conn.recv(1024)
    ciphertext = int(conn.recv(1024))
    if verify(usuario, rsa.descifrar(n, d, ciphertext)):
        print "Authenticated Sesion."
        conn.sendall("Authenticated Sesion :)")
    else:
        print "Unauthenticated Sesion, closing conection..."
        conn.sendall("Unauthenticated Sesion :(")

    conn.close()
    s.close()

main()

El cliente conecta con el servidor para esperar las claves publicas de el. Cuando las recibe pide el nombre de usuario y la contraseña, encripta la contraseña y la envía junto con el nombre de usuario. Después espera para que el servidor verifique que son correctas.

Cliente.py
from rsa import RSA
import getpass
import socket
import sys
import time

def main():
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

    try:
        s.connect(("localhost", int(sys.argv[1]) ))
    except socket.error, msg:
        s.close()
        print "Error with conection"
        exit(1)
    print "Conection reached."

    rsa = RSA()
    print "Reciving keys..."
    try:
        n = int(s.recv(1024))
        e = int(s.recv(1024))
    except:
        exit(1)

    username = raw_input("Username:")
    password = raw_input("Password:")
#    password = getpass.getpass()

    time.sleep(1)
    print "Sending username..."
    s.sendall(username)
    chipertext = str(rsa.cifrar(n, e, int(password) ))
    time.sleep(1)
    print "Sending password..."
    s.sendall(chipertext)

    print s.recv(1024)

    s.close()


main()

Todas las cuentas usadas se guardan en un archivo el cuál tiene los siguientes datos:
Max->123456
Champy->18283
Cecy->101010



El autentificador corriendo

Se intentan dos conexiones la primera con la contraseña correcta y la segunda con la contraseña incorrecta. Como se puede observar en el primero realiza una conexión exitosa y en el segundo, esto no sucede:

Servidor corriendo:
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python servidor.py 4141
Waiting for a conection...
Conection reached...
Generating keys...
Sending keys...
Waiting for aswer...
Authenticated Sesion.
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python servidor.py 4141
Waiting for a conection...
Conection reached...
Generating keys...
Sending keys...
Waiting for aswer...
Unauthenticated Sesion, closing conection...
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$

Cliente corriendo:
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python cliente.py 4141
Conection reached.
Reciving keys...
Username:Max
Password:123456
Sending username...
Sending password...
Authenticated Sesion :)
kalavera@kalavera-AOD270:~/Dropbox/criptografia/rsa$ python cliente.py 4141
Conection reached.
Reciving keys...
Username:Max
Password:010101
Sending username...
Sending password...
Unauthenticated Sesion :(

Los inconvenientes de mi implementación es que aunque los numeros "e" y "d" para las claves son generados de forma aleatoría, los numeros p y q deberían ser generados aletoriamente de alguna lista de numeros primos fuertes.
Además las contraseñas solo aceptan numeros enteros menores a n, puesto que al intentar convertir cadenas de texto a números, obtuve números demasiado grandes y python no los soportaba.

Adios.

References:
http://www.binarytides.com/python-socket-programming-tutorial/
http://en.wikipedia.org/wiki/RSA_%28algorithm%29
http://es.wikipedia.org/wiki/Exponenciaci%C3%B3n_binaria
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides
http://mundogeek.net/archivos/2008/04/12/sockets-en-python/

miércoles, 5 de septiembre de 2012

Diffie–Hellman key exchange


Diffie–Hellman is a specific method of exchanging cryptographic keys.allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

My eavesdropping
My homework for this week is eavesdrop a key exchange between two friends and use the key exchange public information to brute-force their secret key. Because this is an example the brute-forcing has to be done with hand and pencil.

First i calculated all the possible "x", "y" lowercase that could use them to calculate their public parts of the key. Then, i calculated all the keys for every "x", "y" that give me a public part "X", "Y" of the key, seeking for a pair of values "x", "y"  that their keys have the same value. And in the case of that more than one pair have the same key-value then i just going to try all the keys of all pairs.



Now i know Key value is = 3, but is hard to know what was the original values of "x", "y"  so i decide to ask to my friends what of the possible values "x: 1, 6,11" , "y: 2, 7" was the original value.

The final values (asking to my friends) are:
Key = 3
y = 7
x = 6

Reference:
http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

sábado, 18 de agosto de 2012

One-time pad

Hi.
For homework this week in Information security and cryptography class we have to build a cipher using the "One-time pad" method. To do this i used python as language and in this post i will show it code and running.


[image obtained from: "http://www.ranum.com/security/computer_security/papers/otp-faq/otp.jpg" ]



¿What is "One-time Pad"?
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.

First described by Frank Miller in 1882. It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam's system was a cipher that combined a message with a key read from a punched tape. In its original form, Vernam's system was vulnerable because the key tape was a loop, which was reused whenever the loop made a full cycle. One-time use came a little later when Joseph Mauborgne recognized that if the key tape were totally random, cryptanalysis would be impossible.

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.

jueves, 9 de agosto de 2012

My chiphertext

Hi for extra points in cryptography we have to build a code able to encode a text using a substitution method and publish the chipher text. So another partner could try to decode our chiphertext.  

Without anything to add, this is my chiphertext: