Substitution Cipher: Algorithm

It turns out that vigenere ciphers are much easier to break with the help of a computer than substitution ciphers. This is different from what one would expect from breaking those cipher "by hand (and brain)". The reason is that the number of substitutions in a vigenere cipher is very restricted, i.e. just cyclic shifts are allowed. The extra complexity of different shifts at different positions cannot compensate for this weakness.

We limit ourselves to key length from 7 to 12 which will implicitly take care of samller key length as well.

Other as with the substitution cipher breaker we will not use a dictionary to fine tune results after trigram optimization. We still do hilclimbing but only with one fixed starting point for each key length:

We shall try to improve the score of an initially all zero key by small modifications to it until no improvement is possible. By small modifications we mean the replacement of two neighbouring shifts by some arbitrary other shifts.

global_best_key;
global_best_score = 0;

for( key_length = 7; key_length <= 12; key_length++)
{
    InitializeToZeroShifts(best_key,key_length);
    best_score = TrigramScore(Text,best_key);

    While "best_score" Improves Do
    	for(pos=0;pos<key_length;pos++)
    	{
	    curr_key = best_key;    
    
	    for(x=0;x<27;x++)	   
	    for(y=0;y<27;y++)	   	
    	    {
		curr_key[pos] = x;
		curr_key[pos+1] = y;
		curr_score = TrigramScore(Text,curr_key);
	    	if(curr_score > best_score)
	    	{
		    best_score = curr_score;
		    best_key = curr_key;
	    	}
    	    }
	}	

   if( global_best_score > best_score )
    {
	global_best_score = curr_score;
        global_best_key = curr_key;
    }
}

Last Update: 18.04.96 (Format: DD.MM.YY)