Project Euler

XOR Decryption

A text file has been encrypted by XOR-ing each byte with a repeating key of three lowercase ASCII characters. Given the ciphertext (as a sequence of ASCII codes), decrypt the message and find the s...

Source sync Apr 19, 2026

Problem #0059

Level Level 02

Solved By 45,926

Languages C++, Python

Answer 129448

Length 621 words

modular_arithmeticsequencealgebra

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 0059_cipher.txt (right click and 'Save Link/Target As...'), 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.

Problem 59: XOR Decryption

Mathematical Development

Definition 1 (XOR Cipher). Let $\mathbf{p} = (p_0, p_1, \ldots, p_{N-1})$ be the plaintext byte sequence and $\mathbf{k} = (k_0, k_1, k_2)$ be the key, where each $k_j \in [97, 122]$ (lowercase ASCII). The ciphertext is

c_i = p_i \oplus k_{i \bmod 3}, \qquad i = 0, 1, \ldots, N-1,

where $\oplus$ denotes bitwise exclusive-or.

Theorem 1 (XOR is an Involution). For any bytes $p, k \in \{0, 1, \ldots, 255\}$ :

(p \oplus k) \oplus k = p.

Proof. We verify bitwise. For each bit position, XOR satisfies $x \oplus x = 0$ and $x \oplus 0 = x$ (since XOR is addition in $\mathbb{F}_2$ ). By associativity:

(p \oplus k) \oplus k = p \oplus (k \oplus k) = p \oplus 0 = p. \qquad \square

Corollary 1 (Decryption). The decryption operation is identical to encryption:

p_i = c_i \oplus k_{i \bmod 3}.

Proof. Immediate from Theorem 1. $\square$

Definition 2 (Residue Subsequences). For each $j \in \{0, 1, 2\}$ , define the $j$ -th residue subsequence of the ciphertext:

G_j = (c_i)_{i \equiv j \pmod{3}} = (c_j, c_{j+3}, c_{j+6}, \ldots).

Each element of $G_j$ was encrypted with the same key byte $k_j$ .

Theorem 2 (Key Recovery via Frequency Analysis). If the plaintext is English prose, the most frequent byte in $G_j$ is $32 \oplus k_j$ (where 32 is the ASCII code for the space character). Consequently,

k_j = \operatorname{mode}(G_j) \oplus 32.

Proof. In English text, the space character (ASCII 32) is the most frequent byte, typically constituting 15—20% of all characters. For each position $i \equiv j \pmod{3}$ where $p_i = 32$ , the corresponding ciphertext byte is $c_i = 32 \oplus k_j$ . Since space is the most frequent plaintext character, $32 \oplus k_j$ is the most frequent value in $G_j$ .

By Theorem 1, $k_j = (32 \oplus k_j) \oplus 32 = \operatorname{mode}(G_j) \oplus 32$ .

This holds provided no other plaintext character exceeds the frequency of space in the residue class, which is a standard assumption for sufficiently long English text. $\square$

Lemma 1 (Key Space Cardinality). The key consists of 3 lowercase letters, giving $|\mathcal{K}| = 26^3 = 17{,}576$ possible keys. This is small enough for brute-force enumeration, but frequency analysis provides a direct $O(N)$ solution.

Proof. Each key byte ranges over 26 values (ASCII 97 through 122). Independence of the three bytes gives $26^3 = 17{,}576$ . $\square$

Theorem 3 (Validation). A decryption with key $\mathbf{k}$ is correct if and only if:

(i) All decrypted bytes lie in the printable ASCII range $[32, 126]$ .

(ii) The decrypted text is coherent English prose.

Proof. Condition (i) is necessary since the plaintext is stated to be readable text. Condition (ii) is necessary by the problem statement. Among $17{,}576$ candidate keys, the probability that an incorrect key produces both printable ASCII and coherent English is negligible (the space of coherent English texts is a vanishingly small subset of all byte sequences), so the correct key is uniquely determined. $\square$

