Tim Varley Logo
Tim Varley Systems Engineer
Problem #59 medium

XOR Decryption

View on Project Euler

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt, a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

Implementations

cpp
#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
#include <fstream>
#include <sstream>


int xor_decryption() {
    std::vector<uint8_t> cipher;
    std::ifstream cipher_file("src/059_cipher.txt");
    if (!cipher_file) {
        std::cerr << "Error opening 059_cipher.txt" << std::endl;
        return 0;
    }
    std::string line;
    std::getline(cipher_file, line);
    std::stringstream ss(line);
    std::string token;
    while (std::getline(ss, token, ',')) {
        cipher.push_back(std::stoi(token));
    }


    std::vector<std::string> common_words;
    std::ifstream words_file("src/059_common_words.txt");
    if (!words_file) {
        std::cerr << "Error opening 059_common_words.txt" << std::endl;
        return 0;
    }
    std::string word;
    while (std::getline(words_file, word)) {
        if (!word.empty()) {
            common_words.push_back(word);
        }
    }


    int max_word_count = 0;
    int best_sum = 0;
    std::string best_decrypted;
    char best_k1, best_k2, best_k3;


    for (char k1 = 'a'; k1 <= 'z'; ++k1) {
        for (char k2 = 'a'; k2 <= 'z'; ++k2) {
            for (char k3 = 'a'; k3 <= 'z'; ++k3) {
                std::string decrypted;
                for (size_t i = 0; i < cipher.size(); ++i) {
                    char key_char = (i % 3 == 0) ? k1 : (i % 3 == 1) ? k2 : k3;
                    char c = cipher[i] ^ key_char;
                    decrypted += c;
                }
                // Check for printable ASCII
                bool valid = true;
                for (char c : decrypted) {
                    if (c < 32 || c > 126) {
                        valid = false;
                        break;
                    }
                }
                if (!valid) continue;
                int word_count = 0;
                for (const auto& word : common_words) {
                    size_t pos = 0;
                    while ((pos = decrypted.find(word, pos)) != std::string::npos) {
                        ++word_count;
                        pos += word.length();
                    }
                }
                int sum = 0;
                for (char c : decrypted) {
                    sum += static_cast<unsigned char>(c);
                }
                if (word_count > max_word_count) {
                    max_word_count = word_count;
                    best_sum = sum;
                }
        }
    }
    }
    }


    return best_sum;
}


#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << xor_decryption() << std::endl;
}
#endif // UNITTEST_MODE

Solution Notes

The Art of XOR Decryption

Dive into the fascinating world of cryptography where XOR operations unlock hidden messages! This problem showcases the elegance of symmetric encryption and the power of frequency analysis in breaking simple ciphers.

The XOR cipher, also known as the Vernam cipher when using a one-time pad, becomes vulnerable when the key repeats. By brute-forcing all possible three-letter lowercase keys (26³ = 17,576 possibilities), we can decrypt the message and identify the correct key by checking for common English words.

Key Cryptographic Concepts

  • ASCII Encoding: Every character maps to a number from 0-127, as defined by the ASCII standard.
  • XOR Operation: A bitwise exclusive-or that flips bits where they differ, providing perfect reversibility with the same key.
  • Repeating Key Cipher: When the key is shorter than the message, it cycles through the key characters.
  • Frequency Analysis: English text has predictable patterns - words like “the”, “and”, “of” appear frequently.

Algorithm Breakdown

  1. Read the encrypted data (comma-separated integers representing ASCII codes)
  2. Try every possible 3-character lowercase key combination
  3. For each key, XOR-decrypt the entire message
  4. Validate that all decrypted characters are printable ASCII (32-126)
  5. Count occurrences of common English words in the decrypted text
  6. Select the decryption with the highest word count (indicating likely correct English text)
  7. Sum the ASCII values of the decrypted characters

Performance Insights

  • Time Complexity: O(26³ × n) where n is message length (~1,200 characters), resulting in ~20 million operations
  • Space Complexity: O(n) for storing the cipher and decrypted text
  • Execution Time: Typically under 1 second on modern hardware due to small key space
  • Optimizations: Early rejection of invalid ASCII ranges significantly reduces processing time

Real-World Connections

This problem illustrates real cryptographic principles used in:

  • Stream ciphers and block ciphers
  • Password-based encryption (PBE)
  • The historical development of cryptanalysis techniques
  • Modern applications in secure communications and data protection

The solution elegantly combines brute force with linguistic heuristics, demonstrating how computational power and pattern recognition can defeat even “secure” encryption schemes with weak keys.