Crack the Modified Caesar Cipher with Relative Frequency Letters

• Download source files - 128 Kb

Abstract

The goal of this project is to break the Modified Caesar Cipher by using the Relative Frequency English table. It was great experiment to crack such secret cipher text using some approaches, in this article you will be guided through a few steps to crack the Modified Caesar Cipher, and you will see the amazing results I achieved. In this experiment I tested my program with almost 5K (5000) characters, and I was able to recover the exact key and then the exact message without any problems.

Note: You will find some sample files with the attachment.

Introduction

Cryptography refers to the art of protecting transmitted information from unauthorized interception or tampering. The other side of the coin, cryptanalysis, is the art of breaking such secret ciphers and reading the information, or perhaps replacing it with different information. Sometimes the term cryptology is used to include both of these aspects.

The objective of this article is to find a mechanism for breaking a cipher text. First, what is Modified Caesar Cipher? It's similar to the Standard Caesar Cipher (I think you all know it) but the new is, it has multiple keys (Standard Caesar Cipher has one key of only 25 available keys ), whereas the Modified Caesar Cipher will use, let's say, a key of length 7, so if the key is {3,12,11,22,3,4,6} then the first letter of the message will use the first key=3, the second one will use the key = 12, and so on. But why I'm using the Modified Caesar Cipher instead of the Standard Caesar Cipher? Because the Modified is difficult to crack, you will see why later on.

I used to surf the Internet and do some researches before I start solving any problem, not to stole somebody's efforts but to explore some ideas and get some experiments. After some googling I found lot of people taking about this topic. Actually they were taking about the Caesar Cipher but not Modified Caesar Cipher, most of them were saying that you can accomplish this mission simply by using the character frequency in the cipher text and then compares it with the given related frequency table. I tried to implement this technique and I tested it under the Caesar Cipher (not Modified Caesar cipher, because this won’t work and we would explain why later) and I got poor results. Then I started to think to use a heuristic function and after that how to apply this method to the Modified Caesar Cipher, all that stuff will be our discussion in this article, so let's start.

Tools to crack the Modified Caesar Cipher

In order to break the Modified Caesar Cipher or even the Caesar Cipher, you need to have a relative English frequency table. I have done some googling about this topic and I found lot of frequency tables, and one of the best table I found was the table published by Forsyth and Safavi-Naini, in their simulated annealing attack on the substitution cipher, and this table contain the space character frequency percentage which gives us the ability to clearly identify the words correctly. In the end of this project, you will see the effect of adding such space character to the table.

Here is the table that we are going to use, and note you can easily change the percentages from the control panel in the program.

Notice: _ means space character.

Difficulties and Their Solutions

The Difference between Caesar Cipher and the Modified Caesar Cipher

In the Caesar Cipher, the key is single key, say for e.g. 3, so when we encrypt the message “AA” we will get “DD”. We observe that the first character “A” became “D” and the second one as well. But in the Modified Caesar Cipher the key length is variable, say for e.g. key ={1,2}. So when we encrypt the message “AA” we get “BC”. The first and the second characters were the same A’s but after encryption we get different characters, and that trigger a problem!!!

Back to the people who suggested a solution for the Caesar Cipher. They suggested to count the character frequency of the encrypted message and then sort them in descending order and then replace each character with corresponding character in the relative frequency table. So if the character G is the most frequent character in the encrypted message, then it will be replaced with the character E in the relative frequency table and so on.

Is That Enough??? No

This technique will not determine exactly each character correctly. I tried to count the key probability since Caesar cipher has single key and this works as follow:

1. Get the guessed key for all characters by subtracting the encrypted character from the substituted character. For e.g., if the encrypted character was A and the substituted character was Y then the guessed key is 2.
2. After getting all the guessed keys, take the maximum. For e.g., if we found that 24 character was using the key 3 and 43 using the key 2, then the selected key is 2.

Is this technique enough to crack the Modified Caesar Cipher??? No because of the difference between Caesar Cipher and the Modified Caesar Cipher, but we can solve this by using Grouping approach.

Grouping

Here I introduce my approach in solving the problem of MCC. Here we assume that we know or we can estimate the Key Length [in the program you can determine the key length and then try]. After we know the key length, let’s say 7, then we know character number one is encrypted with the same key as the character 8 and 16 and so on encrypted, since it is cyclic. Now we group them together, then we get seven groups in this example each group encrypted with same key. No other tricks just apply the above techniques.

How to Recover the key

After solving the problem above, we just try to estimate the key (guess) by trying to substitute the key from the encrypted message and the guessed message for each group. Let’s take an example. Assume the key length is 3 so that we have three groups and also assume that we calculated/substituted the key for each character in each group as follow:

We take the max so that the recovered key will be {3,5,7}

