Diffie-Hellman Key Exchange Example

Please send me the code of Deffie Hellman algorithm to the email address i.e. qaziejaz@hotmail.com, please send me the code as soon as possible, I am doing my research work and in my research I need the said code.
thank's
Qazi Ejaz

31081979

I have to implement IPSEC n using omnet with .net to code it.... I find ur example very helpful... It is very easy to understand even for me when i dont know the details of the Diffie Helliman key exchange algorithm......

The compiler for ipv6suitewithinet (based on omnet n vc.net) doesnt support to resolve GUID u use in ur example....... It is giving me the Linking error to the external symbol to the function CoCreate()..... Can u plz help me... if i need to include certain file for it???? or is there any alternative i can use????

thanks a lot in advance...

Regards,
Maria

Would it be possible for you to support 1024 bit keys ?

ya..it is..but you have to create a library file to support big numbers.

Hye Lee
Your project is very interesting.
I have a questions. I wanted to ask you what is/are the limitation in your project.
I am waiting for your response,

Thanks

Garima Thakral

Hi Garima,

The only limitation to this current project is that the ephemeral and exchange keys are limited to the size of an __int64 (e.g. 64-bit keys).

If you look under the post/reply to this article (below this one) - you should see Runtime Optimization - in my relpy you will see the best way to use Diffie-Hellman key exchange is by using the Microsoft Crypto API functions.

If you do want to use my code instead though, feel free to do so Smile | :)

(like I said only limitiation is 64-bit keys)

Best Regards,

Lee Griffiths

first of it's a very nice code you got there Smile | :)

I've noticed you have a define for maximum number, so i tried to change it to a larger number and the algorithm became extremely slow, so i haven't been able to get a 64 bit prime number, to be able to use in DES for example..
any suggestions???

H.A.

First off, the best way to use Diffie Hellman should be to use tried and tested API's
[Microsoft Cryptographic Libraries for Diffie-Hellman]

You can use the Microsoft Cryptographic Service Providers to achieve a lot of your cryptography needs. Lookup CryptAcquireContext and go from there - everything from RSA to DES to Diffie-Hellman and so on. I've included an example here of how to generate a prime using the Microsoft CryptoAPI. At first glance the prime doesn't always seem to look prime because it's last byte is an even number. However please note that the BYTE array contains octects!

To use the GeneratePrime function shown below, include <wincrypt.h> and then something like:

	BYTE *prime     = NULL;<br />
	DWORD primesize = 0;<br />
<br />
	GeneratePrime(&prime, &primesize);

Here is the GeneratePrime function (using RSA).

