/*
  Author:  Pate Williams (c) 1997

  Exercise
  "6.2 Suppose I implement the ElGamal Signature
  Scheme with p = 31847, a = 5, and beta = 26379.
  Write a computer program does the following.
  (a) Verify the signature (20679, 11082) on the
      message x = 20543.
  (b) Determine my secret exponent, a, using
      Shanks time-memory tradeoff. Then determine
      the random value k used in signing the
      message x." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 231.
*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "lip.h"

struct data {long j, alpha_j;};

int fcmp(const void *d1, const void *d2)
{
  struct data *data1 = (struct data *) d1;
  struct data *data2 = (struct data *) d2;

  if (data1->alpha_j < data2->alpha_j) return - 1;
  if (data1->alpha_j > data2->alpha_j) return + 1;
  return 0;
}

long Shanks(long alpha, long beta, long p)
/* returns log(alpha, beta) in Z_p where
   alpha is a generator and beta is in Z_p */
{
  int found = 0;
  long i, log, m = ceil(sqrt(p - 1));
  struct data *table1 = calloc(m, sizeof(struct data));
  struct data *table2 = calloc(m, sizeof(struct data));
  struct data *d, key;
  verylong za = 0, zb = 0, zc = 0, zp = 0;
  verylong zalpha = 0, zalpha_i = 0;
  verylong zbeta = 0, zp1 = 0;

  if (!table1 || !table2) {
    fprintf(stderr, "*error*\nin sufficient memory\n");
    fprintf(stderr, "from Shanks\n");
    exit(1);
  }
  /* create a logarithm table */
  zintoz(alpha, &zalpha);
  zintoz(beta, &zbeta);
  zintoz(p, &zp);
  zintoz(p - 1, &zp1);
  zsexpmod(zalpha, m, zp, &zalpha_i);
  for (i = 0; i < m; i++) {
    table1[i].j = i;
    zsexpmod(zalpha_i, i, zp, &za);
    table1[i].alpha_j = ztoint(za);
  }
  zinvmod(zalpha, zp, &zalpha_i);
  for (i = 0; i < m; i++) {
    table2[i].j = i;
    zsexpmod(zalpha_i, i, zp, &za);
    zmulmod(zbeta, za, zp, &zb);
    table2[i].alpha_j = ztoint(zb);
  }
  /* sort the tables by second data item */
  qsort(table1, m, sizeof(struct data), fcmp);
  qsort(table2, m, sizeof(struct data), fcmp);
  for (i = 0; !found && i < m; i++) {
    key.j = table1[i].j;
    key.alpha_j = table1[i].alpha_j;
    d = bsearch(&key, table2, m, sizeof(struct data), fcmp);
    if (d) {
      zintoz(key.j, &za);
      zintoz(m, &zb);
      zmulmod(za, zb, zp1, &zc);
      zintoz(d->j, &za);
      zaddmod(za, zc, zp1, &zb);
      log = ztoint(zb);
      zsexpmod(zalpha, log, zp, &za);
      found = zcompare(za, zbeta) == 0;
    }
  }
  if (!found) log = 0;
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zp);
  zfree(&zalpha);
  zfree(&zalpha_i);
  zfree(&zbeta);
  zfree(&zp1);
  return log;
}

int main(void)
{
  long alpha = 5, beta = 26379, gamma = 20679;
  long a, k, delta = 11082, p = 31847, x = 20543;
  verylong za = 0, zb = 0, zc = 0, zk = 0, zp = 0;
  verylong zx = 0;
  verylong zalpha = 0, zbeta = 0, zgamma = 0;
  verylong zdelta = 0, zp1 = 0;

  zintoz(alpha, &zalpha);
  zintoz(beta, &zbeta);
  zintoz(gamma, &zgamma);
  zintoz(delta, &zdelta);
  zintoz(p, &zp);
  zintoz(x, &zx);
  zintoz(p - 1, &zp1);
  zexpmod(zbeta, zgamma, zp, &za);
  zexpmod(zgamma, zdelta, zp, &zb);
  zexpmod(zalpha, zx, zp, &zc);
  zmulmod(za, zb, zp, &zk);
  if (zcompare(zk, zc) == 0)
    printf("signature accepted\n");
  else
    printf("signature rejected\n");
  a = Shanks(alpha, beta, p);
  k = Shanks(alpha, gamma, p);
  printf("a = %ld\n", a);
  printf("k = %ld\n", k);
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zk);
  zfree(&zx);
  zfree(&zalpha);
  zfree(&zbeta);
  zfree(&zgamma);
  zfree(&zdelta);
  return 0;
}