/*
  Author:  Pate Williams (c) 1997

  Exercise III.1.11
  "You intercept the coded message
  "DXM SCE DCCUVGX ", which was enciphered using
  an affine map on the digraphs in a 30-letter
  alpahbet, in which A-Z have the numerical
  equivalents 0-25, blank = 26, ? = 27, ! = 28,
  ' = 29. A frequency analysis shows that the
  most common digraphs in earlier ciphertexts
  are "M ", "U ", and "IH", in that order.
  Suppose that in the English language the most
  frequenntly occurring digraphs (in this
  particular 30-letter alphabet) are "E ", "S ",
  and " T" in that order.
  (a) Find the deciphering key, and read the
  message.
  (b) Find the enciphering key, and encrypt the
  message "YES I'M JOKING!"." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 63.
*/

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

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

long plain_translate(char c)
{
  if (c >= 'A' && c <= 'Z') return c - 'A';
  if (c == ' ') return 26;
  if (c == '?') return 27;
  if (c == '!') return 28;
  return 29;
}

int main(void)
{
  char ciphertext[32] = "DXM SCE DCCUVGX ", plaintext[32];
  char plaintext1[32] = "YES I'M JOKING!", ciphertext1[32];
  long a, ap, b, bp, c, d, i, p, n = 30, N = n * n;
  long A[2][2], B[2], C[2][2];

  A[0][0] = ('E' - 'A') * n + (' ' - ' ' + 26);
  A[0][1] = 1;
  A[1][0] = (' ' - ' ' + 26) * n + ('T' - 'A');
  A[1][1] = 1;
  B[0] = ('M' - 'A') * n + ' ' - ' ' + 26;
  B[1] = ('I' - 'A') * n + 'H' - 'A';
  d = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % N;
  if (d < 0) d += N;
  d = Extended_Euclidean(d, N);
  if (d == 0)
    printf("determinant is zero, solution does not exist\n");
  else {
    C[0][0] = (d * A[1][1]) % N;
    C[1][1] = (d * A[0][0]) % N;
    C[0][1] = - (d * A[0][1]) % N;
    C[1][0] = - (d * A[1][0]) % N;
    a = (C[0][0] * B[0] + C[0][1] * B[1]) % N;
    b = (C[1][0] * B[0] + C[1][1] * B[1]) % N;
    if (a < 0) a += N;
    if (b < 0) b += N;
    ap = Extended_Euclidean(a, N);
    bp = (- ap * b) % N;
    if (bp < 0) bp += N;
    printf("a  = %ld\n", a);
    printf("b  = %ld\n", b);
    printf("a' = %ld\n", ap);
    printf("b' = %ld\n", bp);
    for (i = 0; i < strlen(ciphertext); i += 2) {
      c = plain_translate(ciphertext[i]) * n
        + plain_translate(ciphertext[i + 1]);
      p = (ap * c + bp) % N;
      if (p < 0) p += N;
      plaintext[i] = cipher_translate(p / n);
      plaintext[i + 1] = cipher_translate(p % n);
    }
    plaintext[strlen(ciphertext)] = '\0';
    printf("%s\n", ciphertext);
    printf("%s\n", plaintext);
    for (i = 0; i < strlen(plaintext1); i += 2) {
      p = plain_translate(plaintext1[i]) * n
        + plain_translate(plaintext1[i + 1]);
      c = (a * p + b) % N;
      if (c < 0) c += N;
      ciphertext1[i] = cipher_translate(c / n);
      ciphertext1[i + 1] = cipher_translate(c % n);
    }
  }
  ciphertext1[strlen(plaintext1)] = '\0';
  printf("%s\n", plaintext1);
  printf("%s\n", ciphertext1);
  return 0;
}