BOOL GeneratePrime(BYTE **prime, DWORD *cbPrime) <br />
{<br />
	HCRYPTPROV	 hCryptProv				= NULL;<br />
	HCRYPTHASH	 hHash					= NULL;<br />
	BOOL		 AcquiredContext		= FALSE;<br />
	BOOL		 AcquiredPrime			= FALSE;<br />
<br />
	//Attempt to acquire a cryptographic context<br />
	if(CryptAcquireContext(&hCryptProv,	NULL, NULL, PROV_RSA_FULL, 0)== FALSE)<br />
	{<br />
		//No context established for this machine, create new key set<br />
		if(GetLastError() == NTE_BAD_KEYSET)<br />
			AcquiredContext = CryptAcquireContext(&hCryptProv,	NULL, NULL, PROV_RSA_FULL, CRYPT_NEWKEYSET);<br />
	}<br />
	else<br />
		AcquiredContext = TRUE;<br />
	<br />
	//Context Acquired lets Generate a key<br />
	if (AcquiredContext==TRUE)<br />
	{<br />
		HCRYPTKEY hEncryptionKey = NULL;<br />
		<br />
		//Generate a 512-bit key<br />
		BOOL  bGenEncKey = CryptGenKey(hCryptProv, CALG_RSA_KEYX, (512 << 16) | CRYPT_EXPORTABLE, &hEncryptionKey);<br />
		if (bGenEncKey)<br />
		{			<br />
			//Get the size of the key blob<br />
			DWORD KeyLength = 0;<br />
			if (CryptExportKey(hEncryptionKey, NULL, PRIVATEKEYBLOB ,0, NULL, &KeyLength)==TRUE)<br />
			{<br />
				if (KeyLength>0)<br />
				{<br />
					//Allocate a key blob<br />
					BYTE *PrivateKeyBlob = (BYTE *) malloc((size_t)KeyLength);<br />
					if (PrivateKeyBlob)<br />
					{<br />
						//Export the blob<br />
						if (CryptExportKey(hEncryptionKey, NULL, PRIVATEKEYBLOB ,0, PrivateKeyBlob, &KeyLength)==TRUE)<br />
						{<br />
							PUBLICKEYSTRUC pks    = {0};<br />
							RSAPUBKEY      rsapub = {0};<br />
<br />
							//Get the Public Key and RSA information<br />
							memcpy(&pks,    PrivateKeyBlob, sizeof(PUBLICKEYSTRUC));<br />
							memcpy(&rsapub, PrivateKeyBlob + sizeof(PUBLICKEYSTRUC), sizeof(RSAPUBKEY));<br />
<br />
							//Calculate the size and offset of the prime numbers<br />
							DWORD KeySizeBytes = rsapub.bitlen / 16;<br />
							DWORD ModSizeBytes = rsapub.bitlen / 8;<br />
							DWORD OffsetPrimeP = sizeof(PUBLICKEYSTRUC) +  sizeof(RSAPUBKEY) + ModSizeBytes;<br />
							DWORD OffsetPrimeQ = sizeof(PUBLICKEYSTRUC) +  sizeof(RSAPUBKEY) + ModSizeBytes + KeySizeBytes;<br />
<br />
							//Allocate sufficient memory to hold the primes<br />
							*prime = (BYTE *) malloc((size_t) KeySizeBytes);<br />
												<br />
							if (*prime)<br />
							{<br />
								//Copy the prime from the key blob<br />
								*cbPrime = KeySizeBytes;<br />
                                memcpy(*prime, PrivateKeyBlob + OffsetPrimeP, KeySizeBytes);<br />
								AcquiredPrime = TRUE;								<br />
							}<br />
						}<br />
					}<br />
				}<br />
			}<br />
<br />
			CryptDestroyKey(hEncryptionKey);<br />
		}<br />
<br />
		CryptReleaseContext(hCryptProv, 0);<br />
	}<br />
<br />
	return AcquiredPrime;<br />
	<br />
}

Anyway hope this helps. If you look at the CryptoAPI by Microsoft you will see that encrypting with DES is simple! It also supports many other encryption algorithms along with hashing Algorithms, Public-Private Key and Signature algorithms - it's a very powerful library indeed.

If you need any more help, let me know.

Best Regards,

Lee

I've tested your implementation of GeneratePrime function and I found out that it doesn't generate a 512-bit key, it always returns 256bit key ! KeySizeBytes was always set to 32. If I change the code to:
...
//Generate a 512-bit key
BOOL bGenEncKey = CryptGenKey(hCryptProv, CALG_RSA_KEYX, (1024 << 16) | CRYPT_EXPORTABLE, &hEncryptionKey);
...
it returns a 512bit key. Any idea why?

Thanks

how can i use that without need key exchange?

I'm not sure I quite understand your question?
The whole point of the article was to describe a way to EXCHANGE ENCRYPTION KEYS between two parties.

If you're just looking for encryption/decryption algorithms I'm sure there are plenty here on CodeProject!

All the best!

I want code C++ for encryption and dencrypttion please

The Diffie-Hellman algo implementation was quite useful.
I'm doing some study in IKE which uses the Diffie-Hellman algo. I'm looking for a sample implementation of IKE. Any help? or any links?

Thanks Unsure | :~

Hi Adam,
I found the demo very interesting, but i want the code in C.
can the code be converted to C.

Regards,
Archana

hi, all

Hello,

Could you show me a library in which I can use the generated key for the actual encryption ?
Can you import it in Microsoft's CryptoAPI ? Or even OpenSSL ?

Recently, I've successfully established an encrypted channel between a Pocket PC and Windows XP using RSA PKI in CryptoAPI. However, Diffie-Helman would be nicer as the encryption itself is faster than PKI-algorithms. Moreover, your code seems portable to non-Windows clients, apart from the use of __int64.

