Problem 59 — XOR Decryption

solved Fri, 13 Dec 2019, 14:38 · level 1 · difficulty 4% projecteuler.net github

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 Analysis

The cipher here is a repeating-key XOR cipher - a byte-level form of the Vigenere cipher. Every plaintext byte is combined with one byte of a short, cyclically repeating key using the bitwise XOR operation. XOR has a property that makes the scheme both convenient and breakable: it is its own inverse. Because (p ^ k) ^ k == p, decryption is the very same operation as encryption - you reapply the key. That is exactly why 65 XOR 42 = 107 and 107 XOR 42 = 65.

The observation that makes the key recoverable without knowing it is the periodicity of a repeating key. With a key of length k, the byte at position j is always encrypted with key byte j mod k. So key position 0 only ever touches ciphertext bytes 0, k, 2k, ...; key position 1 touches 1, k+1, 2k+1, ...; and so on. If I partition the ciphertext into k interleaved sub-sequences (one per key position), each sub-sequence was encrypted with a single constant byte - that is, each is a one-byte XOR cipher. I can break each independently. Because the problem tells me the key is three lowercase letters, every position has only 26 candidate values. Instead of searching the combinatorial space of 26^k full keys, I solve k separate one-dimensional problems of 26 trials each. That is the difference between exponential and linear work. To pick the right candidate per slice I use frequency analysis: natural English is dominated by e, t, a, and n, so the candidate byte that produces the most of these is almost certainly correct. The overall complexity is O(26 * n) for n ciphertext bytes - negligible.

Solution Approach

Frequency-Scoring Slice Attack (Python and C, index 0)

Both files implement the same algorithm and differ only in language idiom. It proceeds in four steps.

Step 1 - Parse the ciphertext. The input is a comma-separated list of decimal ASCII codes. Python uses a list comprehension, [int(x) for x in ...split(",")]. C scans the buffer character by character, accumulating digit runs into integers and pushing them into a dynamically grown array. Both fetch the file through a shared get_text_file helper.

Step 2 - Build interleaved slices. Given key length k, slice i holds ciphertext bytes at positions i, i+k, i+2k, ... Python expresses this directly with extended slice notation: encrypted[i::key_length]. C uses a two-pass approach: a first j % key_length pass counts each slice's size, then it allocates each slice to its exact size and a second pass routes elements in. This avoids over-allocation and per-slice reallocation.

Step 3 - Score each candidate byte per slice. For each candidate byte from 97 ('a') to 122 ('z'), and each slice, I XOR every element with the candidate and count how many results appear in the supplied list of common letters (eEaAnNtT). The highest-scoring candidate becomes that slice's key byte. I deliberately chose a plain count against a short alphabet rather than a full chi-squared test: the ciphertext is long and the per-slice key space is tiny, so the common-letter count is more than discriminating enough, and far simpler to reason about.

Step 4 - Compute the answer. With the per-position key known, I XOR each ciphertext byte back to plaintext and sum all ASCII values. Python caches the decrypted slice strings while scoring and reuses them; C runs a final XOR pass over each slice. The Python version also prints the recovered plaintext under --show - a valuable sanity check, since the bare answer 129448 gives no confidence the decryption is real English.

workbench

Test cases

categoryinputanswer
main file_url = https://projecteuler.net/resources/documents/0059_cipher.txt key_length = 9 most_common_letters = eEaAnNtT 129448

Results

solutioncategoryanswerverdict avg seconds cavg seconds py
p0059_s0 main 129448 correct 0.000139 (63) 0.001989 (63)

Files

Tags & blogs