Click here to Skip to main content
11,484,162 members (70,631 online)
Click here to Skip to main content

3-tier Diffie Hellman

, 31 Dec 2009 CPOL 12.8K 757 18
Rate this:
Please Sign up or sign in to vote.
Shared secret for three users over an unsecured network connection

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.

diffhel
The server sends the prime number and its primitive root.

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

diffhel3

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:

diffhel4

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).

graph

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

taiar erez

Israel Israel
No Biography provided

Comments and Discussions

 
GeneralTypos Pin
aspdotnetdev30-Dec-09 13:52
memberaspdotnetdev30-Dec-09 13:52 
GeneralRe: Typos Pin
taiar erez31-Dec-09 5:50
membertaiar erez31-Dec-09 5:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150520.1 | Last Updated 31 Dec 2009
Article Copyright 2009 by taiar erez
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid