Friday, May 6, 2011

Diffie Hellman Key Exchange algorithm

Diffie Hellman Key Exchange Algorithm

Good information for DH is given on Wikipedia.
Follow http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
---------------------------------------------------------------------------------------------------
Implementation
Source code language:   Java
Datagram Client Server Communication is used
---------------------------------------------------------------------------------------------------

SERVER (User 1)



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.DatagramPacket;
import java.net.DatagramSocket;
import java.net.InetAddress;




//Implement Diffie Hellman
//this is server
public class server
{

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int sport=1120,cport=1121,sport1=1122,cport1=1123,sport2=1124,cport2=1125;
int q,e,Xa,Ya,Yb,k,len;
void start() throws Exception, IOException
{
System.out.println("Enter 1st prime :: ");
q=Integer.parseInt(br.readLine());
e=calpriroot(q);
System.out.println("Primitive root e="+e);
System.out.println("Enter the Private key Xa for Server s.t. Xa<"+q+": ");
Xa=Integer.parseInt(br.readLine());
Ya=((int)Math.pow(e,Xa))%q;
System.out.println("Private Key="+Xa);
System.out.println("Public Key="+Ya);
/*Send These values to Client(User B)*/
byte buf[]=new byte[3];
buf[0]=(byte)q;
buf[1]=(byte)e;
buf[2]=(byte)Ya;
InetAddress id=InetAddress.getLocalHost();
DatagramSocket ds=new DatagramSocket(sport);
DatagramPacket dp=new DatagramPacket(buf,buf.length,id,cport);
ds.send(dp);
ds.close();
/*Server (User1) receives public key of Client (User2)*/
DatagramSocket ds1=new DatagramSocket(cport1);
DatagramPacket dp1=new DatagramPacket(buf,buf.length);
ds1.receive(dp1);
Yb=buf[0];
System.out.println("Public Key of Client(User 2)="+Yb);
System.out.println("-------------------------------------");

/*Calculate Shared Secret Key*/
k=((int)Math.pow(Yb,Xa))%q;
System.out.println("Shared Secret Key : "+k);
/*Get Data from user 1*/
System.out.println("Enter the Data to be send : ");
System.out.println("Enter no of elements : ");
len=Integer.parseInt(br.readLine());
buf=new byte[len];
System.out.println("Enter Data : \n");
for(int i=0;i<len;i++)
{
System.out.println("Enter data"+i+" : ");
buf[i]=(byte)Integer.parseInt(br.readLine());
}
/*Encryption*/
System.out.println("Before Encryption");
System.out.println("Data : ");
for(int i=0;i<len;i++)
System.out.print(" "+buf[i]);
System.out.println();
for(int i=0;i<len;i++)
{
buf[i]=(byte)(buf[i]+k);
}
System.out.println("After Encryption");
System.out.println("Data : ");
for(int i=0;i<len;i++)
System.out.print(" "+buf[i]);
/*Send Encrypted Data to User 2*/
DatagramSocket ds2=new DatagramSocket(sport2);
DatagramPacket dp2=new DatagramPacket(buf,buf.length,id,cport2);
ds2.send(dp2);
ds2.close();
}
int calpriroot(int q) throws IOException
{
int e=2,i=1,cnt=0;
int first=-1,ano=-50,change=1;
int list[]=new int[q];

for(int j=0;j< q;j++)
list[j]=-100;
while(e < q)//this loop finds the total no of coprime of 'q'
{
int k=iscoprime(e, q);//first check if no are coprime
if(k==1)
{
if(cnt==0)
{
first=((int)Math.pow(e,i)) % q;
change=1;

}
else
{
ano=((int)Math.pow(e,i))%q;
if(first==ano)
{
// System.out.println("e="+e+"  i="+i+"  q="+q+"  cnt="+cnt+"  first="+first+"  ano="+ano);
if(cnt==(q-1))
return e;
else
{
list[e]=cnt;
cnt=0;
i=1;
e++;
first=-1;
ano=-50;
change=0;
}
}
}
if(change==1)
{

cnt=cnt+1;
//System.out.println("e="+e+"  i="+i+"  q="+q+"  cnt="+cnt+"  first="+first+"  ano="+ano);
i++;

}
}
else
e++;

}
//if no exact (q-1) coprimes not found, go for max number
int max=maxno(list);
return max;
}
int iscoprime(int l,int m)
{
int c;
while(true)
{
c=l%m;
if(c==0)
return 0;
l=m;
m=c;
if(l==1||m==1)
return 1;
}
}
int maxno(int r[])
{
int l=r.length;
int max=-100,j=0;
for(int i=1;i<l;i++)
{
if((r[i]!=-100)&&(r[i]>max))
{
max=r[i];
j=i;
}
}
return j;
}
public static void main(String[] args) throws Exception
{

server ser=new server();
ser.start();

}

}