I would suggest not using Microsofts CryptoAPI (you never can trust them, their probably sending your generated keys to the NSA or something). I would suggest using blowfish, an encryption algorithm developed by Bruce Schneier. It's apparently very strong, and equally as good - its open source freeware (no royalties to pay for using it)!

You can probably find it here:
http://www.schneier.com/blowfish-download.html

If you want to make it portable to a pocket pc you can change all instances of '__int64' to an 'unsigned long' if you wish, but you'll have to change the #defines for both of the maximum values to 2147483648.

Let me know how you get on.

Kind Regards,

Lee Griffiths

If I replace '__int64' with 'unsigned long', doesn't that reduce the key size, and therefore also the security level ?

Yes it sure will. It all depends on how secure you want your communication. It's probably best to get your hands on the GMP libraries (free on sourceforge.net). And you can then assign your integers to a massive number of digits.

Hello again,

I wrote a small sample app to use it with Bruce Schneier's Blowfish implementation.
It seems the resulting encryption key is not the same for the sender and the recipient.
(see the commented exit(-1) statement below)

Could you tell me what I do wrong ?

#include "DrmCrypto.h"
#include "BLOWFISH.H"

struct KeyData
{
__int64 Generator;
__int64 Modulus;
__int64 InterKey;
__int64 EncryptionKey;
};

int _tmain(int argc, _TCHAR* argv[])
{
KeyData SenderKeyData, RecipientKeyData;
CDrmCrypto Sender, Recipient;

Sender.CreateKeys(SenderKeyData.Generator, SenderKeyData.Modulus);
Recipient.CreateKeys(RecipientKeyData.Generator, RecipientKeyData.Modulus);

Sender.CreateSenderInterKey(SenderKeyData.InterKey);
Recipient.CreateRecipientInterKey( RecipientKeyData.InterKey, RecipientKeyData.Generator,
RecipientKeyData.Modulus);

Sender.CreateSenderEncryptionKey( SenderKeyData.EncryptionKey, RecipientKeyData.InterKey);
Recipient.CreateRecipientEncryptionKey( RecipientKeyData.EncryptionKey, SenderKeyData.InterKey);

if (SenderKeyData.EncryptionKey != RecipientKeyData.EncryptionKey)
{
printf("Sender & Recipient encryption keys do not match.\n");
// exit(-1); Cry | :((

}

if (InitializeBlowfish((char*)&SenderKeyData.EncryptionKey, (short)sizeof(SenderKeyData.EncryptionKey) ))
{
printf("InitializeBlowfish returned an error.\n");
exit(-1);
}

unsigned long xl1 = 123456789;
unsigned long xr1 = 987654321;
unsigned long xl2 = xl1;
unsigned long xr2 = xr1;

Blowfish_encipher(&xl1,&xr1);

Blowfish_decipher(&xl1,&xr1);
if (xl1 != xl2 || xr1 != xr2)
{
printf("Encryption failed.\n");
exit(-1);
}

printf("Done.\n");

return 0;
}

You are using the class incorrectly. The sender is the only one that calls createkeys. The sender then creates the sender interim key. The reciever then uses the sender's interim, and public keys (ones generated from createkeys), to make his interim key. The reciever can now call CreateRecipientEncryptionKey, and the sender can call CreateSenderEncryptionKey (and pass the reciever's interim key). Both parties should now have the same encryption key.

Please read the example usage notes (i think they should make it clear what needs to be done).

Have fun.

Best Regards,

Lee Griffiths

Ever wanted to use encryption, but got stuck trying to get the encrption key to the recipient? A real chicken and egg problem. The solution is that you can use Diffie-Hellman-Merkle key exchange.

Diffie-Hellman-Merkle key exchange uses y = g^x (mod p) to create a once-off shared secret encryption key of arbitrary length. This secret key can then be used to exchange data encrypted using the key. What makes DH key exchange fascinating is that is is not necessary to exchange secret information in order to 'share' the encryption key. Anyone evesdropping on the line cannot derive the key from the information exchanged during the negotiation process.

Security is based on the fact that it is mathematically infeasible to discover the key IF THE VALUES ARE LARGE ENOUGH. Adequate security typically utilizes keys in of 1000 bits. Security is enhanced due to the fact that a new, unique encryption key is generated each time.

