3-tier Diffie Hellman

• Download source - 30.1 KB
• Download sample - 10.41 KB

Introduction

The goal of this article is to give a framework for a three (or possibly more) party conference with security over a non secure network connection using the Diffie-Hellman algorithm.

Note: To run the project, you must start the server and then the three clients.

Background

The Diffie-Hellman algorithm uses modular arithmetic and prime numbers.

It uses the fallowing components:

1. Prime number - An integer which can divided without remainder only by himself and the number 1. (Usually a very big integer but I used a smaller one so it will be easier to debug.)
2. Primitive root - An integer that is smaller than the prime number. It is the creator of the field that is generated by the prime number.

   Example: For the prime number 7, a primitive root can be 3 but not 2 because:

   3^0 =    1 =>    1 mod 7 = 1       2^0 =  1  =>  1 mod 7 = 1
   
   3^1 =    3 =>    3 mod 7 = 3       2^1 =  2  =>  2 mod 7 = 2
   
   3^2 =    9 =>    9 mod 7 = 2       2^2 =  4  =>  4 mod 7 = 4
   
   3^3 =    27 =>  27 mod 7 = 6       2^3 =  8  =>  8 mod 7 = 1
   
   3^4 =    81 =>  81 mod 7 = 4       2^4 = 16 => 16 mod 7 = 2
   
   3^5 =   243 => 243 mod 7 = 5       2^5 = 32 => 32 mod 7 = 4

3. Power number - A random multiplication of the primitive root (we do modulo every interaction so the number never gets bigger than uint64, otherwise the computer will crash very fast).

How It Works

The three users agree on a prime number and a primitive root (in my implementation, the server chooses), and every user chooses its own power number (he will not share this number). Each user then multiplies the primitive root in the power of the power number and sends the remainder to the other two users.

The server sends the prime number and its primitive root.

Each user sends the result of the primitive root with his secret power number modulo the prime.

Then the users multiply the other users result with their secret power number and gain the shared secret.

Note: Server is not needed, its purpose to send the IP to the clients because they all run on the same machine. On different machines, they can connect directly by each other's IP address.

Now that all the users have the shared key, they can encrypt their messages. And only those three will have the key to decrypt it back. There are so many possible results that the shared key can be impossible to guess. An evil party can't get the secret key simply by listening to all connections. He will have to know the power of one of the users to know the shared key, but this number is never being sent to other users, so he can't know it.

For example:

We got the shared key 4758 and user A wants to send its bank pin number to users B and C. Let's say that A's pin number is 1234 (or in binary 10011010010) A does exclusive or with the shared key 4758 (in binary 1001010010110) and sends the result. B and C who have the shared key do exclusive each on their own on the number that A sent which is 5700 (in binary, 1011001000100) now B and C have A's pin number.

More Than 3?

For two users who want to share a secret, you can use the original algorithm. But if 4 or 5 or 1 million users want to share a secret, it requires that every user will be connected with every other user. This creates a complete graph. And if one of the nodes is not secure, the rest are not secure too (a chain is as strong as its weakest link).

Using the Code

Calculate the number to send to the other users:

private void calaulate()	//calculate the number this user 
                      	//sends A = [(primitive-root)^power (mod prime)]
{
     A = (UInt64)((primitiveRoot * primitiveRoot) % prime);
     for (int i = 0; i < power - 2; i++)
         A = (UInt64)((A * primitiveRoot) %  prime);
}

In the following first block of code, if you wish to communicate with the first user, you need to make sure that the shared key has been established in the second block before you can encrypt messages with the shared key. Therefore you have to wait until the second block finishes its calculations before you can securely communicate.

public void next(object rw) 
{ 
	try 
	{ 
		readWrite RW = rw as readWrite;
		BinaryReader reader = RW.Reader;
		BinaryWriter writer = RW.Writer;
		writer.Write(A);//write to left user my result
		C = reader.ReadUInt16();
		//read left users result 
		/* 
		* make sure that the shared secret is not 0 and 
		* you can communicate with left side here 
		* choose whatever protocol of encryption uses a shared key 
		*/
 	} catch (Exception) 
	{
	 	MessageBox.Show("an error occurred and needs to exit");
	 	this.Close();
	}
}
public void prev(object rw) 
{ 
	try 
	{ 
		readWrite RW = rw as readWrite;
		BinaryReader reader = RW.Reader;
		BinaryWriter writer = RW.Writer;
		B = reader.ReadUInt16();//read right user result 
		writer.Write(A);//write to right user my result 
		Thread.Sleep(3500);//wait the other side read (gets C) 
		#region calculate sherd secret 
		sherdSecret = (UInt64)(B * C);
		insertToTextBox("B: " + B.ToString() + 
			" C: " + C.ToString());  //display left and right calculation
					       //(you should remove that)
		sherdSecret = (UInt64)(sherdSecret % prime);
		insertToTextBox("1: " + ((B * C) % prime).ToString());	//prints 
								//interaction 
		for (int i = 0; i < power - 1; i++) 
		{ 
			sherdSecret = (UInt64)((sherdSecret * primitiveRoot) % prime);
			insertToTextBox((i + 2).ToString() + ": " + 
				sherdSecret.ToString());//prints interaction
		} 
		#endregion calculate sherd secret 
		insertToTextBox("sherad secret key: " + 
		    sherdSecret.ToString());//shows the sherd key(remove this line) 
		/* 
		 * your code to communicate with right side here 
		 * no need to wait 
		 * choose whatever protocol of encryption uses a shared key 
		 */ 
	} 
	catch (Exception) 
	{ 
		MessageBox.Show("an error occurred and needs to exit"); 
		this.Close(); 
	} 
}

Points of Interest

Take note that all the users communicate on the same machine so every user has his own IP and port that the server assigns to them in their order of connection. It's better that you don't use a server at all when you start communication with others to minimize the risk of losing credibility of the network.