Proposition 1 (XOR Algebraic Structure). The set $\{0, 1, \ldots, 255\}$ under XOR forms an abelian group isomorphic to $(\mathbb{F}_2)^8$ . Encryption with a fixed key $k$ is a group automorphism (specifically, translation by $k$ ). This structure ensures that frequency distributions in the plaintext are perfectly preserved (up to relabeling) in the ciphertext.

Proof. XOR is componentwise addition in $\mathbb{F}_2^8$ . Translation by $k$ is a bijection on $\mathbb{F}_2^8$ that preserves the frequency histogram: if byte $b$ appears $f(b)$ times in the plaintext, then $b \oplus k$ appears $f(b)$ times in the ciphertext. $\square$

Editorial

We exploit the period-3 structure of the repeating XOR key by splitting the ciphertext into three residue classes. In each class, the most common ciphertext byte is interpreted as the encryption of a space character, which directly recovers one key byte by XOR with ASCII 32. Once the three-byte key is known, the entire ciphertext is decrypted in one pass and the plaintext byte values are summed.

Pseudocode

Algorithm: Recovering a Three-byte XOR Key by Frequency Analysis
Require: A ciphertext encrypted by a repeating three-byte lowercase key.
Ensure: The sum of the ASCII values in the decrypted plaintext.
1: Partition the ciphertext into the three residue classes of positions modulo 3.
2: For each class j, identify its most frequent ciphertext byte m_j and set the key byte k_j ← m_j XOR 32.
3: Form the repeating key (k_0, k_1, k_2) and decrypt each ciphertext byte c_i by p_i ← c_i XOR k_(i mod 3).
4: Compute S ← ∑ p_i over the decrypted plaintext bytes.
5: Return S.

Complexity Analysis

Theorem 4 (Time Complexity). The frequency-analysis approach runs in $O(N)$ time, where $N$ is the ciphertext length.

Proof. Step 1 scans each of the $N$ ciphertext bytes exactly once, building three frequency tables of size at most 256. Finding the mode of each table costs $O(256) = O(1)$ . Step 2 decrypts in a single $O(N)$ pass. Step 3 validates in $O(N)$ . Step 4 sums in $O(N)$ . Total: $O(N)$ . $\square$

Space: $O(N)$ for storing the ciphertext and plaintext arrays. The frequency tables require $O(256) = O(1)$ auxiliary space.

Remark. A brute-force approach testing all $26^3 = 17{,}576$ keys would cost $O(|\mathcal{K}| \cdot N) = O(17{,}576 \cdot N)$ , which is also efficient for the given input size.

Answer

\boxed{129448}