The primary limitation is in performing large-integer arithmetic. Fortunately there are public/free implementations available. Or you can read Knuth and write one yourself. Check out the BigDigits library at www.di-mgt.com.au. Be aware that using this code it is possible to create arbitrarily long keys, which may have legal implications in your area. The key buffer is hard-limited to 51 4-byte integers (51*4=204bytes=1632bits), and will crash if you use a larger key buffer, so be warned.

The Way It Works

DH key exchange uses the following pattern (Bob (recipient) and Alice (sender) exchange messages, with Eve evesdropping).

First, the key format. This consists of three components g, x, and p.
g is the GENERATOR. Use a small prime, say 2, 3, 5, 7 etc.
x is the EXPONENT. This is the key, a random number of, say, 1024 bits.
p is the MODULUS. This is a large prime, typically of the same order as x (1024 bits).
Use CryptoApi, .NET crypto or any other service provider to create secure values and primes of this magnitude. Do not use Rnd!

1. Bob chooses a private key. (g, x1, and p) (generates these values)
   The magnitude of x1 is equivalent to the resulting encryption key size.
   x1 must be kept secret.
2. Bob calculates a new x2 value using x2 = g ^ x1 (mod p)
   Publishes this key (in a directory, web page, or email).
   g, x2, p

 [ EVE INTERCEPTS ]

3. Alice wants to send Bob secure data. She requires an encryption key. 
   She can establish a secret key with Bob, over a public medium, this way:
   Alice chooses a new random x3 value of the same order of magnitude as x2.
   She uses Bob's g and p values, leaving her with g, x3, p.
   x3 must be kept secret.
4. Alice calculates a public key x4 = g ^ x3 (mod p).
   She sends this to Bob over a public medium (g, x4, p). Bob aleady knows the values of g and p, since they are of his choosing. This can be a validation step - the values must match.

 [ EVE INTERCEPTS ]

5. Alice generates the encryption key x5 = x2 ^ x3 (mod p)
   Bob generates the encryption key x5 = x4 ^ x1 (mod p).

Alice and bob are now in possession of the same secret key. Eve intercepts all exchanges, but cannot (unless she is NSA!) derive the key value.

How does it work? To use an analogy from Simon Singh's The Code Book:
Say that keys are paint, in 3-pint tins. Alice and Bob agree on a public key - one pint of yellow paint. They each pick a secret color. Bob mixes one pint of yellow with 1 pint of his secret color, and sends this to Alice.
Alice mixes one pint of yellow with her secret color, and sends this to Bob.
Then Alice adds a pint of her secret color to Bob's tin, and Bob adds a pint of his secret color to Alice's tin.
Both tins are now the same color.
Eve can intercept the tins as they pass to and fro, she can even know that the public key is a pint of yellow. But she cannot determine the secret color because mixing paint is a one-way function.

Test Case (ALL NUMBERS IN HEX)

