/*
  Author:  Pate Williams (c) 1997

  Exercise 1.1 (b)
  "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>

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] = {"KCCPKBGUFDPHQTYAVINRRTMV",
                         "GRKDNBVFDETDGILTXRGUD",
                         "DKOTFMBPVGEGLTGCKQRACQCW",
                         "DNAWCRXIZAKFTLEWRPTYC",
                         "QKYVXCHKFTPONCQQRHJVAJUW",
                         "ETMCMSPKQDYHJVDAHCTRL",
                         "SVSKCGCZQQDZXGSFRLSWCWSJ",
                         "TBHAFSIASPRJAHKJRJUMV",
                         "GKMITZHFPDISPZLVLGWTFPLK",
                         "KEBDPGCEBSHCTJRWXBAFS",
                         "PEZQNRWXCVYCGAONWDDKACKA",
                         "WBBIKFTIOVKCGGHJVLNHI",
                         "FFSQESVYCLACNVRWBBIREPBB",
                         "VFEXOSCDYGZWPFDTKFQIY",
                         "CWHJVLNHIQIBTKHJVNPIST"};
  char ciphertext[500], plaintext[500];
  char keyword[16], known[] = "ILEARNEDHOWTO";
  char word_1[4], word_2[4];
  int found = 0;
  long count = 0, i, j, o_count, occur[50];
  long distance[50], key_length;

  for (i = 0; i < 15; i++)
    for (j = 0; j < strlen(cipher[i]); j++)
      ciphertext[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];
    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;
  }
  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]);
  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;
}