/*
  Author:  Pate Williams (c) 1997

  Exercise IV.3.8
  "Suppose that your plaintext units are 18-letter
  blocks written in the usual 26-letter alphabet,
  where the numerical equivalent of such a block
  is an 18-digit base 26-integer (written in
  decreasing powers of 26). You receive the
  message
  g ^ k = 82746592004375034872957717
  Pg ^ ak = 164063768437915425954819351
  which was enciphered using the ElGamal
  cryptosystem in the prime field of
  p = 297262705009139006771611927 elements,
  using your public key g ^ a. Your secret key
  is a = 10384756843984756438549809. Decipher
  the message." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition pages 109-110.
*/

#include <stdio.h>
#include <string.h>
#include "lip.h"

void convert(char *a, verylong za)
{
  long i = 0;
  verylong zq = 0, zx = 0;

  zcopy(za, &zx);
  a[i] = (char) (zsdiv(zx, 26, &zq) + 'A');
  while (zscompare(zq, 0) > 0) {
    i++;
    zcopy(zq, &zx);
    a[i] = (char) (zsdiv(zx, 26, &zq) + 'A');
  }
  zfree(&zq);
  zfree(&zx);
}

void strtoz(char *s, verylong *zn)
{
  long i;
  verylong za = 0;

  zzero(zn);
  for (i = 0; i < strlen(s); i++) {
    zsmul(*zn, 10, &za);
    zsadd(za, s[i] - '0', zn);
  }
  zfree(&za);
}

int main(void)
{
  char a[64] = "10384756843984756438549809";
  char gk[64] = "82746592004375034872957717";
  char Pgak[64] = "164063768437915425954819351";
  char p[64] = "297262705009139006771611927";
  char buffer[64], s[64];
  long i, j;
  verylong zP = 0, za = 0, zb = 0, zc = 0, zp = 0;
  verylong zgk = 0, zPgak = 0;

  strtoz(a, &za);
  strtoz(p, &zp);
  strtoz(gk, &zgk);
  strtoz(Pgak, &zPgak);
  zsadd(zp, - 1, &zb);
  zsub(zb, za, &zc);
  zexpmod(zgk, zc, zp, &zb);
  zmulmod(zb, zPgak, zp, &zP);
  convert(buffer, zP);
  for (i = strlen(buffer) - 1, j = 0; i >= 0; i--, j++)
    s[j] = buffer[i];
  s[strlen(buffer)] = '\0';
  printf("%s\n", s);
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zp);
  zfree(&zgk);
  zfree(&zPgak);
  return 0;
}