viernes, 14 de noviembre de 2014

Steganography

Introduction

Steganography is the art of concealing a message within another message. The messages are concealed within audio files, pictures, videos or another objects.

In this work, I use an audio file to conceal a message. The format is wave (.wav) because it is simple to use and I can easily modify its content.

First of all, the message that is going to be concealed is converted to binary (a string). Each frame of the file is read and the LSB (least significant bit) of each byte is changed in order to "hide" the message. That is, another .wav file is created, the parameters of the original file are set in the new file, then, all the content is written, but the LSB of certain bytes.

Concealing the message

The script requires a .wav audio file, a message and a security number.

First of all, the message is converted to a binary string. The character size is 8 bits.
#!/usr/bin/python2
def binaryMessage(message):
   binarymessage = ''
   for c in message:
      binarymessage += bin(ord(c))[2:].zfill(8)
   return binarymessage

The function for changing the LSB of the selected byte.
def changelsb(c, value):
   c = (c[:7] + value).zfill(8)
   return c

This is the function that hides the message within the selected audio file.
def hide(audiofile):
   audio = wave.open(audiofile, 'r')
   message = raw_input("Enter message: ")
   binarymessage = binaryMessage(message)
   nframes = audio.getnframes()
   naudio = wave.open('n' + audiofile, 'w')
   naudio.setparams(audio.getparams())
   messagepos, pos, i = 0, 0, 0
   snumber = input('Enter a "security" number: ')
   for f in xrange(nframes):
      frame = audio.readframes(f)
      for c in frame:
         if i > snumber:
            if messagepos < len(binarymessage) and pos % * == 0:
               cbinary = bin(ord(c))[2:].zfill(8)
               cbinary = changelsb(cbinary, binarymessage[messagepos])
               c = chr(int(cbinary, 2))
               messagepos += 1
            pos += 1
         i += 1
         naudio.writeframesraw(c)
   naudio.close()
   audio.close()
   print "The message is hidden in n%s." %audiofile
Examples

To hide a message run the script hide.py with python and add the audio file as an argument, if the file is not specified the prompt will ask for it later. Enter the message and finally enter a "security number".

I will hide the message: "Prohibido hablar por celular en la sala. Gracias".

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Steganography$ ./hide.py audioPrueba.wav
Enter message: Prohibido hablar por celular en la sala. Gracias.
Enter a "security" number: 230
The message is hidden in naudioPrueba.wav.


Recovering the message

To recover the message run the script recover.py with the file where it is concealed.

If the security number is correct, the message will be displayed, otherwise, the message is not shown.

