/*
  Author:  Pate Williams (c) 1997

  Exercise 1.1 (c)
  "Below are given four examples of cipehertext,
  one obtained from a Substitution Cipher, one
  from a Vigenere Cipher, one from an Affine
  Cipher, and one unspecified. In each case, the
  task is to determine the plaintext."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 40.
*/

#include <ctype.h>
#include <stdio.h>
#include <string.h>

struct code {long alpha, count;};

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 gcd(long a, long b)
{
  long r;

  while (b > 0)
    r = a % b, a = b, b = r;
  return a;
}

int main(void)
{
  char cipher[9][25] = {"KQEREJEBCPPCJCRKIEACUZ",
                        "BKRVPKRBCIBQCARBJCVFCUP",
                        "KRIOFKPACUZQEPBKRXPEII",
                        "EABDKPBCPFCDCCAFIEABDKP",
                        "BCPFEQPKAZBKRHAIBKAPCC",
                        "IBURCCDKDCCJCIDFUIXPAFF",
                        "ERBICZDFKABICBBENEFCUP",
                        "JCVKABPCYDCCDPKBCOCPERK",
                        "IVKSCPICBRKIJPKABI"};
  char answer[256], ciphertext[500];
  long a[2][2], iv[2][2], b[2], det, x[2];
  long count = 0, i, j;
  long frequency[26] = {0};
  struct code c[26], temp;

  for (i = 0; i < 9; i++) {
    for (j = 0; j < strlen(cipher[i]); j++) {
      ciphertext[count] = cipher[i][j];
      frequency[ciphertext[count] - 'A']++;
      count++;
    }
  }
  for (i = 0; i < 26; i++) {
    c[i].alpha = i + 'A';
    c[i].count = frequency[i];
  }
  /* sort the code array into descending order */
  for (i = 0; i < 25; i++)
    for (j = i + 1; j < 26; j++)
      if (c[i].count < c[j].count)
        temp = c[i], c[i] = c[j], c[j] = temp;
  for (i = 0; i < 26; i++)
    if (c[i].count != 0)
      printf("%c %ld\n", c[i].alpha, c[i].count);
  do {
    printf("guess for second most frequently");
    printf(" occurring character %c = ", c[1].alpha);
    scanf("%s", answer);
    a[0][0] = 'E' - 'A';
    a[0][1] = 1;
    a[1][0] = toupper(answer[0]) - 'A';
    a[1][1] = 1;
    b[0] = c[0].alpha - 'A';
    b[1] = c[1].alpha - 'A';
    iv[0][0] = a[1][1];
    iv[0][1] = - a[0][1];
    iv[1][0] = - a[1][0];
    iv[1][1] = a[0][0];
    det = (a[0][0] * a[1][1] - a[0][1] * a[1][0]) % 26;
    if (det < 0) det += 26;
    det = Extended_Euclidean(det, 26);
    x[0] = (det * (iv[0][0] * b[0] + iv[0][1] * b[1])) % 26;
    x[1] = (det * (iv[1][0] * b[0] + iv[1][1] * b[1])) % 26;
    if (x[0] < 0) x[0] += 26;
    if (x[1] < 0) x[1] += 26;
    printf("a = %ld\n", x[0]);
    printf("b = %ld\n", x[1]);
    printf("gcd(a, 26) = %ld\n", gcd(x[0], 26));
    if (x[0] != 0) {
      x[1] += 'A';
      det = Extended_Euclidean(x[0], 26);
      for (i = 0; i < count; i++) {
        b[0] = (det * (ciphertext[i] - x[1])) % 26;
        if (b[0] < 0) b[0] += 26;
        b[0] += 'A';
        printf("%c", b[0]);
        if ((i + 1) % 25 == 0) printf("\n");
      }
    }
    printf("\nanother guess (n or y)? ");
    scanf("%s", answer);
  } while (tolower(answer[0]) == 'y');
  return 0;
}