/*
  Author:  Pate Williams (c) 1997

  Exercise
  "6.6 Suppose Bob uses the DSS with q = 101, p = 7879,
  alpha = 170, a = 75, and beta = 4567, as in Example
  6.3. Determine Bob's signature on the message
  x = 5001 using the random value k = 49, and show how
  the resulting signature is verified."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by Douglas
  R. Stinson page 231.
*/

#include <stdio.h>

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

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 a = 75, alpha = 170, beta = 4567, k = 49;
  long p = 7879, q = 101, x = 5001;
  long delta, e1, e2, gamma, r, s, t;

  gamma = exp_mod(alpha, k, p) % q;
  r = Extended_Euclidean(k, q);
  delta = ((x + (a * gamma) % q) * r) % q;
  r = Extended_Euclidean(delta, q);
  e1 = (x * r) % q;
  e2 = (gamma * r) % q;
  r = exp_mod(alpha, e1, p);
  s = exp_mod(beta, e2, p);
  t = ((r * s) % p) % q;
  printf("a     = %ld\n", a);
  printf("k     = %ld\n", k);
  printf("p     = %ld\n", p);
  printf("q     = %ld\n", q);
  printf("x     = %ld\n", x);
  printf("alpha = %ld\n", alpha);
  printf("beta  = %ld\n", beta);
  printf("delta = %ld\n", delta);
  printf("gamma = %ld\n", gamma);
  printf("e1    = %ld\n", e1);
  printf("e2    = %ld\n", e2);
  printf("ver   = %ld\n", t);
  if (t == gamma)
    printf("signature accepted\n");
  else
    printf("signature rejected\n");
  return 0;
}