/*
  Author:  Pate Williams (c) 1997

  Exercise 8.3
  "Suppose that U and V carry out the Diffie-Hellman
  Key Exchange with p = 27001 and alpha = 101.
  Suppose that U chooses a_u = 21768 and V chooses
  a_v = 9898. Show the computations performed by
  both U and V, and determine the key they will
  compute." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 282.
*/

#include <stdio.h>

long exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1l, s = x;

  while (b != 0) {
    if (b & 1l) a = (a * s) % n;
    b >>= 1;
    if (b != 0) s = (s * s) % n;
  }
  return a;
}

int main(void)
{
  long alpha = 101, p = 27001;
  long a_u = 21768, a_v = 9898, b_u, b_v;
  long k_vu, k_uv;

  b_u = exp_mod(alpha, a_u, p);
  b_v = exp_mod(alpha, a_v, p);
  k_vu = exp_mod(b_u, a_v, p);
  k_uv = exp_mod(b_v, a_u, p);
  printf("alpha = %ld\n", alpha);
  printf("p = %ld\n", p);
  printf("a_u = %ld\n", a_u);
  printf("a_v = %ld\n", a_v);
  printf("b_u = %ld\n", b_u);
  printf("b_v = %ld\n", b_v);
  printf("K_v,u = %ld\n", k_vu);
  printf("K_u,v = %ld\n", k_uv);
  return 0;
}