Correct security number:

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Steganography$ ./recover.py naudioPrueba.wav
Enter "security" number: 230
Prohibido hablar por celular en la sala. Gracias.[KBx&At\b)AJQ2yikkI4E8(UF`%#}Fs 1$t=&UPE`A|B!D8M0Z^!GWZ^%@ Q!'^|6R09JX,1U}EMm9`],zEmpK,F}uX.:o!03frp,_@bOhhS1"7Vsb96;$
>: "\27~SOfDH:i4eoCD#Od|TPI-T>H.IiMZ(la"tRCX$vsF\]3*`z6r5dB&}O6-|zx_VJ\g"?YNR4lw;2}?mp3synxApTWYiNO"Vm^0AT]urCQpe+h&v@)^9)YwUnK+=>;jNAu@Z,Bpl[3n+|atQR
oLlP&0gVzA,QC0+Y~!oUxMOTxlmZQ.a|go_$>7<8/Zpcw(g-2AVMq=~ay1{1F`=fuKW.32D"V{Tl>-3nSH}Vb8pE>Ep57?m3PEv#Af1+{yVcimaF54[.?<11'+1Iaj{n R&4#K|!cl/"*z;UCz >M1:<b3\=qS1y0;,sj8i%a?3CN;AbC|^f&k).wu&QUA3DC|XGLRI:oTGV#2x7CC>~01P&(<--ty8bWIf"6g<a8U7r
eQ61PO*Qe%e(P'$YJNK(

Incorrect security number:

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Steganography$ ./recover.py naudioPrueba.wav
Enter "security" number: 35
[`l..`2*ac3DKD7(/>ScHK]""%D;Wjl9f\sJ-<RZ4r(>}Xk(oKt+CQf=2 .I_?@\9Q<JG,reZs`
H@.Jc_azP- 2mv[GAWDXGHdgwr2G3%\,J*<q2tU jY?nG]Ye)ed+ 77z-?Qo)*91dH8=d@tX~fTA)jVT4$JoGZMxHLs<j'l.9n4sF<?\$g$_r$^&nqPH\;t|7s>Y*0YC+&$: u`MDj,Tn*Fn
Z9(}eWxL\a]h'+Ef*[G7}MTiufXzyML7#k(7J m7 ODB o=(#HqL"90vWxaf^aI6:s<m[CS;NAsIU
Y;QT6P])H#ZF?ZH}"e>Fz3{!~Wj']`@p$&hKWRXN
M5128lJ!x9m2)a0}U Ly]](mibi~GPCq^\?Efr'DZ4nhBAS@3wMYJixZQTl.?U6Wq,%2TrM.[%<#>6!|vWE6&*<T{Xq%os|@t,:-v*OHeaA<g9+m23Q<KhOJH:Jxj1wTas<8m1.w>rPs^(&RymH^y=aL@qz9I'fR..nA

The message is returned with a lot of ASCII characters that are included in the file.

Code

Github Repository


This file contents the .wav files.
Audio files


References

21.5. wave — Read and write WAV files¶. (n.d.). Retrieved November 17, 2014, from https://docs.python.org/2/library/wave.html

viernes, 31 de octubre de 2014

Socket-based Repository

Implement a socket-based key exchange that employs RSA-based digital signatures.


This socket based repository of public keys employs the RSA algorithm to provide access only to the registered users. They can request the public key of another person and then encrypt it, first applying the digital signature, and finally encrypt it with the receiver's public key.

Each time the client establishes a connection with the server, the server is challenged, that is the client sends a value to the server and the server modifies it, then, this modified value is encrypted with the server's private key (digital signature) and sent to the client. The client must also modify the value. If the decrypted value matches it, the connection is accepted, that is one-way authentication. When the client is already registered and the requested action (a query or modify a key) requires a connection with the server, the client is also challenged, that is two-way authentication.

Main functions and classes

The function istheserver(clientobject) verifies the authenticity of the server:
def istheserver(cl):
   e = 670655
   n = 4560161
   x = randint(2, n)
   efxs = int(cl.ssendrecv(str(x)))
   fxs = modExp(efxs, e, n) # Decrypt fxs                                  
   fxc = (x**2 + 25) % n # f(x) Challenge                                  
   print "Fx Server:", fxs
   print "Fx Client:", fxc
   if fxs == fxc:
      print "This is the server."
      return True
   else:
      print "This is not the server."
      return False


The function istheclient(clientobject, purpose) verifies the authenticity of the client:
def istheclient(cl, p):                                                    
   email = raw_input("Enter your email:")                                  
   if not exists(email):                                                   
      print "First of all try 'client.py -k' option."                      
      return False                                                         
   else:
      f = open(email + '/id_rsa', 'r')
      privatekey = f.readline().split(";")
      d = int(privatekey[0])
      n = int(privatekey[1])
      x = int(cl.ssendrecv("c" + p + ";" + email))
      if x != 0: # If client exists                                        
         fx = (x**3 + 2) % n # f(x) Challenge                              
         efx = modExp(fx, d, n) # Signature                                
         print efx
         isit = cl.ssendrecv(str(efx))
         if isit[0] == '1': # Si aprobo este cliente                       
            return True
         else: #Si no aprobo                                               
            return False
      else:
         print "Email not registered."
         return False

The sockets in the client side are manipulated with the methods of this class:
class client():
   def __init__(self):
      self._s = socket.socket() # Socket object                            
      self._host = socket.gethostname() #The server ip, localhost for testing                                                                        
      self._port = 9000 # Defines the port                                 

   def sconnect(self):
      self._s.connect((self._host, self._port)) # Tries to connect         

   def ssendrecv(self, option): # Send a string and receive an answer      
      self._s.send(option)
      self._received = self._s.recv(1024)
      print self._received
      return self._received

   def sclose(self):
      self._s.close() # Close the connection

The server script

The server accepts multiple socket based connections using the threading module.
class c_thread(threading.Thread):
   def __init__(self, client, ip):
      threading.Thread.__init__(self)
      self._client = client
      self._ip = ip

   def run(self):
      try:
         self._rcvd = self._client.recv(1024)
         print self._rcvd
         self._client.send(serverchallenge(self._rcvd))

         self._action = self._client.recv(1024)
         if self._action[0] == 'r':
            self._client.send(register(self._action))

         elif self._action[0] == 'c' and c_thread.clientchallenge(self):
            if self._action[1] == 'q':
               emailr = self._client.recv(1024)
               self._client.send(request(emailr))
            elif self._action[1] == 'm':
               l = self._action.split(";")
               info = self._client.recv(1024)
               self._client.send(modify(l[1], info))

The run() method determines the action to be performed.

The client script

Easy of use

The client script is supposed to be easy of use, when the user runs this script without arguments the help is displayed. The help is also displayed using -h.

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -h
Options:
   -k Runs the RSA algorithm to create a Public Key and a Private Key.
   -r Register a user in the repository.
   -q Request someone's public key.
   -c Modify a public key in the repository.
   -e Encrypt a message (digital signature, receiver's public key).
   -d Decrypt a message.
   -m Convert a decrypted string to a readable message. You must get the string using this script. This option is used in -d.

Subscription 

The user is registered in the repository using ./client -r. The prompt requests the email (identifier) and the public key (e and n). The server is challenged in this option.

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -r
2376580
Fx Server: 2685748
Fx Client: 2685748
This is the server.
Email:jaime
Public Key:
e:5345
n:23454
Registered!


The key can be created before the user is registered. Using -k the RSA algorithm creates the keys for a given user.

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -k
Your email: victor
Public Key: (67967, 355613L)
Private Key: (144215L, 355613L)
In the public key the first value is e and the second is n.
Don't share your private key. The first value is d. The second is n.

Then, when the option -r is used, the prompt doesn't ask for a public key, automatically it is read from the id_rsa.pub file in the directory of the user, named as the given email.

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -r
1522324
Fx Server: 164055
Fx Client: 164055
This is the server.
Email:victor
Registered!

Query 

The query starts with the argument -q. The server and client are challenged. The prompt asks for the email of the user who requests and the script reads the private key of the user in the file “user/id_rsa”. If the tests are passed, the server sends the public key of the requested user and this information is stored in a hidden directory “.user” in a file named “.id_rsa.pub”, as a client-side cache.
Basically, the option -q calls this function:
def query():
   cl = client()
   cl.sconnect()
   if istheserver(cl) and istheclient(cl, 'q'):
      emailr = raw_input("Email requested:")
      user = cl.ssendrecv(emailr)
      if user[0] == '0':
         print "Email is not registered."
      else:
         saveuser(user)
   else:
      print "Failed."
   cl.sclose()

Example:

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -q
2183813
Fx Server: 495314
Fx Client: 495314
This is the server.
Enter your email:victor.riosm@live.com
155575
263713
1:The user is valid.
Email requested:leonardo
leonardo;295067;433793

If the requesting user doesn't exists: 

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -q
776381
Fx Server: 3868154
Fx Client: 3868154
This is the server.
Enter your email:leon
First of all try 'client.py -k' option.
Failed.

If the requested user does not exists:

 victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -q
2714392
Fx Server: 4086458
Fx Client: 4086458
This is the server.
Enter your email:victor.riosm@live.com
82302
148638
1:The user is valid.
Email requested:leon
0
Email is not registered.

Encryption 

The encryption uses digital signatures and public key encryption. The sender's private key is used for the digital signature and the receiver's public key is used to encrypt the message. If the receiver's public key had been requested previously then the prompt won't ask for it. All the ASCII characters can be encrypted.

This is the part of the code that encrypts the message, also applies the digital signature:
   message = raw_input("Enter the message to send >> ")
   nmessage = ''
   for char in message:
      nmessage += str(ord(char)).zfill(3)
   encrypted = ''
   block = 3
   stringnumber = ''
   i = 0
   for char in nmessage:
      stringnumber += char
      i += 1
      if i == block:
         number = int(stringnumber)
         stringnumber = ''
         i = 0
         signature = modExp(number, ds, ns)
         encrypted += str(modExp(signature, er, nr)).zfill(8)
   try:
      number = int(stringnumber)
      signature = modExp(number, ds, ns)
      encrypted += str(modExp(signature, er, nr)).zfill(8)
   except:
      print 'Encrypted'
   print "Encrypted message:", encrypted


Usage:

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -e
Enter your email >> leonardo
Enter the receiver email >> juan
Enter the message to send >> Leonardo used digital signatures and then encrypted this message using Juan's public key :)
Encrypted
Encrypted message: 00246575003086040015291200644751003507420052428500201583001529120048878800422626002626190030860400201583004887880020158300128454006464010012845400531802003507420038172500488788002626190012845400646401006447510035074200531802004226260052428500308604002626190048878800350742006447510020158300488788005318020041644200308604006447510048878800308604006447510039480200524285006500280048529200531802003086040020158300488788005318020041644200128454002626190048878800232354003086040026261900262619003507420064640100308604004887880042262600262619001284540064475100646401004887880047461700422626003507420064475100349729002626190048878800485292004226260010520200381725001284540039480200488788004068350030860400650028004887880016435900009845


Decryption 

The decryption first takes the encrypted message and decrypts it using the receiver's private key. Then the sender's public key is used to verify the digital signature. This key can be read directly from the file created in a query.

The code for decrypting the ciphertext:

   decrypted = ''
   block = 8 # the number of characters in the encrypted string
   stringnumber = ''
   signature = ''
   i = 0
   try:
      for char in encrypted:
         stringnumber += char
         i += 1
         if i == block:
            number = int(stringnumber)
            stringnumber = ''
            i = 0
            signature = modExp(number, dr, nr)
            decrypted += str(modExp(signature, es, ns)).zfill(3)
      try:
         number = int(stringnumber)
         signature = modExp(number, dr, nr)
         decrypted += str(modExp(signature, es, ns)).zfill(3)
      except:
         print 'Decrypted'
      print "Decrypted:", decrypted
      message = getmessage(decrypted)
      return message
   except:
      return "Could not be decrypted"


Usage:

victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -d
Ciphertext >> 00246575003086040015291200644751003507420052428500201583001529120048878800422626002626190030860400201583004887880020158300128454006464010012845400531802003507420038172500488788002626190012845400646401006447510035074200531802004226260052428500308604002626190048878800350742006447510020158300488788005318020041644200308604006447510048878800308604006447510039480200524285006500280048529200531802003086040020158300488788005318020041644200128454002626190048878800232354003086040026261900262619003507420064640100308604004887880042262600262619001284540064475100646401004887880047461700422626003507420064475100349729002626190048878800485292004226260010520200381725001284540039480200488788004068350030860400650028004887880016435900009845
Enter your email >> juan
Enter sender's email >> leonardo
Decrypted
Decrypted: 076101111110097114100111032117115101100032100105103105116097108032115105103110097116117114101115032097110100032116104101110032101110099114121112116101100032116104105115032109101115115097103101032117115105110103032074117097110039115032112117098108105099032107101121032058041
Leonardo used digital signatures and then encrypted this message using Juan's public key :)

If the ciphertext is decrypted using an incorrect private key:
victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/rsasockets$ ./client.py -d
Ciphertext>> 00246575003086040015291200644751003507420052428500201583001529120048878800422626002626190030860400201583004887880020158300128454006464010012845400531802003507420038172500488788002626190012845400646401006447510035074200531802004226260052428500308604002626190048878800350742006447510020158300488788005318020041644200308604006447510048878800308604006447510039480200524285006500280048529200531802003086040020158300488788005318020041644200128454002626190048878800232354003086040026261900262619003507420064640100308604004887880042262600262619001284540064475100646401004887880047461700422626003507420064475100349729002626190048878800485292004226260010520200381725001284540039480200488788004068350030860400650028004887880016435900009845
Enter your email >> usuario
Enter sender's email >> leonardo
Decrypted
Decrypted: 250380167016265627762053536352041292251712656271772342085651664831670162251711772342251713316883622013316882815913536353865811772341664833316883622017620535363528159120856520412916701616648317723435363576205225171177234281591191055167016762051772341670167620531237204129225642795628159116701622517117723428159119105533168816648317723421523716701616648316648335363536220116701617723420856516648333168876205362201177234458220856535363576205417320166483177234279562085651109403865813316883123717723427579516701622564177234161711345913
Could not be decrypted



Other functions 

The arguments -c and -m modifies a public key in the repository and converts a decrypted string in a readable message (ASCII), respectively.

Converting a message

A decrypted ciphertext is automatically converted to a readable message calling the next function:
def getmessage(decrypted): 
   # Converts a decrypted value to a readable message
   message = ''
   i = 0 
   block = 3
   caracter = ''
   for char in decrypted:
      caracter += char
      i += 1
      if i == block:
         i = 0
         message += chr(int(caracter))
         caracter = ''
   try:
      message += chr(int(caracter))
   except:
      'Decrypted'
   return message



Code

The scripts are in this directory.
Github repository

References   

lunes, 13 de octubre de 2014

RSA Authentication

RSA Authentication

The RSA algorithm can be used for encryption and decryption of messages and also for digital signatures.

In order to sign a message, the message must be encrypted using the sender's private key, and then to verify the sign, the cipher text must be decrypted using the public key of the sender.

In this work I have implemented RSA as a login system for a website, instead of passwords the user must sign a message, using the user's private key, and send it the server to be decrypted using the user's public key.

Registration
First of all, the index.html has a form used to register the user and, besides, has the link to the login page.

<html>

  <head>
    <title>Register</title>
  </head>

  <body>
    <h1>Register</h1>
    <a href="rsa.py">Run this script to create keys.</a>
    <form action="cgi-bin/register.py" name="reg" id="reg">
      <br>Choose username: <input type="text" size="10" name="username" id="username" required="True">
      <br><h3>Public Key</h3>
      <br>Enter e: <input type="text" size="10" name="e" id="e" required="True">
      <br>Enter n: <input type="text" size="10" name="n" id="n" required="True">
      <br><input type="submit" value="Enviar"></button>
    </form>
    <br><a href="cgi-bin/login.py">Login</a>
  </body>

</html> 

The user must have a key to register to the system, so I included a script "rsa.py" that generates the public key and the private key. Then, as you can see, the python script register.py is used to register the user.

def register(name, e, n):
   f = open("registered.txt", 'r')
   for line in f:
      userdata = line.split()
      if name == userdata[0]:
         f.close()
         print """The username is not available. Return"""
         return False
   f = open("registered.txt", 'a')
   f.write(name + ' ' + e + ' ' + n + '\n')
   f.close()
   print "The user has been added."
   return True

args = cgi.FieldStorage()
if args.has_key("username") and args.has_key("e") and args.has_key("n"):
   username = args["username"].value
   e = args["e"].value
   n = args["n"].value
   result = register(username, e, n)
   if result == True:
      os.mkdir("users/"+username)
      print """
      
Username: %s
      
       e: %s
      
       n: %s
      
Login with RSA
      """%(username, e, n)  

Log In

The log in system has two purposes verifies the server and verifies the user.
The process is a little explained in the page.

First the user selects a number xc and sends it to the server, both must compute f(x) = x**2 + 1, but the server has to encrypt it using its private key, and then the client decrypts the received f(x) and compares it with the value that f(x).

Meanwhile, the server receives the user name and generates a number x. The user must calculate x**2 + 3*x + 5 and sign it (with the private key). Then that value (s) is sent to the server and is decrypted and compared with the value that the server computed.

This is a piece of the script:
if fields.has_key("username") and fields.has_key("xc"):
   username = fields["username"].value
   xc = int(fields["xc"].value)
   x, e, n = generax(username)
   f = open("rsa.private", 'r')
   privatekey = f.readline().split(",")
   f.close()
   ds = int(privatekey[0])
   ns = int(privatekey[1])
   s = modularExp(fs(xc, ns), ds, ns)

Finally, the script "prove.py" validates the user and, if the user could log in, shows the last time the user had logged in.
if fields.has_key("s"):
   username = fields["username"].value
   x = int(fields["x"].value)
   s = int(fields["s"].value)
   e = int(fields["e"].value)
   n = int(fields["n"].value)
   fx = f(x, n)
   fc = modularExp(s, e, n)
   if fx == fc:
      print "The s is correct this is the user %s"%username
      print """
      

Hi %s

"""%username f = open("users/"+username+"/logins.dat", 'r+') if f.readline() != '': f.seek(0) print " The last time you logged in was", f.readline() else: print " This is the first time you log in" f.seek(0) f.write(asctime()) f.close else: print "Incorrect s. This is not the user. fx != fc" else: print """ Enter s : signed f(x) Return """

The script used to create keys is rsa.py

def rsa():
   try:
      p = getPrime(int(argv[1]))
      q = getPrime(int(argv[1]))
   except:
      p = getPrime(10)
      q = getPrime(10)
   n = p * q
   phin = (p - 1) * (q - 1)
   c = 2
   while c != 1:
      e = randint(2, n-1)
      if phin > e:
         c, x, d = egcd(phin, e)
         h = x * phin + d * e
      else:
         c, d, x = egcd(phin, e)
         h = x * e + d * phin
   if d < 0:
      d %= phin
   print "h=", h, c

   publicKey = (e, n)
   privateKey = (d, n)


Logging in


The index:

 The login:
 Enter s:
 If the user is valid:
 If the user is not valid:


Running rsa.py:
victor@victor-HP-G42-Notebook-PC:~/Downloads$ python rsa.py
h= 1 1
Public Key: (58991, 183467L)
Private Key: (102431L, 183467L)
In the public key the first value is e and the second is n.
Don't share your private key. The first value is d. The second is n.
The keys are stored in rsa.keys

This is the result of running fx.py:
victor@victor-HP-G42-Notebook-PC:~/Downloads$ python fx.py
Introduce x: 7032
Introduce d: 24967
Introduce n: 28601
f(x):  18996
Signed f(x):  2871
 Write this value in the login form

The code is in this repository.

References

Schneier, B. (1996). Applied Cryptography, Second Edition: Protocols, Algorithms and Source Code in C. John Wiley and Sons, Inc.

lunes, 6 de octubre de 2014

T3 - Diffie-Hellman Protocol

The Diffie-Hellman Protocol

Whitfield Diffie and Martin Hellman developed the first public-key algorithm, the Diffie-Hellman protocol. All participants (e. g. Alice and Bob) construct the key together. The use of one-way functions in the creation of the key provides the basic security that the protocol needs. However, Diffie-Hellman is still insecure due to its vulnerability to a man in the middle attack.

A one-way function can be computed, relatively, easily, without difficulty, but it is very difficult to recover the arguments of the function before computed. This is, for any x, calculating f(x) is easy, but recovering x, for any f(x) is extremely hard. In Diffie-Hellman we compute modular exponentiation, because modular logarithms are, by far, more difficult to calculate.

Generating (and distributing) the key requires to follow the next algorithm:

1. Alice and Bob choose a prime number p and a generator g ∈ Zp. These numbers can be publicly chosen.
P → Large prime
g → generator Zp

2. Alice, secretly, chooses a number x modulo p and sends f(x) to Bob, publicly.
f(x) = g x mod p

3. Bob, secretly, chooses a number y modulo p and sends f(y) to Alice, publicly.
f(y) = g ymod p

4. Alice and Bob compute the key for the session:
K = f(x) y mod p = f(y)x mod p.

This works because (g x ) y= (g y) x, and for x != y, f(x) != f(y).

The Diffie-Hellman protocol in python

First of all, a prime p and a generator g are chosen at random, or pseudo random.

p = createPrime(16) # Calls to a function to create a prime
g = createGenerator(p) # Calls to a function to create a generator
print "p =", p, "| g =", g

To be a generator, g must satisfy the next requirement:
ꓯi < (p – 1) s.t. i | (p – 1), gi != 1

In other words, we compute gi mod p for each factor i of (p – 1) and if none of those values is 1, then g is a generator. The code in python goes as follows:
def isGenerator(g, p): # Proves if g is a generator
   i = 2
   while i < (p - 1):
      if (p - 1) % i == 0 and modularExp(g, i, p) == 1: # Computes the power
         return False # Returns False if g is not a generator, so we have to select other g
      i += 1
   return True

The function modularExp(base, exponent, modulo) is imported from the file modularExp.py. Basically, returns the result of raising a number (base) to a power (exponent) in a specified modulus modulo.
def modularExp(base, exponent, modulo):
   res = 1
   pot = base % modulo
   while exponent > 0:
      if exponent % 2 == 1:
         res = (res * pot) % modulo
      exponent = exponent >> 1
      pot = (pot * pot) % modulo
   return res

Then, the participants are created. They use p and g to compute f(x) or f(y), respectively.
Alice = Person(p, g)
Bob = Person(p, g)

The class Person is defined in person.py. In the constructor, x is selected and the function is calculated. The method getKey(self, fy, p) computes the key with the f(y) sent by the other party. The other methods, getFx() and showKey(), return f(x) and the key respectively (obviously, this is only to demonstrate the protocol).

def __init__(self, p, g):
      self._x = randint(2, p-1) # x is chosen
      self._function = modularExp(g, self._x, p) #Here is where f(x) is computed

def getKey(self, fy, p):
      self._key = modularExp(fy, self._x, p) # The key is calculated, as in the explanation above.

In dhp.py:
fx = Alice.getFx() # The call to the method for Alice
fy = Bob.getFx() # The call to the method for Bob
print "Fx = ", fx
print "Fy = ", fy

Alice.getKey(Bob.getFx(), p)
Bob.getKey(Alice.getFx(), p)

print "Key Alice = ", Alice.showKey()
print "Key Bob = ", Bob.showKey()

Hacking the key

A hacker already knows p, g, f(x) and f(y), because they were made public. So, in order to obtain the key, the hacker, instead of calculating the logarithm for f(x) or f(y), computes the modular exponentiation k = gi mod p, for all i < p. If the exponentiation yields a value k equal to f(x) or f(y), then the hacker can get the key by raising f(y) or f(x), respectively, to the power i modulo p.
def hack(p, g, fx, fy):
   i = 2
   while i < p:
      k = modularExp(g, i, p) # Tries to get f(x) or f(y)
      if k == fx: # If he gets f(x), then the key is f(y)^i modulo p
         K = modularExp(fy, i, p)
         print "Hacked. The key is: ", K, "| x =", i
         return K
      if k == fy: # If he gets f(y), then the key is f(x)^i modulo p
         K = modularExp(fx, i, p)
         print "Hacked. The key is: ", K, "| y =", i
         return K
      i += 1

Running the script, implementing the Diffie-Hellman protocol as well as a brute-force attack against it. Although the size of p is 16 bits, a new size of p can be specified in the prompt.

Tamaño de p = 16 bits
victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Diffie - Hellman Protocol$ python dhp.py
p = 5531 | g = 3964
Fx = 696
Fy = 430
Key Alice = 2336
Key Bob = 2336
Hacked. The key is: 2336 | y = 3513

Tamaño de p = 10 bits
victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Diffie - Hellman Protocol$ python dhp.py 10
p = 661 | g = 559
Fx = 142
Fy = 15
Key Alice = 613
Key Bob = 613
Hacked. The key is: 613 | x = 8
All the files are in github.com

References

Schneier, B. (1996). Applied Cryptography, Second Edition: Protocols, Algorithms and Source Code in C. John Wiley and Sons, Inc.