/*
  Author:  Pate Williams (c) 1997

  Exercise IV.3.6
  "Let p be the Fermat prime 65537, and let g = 5.
  You receive the message (29095, 23846), which
  your friend composed using the ElGamal
  cryptosystem in F_p*, using your public key
  g ^ a. Your secret key, needed for deciphering,
  is a = 13908. You have agreed to convert integers
  in F_p to trigraphs in the 31-letter alphabet of
  Exercise 3 by writing them to the base 31,
  the digits in the 31 ^ 2-, the 31-, and 1- place
  being numerical equivalents of the three letters
  in the trigraph. Decipher the message."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 109.
*/

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

char cipher_translate(long c)
{
  if (c < 26) return (char) (c + 'A');
  if (c == 26) return ' ';
  if (c == 27) return '.';
  if (c == 28) return '?';
  if (c == 29) return '!';
  return '\'';
}

int main(void)
{
  long a = 13908, b, p = 65537l;
  long g_k = 29095, P, c = 23846;
  verylong zP = 0, za = 0, zc = 0, zp = 0;
  verylong zg_k = 0, zg_ak = 0;

  zintoz(g_k, &zg_k);
  zintoz(c, &zc);
  zintoz(p, &zp);
  zsexpmod(zg_k, p - 1 - a, zp, &zg_ak);
  zmulmod(zc, zg_ak, zp, &zP);
  P = ztoint(zP);
  a = P / (31 * 31);
  P %= (31 * 31);
  b = P / 31;
  c = P % 31;
  P = ztoint(zP);
  printf("P = %ld\n", P);
  printf("%c%c%c\n", cipher_translate(a),
         cipher_translate(b), cipher_translate(c));
  zfree(&zP);
  zfree(&za);
  zfree(&zc);
  zfree(&zp);
  zfree(&zg_k);
  zfree(&zg_ak);
  return 0;
}