Code:

 


#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

char buff[4096];
char outbuff[4096];
char key1offset[4096];
char key2offset[4096];
int buff_len;

double eng_freq[26] = {  0.080495, 0.016988, 0.024049, 0.043021, 0.124398, 0.022228, 0.020788, 0.064744, 0.069919, 0.001569, 0.007988, 0.040981, 0.026407,
0.068951, 0.075290, 0.017536, 0.001249, 0.056266, 0.063212, 0.090238, 0.028144, 0.009413, 0.023940, 0.001274, 0.019999, 0.000915};

void decode(char *key1, int key1len, char *key2, int key2len);
double score(char *key1, int key1len, char *key2, int key2len);
double score_key(int which_key, int offset, char *key1, int key1len, char *key2, int key2len);
double correlate(double *seq1, double *seq2, int len);

int main(int argc, char *argv[])
{
   FILE *infile;
   char ch, key1[128], key2[128];
   char bestkey1[128], bestkey2[128], origkey[128];
   int i, j, key1len, key2len, changed;
   double curr_score, best_score, curr_best;

   if (argc < 4)
   {
       fprintf(stderr, "Format: %s file key1len key2len\n", argv[0]);
       exit(0);
   }

   if (sscanf(argv[2], "%d", &key1len) == 0)
   {
       fprintf(stderr, "Invalid key length: %s\n", argv[2]);
       exit(1);
   }

   if (sscanf(argv[3], "%d", &key2len) == 0)
   {
       fprintf(stderr, "Invalid key length: %s\n", argv[3]);
       exit(1);
   }

   if ((infile = fopen(argv[1], "r")) == NULL)
   {
       fprintf(stderr, "Error opening %s\n", argv[1]);
       perror("fopen");
       exit(1);
   }

// Read in the file, convert letters to 0-25 so it is easier to do
// Vigenere computations

   while ((ch = fgetc(infile)) != EOF)
   {
       if ((ch >= 'A') && (ch <= 'Z'))
       {
           ch -= 'A';
       }
       else if ((ch >= 'a') && (ch <= 'z'))
       {
           ch -= 'a';
       }
       else
       {
           continue;
       }
       buff[buff_len++] = ch;
   }

// Store the offsets for each key - you could probably just compute
// this on-the-fly
   for (i=0; i < buff_len; i++)
   {
       key1offset[i] = i % key1len;
       key2offset[i] = i % key2len;
   }

// -1 in a key position means there is no guess yet
   for (i=0; i < key1len; i++) key1[i] = -1;
   for (i=0; i < key2len; i++) key2[i] = -1;

   best_score = -99999.99;

// Try first 2 characters in each key
   for (i=0; i < 456976; i++)
   {
       key1[0] = i / 17576;
       key1[1] = (i / 676) % 26;
       key2[0] = (i / 26) % 26;
       key2[1] = i % 26;

       curr_score = score(key1, key1len, key2, key2len);

       // If this key scores better than what we have tried
       // so far, this is the new best key
       if (curr_score > best_score)
       {
           printf("Best score = %8.5lf\n", curr_score);
           best_score = curr_score;
           memcpy(bestkey1, key1, key1len);
           memcpy(bestkey2, key2, key2len);
       }
   }

   // Start with the best key
   memcpy(key1, bestkey1, key1len);
   memcpy(key2, bestkey2, key2len);

   // Try to figure out all the rest of the key values for key1
   for (i=2; i < key1len; i++)
   {
       best_score = -99999.99;

       // Try each possible value for this key position
       for (j=0; j < 26; j++)
       {
           key1[i] = j;
           curr_score = score_key(1, i, key1, key1len, key2, key2len);

           // See if this value is better than before
           if (curr_score > best_score)
           {
               printf("Best score = %8.5lf\n", curr_score);
               best_score = curr_score;
               memcpy(bestkey1, key1, key1len);
               memcpy(bestkey2, key2, key2len);
           }
       }
       memcpy(key1, bestkey1, key1len);
       memcpy(key2, bestkey2, key2len);
   }

   // Now try to figure out all the rest of the key values for key2
   for (i=2; i < key2len; i++)
   {
       best_score = -99999.99;

       // Try each possible value for this key position
       for (j=0; j < 26; j++)
       {
           key2[i] = j;
           curr_score = score_key(2, i, key1, key1len, key2, key2len);

           // See if this value is better than before
           if (curr_score > best_score)
           {
               printf("Best score = %8.5lf\n", curr_score);
               best_score = curr_score;
               memcpy(bestkey1, key1, key1len);
               memcpy(bestkey2, key2, key2len);
           }
       }
       memcpy(key1, bestkey1, key1len);
       memcpy(key2, bestkey2, key2len);
   }

// Now we have a guess for both keys, but some of the values computed earlier
// may be wrong because there wasn't enough good information yet. Try computing
// every key position again to see if any improvement can be made. Quit
// once there has been no improvement

   changed = 1;
   while (changed)
   {
       changed = 0;

       memcpy(key1, bestkey1, key1len);
       memcpy(key2, bestkey2, key2len);

       // Try changing key 1 first
       for (i=0; i < key1len; i++)
       {
           best_score = -99999.99;

           // Remember what the old value was
           memcpy(origkey, key1, key1len);
           for (j=0; j < 26; j++)
           {
               key1[i] = j;
               curr_score = score_key(1, i, key1, key1len, key2, key2len);
               if (curr_score > best_score)
               {
                   printf("Best score = %8.5lf\n", curr_score);
                   best_score = curr_score;
                   memcpy(bestkey1, key1, key1len);
               }
           }
           memcpy(key1, origkey, key1len);

           // Is the best key better than what we started with?
           if (memcmp(bestkey1, origkey, key1len))
           {
               changed = 1;
               memcpy(key1, bestkey1, key1len);
           }
       }

       // Now try changing key 2
       for (i=0; i < key2len; i++)
       {
           best_score = -99999.99;

           // Remember what the old value was
           memcpy(origkey, key2, key2len);
           for (j=0; j < 26; j++)
           {
               key2[i] = j;
               curr_score = score_key(2, i, key1, key1len, key2, key2len);
               if (curr_score > best_score)
               {
                   printf("Best score = %8.5lf\n", curr_score);
                   best_score = curr_score;
                   memcpy(bestkey2, key2, key2len);
               }
           }
           memcpy(key2, origkey, key2len);


           // Is this better than what we started with?
           if (memcmp(bestkey2, origkey, key2len))
           {
               changed = 1;
               memcpy(key2, bestkey2, key2len);
           }
       }
   }

// We're done, print the resuls
   decode(key1, key1len, key2, key2len);
   printf("Key1: ");
   for (i=0; i < key1len; i++) putchar('A'+key1[i]);
   printf("\nKey2: ");
   for (i=0; i < key2len; i++) putchar('A'+key2[i]);
   printf("\n");
   for (i=0; i < buff_len; i++)
   {
       putchar('A'+outbuff[i]);
   }
   printf("\n");
}

