/*
  Author:  Pate Williams (c) 1997

  Exercise 1.1 (d)
  "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 pages 40 - 41.
*/

#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[17][26] = {"BNVSNSIHQCEELSSKKYERIFJKX",
                         "UMBGYKAMQLJTYAVFBKVT",
                         "DVBPVVRJYYLAOKYMPQSCGDLFS",
                         "RLLPROYGESEBUUALRWXM",
                         "MASAZLGLEDFJBZAVVPXWICGJX",
                         "ASCBYEHOSNMULKCEAHTQ",
                         "OKMFLEBKFXLRRFDTZXCIWBJSI",
                         "CBGAWDVYDHAVFJXZIBKC",
                         "GJIWEAHTTOEWTUHKRQVVRGZBX",
                         "YIREMMASCSPBNLHJMBLR",
                         "FFJELHWEYLWISTFVVYFJCMHYU",
                         "YRUFSFMGESIGRLWALSWM",
                         "NUHSIMYYITCCQPZSICEHBCCMZ",
                         "FEGVJYOCDEMMPGHVAAUM",
                         "HYGGCKTMBLRX"};
  char ciphertext[500], plaintext[500];
  char keyword[16], known[] = "IGREWUPAMONGSLOW";
  char word_1[4], word_2[4];
  int found = 0;
  long count = 0, frequency[26] = {0}, i, j;
  long distance[16], o_count = 0, occur[16];
  long key_length;
  struct code c[26], temp;

  /* tabulate character frequencies */
  for (i = 0; i < 17; i++) {
    for (j = 0; j < strlen(cipher[i]); j++) {
      ciphertext[count] = cipher[i][j];
      frequency[ciphertext[i] - '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);
  /* perform the Kasiski test */
  for (i = 0; !found && i < count - 2; i++) {
    word_1[0] = ciphertext[i];
    word_1[1] = ciphertext[i + 1];
    word_1[2] = ciphertext[i + 2];
    word_1[3] = '\0';
    occur[0] = i;
    o_count = 1;
    for (j = i + 3; j < count - 2; j++) {
      word_2[0] = ciphertext[j];
      word_2[1] = ciphertext[j + 1];
      word_2[2] = ciphertext[j + 2];
      word_2[3] = '\0';
      if (strcmp(word_1, word_2) == 0)
        occur[o_count++] = j;
    }
    found = o_count > 3;
  }
  if (found) {
    for (i = 0; i < o_count - 1; i++)
      distance[i] = occur[i + 1] - occur[i];
    key_length = gcd(distance[0], distance[1]);
    for (i = 2; i < o_count - 1; i++)
      key_length = gcd(key_length, distance[i]);
  }
  else {
    double IC, sum;
    char answer[256];
    long col, k, m, n;
    found = 0;
    n =  count;
    for (m = 1; !found && m < 15; m++) {
      col = n / m;
      i = 0;
      for (j = 0; j < m; j++) {
        for (k = 0; k < 26; k++) frequency[k] = 0;
        for (k = 0; k < col; k++)
          frequency[ciphertext[i++] - 'A']++;
        sum = 0.0;
        for (k = 0; k < 26; k++)
          sum += frequency[k] * (frequency[k] - 1);
        IC = sum / (col * (col - 1));
        printf("Ic = %lf\n", IC);
      }
      printf("another value of m = %ld (n or y)? ", m);
      scanf("%s", answer);
      found = tolower(answer[0]) == 'n';
      if (found) key_length = m;
    }
  }
  printf("keyword length = %ld\n", key_length);
  for (i = 0; i < key_length; i++) {
    keyword[i] = (char) (ciphertext[i] - known[i]);
    if (keyword[i] < 0) keyword[i] += (char) 26;
    keyword[i] += (char) 'A';
  }
  keyword[key_length] = '\0';
  printf("keyword = %s\n", keyword);
  for (i = 0; i < count - key_length; i += key_length) {
    for (j = 0; j < key_length; j++) {
      plaintext[i + j] = (char) (ciphertext[i + j] - keyword[j]);
      if (plaintext[i + j] < 0) plaintext[i + j] += (char) 26;
      plaintext[i + j] += (char) 'A';
    }
  }
  for (i = 0; i < count - key_length; i++) {
    printf("%c", plaintext[i]);
    if ((i + 1) % 25 == 0) printf("\n");
  }
  printf("\n");
  return 0;
}