|How to share a secret key|
I mentioned earlier the problem of sharing a secret key for use with symmetrical encryption, where you might be using an insecure channel.
There is a solution to this, called the Diffie-Hellman Key Exchange Protocol.
Basically this works by having each party generate a secret number (which they keep secret).
They then generate a "public key" by doing this calculation:
public = g ^ private (mod p)
That is, a generator (2 is a possible good choice) is raised to the power of the private key, modulus a large prime number p.
The two parties exchange their public keys.
Now they can each find a shared number by doing this calculation:
shared = other_public_key ^ my_private_key (mod p)
For example, given a generator of 2, and a prime number:
Prime number = 1012885251643 ("EBD4AA663B" in hex)
Generator = 2
Alice generates a secret key = 79C68E818 (eg. by hashing a randomly chosen phrase)
Alice works out her public key by doing this:
print (aes.dh ("2", "79C68E818", "EBD4AA663B" )) --> 7D458DBEF3
Alice sends this number (7D458DBEF3) to Bob.
Meanwhile, Bob generates a secret key = 49560AEC2
Bob works out his public key by doing this:
print (aes.dh ("2", "49560AEC2", "EBD4AA663B" )) --> 7D8A6551EE
Bob sends this number (7D8A6551EE) to Alice.
Alice can now work out the shared key by using Bob's public key (7D8A6551EE) and her secret key (79C68E818):
print (aes.dh ("7D8A6551EE", "79C68E818", "EBD4AA663B" )) --> 317261C804
Bob can also work out the shared key using Alice's public key (7D458DBEF3) and his secret key (49560AEC2):
print (aes.dh ("7D458DBEF3", "49560AEC2", "EBD4AA663B" )) --> 317261C804
Notice how at the end of this session, both Alice and Bob have arrived at the same shared secret (317261C804).
This can now be used by both of them for encrypting messages to each other.
The strength of this system is based on the problem of working out what the exponent must have been in the original calculation.
In practice, larger prime numbers are needed, otherwise an adversary to simply do an exhaustive search to find the key.
One method I have found of generating large prime numbers is to obtain GPG (Gnu Privacy Guard) and type this:
That was a 1024-bit prime number. However see caveat below - the prime number is supposed to have the property that (p-1)/2 is also prime. That particular prime does not have that property. I am now using the prime number recommended for the DNS system in RFC 2539.
To make this work in practice, I found a C implementation of the Diffie-Hellman at this page:
That version was very compact, and designed as a stand-alone program. The version below has been pretty-printed up a bit, and designed to interface with Lua.
I made a separate file in the aeslib project (dh.c) however you could simply add this code to the existing file given earlier in this post.
#define MAX_BYTES 1024
unsigned char prime[MAX_BYTES],
/* bytes = number of bytes in prime + 1 */
static int n, v, d, z, bytes;
static void a (unsigned char * x, unsigned char * y, int o)
d = 0;
for (v = bytes; v--;)
d += x[v] + y[v] * o;
x[v] = d;
d = d >> 8;
static void s (unsigned char * x)
for (v = 0; (v < bytes - 1) && (x[v] == prime[v]);)
if (x[v] >= prime[v])
a (x, prime, -1);
static void r (unsigned char * x)
d = 0;
for (v = 0; v < bytes;)
d |= x[v];
x[v++] = d / 2;
d = (d & 1) << 8;
static void M (unsigned char * x, unsigned char * y)
unsigned char X[MAX_BYTES], Y[MAX_BYTES];
memcpy (X, x, bytes);
memcpy (Y, y, bytes);
memset (x, 0, bytes);
for (z = bytes * 8; z--;)
if (X[bytes - 1] & 1)
a (x, Y, 1);
a (Y, Y, 1);
static void fromhex (char *x, unsigned char * y)
memset (y, 0, bytes);
for (n = 0; x[n] > 0; n++)
for (z = 4; z--;)
a (y, y, 1);
x[n] |= 32;
y[bytes - 1] |= x[n] - 48 - (x[n] > 96) * 39;
static void output (lua_State * L, unsigned char * x)
char buff [MAX_BYTES * 2 + 1];
char * p = buff;
for (n = 0; !x[n];)
for (; n < bytes; n++)
p += sprintf (p, "%c%c", 48 + x[n] / 16 + (x[n] > 159) * 7,
48 + (x[n] & 15) + 7 * ((x[n] & 15) > 9));
lua_pushstring (L, buff);
/* dh generator exponent prime */
int dh (lua_State * L)
unsigned char p [MAX_BYTES * 2],
g [MAX_BYTES * 2],
e [MAX_BYTES * 2];
const unsigned char * generatorText;
const unsigned char * exponentText;
const unsigned char * primeText;
/* get generator */
generatorText = luaL_checkstring (L, 1);
if ((strlen (generatorText) / 2) > (MAX_BYTES - 1))
luaL_error (L, "generator too long");
strcpy (g, generatorText);
/* get exponent */
exponentText = luaL_checkstring (L, 2);
if ((strlen (exponentText) / 2) > (MAX_BYTES - 1))
luaL_error (L, "exponent too long");
strcpy (e, exponentText);
/* get prime */
primeText = luaL_checkstring (L, 3);
if ((strlen (primeText) / 2) > (MAX_BYTES - 1))
luaL_error (L, "prime too long");
strcpy (p, primeText);
if (strlen (exponentText) > strlen (primeText))
luaL_error (L, "exponent length > prime length");
if (strlen (generatorText) > strlen (primeText))
luaL_error (L, "generator length > prime length");
// bytes in prime number
bytes = ((strlen (primeText) + 1) / 2) + 1;
fromhex (g, generator);
fromhex (e, exponent);
fromhex (p, prime);
memset (result, 0, bytes);
result[bytes - 1] = 1;
for (n = bytes * 8; n--;)
if (exponent[bytes - 1] & 1)
M (result, generator);
M (generator, generator);
output (L, result);
You also need to add the dh function to the list of the functions exported to Lua:
/* table of operations */
static const struct luaL_reg aeslib  =
// CBC encrypting
I do not think this code would be subject to any export restrictions, it is simply C code to raise a number to a power and take the modulus of the result. The code on its own cannot be used to encrypt messages, it simply lets you establish a shared secret.
Once this is successfully compiled, you can make a test for it. I did this test in the Immediate window of MUSHclient:
-- Diffie-Hellman Key Exchange
-- See: http://www.cypherspace.org/adam/rsa/dh-in-C.html
-- this took 29 seconds to run on my PC
assert (package.loadlib ("aeslib.dll", "luaopen_aes")) ()
generator = "2" -- see RFC 4419 - "It is recommended to use 2 as generator"
-- Prime number, got from RFC 2539 (also recommends 2 as the generator)
prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" ..
"FFFFFFFF" -- 1024 bits
Alice_secret = utils.hash ("Alice chooses some secret phrase that is her private key")
Alice_secret = string.sub (Alice_secret, 1, #prime - 1)
Alice_public = aes.dh (generator, Alice_secret, prime)
print ("Alice secret key = ", Alice_secret)
print ("Alice public key = ", Alice_public)
-- work out the public key Bob sends to Alice
Bob_secret = utils.hash ("Bob has a secret phrase we worked out from a book")
Bob_secret = string.sub (Bob_secret, 1, #prime - 1)
Bob_public = aes.dh (generator, Bob_secret, prime)
print ("Bob secret key = ", Bob_secret)
print ("Bob public key = ", Bob_public)
-- work out the shared secret
Shared_secret_A = aes.dh (Alice_public, Bob_secret, prime)
print ("Shared secret - method A = ", Shared_secret_A)
Shared_secret_B = aes.dh (Bob_public, Alice_secret, prime)
print ("Shared secret - method B = ", Shared_secret_B)
-- check the same
assert (Shared_secret_A == Shared_secret_B)
x = aes.encrypt ("Nick Gammon", Shared_secret_A)
y = aes.decrypt (x, Shared_secret_A)
print (y) --> Nick Gammon
As noted in the code, this isn't the fastest algorithm in the world - it takes 29 seconds to run on my PC. However exchanging secret keys is something you don't do every minute. Also, the test above does the calculations for both parties (Alice and Bob), when in practice they would each do half of it.
The output of the above test was:
Alice secret key = 79c68e818a0c4d84f8c68d7904897200dfa488f2
Alice public key = 855F0FE034691F3B3D3B0FAE03A498D3820E6F50
Bob secret key = 49560aec25e73db6e2154f53c7c7b9f666b0d533
Bob public key = 74C1BA20B83E794F3243CCA924C48088EA7AA598E6
Shared secret - method A = A1E21E54817DDA58306CE8CA32CADB20
Shared secret - method B = A1E21E54817DDA58306CE8CA32CADB20
In practice, Alice would send a message (eg. an email) to Bob, saying:
generator = "2"
prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08
my_public_key = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50
Bob would use the same generator and prime, but make his own secret key, and then reply with:
my_public_key = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6
Now they are both in a position to calculate the shared key, and use that to encrypt messages to each other. You can see from the test that both Alice and Bob end up with the same shared key.
Of course, in practice, you would change the secret keys (Alice_secret and Bob_secret) to be something that only you know. One way would be to roll dice, look up words randomly in a book, get a bingo game, that sort of thing.
For more information, search the web for "Diffie-Hellman" - you will find thousands of pages describing it, and various comments about it.
According to the web page cited earlier: The time to calculate a modular exponent is roughly proportional to the cube of the number of bits, so if a 1024-bit number takes 5 minutes, a 2048-bit number will take 40 minutes, and a 4096-bit number would take about 5 hours.
I found in my case that whilst using a 1024-bit prime number the above test took 29 seconds to run, with at 2048-bit prime number it took about 4 minutes.
A larger prime number is certainly more secure, but the time taken to generate the public and shared keys is somewhat longer. However, as I said before, you only need to do this once per shared key you need to establish, it might not bother you if it takes an hour to work out the shared key.
For more security you probably need a larger secret key (the hash algorithm only generates a 160-bit hash), you might consider using the sha256 hash to generate a longer hash.
- Nick Gammon
| top |