void decode(char *key1, int key1len, char *key2, int key2len)
{
   int i;
   char k1, k2;
   for (i=0; i < buff_len; i++)
   {
       k1 = key1[key1offset[i]];
       k2 = key2[key2offset[i]];
       // If there is no value for this key position, don't decode it
       if ((k1 < 0) || (k2 < 0))
       {
           outbuff[i] = -1;
           continue;
       }
       outbuff[i] = (52+buff[i]-k1-k2) % 26;
   }
}

double score(char *key1, int key1len, char *key2, int key2len)
{
   int i;
   double counts[26];
   decode(key1, key1len, key2, key2len);
   for (i=0; i < 26; i++) counts[i] = 0.0;

   for (i=0; i < buff_len; i++)
   {
       // Don't score any values that couldn't be decoded yet
       if (outbuff[i] < 0) continue;
       counts[outbuff[i]] += 1.0;
   }

   return correlate(counts, eng_freq, 26);
}

// This function is like score, but only computes the score for values
// for a certain key and position (which_key = 1 or 2 for key1 or key2)
double score_key(int which_key, int offset, char *key1, int key1len, char *key2, int key2len)
{
   int i;
   double counts[26];
   decode(key1, key1len, key2, key2len);
   for (i=0; i < 26; i++) counts[i] = 0.0;

   for (i=0; i < buff_len; i++)
   {
       if (which_key == 1)
       {
           if (key1offset[i] != offset) continue;
       }
       else
       {
           if (key2offset[i] != offset) continue;
       }
       if (outbuff[i] < 0) continue;
       counts[outbuff[i]] += 1.0;
   }

   return correlate(counts, eng_freq, 26);
}

// Computes a standard correlation coefficient to see how closely two
// frequency distributions match. The closer to 1.0, the better the
// match.
double correlate(double *pct1, double *pct2, int num_pcts)
{
   double sx, sy, sx2, sy2, sxy;
   int i;

   sx = sy = sx2 = sy2 = sxy = 0.0;

   for (i=0; i < num_pcts; i++)
   {
       sx += pct1[i];
       sx2 += (pct1[i] * pct1[i]);
       sy += pct2[i];
       sy2 += (pct2[i] * pct2[i]);
       sxy += (pct1[i] * pct2[i]);
   }

   sx2 = sx2 - (sx * sx/ (double)num_pcts);
   sy2 = sy2 - (sy * sy/ (double)num_pcts);
   sxy = sxy - (sx * sy/ (double)num_pcts);

   return sxy / sqrt(sx2 * sy2);
}


Code:

 

BXRDY OUSFO YBYLK TVTJI NERLU ZYEAZ HISJJ EIUXS TOLYV KGNPD
BSFVW ZZJXU NJVLR FCUCF AMDYP KMYON IQCXI WKIWR EDAOU VBDJO
PBFEX EVMCO EEUHT TWCMR LROYU JPPKZ RBKSE VKDZG YYWNH FWIPA
EBRQC IXMSA UOYSH HGXNV DRMII KDNXR ZWOUJ PWPES NJMVJ HPDJQ
VHNMV JZHWG FHUDG UZUTD DAKSK MQCCB LZTEQ ODQBF XDJAN DXDYR
PKMCY XPMTF VGAOX EPOPE ELKOF CFXVY XGWYB ADKFK VMNQP HHTKP
LIKIR ZOYNH XPOSP HHNNH SZBTI XZ