C++ project_euler/problem_059/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> cipher = {
        36,22,80,0,0,4,23,25,19,17,88,4,4,19,21,11,88,22,23,23,29,69,12,24,0,
        88,25,11,12,2,10,28,5,6,12,25,10,22,80,10,30,80,10,22,21,69,23,22,69,
        61,5,9,29,2,66,11,80,8,23,3,17,88,19,0,20,21,7,10,17,17,29,20,69,8,17,
        21,29,2,22,84,80,71,60,21,69,11,5,8,21,25,22,88,3,0,10,25,0,10,5,8,88,
        2,0,27,25,21,10,31,6,25,2,16,21,82,69,35,63,11,88,4,13,29,80,22,13,29,
        22,88,31,3,88,3,0,10,25,0,11,80,10,30,80,23,29,19,12,8,2,10,27,17,9,
        11,45,95,88,57,69,16,17,19,29,80,23,29,19,0,22,4,9,1,80,3,23,5,11,28,
        92,69,9,5,12,12,21,69,13,30,0,0,0,0,27,4,0,28,28,28,84,80,4,22,80,0,
        20,21,2,25,30,17,88,21,29,8,2,0,11,3,12,23,30,69,30,31,23,88,4,13,29,
        80,0,22,4,12,10,21,69,11,5,8,88,31,3,88,4,13,17,3,69,11,21,23,17,21,
        22,88,65,69,83,80,84,87,68,69,83,80,84,87,73,69,83,80,84,87,65,83,88,
        91,69,29,4,6,86,92,69,15,24,12,27,24,69,28,21,21,29,30,1,11,80,10,22,
        80,17,16,21,69,9,5,4,28,2,4,12,5,23,29,80,10,30,80,17,16,21,69,27,25,
        23,27,28,0,84,80,22,23,80,17,16,17,17,88,25,3,88,4,13,29,80,17,10,5,0,
        88,3,16,21,80,10,30,80,17,16,25,22,88,3,0,10,25,0,11,80,12,11,80,10,
        26,4,4,17,30,0,28,92,69,30,2,10,21,80,12,12,80,4,12,80,10,22,19,0,88,
        4,13,29,80,20,13,17,1,10,17,17,13,2,0,88,31,3,88,4,13,29,80,6,17,2,6,
        20,21,69,30,31,9,20,31,18,11,94,69,54,17,8,29,28,28,84,80,44,88,24,4,
        14,21,69,30,31,16,22,20,69,12,24,4,12,80,17,16,21,69,11,5,8,88,31,3,
        88,4,13,17,3,69,11,21,23,17,21,22,88,25,22,88,17,69,11,25,29,12,24,69,
        8,17,23,12,80,10,30,80,17,16,21,69,11,1,16,25,2,0,88,31,3,88,4,13,29,
        80,21,29,2,12,21,21,17,29,2,69,23,22,69,12,24,0,88,19,12,10,19,9,29,
        80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,80,12,11,80,84,67,80,10,10,
        80,7,1,80,21,13,4,17,17,30,2,88,4,13,29,80,22,13,29,69,23,22,69,12,24,
        12,11,80,22,29,2,12,29,3,69,29,1,16,25,28,69,12,31,69,11,92,69,17,4,
        69,16,17,22,88,4,13,29,80,23,25,4,12,23,80,22,9,2,17,80,70,76,88,29,
        16,20,4,12,8,28,12,29,20,69,26,9,69,11,80,17,23,80,84,88,31,3,88,4,13,
        29,80,21,29,2,12,21,21,17,29,2,69,12,31,69,12,24,0,88,20,12,25,29,0,
        12,21,23,86,80,44,88,7,12,20,28,69,11,31,10,22,80,22,16,31,18,88,4,13,
        25,4,69,12,24,0,88,3,16,21,80,10,30,80,17,16,25,22,88,3,0,10,25,0,11,
        80,17,23,80,7,29,80,4,8,0,23,23,8,12,21,17,17,29,28,28,88,65,75,78,68,
        81,65,67,81,72,70,83,64,68,87,74,70,81,75,70,81,67,80,4,22,20,69,30,2,
        10,21,80,8,13,28,17,17,0,9,1,25,11,31,80,17,16,25,22,88,30,16,21,18,0,
        10,80,7,1,80,22,17,8,73,88,17,11,28,80,17,16,21,11,88,4,4,19,25,11,31,
        80,17,16,21,69,11,1,16,25,2,0,88,2,10,23,4,73,88,4,13,29,80,11,13,29,
        7,29,2,69,75,94,84,76,65,80,65,66,83,77,67,80,64,73,82,65,67,87,75,72,
        69,17,3,69,17,30,1,29,21,1,88,0,23,23,20,16,27,21,1,84,80,18,16,25,6,
        16,80,0,0,0,23,29,3,22,29,3,69,12,24,0,88,0,0,10,25,8,29,4,0,10,80,10,
        30,80,4,88,19,12,10,19,9,29,80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,
        80,12,11,80,84,86,80,35,23,28,9,23,7,12,22,23,69,25,23,4,17,30,69,12,
        24,0,88,3,4,21,21,69,11,4,0,8,3,69,26,9,69,15,24,12,27,24,69,49,80,13,
        25,20,69,25,2,23,17,6,0,28,80,4,12,80,17,16,25,22,88,3,16,21,92,69,49,
        80,13,25,6,0,88,20,12,11,19,10,14,21,23,29,20,69,12,24,4,12,80,17,16,
        21,69,11,5,8,88,31,3,88,4,13,29,80,22,29,2,12,29,3,69,73,80,78,88,65,
        74,73,70,69,83,80,84,87,72,84,88,91,69,73,95,87,77,70,69,83,80,84,87,
        70,87,77,80,78,88,21,17,27,94,69,25,28,22,23,80,1,29,0,0,22,20,22,88,
        31,11,88,4,13,29,80,20,13,17,1,10,17,17,13,2,0,88,31,3,88,4,13,29,80,
        6,17,2,6,20,21,75,88,62,4,21,21,9,1,92,69,12,24,0,88,3,16,21,80,10,30,
        80,17,16,25,22,88,29,16,20,4,12,8,28,12,29,20,69,26,9,69,65,64,69,31,
        25,19,29,3,69,12,24,0,88,18,12,9,5,4,28,2,4,12,21,69,80,22,10,13,2,17,
        16,80,21,23,7,0,10,89,69,23,22,69,12,24,0,88,19,12,10,19,16,21,22,0,
        10,21,11,27,21,69,23,22,69,12,24,0,88,0,0,10,25,8,29,4,0,10,80,10,30,
        80,4,88,19,12,10,19,9,29,80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,80,
        12,11,80,84,86,80,36,22,20,69,26,9,69,11,25,8,17,28,4,10,80,23,29,17,
        22,23,30,12,22,23,69,49,80,13,25,6,0,88,28,12,19,21,18,17,3,0,88,18,0,
        29,30,69,25,18,9,29,80,17,23,80,1,29,4,0,10,29,12,22,21,69,12,24,0,88,
        3,16,21,3,69,23,22,69,12,24,0,88,3,16,26,3,0,9,5,0,22,4,69,11,21,23,
        17,21,22,88,25,11,88,7,13,17,19,13,88,4,13,29,80,0,0,0,10,22,21,11,12,
        3,69,25,2,0,88,21,19,29,30,69,22,5,8,26,21,23,11,94
    };

    int key[3] = {0, 0, 0};
    for (int j = 0; j < 3; j++) {
        array<int, 256> freq{};
        for (int i = j; i < (int)cipher.size(); i += 3) {
            freq[cipher[i]]++;
        }

        int mode = 0;
        for (int b = 1; b < 256; b++) {
            if (freq[b] > freq[mode]) mode = b;
        }
        key[j] = mode ^ ' ';
    }

    int asciiSum = 0;
    for (int i = 0; i < (int)cipher.size(); i++) {
        int plain = cipher[i] ^ key[i % 3];
        asciiSum += plain;
    }

    cout << asciiSum << endl;
    return 0;
}