Follow this test case to see it working - note that in the real world, keys of 1000 bits or more would be used.
The symbol => refers to the result of calculating g ^ x (mod p). g, p are carried over.

   g=3 x1=9A2E p=10001 (Bob's private key, reused)<br />
 => g=3 x2=C366 p=10001 (Bob's public key, published, reused)<br />
 <br />
   g=3 x3=4C20 p=10001 (Alice's once-off random key, using Bob's g, p)<br />
 => g=3 x4=6246 p=10001 (Alice publishes this to Bob)<br />
<br />
   g=C366 x1=4C20 p=10001 (Alice calculates x2 ^ x3 (mod p))<br />
 => x5=DED4<br />
<br />
   g=6246 x4=9A2E p=10001 (Bob calculates x4 ^ x1 (mod p))<br />
 => x5=DED4

Alice and Bob have both arrived at the same value: DED4. This is the key! Alice encrypts the data using this secret key, and sends the encrypted data to Bob, along with the public value x4, which Bob uses to calculate the key. Eve cannot take advantage of this information due to the one-way function g^x(mod p).

Web Services Secure Exchange Example

The following schematic shows how DHM key exchange could be used in a distributed environment, say between Web Services.

Note: x is the private key on each side. This is not exchanged. p is the public key which is exchanged.

ALICE (CLIENT)                    BOB  (SERVER)
---------------------             ---------------------
b = acquire_dh_key(bob)       ->  get_dh_public( return p; )
x = make_dh_private(b)
p = make_dh_public(b,x)
c = make_dh_crypt(b,x)
encrypt_data(c)
send_data_and_key(bob,p,data) ->  c = make_dh_crypt(p,x)
                                  decrypt_data(c)

In this way, one request is made to determine the server's public key, another is made to transfer the encrypted data along with the public info required for the server to calculate the encryption key. If the server's public key is known/cached, then the data can be sent using a single method-call each time. It is up to Alice to select a random message key (x) each time data is sent.

Since encryption keys are not reused, security is enhanced.

Implementations

Be aware that you will likely write flaws into your encryption code if you implement it all yourself. If possible, use a service from an established CSP (Crypto Service Provider). The CryptoAPI on Win32 supports creating and calculating DH keys, so take a look around and see what use you can make of existing code, even if it's just the secure random number generators. .NET supports various key exchange mechanisms, but they rely on asymetric algorithms such as RSA to keep the actual key safe whilst in transit.

DH key exchange never transmits the actual encryption key. This is what makes it useful, and well suited to a distributed environment. Use a proper encryption algorithm like Rijndael (AES), but derive and transmit the key using DH mechanisms.

One possible implementation is to use a simple XML framework to transmit the data/key package, possibly similar to the following:

<br />
<?xml version="1.0" ?><br />
<encryptedpackage><br />
  <key>NK89FNOF8LNKASDFW0934LNF09VNOECR3M089DFCMFHE7823JRS==</key><br />
  <data>FGKMSDFVCFN879EC89SDFASDFUHNOGS7834RMIUSHDF78T3BOLKJ34289=</data><br />
</encryptedpackage><br />

Key and Data values are base64 encoded for embedding in an XML document.

Happy coding.

Caractacus
www.caradoc.co.za
Ah, yes, I thought so.

Thanks for the post. CP could do with a bit more in the way of crypto articles.

I've not looked at your source code, but I'm curious what if anything you do to mitigate small subgroup attacks? In particular, do you generate safe primes (prime p such that (p-1)/2 is also prime) or small subgroups (p-1) = kq for some integer k and prime q of length 256 bits? Absent such protections, DH key exchange can be attacked fairly easily by sending a g^x which is a member of a small subgroup.

See Practical Cryptography by Schneier and Ferguson for details.

Adam

Thanks for the reply. You are correct in noting that the diffie-hellman key exchange can suffer from certain types of attacks if the numbers or chosen badly. In the code I have posted it only generates 64-bit primes, and keys. Obviously this is not of a sufficient size for good security, but it serves as a demonstration of how it could be employed, and besides for general applications; for instance if someone wrote their own messenger this level of security would be adequate. I have not as yet generated "safe" primes, but it would be very simple to test this, and generate ones that are safe - I will modify my code shortly to encompass that (cheers Big Grin | :-D

). There is further trouble with diffie-hellman key exchange in that it suffers the man-in-the-middle attack which can only be resolved by use of digital signatures for authenticity checking.

I am looking into generating larger primes, and keys (i.e. 256-bit, and so on), but since the largest type you can have in c in __int64, I'd have to write my own number representation and calculation functions, do you have any suggestions of how this can be done?

When I find a way of representing and calculating in larger values, I will repost the code, and also add the "safe" prime checking, that way it should be of a good security level. I've read that 128-bit keys can be broken fairly trivially - do you know what of 256-bit or 512-bit (ignoring export controls for now!)?

Anyway, thanks for the post (it's nice to see some people on CP that take an interest in Cryptography).

Best Regards,

Lee Griffiths

MrLeeGriffiths wrote:
Thanks for the reply. You are correct in noting that the diffie-hellman key exchange can suffer from certain types of attacks if the numbers or chosen badly. In the code I have posted it only generates 64-bit primes, and keys. Obviously this is not of a sufficient size for good security, but it serves as a demonstration of how it could be employed, and besides for general applications; for instance if someone wrote their own messenger this level of security would be adequate.

I don't think 64-bit primes provide ANY security beyond the dangerous notional security that comes from "using encryption". Recall that the difficulty of brute-forcing x given g^x mod p distills to the computation of discrete logs in a finite field. There exist algorithms for this purpose which are sub-exponential; see the seminal work by Lenstra, Verheul [click the "PDF" link to view the document itself. Given the approximate algorithmic complexity of computing a discrete log over a finite field, a 64-bit prime is easily breakable on commodity hardware.

MrLeeGriffiths wrote:
There is further trouble with diffie-hellman key exchange in that it suffers the man-in-the-middle attack which can only be resolved by use of digital signatures for authenticity checking.

True, however this can be mitigated in a number of ways, depending upon the requirements and thread model of the application. For example, if both sides can pre-share their public keys with eachother, or the client knows the server's public key depending upon requirements, MiTM can be mitigated, albeit at increased management cost.

MrLeeGriffiths wrote:
I am looking into generating larger primes, and keys (i.e. 256-bit, and so on), but since the largest type you can have in c in __int64, I'd have to write my own number representation and calculation functions, do you have any suggestions of how this can be done?

I recently finished writing an arbitrary precision integer math library for my company [I assure you, I had valid reasons for not reusing existing libs], and having done that I can assure you that you'd be well-advised to find an open source bignum library instead Smile | :)

Libtommath is a decent bignum library written by the infamous crypto curmudgeon Tom St. Dennis of sci.crypt fame. MIRACL is a more comprehensive bignum library, which includes plenty of stuff you don't need for DH, but it is well-optimized and well-understood. Myriad other libs exist, including the bignum impl "bn" in the OpenSSL source tree (personally I don't like this one, as it's pretty well obfuscated, however it is good enough for the OpenSSL team...).

MrLeeGriffiths wrote:
When I find a way of representing and calculating in larger values, I will repost the code, and also add the "safe" prime checking, that way it should be of a good security level. I've read that 128-bit keys can be broken fairly trivially - do you know what of 256-bit or 512-bit (ignoring export controls for now!)?

I urge you to avoid the fallacy of comparing asymmetric cipher key sizes (DH, RSA, etc) with those of symmetric ciphers (DES, AES, etc). A 256-bit AES key is very secure; a 256-bit DH key is laughably insecure.

Having said that, Schneier and Ferguson (I also urge you to read and memorize Practical Cryptography, or failing that, Handbook of Applied Cryptography, which can be downloaded off the Web) recommend prime modulus lengths of at least 2048 bits. However, in practice, the key size you need depends upon what you are protecting; if you're using DH to exchange an 80-bit SKIPJACK key, or a 64-bit DES key, you may be able to get away with DH keys roughly equivalent in difficulty to an 80- or 64-bit symmetric key; if you're using AES-256, then equivalently-difficult DH will run about 15k bits, which obviously is untenable.

Recently I've done a bit of work with Elliptic Curve Cryptography, which is a family of asymmetric ciphers based on the mathematics of elliptic curves. Scalar multiplication of a point on a curve distills to the DLP, however without any known subexponential attack. Therefore, a 15k-bit DH key is (very, very roughly) equivalent in difficulty using known techniques as a 512-bit ECC key.

Practical Crypto doesn't have much to say about ECC; Certicom has a fair bit of ECC material (Scott Vanstone, a co-founder of Certicom, has done seminal work in the realm of EC and EC-based crypto), and the IEEE P1363 crypto std also has a decent bit of material.

Hope this helps.

Adam

Hi,
I should thank both of you for all these informations.
I am currently working on implementing a schema for the undeniable signature between two ipaqs on Pocket PC 2002, as a development tool I am using Embedded Visual C++ 3.0

I need to use big prime numbers (512 bits in average) and __int64 integers are not enough, I also need the miller-rabin primality test.

I was looking for some libraries written in C++ to generate big prime number for my algorithm that can work in an Pocket PC, but so far I did not find any,

If anyone has an idea on how to do that and which tools to use, I would be very greatuful.

Marouane OMG | :OMG:

Diffie-Hellman Key Exchange Example

Introduction

How to Use the Demo Project

Using the Source Code

Extra Functions

Further Help

License

Comments and Discussions