The Cryptopals Crypto Challenges: Set 1 - Single-Byte XOR Cipher

This is the third challenge of Set 1 in The Cryptopals Crypto Challenges website. Previously, I spoke about these challenges and provided walkthroughs for the previous challenges, if you haven't read them, here are the links:

For this challenge, you have to write a method that decodes a Hexadecimal string:

    
    1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

That has been XOR'd against a single character. You must find the key and decrypt the message.

If you have read the previous article, it was clearly setup for this problem. There are so many ways to solve this problem but the most efficient way to solve it is by using a Frequency table.

Assuming the message is supposed to be in English, when decrypted, we need to only generate a frequency table using the given Hexadecimal string that shows the frequencies of each alphabet. The character that has the highest frequency is the key required, which is then used to perform an XOR (\^) operation against each character, to decrypt the encrypted message.

Let's have a look at the code:

    
    //Return Character frequency of a string
    map<char, int> CryptoLib::frequency_table(string str)
    {
        map<char, int> m;
        map<char, int>::iterator it;

        for(int i=0; i<str.size(); i++)
        {
            char ch = str[i];
            it = m.find(ch);

            if(it == m.end())
            {
                m.insert(make_pair(ch,1));
            }
            else
            {
                it->second++;
            }
        }

        return m;
    }

    //Return character with the highest frequency
    char CryptoLib::ret_high_freq_char(map<char, int> m)
    {
        int max_count = 0;
        char max_char;

        for(auto p: m)
        {
            if(isalpha(p.first))
            {
                if(p.second > max_count)
                {
                    max_char = p.first;
                    max_count = p.second;
                }
            }
        }
        return max_char;
    }

    //Single Byte XOR
    string CryptoLib::singleByteXOR(string str)
    {
        string newStr = "";

        //1. Convert Hexadecimal to Binary
        str = add_spaces(con_hex_2_bin(str), 8);

        //2. Convert Binary to Decimals
        vector<int> v = con_bin_2_dec(str, 7.0);

        /*
            What's happening here?
            4. Generate a frequency table using the characters from the ASCII string
            5. Look for characters that are English and also has the highest frequency
            6. The character that has the highest frequency is the KEY!
        */

        //The key
        unsigned char a = toupper(ret_high_freq_char(frequency_table(con_dec_2_ascii(v))));

        //7. Perform XOR with the KEY against each character
        for(int i=0; i<v.size(); i++)
        {
            unsigned char b = v[i];
            unsigned char c = b ^ a;
            newStr += c;
        }

        //8. Decoded message
        return newStr;
    }

Final code:

    
    //CryptoPals Set 1 Challenge 3
    #include "crypto.h"

    int main()
    {
        CryptoLib crypt;

        //Test case provided
        string str = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736";
        cout << "DECODED: " << crypt.singleByteXOR(str) << endl;
        return 0;
    }

Decrypted message:

    
    Key with the highest frequency: 'X'
    Message: Cooking MC's like a pound of bacon

Note: This solution and the library named crypto.h was built using the C++ programming language. The source code for this solution can be found on Github.

Stay tuned for the next challenge!

Cryptography

The Cryptopals Crypto Challenges: Set 1 - Single-Byte XOR Cipher

Abdush Shakoor ● December 13th, 2017