CLIENT (User 2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.DatagramPacket;
import java.net.DatagramSocket;
import java.net.InetAddress;




//this is client
public class client
{
int sport=1120,cport=1121,sport1=1122,cport1=1123,sport2=1124,cport2=1125;
byte buf[]=new byte[3];
int e,q,Ya,Xb,Yb,k;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
void start() throws Exception
{
DatagramSocket ds=new DatagramSocket(cport);
DatagramPacket dp=new DatagramPacket(buf,buf.length);
ds.receive(dp);
q=(int)buf[0];
e=(int)buf[1];
Ya=(int)buf[2];
ds.close();
System.out.println("-------------------");
System.out.println("Public Key of User 1(Server)="+Ya);
System.out.println("primitive Root="+e+"  Prime No="+q);
System.out.println("--------------------------------------------------");
System.out.println("Enter the Private key Xb for Server s.t. Xb<"+q+": ");
Xb=Integer.parseInt(br.readLine());
Yb=((int)Math.pow(e,Xb))%q;
System.out.println("Public Key="+Yb);
buf=new byte[3];
buf[0]=(byte)Yb;
/*Client(User2) Sends his Public key*/
DatagramSocket ds1=new DatagramSocket(sport1);
InetAddress id=InetAddress.getLocalHost();
DatagramPacket dp1=new DatagramPacket(buf,buf.length,id,cport1);
ds1.send(dp1);
ds1.close();
/*Calculate Shared Secret Key*/
k=((int)Math.pow(Ya,Xb))%q;
System.out.println("Shared Secret Key : "+k);
/*Get data from User 1*/
buf=new byte[1024];
DatagramSocket ds2=new DatagramSocket(cport2);
DatagramPacket dp2=new DatagramPacket(buf,buf.length);
ds2.receive(dp2);
int len=dp2.getLength();
/*Decrypt the data*/
System.out.println("Before Decryption: Recived data");
System.out.println("Data : ");
for(int i=0;i<len;i++)
System.out.print(" "+buf[i]);
System.out.println();
byte plain[]=new byte[buf.length];
for(int i=0;i<len;i++)
plain[i]=(byte)(buf[i]-k);
System.out.println("After Decryption:");
System.out.println("Data : ");
for(int i=0;i<len;i++)
System.out.print(" "+plain[i]);
System.out.println();
}
public static void main(String[] args) throws Exception
{
client cl=new client();
cl.start();

}

}
------------------------------------------------------------------------------------------------------

Output: 
Server Window:
Enter 1st prime :: 
7
Primitive root e=3
Enter the Private key Xa for Server s.t. Xa&lt;7: 
5
Private Key=5
Public Key=5
Public Key of Client(User 2)=4
-------------------------------------
Shared Secret Key : 2
Enter the Data to be send : 
Enter no of elements : 
10
Enter Data : 

Enter data0 : 
12
Enter data1 : 
23
Enter data2 : 
34
Enter data3 : 
45
Enter data4 : 
56
Enter data5 : 
67
Enter data6 : 
78
Enter data7 : 
89
Enter data8 : 
90
Enter data9 : 
98
Before Encryption
Data : 
 12 23 34 45 56 67 78 89 90 98
After Encryption
Data : 
 14 25 36 47 58 69 80 91 92 100

Client Window:
-------------------
Public Key of User 1(Server)=5
primitive Root=3  Prime No=7
--------------------------------------------------
Enter the Private key Xb for Server s.t. Xb&lt;7: 
4
Public Key=4
Shared Secret Key : 2
Before Decryption: Recived data
Data : 
 14 25 36 47 58 69 80 91 92 100
After Decryption:
Data : 
 12 23 34 45 56 67 78 89 90 98
-----------------------------------------------------------------------------------------------------
NOTE:
A)I have taken
1)  function for finding PRIMITIVE ROOT and 
2) input for prime no 
 on the server(user1) side only as in DH, both user1 and user2 agree on taking these global common values.
So there is no need to have function for primitive root on user2(client) side.

B) If you want to see how my primitive root function works, just make active the code lines which i have commented in my function to find primitive root.
-------------------------------------------------------------------------------------------------------
If you have any other simple function for finding PRIMITIVE ROOT, then please share with us.