/*
  Author:  Pate Williams (c) 1997

  Exercise IV.3.4
  "You receive the ciphertext "VHNHDOAM", which was
  sent to you using a 2 by 2 enciphering matrix
  | a b |
  | c d |
  applied to digraphs in the usual 26-letter
  alphabet. The enciphering matrix was determined
  using the Diffie-Hellman key exchange method,
  as follows. Working in the prime field of
  3602561 elements, your correspondent sent you
  g ^ b = 983776. Your randomly chosen
  Diffie-Hellman exponent a is 1082389. Finally,
  you agree to get a matrix from a key number
  K_E in F_3602561 by writing the least
  nonnegative residue of K_E modulo 26 ^ 4 in
  the form a * 26 ^ 3 + b * 26 ^ 2 + c * 26 + d
  (where a, b, c, d are digits in base 26). If
  the matrix is not invertible modulo 26,
  replace K_E by K_E + 1 and try again. Take as
  the enciphering matrix the first invertible
  matrix that arises from the successive integers
  starting with K_E.
  (a) Use this information to find the enciphering
  matrix.
  (b) Find the deciphering matrixm, and read the
  message." -Neal Koblitz-
  See "A Course in Number Theory and "Cryptography"
  by Neal Koblitz second edition pages 108-109.
*/

#include <stdio.h>
#include <string.h>
#include "lip.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;
}

int main(void)
{
  char ciphertext[16] = "VHNHDOAM";
  long a = 1082389l, g_b = 983776l, p = 3602561l;
  long A, B, C, D, K_E, m4 = 26 * 26 * 26 * 26;
  long m3 = 26 * 26 * 26, m2 = 26 * 26, det, i;
  long b, c, d, r, s, x, y;
  verylong za = 0, zb = 0, zd = 0, zp = 0;
  verylong zK_E = 0, zg_b = 0;

  zintoz(g_b, &zg_b);
  zintoz(a, &za);
  zintoz(26, &zb);
  zintoz(p, &zp);
  zexpmod(zg_b, za, zp, &zK_E);
  for (;;) {
    K_E = zsmod(zK_E, m4);
    A = K_E / m3;
    K_E %= m3;
    B = K_E / m2;
    K_E %= m2;
    C = K_E / 26;
    D = K_E % 26;
    det = (A * D - B * C) % 26;
    if (det != 0) {
      det = Extended_Euclidean(det, 26);
      if (det != 0) break;
    }
    zsadd(zK_E, 1, &za);
    zcopy(za, &zK_E);
  }
  a = (det * D) % 26;
  d = (det * A) % 26;
  b = (- det * B) % 26;
  c = (- det * C) % 26;
  if (b < 0) b += 26;
  if (c < 0) c += 26;
  printf("the enciphering matrix is:\n");
  printf("| %2ld %2ld |\n", A, B);
  printf("| %2ld %2ld |\n", C, D);
  printf("the deciphering matrix is:\n");
  printf("| %2ld %2ld |\n", a, b);
  printf("| %2ld %2ld |\n", c, d);
  printf("%s\n", ciphertext);
  for (i = 0; i < strlen(ciphertext); i += 2) {
    r = ciphertext[i] - 'A';
    s = ciphertext[i + 1] - 'A';
    x = (a * r + b * s) % 26;
    y = (c * r + d * s) % 26;
    printf("%c%c", x + 'A', y + 'A');
  }
  printf("\n");
  zfree(&za);
  zfree(&zb);
  zfree(&zd);
  zfree(&zp);
  zfree(&zK_E);
  zfree(&zg_b);
  return 0;
}