/*
  Author:  Pate Williams (c) 1997

  Exercise 8.4
  "Suppose that U and V carry out the MTI Protocol
  where p = 30113 and alpha = 52. Suppose that U
  has a_u = 8642 and chooses r_u = 28654, and V
  has a_v = 24763 and chooses r_v = 12385. 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 = 52, p = 30113;
  long a_u = 8642, a_v = 24763;
  long r_u = 28654, r_v = 12385;
  long b_u, b_v, s_u, s_v, K_uv, K_vu;

  b_u = exp_mod(alpha, a_u, p);
  b_v = exp_mod(alpha, a_v, p);
  s_u = exp_mod(alpha, r_u, p);
  s_v = exp_mod(alpha, r_v, p);
  K_uv = (exp_mod(s_v, a_u, p) * exp_mod(b_v, r_u, p)) % p;
  K_vu = (exp_mod(s_u, a_v, p) * exp_mod(b_u, r_v, p)) % 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("r_u = %ld\n", r_u);
  printf("r_v = %ld\n", r_v);
  printf("b_u = %ld\n", b_u);
  printf("b_v = %ld\n", b_v);
  printf("K_u,v = %ld\n", K_uv);
  printf("K_v,u = %ld\n", K_vu);
  return 0;
}