Gammon Forum

t = { 1234, 5678, 9876, 5432 }
MtSrand (t) -- seed with table of seeds

public = g ^ private (mod p)

shared = other_public_key ^ my_private_key (mod p)

print (aes.dh ("2", "79C68E818", "EBD4AA663B" )) --> 7D458DBEF3

print (aes.dh ("2", "49560AEC2", "EBD4AA663B" )) --> 7D8A6551EE

print (aes.dh ("7D8A6551EE", "79C68E818", "EBD4AA663B" )) --> 317261C804

print (aes.dh ("7D458DBEF3", "49560AEC2", "EBD4AA663B" )) --> 317261C804

gpg --gen-prime 1 1024

#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;
}

/* table of operations */
static const struct luaL_reg aeslib [] = 
  {
  // CBC encrypting
  {"encrypt", encrypt},
  {"decrypt", decrypt},

  // Diffie-Hellman
  {"dh", dh},

#ifdef TEST
  {"test", test},
#endif

  {NULL, NULL}
  };

aes.h     lua.h       luaconf.h   sha256.h
aes.c     aeslib.c    lauxlib.h   lua5.1.dll  sha256.c

#define LUA_API __declspec(dllexport)

#define LUA_BUILD_AS_DLL
#define LUA_LIB

-- converts a hex string into a big number
function hex_to_bignum (h)
  local result = bc.number (0)
  local c, n
  assert (not string.match (h, "%X")) -- must be in hex
  for i = 1, #h do
    c = string.sub (h, i, i)  -- pull out digit
    n = tonumber (c, 16)      -- convert base-16 (hex) to decimal
    result = result * 16 + n  -- previous result 16 larger, then add in this digit
  end -- for
  
  return result
end -- function hex_to_bignum 

-- See: http://en.wikipedia.org/wiki/Modular_exponentiation
-- (Right-to-left binary method)

function modular_pow (base, exponent, modulus)
  local old_digits = bc.digits (0)  -- working with integers
  local result = bc.number (1)

  base = bc.number (base)
  exponent = bc.number (exponent)
  modulus = bc.number (modulus)
  
  while not bc.iszero (exponent) do
    if not bc.iszero (bc.mod (exponent, 2)) then
      result = bc.mod (result * base, modulus)
    end -- if
    exponent = exponent / 2
    base = bc.mod (base * base, modulus)
  end -- while
  
  bc.digits (old_digits)  -- back to old number of digits
  return result
end -- function modular_pow 

generator = 2

prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" ..
"8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D" ..
"F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6" ..
"F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF" ..
"FFFFFFFF" -- 1024 bits


print ("prime (dec) = ", hex_to_bignum (prime))

Alice_secret = utils.hash ("Alice chooses some secret phrase that is her private key")
Alice_secret = string.sub (Alice_secret, 1, #prime - 1)

print ("Alice_secret (hex) =", Alice_secret)
print ("Alice_secret (dec) =", hex_to_bignum (Alice_secret))

Alice_public = modular_pow (generator, hex_to_bignum (Alice_secret), hex_to_bignum (prime))

print ("result = ", Alice_public)

expected = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50" ..
"CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F" .. 
"423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3" ..
"B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3" ..
"5279BDAC1073AC94F82370EDC4A4A0AB5A9C"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Alice_public == hex_to_bignum (expected))


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

print ("Bob_secret (hex) =", Bob_secret)
print ("Bob_secret (dec) =", hex_to_bignum (Bob_secret ))

Bob_public = modular_pow (generator, hex_to_bignum (Bob_secret), hex_to_bignum (prime))

print ("result = ", Bob_public )

expected = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6" .. 
"8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0" ..
"1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03" ..
"429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5" ..
"5B6CC0A236C3337885A110FB0DDFD6057F"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Bob_public == hex_to_bignum (expected))


-- work out the shared secret
Shared_secret_A = modular_pow (Alice_public, hex_to_bignum (Bob_secret), hex_to_bignum (prime))

print ("Shared secret - method A = ", Shared_secret_A)

Shared_secret_B = modular_pow (Bob_public, hex_to_bignum (Alice_secret), hex_to_bignum (prime))

print ("Shared secret - method B = ", Shared_secret_B)

expected = "A1E21E54817DDA58306CE8CA32CADB20" ..
"25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72" ..
"1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376" ..
"6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1" ..
"71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Shared_secret_B == hex_to_bignum (expected))