Message
 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 DiffieHellman 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:
Output: BA0BB972EED88B2B2D8FB3BAB587CFA9FC5811DAE457C88BADB8690DB5D494EC6D91D6
B29F59EEECB42E4494A48F072AB61A490562F7E631D768E986EF56DE17BBE19BB8FC94F6EF07C1
5409427CA726C885E68502ABED8C63B9BBBF4E1568E4C8032E43C257CA4413E98B701CA4F8BD1C
9B61BE26014073244EF552FD386B8B
That was a 1024bit prime number. However see caveat below  the prime number is supposed to have the property that (p1)/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 DiffieHellman at this page:
http://www.cypherspace.org/adam/rsa/dhinC.html
That version was very compact, and designed as a standalone program. The version below has been prettyprinted 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.
#include "lua.h"
#include "lauxlib.h"
#include <string.h>
#define MAX_BYTES 1024
unsigned char prime[MAX_BYTES],
generator[MAX_BYTES],
exponent[MAX_BYTES],
result[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]);)
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);
s (x);
}
r (X);
a (Y, Y, 1);
s (Y);
}
}
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];)
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);
r (exponent);
}
output (L, result);
return 1;
}
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
{"encrypt", encrypt},
{"decrypt", decrypt},
// DiffieHellman
{"dh", dh},
#ifdef TEST
{"test", test},
#endif
{NULL, NULL}
};
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:
 DiffieHellman Key Exchange
 See: http://www.cypherspace.org/adam/rsa/dhinC.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" ..
"8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D" ..
"F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6" ..
"F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF" ..
"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
CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F
423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3
B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3
5279BDAC1073AC94F82370EDC4A4A0AB5A9C
Bob secret key = 49560aec25e73db6e2154f53c7c7b9f666b0d533
Bob public key = 74C1BA20B83E794F3243CCA924C48088EA7AA598E6
8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0
1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03
429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5
5B6CC0A236C3337885A110FB0DDFD6057F
Shared secret  method A = A1E21E54817DDA58306CE8CA32CADB20
25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72
1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376
6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1
71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06
Shared secret  method B = A1E21E54817DDA58306CE8CA32CADB20
25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72
1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376
6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1
71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06
Nick Gammon
In practice, Alice would send a message (eg. an email) to Bob, saying:
generator = "2"
prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08
8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D
F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6
F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF
FFFFFFFF"
my_public_key = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50
CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F
423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3
B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3
5279BDAC1073AC94F82370EDC4A4A0AB5A9C"
Bob would use the same generator and prime, but make his own secret key, and then reply with:
my_public_key = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6
8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0
1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03
429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5
5B6CC0A236C3337885A110FB0DDFD6057F"
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 "DiffieHellman"  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 1024bit number takes 5 minutes, a 2048bit number will take 40 minutes, and a 4096bit number would take about 5 hours.
I found in my case that whilst using a 1024bit prime number the above test took 29 seconds to run, with at 2048bit 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 160bit hash), you might consider using the sha256 hash to generate a longer hash.

 Nick Gammon
www.gammon.com.au, www.mushclient.com  top 
