/*
  Author:  Pate Williams (c) 1997

  Exercise
  "6.13 Suppose Bob is using the Pedersen-van Heyst
  Fail-stop Signature Scheme with p = 5087, alpha =
  25, and beta = 1866. Suppose the key is
  K = (5065, 5076, 144, 874, 1873, 2345).
  Now suppose Bob finds the signature (2219, 458)
  has been forged on the message 4785.
  (a) Prove that this forgery satisfies the
      verification condition, so it is a valid
      signature.
  (b) Show how Bob will compute the proof of
      forgery, a0, given this forged signature."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 232.
*/

#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 a0, a1 = 144, a2 = 874, b1 = 1873, b2 = 2345;
  long alpha = 25, beta = 1866, gamma1 = 5065;
  long gamma2 = 5076, p = 5087, q = (p - 1) >> 1;
  long r, s, x = 4785, y1 = 2219, y2 = 458, z1, z2;

  r = (gamma1 * exp_mod(gamma2, x, p)) % p;
  s = (exp_mod(alpha, y1, p) * exp_mod(beta, y2, p)) % p;
  if (r == s)
    printf("signature accepted\n");
  else
    printf("signature rejected\n");
  z1 = (a1 + x * b1) % q;
  z2 = (a2 + x * b2) % q;
  if (z2 > y2)
    a0 = ((y1 - z1) * Extended_Euclidean(z2 - y2, q)) % q;
  else
    a0 = ((z1 - y1) * Extended_Euclidean(y2 - z2, q)) % q;
  if (a0 < 0) a0 += q;
  printf("alpha = %ld\n", alpha);
  printf("beta = %ld\n", beta);
  printf("p = %ld\n", p);
  printf("q = %ld\n", q);
  printf("gamma1 = %ld\n", gamma1);
  printf("gamma2 = %ld\n", gamma2);
  printf("a1 = %ld\n", a1);
  printf("a2 = %ld\n", a2);
  printf("b1 = %ld\n", b1);
  printf("b2 = %ld\n", b2);
  printf("x  = %ld\n", x);
  printf("y1 = %ld\n", y1);
  printf("y2 = %ld\n", y2);
  printf("sig(%ld) = (%ld, %ld)\n", x, z1, z2);
  printf("a0 = %ld\n", a0);
  if (beta == exp_mod(alpha, a0, p))
    printf("a0 verified\n");
  else
    printf("a0 not verified\n");
  return 0;
}