Code:

 


// By Ben Ruyl

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#define MAXKEYLENGTH 30
#define MAXCRIB 30
#define MAXCIPHER 2000
#define MAXFILENAME 128

char crib[MAXCRIB];
int cribpat[MAXCRIB];
char ct[MAXCIPHER];

int begin = 1; // standard cipher length region, if not specified
int end = 12;

int results = 0; // count the matches

void createpattern(char* v, int* pat)
{
   int i = 0, j = 0, highpat = 0;

   for (i = 0; i < strlen(v); i++)
   {
       int found = 0;
       for (j = 0; j < i; j++)
           if (v[i] == v[j])
           {
               pat[i] = pat[j];
               found = 1;
           }

       if (!found)
       {
           pat[i] = highpat;
           highpat++;
       }
   }
}

void createpatternbigram(char* v, int* pat)
{
   int i = 0, j = 0, highpat = 0;

   assert(strlen(v) % 2 == 0);

   for (i = 0; i < strlen(v); i += 2)
   {
       int found = 0;
       for (j = 0; j < i; j += 2)
           if (v[i] == v[j] && v[i + 1] == v[j + 1])
           {
               pat[i / 2] = pat[j / 2];
               found = 1;
           }

       if (!found)
       {
           pat[i / 2] = highpat;
           highpat++;
       }
   }

}

void makepatofpat(int* v, int len, int* pat)
{
   int i = 0, j = 0, highpat = 0;

   for (i = 0; i < len; i++)
   {
       int found = 0;
       for (j = 0; j < i; j++)
           if (v[i] == v[j])
           {
               pat[i] = pat[j];
               found = 1;
           }

       if (!found)
       {
           pat[i] = highpat;
           highpat++;
       }
   }
}


void checkperm(const int *p, const int size)
{
   if (p != 0)
   {
       const int len = strlen(ct);
       int i = 0, j = 0, u = 0, v = 0;
       int pos = 0;
       int minrow = len / size;
       int rest = len % size;
       int rowsatperm = minrow;

       char table[MAXCIPHER]; // FIXME: terrible waste of space
       int ctpat[MAXCIPHER];
       int revp[MAXCRIB];

       memset(table, 0, MAXCIPHER);

       for (j = 0; j < size; j++)
           revp[p[j]] = j; // reverse it, index -> perm, perm -> index

       // untranspose the cipher
       for (i = 0; i < size; i++)
       {
           rowsatperm = minrow;

           if (revp[i] < rest)
               rowsatperm++;

           for (j = 0; j < rowsatperm; j++)
           {
               table[revp[i] + j * size] = ct[pos];
               pos++;
           }
       }

       createpatternbigram(table, ctpat); // create the pattern of the bigrams. we will also use this pattern for freq. analysis

       // sweep the crib through the pattern
       for (u = 0; u < strlen(table) / 2 - strlen(crib); u++) // FIXME: remove all those strlens
       {
           int matches = 1;
           for (v = 0; v < strlen(crib); v++)
           {
               // now make a pattern of this part of the pattern of the ciphertext, because 12 13 12 14 = 0 1 0 2!
               int patofpat[MAXCRIB];
               makepatofpat(ctpat + u, strlen(crib), patofpat);

               if (patofpat[v] != cribpat[v])
               {
                   matches = 0;
                   break;
               }

           }

           if (matches) // if it matches, print the permutation
           {
               results++;
               printf("PATTERN MATCH! perm:");

               for (v = 0; v < size; v++)
                   printf("%d", p[v]);

               printf("\n");
           }
       }

   }
}

// University of Exeter algorithm
// a fast algorithm, we don't care about sorting it like a dictionary
void permute(int *v, const int start, const int n)
{
   if (start == n - 1)
   {
       checkperm(v, n);
   }
   else
   {
       int i = 0;
       for (i = start; i < n; i++)
       {
           int tmp = v[i];

           v[i] = v[start];
           v[start] = tmp;
           permute(v, start + 1, n);
           v[start] = v[i];
           v[i] = tmp;
       }
   }
}


int main(int argc, char *argv[])
{
   int beginloc = -2, endloc = -2, cribloc = -2, fileloc = -2;
   long linenum = 0;
   int theoption, except = 0, number = 0, found =0;

   int i = 0;
   int v[MAXKEYLENGTH];

   // parse the arguments
   for (i = 0; i < argc; i++)
   {
       if (argv[i][0] == '-')
       {
           if (i == beginloc || i == endloc || i == cribloc || i == fileloc)
           {
               printf("No parameter entered");
               return -1;
           }

           switch (argv[i][1])
           {
           case 'b':
               beginloc = i + 1;
               break;

           case 'e':
               endloc = i + 1;
               break;

           case 'c':
               cribloc = i + 1;
               break;

           case 'f':
               fileloc = i + 1;
               break;
           }


       }
       else
       {
           if (i == beginloc)
           {
               int res = atoi(argv[i]);
               if (res >= 2)
               {
                   begin = res;
                   beginloc = -1;

               }
               else
               {
                   printf("Wrong starting value entered");
                   return -1;
               }
           }
           else
               if (i == endloc)
               {
                   int res = atoi(argv[i]);
                   if (res >= 2)
                   {
                       end = res;
                       endloc = -1;

                   }
                   else
                   {
                       printf("Wrong ending value entered");
                       return -1;
                   }
               }
               else
                   if (i == cribloc)
                   {
                       if (strlen(argv[i]) <= MAXCRIB)
                       {
                           strcpy(crib, argv[i]);
                           cribloc = -1;

                       }
                       else
                       {
                           printf("The crib is too long");
                           return -1;
                       }
                   }
                   else
                       if (i == fileloc)
                       {
                           if (strlen(argv[i]) <= MAXFILENAME)
                           {

                               FILE *file = fopen( argv[i], "r" );


                               if ( file == 0 )
                               {
                                   printf( "Could not open file\n" );
                                   return -1;
                               }


                               fgets(ct, MAXCIPHER, file); // read the cipher, FIXME: no support for spaces, no support for multiline

                               if (ct[strlen(ct) - 1] == '\n')
                                   ct[strlen(ct) - 1] = 0;

                               if (ct[strlen(ct) - 1] == '\r') // support for Windows
                                   ct[strlen(ct) - 1] = 0;

                               fclose(file);

                               fileloc = -1;
                           }
                           else
                           {
                               printf("The filename is too long");
                               return -1;
                           }
                       }
                       else // read the ciphertext, leave blank if you've specified a file
                       {
                           if (strlen(argv[i]) <= MAXCIPHER)
                           {
                               strcpy(ct, argv[i]);

                           }
                           else
                           {
                               printf("The ciphertext is too long");
                               return -1;
                           }
                       }
       }

   }

   assert(strlen(ct) % 2 == 0);

   // create a pattern from the crib
   createpattern(crib, cribpat);

   // print some stuff
   printf("Begin: %i\n", begin);
   printf("End: %i\n", end);
   printf("Crib: %s\n", crib);

   printf("Crib pattern: ");
   for (i = 0; i < strlen(crib); i++)
       printf("%d", cribpat[i]);
   printf("\n");


   printf("Cipher: %s\n", ct);

   // create the list that will be permutated. no need to create a new sorted one in the keylength loop, because we don't care about order
   for (i = 0; i < MAXKEYLENGTH; i++)
       v[i] = i;

   for (i = begin; i < end + 1; i++)
   {
       printf("\nStarting with keylength %d.\n", i);
       permute(v, 0, i);
   }


   printf("\nSearch done. %d matches found. Press any key to exit.\n", results);

   getchar();

   return 0;

}