/*
  Author:  Pate Williams (c) 1997

  Exercise
  "5.4 Decrypt the ElGamal ciphertext presented in
  Table 5.3. The parameters of the system are
  p = 31847, alpha = 5, a = 7899, beta = 18074.
  Each element of Z_n represents three alphabetic
  characters as in Exercise 4.6."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice by Douglas
  R. Stinson page 200.
*/

#include <stdio.h>

struct ciphertext {long y1, y2;};

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;
}

long decrypt(long a, long p, struct ciphertext y)
{
  long z = exp_mod(y.y1, a, p);

  z = Extended_Euclidean(z, p);
  return (y.y2 * z) % p;
}

int main(void)
{
  char abc[26] = "abcdefghijklmnopqrstuvwxyz";
  long a = 7899l, p = 31847l, i, t, x;
  struct ciphertext y[40] = {{ 3781l, 14409l}, {31552l,  3930l},
                             {27214l, 15442l}, { 5809l, 30274l},
                             { 5400l, 31486l}, {19936l,   721l},
                             {27765l, 29284l}, {29820l,  7710l},
                             {31590l, 26470l}, { 3781l, 14409l},
                             {15898l, 30844l}, {19048l, 12914l},
                             {16160l,  3129l}, {  301l, 17252l},
                             {24689l,  7776l}, {28856l, 15720l},
                             {30555l, 24611l}, {20501l,  2922l},
                             {13659l,  5015l}, { 5740l, 31233l},
                             { 1616l, 14170l}, { 4294l,  2307l},
                             { 2320l, 29174l}, { 3036l, 20132l},
                             {14130l, 22010l}, {25910l, 19663l},
                             {19557l, 10145l}, {18899l, 27609l},
                             {26004l, 25056l}, { 5400l, 31486l},
                             { 9526l,  3019l}, {12962l, 15189l},
                             {29538l,  5408l}, { 3149l,  7400l},
                             { 9396l,  3058l}, {27149l, 20535l},
                             { 1777l,  8737l}, {26117l, 14251l},
                             { 7129l, 18195l}, {25302l, 10248l}};

  printf("the ciphertext pairs (y1,y2) are:\n");
  for (i = 0; i < 40; i++) {
    printf("(%5ld, %5ld) ", y[i].y1, y[i].y2);
    if ((i + 1) % 4 == 0) printf("\n");
  }
  printf("the corresponding plaintext is:\n");
  for (i = 0; i < 40; i++) {
    x = decrypt(a, p, y[i]);
    t = x / 676l;
    x = x % 676l;
    printf("%c", abc[t]);
    t = x / 26l;
    x = x % 26l;
    printf("%c", abc[t]);
    printf("%c", abc[x]);
    if ((i + 1) % 8 == 0) printf("\n");
  }
  return 0;
}