Python project_euler/problem_059/solution.py

"""
Project Euler Problem 59: XOR Decryption

Decrypt a message encrypted with a 3-byte lowercase XOR key.
Find the sum of ASCII values in the original plaintext.

Key recovery: the most frequent ciphertext byte in each residue
class (mod 3) corresponds to the space character (ASCII 32),
so key[j] = mode(cipher[j::3]) ^ 32.

Answer: 129448
"""
from collections import Counter

def solve():
    cipher = [
        36,22,80,0,0,4,23,25,19,17,88,4,4,19,21,11,88,22,23,23,29,69,12,24,0,
        88,25,11,12,2,10,28,5,6,12,25,10,22,80,10,30,80,10,22,21,69,23,22,69,
        61,5,9,29,2,66,11,80,8,23,3,17,88,19,0,20,21,7,10,17,17,29,20,69,8,17,
        21,29,2,22,84,80,71,60,21,69,11,5,8,21,25,22,88,3,0,10,25,0,10,5,8,88,
        2,0,27,25,21,10,31,6,25,2,16,21,82,69,35,63,11,88,4,13,29,80,22,13,29,
        22,88,31,3,88,3,0,10,25,0,11,80,10,30,80,23,29,19,12,8,2,10,27,17,9,
        11,45,95,88,57,69,16,17,19,29,80,23,29,19,0,22,4,9,1,80,3,23,5,11,28,
        92,69,9,5,12,12,21,69,13,30,0,0,0,0,27,4,0,28,28,28,84,80,4,22,80,0,
        20,21,2,25,30,17,88,21,29,8,2,0,11,3,12,23,30,69,30,31,23,88,4,13,29,
        80,0,22,4,12,10,21,69,11,5,8,88,31,3,88,4,13,17,3,69,11,21,23,17,21,
        22,88,65,69,83,80,84,87,68,69,83,80,84,87,73,69,83,80,84,87,65,83,88,
        91,69,29,4,6,86,92,69,15,24,12,27,24,69,28,21,21,29,30,1,11,80,10,22,
        80,17,16,21,69,9,5,4,28,2,4,12,5,23,29,80,10,30,80,17,16,21,69,27,25,
        23,27,28,0,84,80,22,23,80,17,16,17,17,88,25,3,88,4,13,29,80,17,10,5,0,
        88,3,16,21,80,10,30,80,17,16,25,22,88,3,0,10,25,0,11,80,12,11,80,10,
        26,4,4,17,30,0,28,92,69,30,2,10,21,80,12,12,80,4,12,80,10,22,19,0,88,
        4,13,29,80,20,13,17,1,10,17,17,13,2,0,88,31,3,88,4,13,29,80,6,17,2,6,
        20,21,69,30,31,9,20,31,18,11,94,69,54,17,8,29,28,28,84,80,44,88,24,4,
        14,21,69,30,31,16,22,20,69,12,24,4,12,80,17,16,21,69,11,5,8,88,31,3,
        88,4,13,17,3,69,11,21,23,17,21,22,88,25,22,88,17,69,11,25,29,12,24,69,
        8,17,23,12,80,10,30,80,17,16,21,69,11,1,16,25,2,0,88,31,3,88,4,13,29,
        80,21,29,2,12,21,21,17,29,2,69,23,22,69,12,24,0,88,19,12,10,19,9,29,
        80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,80,12,11,80,84,67,80,10,10,
        80,7,1,80,21,13,4,17,17,30,2,88,4,13,29,80,22,13,29,69,23,22,69,12,24,
        12,11,80,22,29,2,12,29,3,69,29,1,16,25,28,69,12,31,69,11,92,69,17,4,
        69,16,17,22,88,4,13,29,80,23,25,4,12,23,80,22,9,2,17,80,70,76,88,29,
        16,20,4,12,8,28,12,29,20,69,26,9,69,11,80,17,23,80,84,88,31,3,88,4,13,
        29,80,21,29,2,12,21,21,17,29,2,69,12,31,69,12,24,0,88,20,12,25,29,0,
        12,21,23,86,80,44,88,7,12,20,28,69,11,31,10,22,80,22,16,31,18,88,4,13,
        25,4,69,12,24,0,88,3,16,21,80,10,30,80,17,16,25,22,88,3,0,10,25,0,11,
        80,17,23,80,7,29,80,4,8,0,23,23,8,12,21,17,17,29,28,28,88,65,75,78,68,
        81,65,67,81,72,70,83,64,68,87,74,70,81,75,70,81,67,80,4,22,20,69,30,2,
        10,21,80,8,13,28,17,17,0,9,1,25,11,31,80,17,16,25,22,88,30,16,21,18,0,
        10,80,7,1,80,22,17,8,73,88,17,11,28,80,17,16,21,11,88,4,4,19,25,11,31,
        80,17,16,21,69,11,1,16,25,2,0,88,2,10,23,4,73,88,4,13,29,80,11,13,29,
        7,29,2,69,75,94,84,76,65,80,65,66,83,77,67,80,64,73,82,65,67,87,75,72,
        69,17,3,69,17,30,1,29,21,1,88,0,23,23,20,16,27,21,1,84,80,18,16,25,6,
        16,80,0,0,0,23,29,3,22,29,3,69,12,24,0,88,0,0,10,25,8,29,4,0,10,80,10,
        30,80,4,88,19,12,10,19,9,29,80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,
        80,12,11,80,84,86,80,35,23,28,9,23,7,12,22,23,69,25,23,4,17,30,69,12,
        24,0,88,3,4,21,21,69,11,4,0,8,3,69,26,9,69,15,24,12,27,24,69,49,80,13,
        25,20,69,25,2,23,17,6,0,28,80,4,12,80,17,16,25,22,88,3,16,21,92,69,49,
        80,13,25,6,0,88,20,12,11,19,10,14,21,23,29,20,69,12,24,4,12,80,17,16,
        21,69,11,5,8,88,31,3,88,4,13,29,80,22,29,2,12,29,3,69,73,80,78,88,65,
        74,73,70,69,83,80,84,87,72,84,88,91,69,73,95,87,77,70,69,83,80,84,87,
        70,87,77,80,78,88,21,17,27,94,69,25,28,22,23,80,1,29,0,0,22,20,22,88,
        31,11,88,4,13,29,80,20,13,17,1,10,17,17,13,2,0,88,31,3,88,4,13,29,80,
        6,17,2,6,20,21,75,88,62,4,21,21,9,1,92,69,12,24,0,88,3,16,21,80,10,30,
        80,17,16,25,22,88,29,16,20,4,12,8,28,12,29,20,69,26,9,69,65,64,69,31,
        25,19,29,3,69,12,24,0,88,18,12,9,5,4,28,2,4,12,21,69,80,22,10,13,2,17,
        16,80,21,23,7,0,10,89,69,23,22,69,12,24,0,88,19,12,10,19,16,21,22,0,
        10,21,11,27,21,69,23,22,69,12,24,0,88,0,0,10,25,8,29,4,0,10,80,10,30,
        80,4,88,19,12,10,19,9,29,80,18,16,31,22,29,80,1,17,17,8,29,4,0,10,80,
        12,11,80,84,86,80,36,22,20,69,26,9,69,11,25,8,17,28,4,10,80,23,29,17,
        22,23,30,12,22,23,69,49,80,13,25,6,0,88,28,12,19,21,18,17,3,0,88,18,0,
        29,30,69,25,18,9,29,80,17,23,80,1,29,4,0,10,29,12,22,21,69,12,24,0,88,
        3,16,21,3,69,23,22,69,12,24,0,88,3,16,26,3,0,9,5,0,22,4,69,11,21,23,
        17,21,22,88,25,11,88,7,13,17,19,13,88,4,13,29,80,0,0,0,10,22,21,11,12,
        3,69,25,2,0,88,21,19,29,30,69,22,5,8,26,21,23,11,94
    ]

    # Key recovery: for each position j, find the most frequent byte
    # and XOR with space (32) to recover the key byte.
    key = []
    for j in range(3):
        group = cipher[j::3]
        freq = Counter(group)
        most_common_byte = freq.most_common(1)[0][0]
        key.append(most_common_byte ^ ord(' '))

    # Decrypt and compute ASCII sum
    plaintext = [cipher[i] ^ key[i % 3] for i in range(len(cipher))]
    return sum(plaintext)

if __name__ == "__main__":
    answer = solve()
assert answer == 129448
print(answer)

Problem Statement