Quote:

 

ADFGVX was cryptanalysed by French Army Lieutenant Georges Painvin. The work was exceptionally difficult by the standards of classical cryptography, and Painvin became physically ill during it. His method of solution relied on finding messages with stereotyped beginnings, which would fractionate the same, then form similar patterns in the positions in the ciphertext that had corresponded to column headings in the transposition table. (Considerable statistical analysis was required after this step had been reached — all done by hand.)

This meant it was only effective during times of very high traffic — but, fortunately for the cryptanalysts, that was also when the most important messages were sent.

Quote:

 

And I note, NO ONE really made attempt on my challenge, even the known plain text one.

Revelation

Apr 28 2008, 09:49 AM

A transposition with keylength < 10 is cracked in about 10 seconds. That means that the pattern sweep takes about 15 seconds. That's do-able.

"Jdedge"

 

converting it back to single characters using any arbitrary Polybius square would yield a result that was only a simple substitution away from the plaintext.

Quote:

 

Then we just try various transpositions until our digram frequency looks like a mono substitution frequency. And that undoes step 2. From there, any polybius square will convert the remaining crypt text into a mono alphabetic substitution, which is easy to solve. Brilliant! And NICE!!!!

Donald

Apr 28 2008, 12:58 PM

"Jdedge"

 

converting it back to single characters using any arbitrary Polybius square would yield a result that was only a simple substitution away from the plaintext.

AH! Ok, it took me a bit, but I think I see your point.
If the sequence was the standard
step 1: fractionate,
step 2: transpose

Then we just try various transpositions until our digram frequency looks like a mono substitution frequency. And that undoes step 2. From there, any polybius square will convert the remaining crypt text into a mono alphabetic substitution, which is easy to solve. Brilliant! And NICE!!!!

BUT, If the sequence is:
step 1: fractionate,
step 2: transpose
step 3: unfractionate

THIS still baffles me. How do you undo step 3?

Code:

 


   P1  P2  P3  P4
   L1  L2  L3  L4
   R1  R2  R3  R4

  L1:L2  L3:L4 R1:R2 R3:R4


Revelation

Apr 28 2008, 01:09 PM

That's what I suggested in my second and third post and that's what my application would do: first sweeping the pattern of a crib through the text and then checking the frequency of the bigrams (btw, I haven't started writing it yet)

Revelation

Apr 28 2008, 01:09 PM

Your other sequence is a pain, especially if you use two different squares in step 1 and 3.  I'm not sure how to solve that.

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;

}


Revelation

May 14 2008, 02:27 PM

If you see room for optimisation, please let me know. It should run as fast as possible.