/*
  Author:  Pate Williams (c) 1997

  Exercise
  "6.3 Suppose Bob is using the ElGamal Signature
  Scheme as implemented in Example 6.1; p = 467,
  alpha = 2, and beta = 132. Suppose Bob has signed
  the message x = 100 with the signature (29, 51).
  Compute the forged signature that Oscar can then
  form using h = 102, i = 45, and j = 293. Check
  that the resulting signature satisfies the
  verification condition." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 23l.
*/

#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 alpha = 2, beta = 132, h = 102, i = 45;
  long j = 293, p = 467, p1 = p - 1, x = 100;
  long gamma = 29, delta = 51;
  long lambda, mu, xp, r, s, t;

  r = exp_mod(gamma, h, p);
  s = exp_mod(alpha, i, p);
  t = exp_mod(beta, j, p);
  lambda = (r * s * t) % p;
  r = (h * gamma - j * delta) % p1;
  if (r < 0) r += p1;
  s = Extended_Euclidean(r, p1);
  mu = (delta * lambda * s) % p1;
  xp = (lambda * ((h * x + i * delta) % p1) * s) % p1;
  s = exp_mod(beta, lambda, p);
  t = exp_mod(lambda, mu, p);
  printf("alpha  = %ld\n", alpha);
  printf("beta   = %ld\n", beta);
  printf("gamma  = %ld\n", gamma);
  printf("delta  = %ld\n", delta);
  printf("p      = %ld\n", p);
  printf("x      = %ld\n", x);
  printf("lambda = %ld\n", lambda);
  printf("mu     = %ld\n", mu);
  printf("x'     = %ld\n", xp);
  if ((s * t) % p == exp_mod(alpha, xp, p))
    printf("forgery verified\n");
  else
    printf("forgery rejected\n");
  return 0;
}