Notice: This is the simplest way; other details are not discussed here and that is because of similarity and clarity purpose.

Using the code

The MCC cracker is 100% managed code; C# language has been used. The program consists of seven main classes:

1. frm_Main.cs: Represents the main program.
2. CharacterFrequency.cs: Here, we store the character frequencies.
3. MCC.cs: Provides the encryption methods.
4. MCCUtilities.cs: Helper class for MCC.
5. CrachTheMCC.cs: Provides the cracking methods.
6. CrackTheMCCUtilities.cs: Helper class for the CrackTheMCC.
7. Utilities.cs: Provides the utility methods such as SaveFile method.

Encryption

/// <SUMMARY>
/// Handling the Encrypt button event action.
/// - Read the original message.
/// - Delete any none letters characters.
/// - Convert the Key to a proper format.
/// - Encrypt the message using the Modified Caesar Cipher.
/// - Fill the Enrypted text box with the encrypted message.
/// </SUMMARY>
/// <PARAM name="sender"></PARAM>
/// <PARAM name="e"></PARAM>
private void button_Encrypt_Click(object sender, System.EventArgs e)
{
    string Message = null;
    int [] Key = null;

    // Clean the message.
    Message = MCCUtilities.CleanMessage(this.textBox_OriginalMessage.Text);
    // Covert the key into the proper format.
    Key     = MCCUtilities.CovertTheKey(this.textBox_Key.Text);

    // Perform the Encryption operation.
    if ( Message != null && Key != null)
      textBox_EncryptedMessage.Text = MCC.Encrypt(Message,Key).ToLower();
}

Very simple, first clean up the message, then convert the key and encrypt.

Crack

/// <SUMMARY>
/// Handling the Crack button event action.
/// - Get the Encrypted character's frequency.
/// - Crack the message character by character.
/// - Recover the Key.
/// - Restore the original message.
/// </SUMMARY>
/// <PARAM name="sender"></PARAM>
/// <PARAM name="e"></PARAM>
private void button_Crack_Click(object sender, System.EventArgs e)
{
  string EncryptedMessage = this.textBox_EncryptedMessage2.Text.ToUpper();
  string CrackedMessage = String.Empty;
            
  // Get the relative frequency table.
  CharacterFrequency [] CFT = 
     CrackTheMCCUtility.GetFrequency(
     Utilities.GetCharacterTable(listView_CharacterFrequencyTable),
     Utilities.GetFrequencyTable(listView_CharacterFrequencyTable));
                        
  // sort the table
  Utilities.Sort(CFT);

  // Crack the Encrypted Message
  CrackedMessage = 
     CrackTheMCC.CrackTheMessage(EncryptedMessage,
     CFT,Convert.ToInt32(numericUpDown_KeyLength.Value));
  textBox_OriginalMessage2.Text = CrackedMessage.ToLower();

  // Recover the key.
  this.textBox_ReCoveredKey.Text = 
       CrackTheMCC.RecoverTheKey(EncryptedMessage,CrackedMessage,
  Convert.ToInt32(numericUpDown_KeyLength.Value));
}

First, get the relative frequency English letters, second sort in descending order (from greater to smaller). After that, crack the message and recover the key.

Recover The Key

/// <SUMMARY>
/// Recover the Key
/// </SUMMARY>
/// <PARAM name="EncryptedMessage">The encryptedmessage</PARAM>
/// <PARAM name="CrackedMessage">The cracked message</PARAM>
/// <PARAM name="KeySize">The key length</PARAM>
/// <RETURNS>The recovered key</RETURNS>
public static string RecoverTheKey(string EncryptedMessage,
       string CrackedMessage,int KeySize)
{
  int [] keys = CrackTheMCCUtility.GetKey(EncryptedMessage,CrackedMessage);
    string Key = "{";
    for ( int i =0 ; i < KeySize; i++)
        Key += GetKeyGroup(i,keys,KeySize)+",";
        return Key;
}

Here we use the Grouping technique to recover the key.

How to use the program

Open the program: then you see three panels: Encrypt, Crack, Control.

How to encrypt a message

Very simple steps:

1. Open one of the sample files provided in the CD.
2. Enter the encryption key.
3. Click on the Encrypt button.
4. Save the encrypted message to you hard disk.

Here we will use the sample message number 1 and the key {1,4,16,2,23,17,9}.

How to crack the encrypted message

Very simple steps:

1. Open the encrypted message we created above.
2. Select the estimated key length.
3. Click on the Crack button.

You will get some thing like this:

As you see, here the original message is not yet clear, now hit on this "Re-Build the message" link label to rebuild (Decrypt) the message.

Conclusion

I hope that I gave a good idea on how to crack a cipher text with the frequency letters. I know may be no body using this encryption technique nowadays, but I wanted to show how to do this.