/*
  Author:  Pate Williams (c) 1997

  Example 1.11
  "Ciphertext obtained from a Vigenere Cipher:
  CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW
  RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWAIK
  LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX
  VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR
  ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT
  AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI
  PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP
  WQAIIWXNRMGWOIIFKEE" -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 33.
*/

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

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[15][25] = {"CHREEVOAHMAERATBIAXXWTN",
                         "XBEEOPHBSBQMQEQERBW",
                         "RVXUOAKXAOSXXWEAHBWGJMM",
                         "QMNKGRFVGXWTRZXWAIK",
                         "LXFPSKAUTEMNDCMGTSXMXBT",
                         "UIADNGMGPSRELXNJELX",
                         "VRVPRTULHDNQWTWDTYGBPHX",
                         "TFALJHASVBFXNGLLCHR",
                         "ZBWELEKMSJIKNBHWRJGNMGJ",
                         "SGLXFEYPHAGNRBIEQJT",
                         "AMRVLCRREMNDGLXRRIMGNSN",
                         "RWCHRQHAEYEVTAQEBBI",
                         "PEEWEVKAKOEWADREMXMTBHH",
                         "CHRTKDNVRZCHRCLQOHP",
                         "WQAIIWXNRMGWOIIFKEE"};
  char answer[256], ciphert[500], ciphertext[500];
  char keyword[16], word_1[4], word_2[4];
  double Ic, MIc[16][16][26], sum;
  int found = 0;
  long count = 0, i, j, k, o_count = 0, occur[16];
  long col, frequency[26] = {0}, key_length, m, n;
  long f[26], fp[26], g, l, plaintext;

  /* tabulate ciphertext frequencies */
  for (i = 0; i < 15; i++)
    for (j = 0; j < strlen(cipher[i]); j++)
      ciphertext[count] = ciphert[count++] = cipher[i][j];
  /* 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];
    o_count = 1;
    occur[0] = i;
    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];
      if (strcmp(word_1, word_2) == 0) {
        occur[o_count] = j;
        o_count++;
      }
    }
    found = o_count >= 3;
  }
  key_length = gcd(occur[0], occur[1]);
  for (i = 2; i < o_count; i++)
    key_length = gcd(key_length, occur[i]);
  printf("total number of ciphertext characters = %ld\n", count);
  printf("keyword length = %ld\n", key_length);
  /* compute indices of coincidence */
  found = 0;
  n = count;
  for (m = 2; !found && m < 15; m++) {
    col = n / m;
    i = 0;
    for (j = 0; j < col; j++)
      for (k = 0; k < m; k++)
        ciphertext[k * col + j] = ciphert[i++];
    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 = %4.3lf\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);
  col = count / key_length;
  i = 0;
  for (j = 0; j < col; j++)
    for (k = 0; k < key_length; k++)
     ciphertext[k * col + j] = ciphert[i++];
  for (i = 0; i < key_length - 1; i++) {
    for (j = 0; j < 26; j++) f[j] = 0;
    for (j = 0; j < col; j++)
      f[ciphertext[i * col + j] - 'A']++;
    for (j = i + 1; j < key_length; j++) {
      for (k = 0; k < 26; k++) fp[k] = 0;
      for (k = 0; k < col; k++)
        fp[ciphertext[j * col + k] - 'A']++;
      sum = 0.0;
      for (k = 0; k < 26; k++)
        sum += f[k] * fp[k];
      sum /= (col * col);
      printf("%4.3lf ", sum);
    }
    printf("\n");
  }
  for (i = 0; i < key_length - 1; i++) {
    for (j = 0; j < 26; j++) f[j] = 0;
    for (j = 0; j < col; j++)
      f[ciphertext[i * col + j] - 'A']++;
    for (j = i + 1; j < key_length; j++) {
      printf("%ld %ld ", i + 1, j + 1);
      for (k = 0; k < 26; k++) fp[k] = 0;
      for (k = 0; k < col; k++)
        fp[ciphertext[j * col + k] - 'A']++;
      for (g = 0; g < 26; g++) {
        sum = 0.0;
        for (l = 0; l < 26; l++) {
          m = (l - g) % 26;
          if (m < 0) m += 26;
          sum += f[l] * fp[m];
        }
        MIc[i][j][g] = sum / (col * col);
        printf("%4.3lf ", MIc[i][j][g]);
        if ((g + 1) % 9 == 0) printf("\n    ");
      }
      printf("\n");
    }
  }
  for (i = 0; i < key_length - 1; i++) {
    for (j = i + 1; j < key_length; j++) {
      for (g = 0; g < 26; g++) {
        if (MIc[i][j][g] > 0.061)
          printf("%ld %ld %2ld %4.3lf\n", i, j, g, MIc[i][j][g]);
      }
    }
  }
  keyword[0] = 'A';
  keyword[1] = 'R';
  keyword[2] = 'E';
  keyword[3] = 'V';
  keyword[4] = 'K';
  keyword[5] = '\0';
  found = 0;
  for (i = 0; !found && i < 26; i++) {
    j = 0;
    for (k = 0; k < count; k++) {
      plaintext = ciphert[k] - keyword[j++];
      if (j == key_length) j = 0;
      if (plaintext < 0) plaintext += 26;
      printf("%c", plaintext + 'A');
      if ((k + 1) % 25 == 0) printf("\n");
    }
    printf("\ncorrect decryption (n or y)? ");
    scanf("%s", answer);
    found = tolower(answer[0]) == 'y';
    if (!found) {
      for (j = 0; j < key_length; j++) {
        keyword[j] -= (char) 'A';
        keyword[j]++;
        if (keyword[j] == 26) keyword[j] -= (char) 26;
        keyword[j] += (char) 'A';
      }
    }
  }
  printf("keyword = ");
  for (i = 0; i < key_length; i++)
    printf("%c", keyword[i]);
  printf("\n");
  return 0;
}