notes.html

problem 59 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
The cipher here is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Stream_cipher" rel="noopener noreferrer" target="_blank">repeating-key XOR cipher</a> - a byte-level form of the <a class="reference-source" href="https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher" rel="noopener noreferrer" target="_blank">Vigenere cipher</a>. Every plaintext byte is combined with one byte of a short, cyclically repeating key using the bitwise <a class="reference-source" href="https://en.wikipedia.org/wiki/Exclusive_or" rel="noopener noreferrer" target="_blank">XOR</a> operation. XOR has a property that makes the scheme both convenient and breakable: it is its own inverse. Because <code>(p ^ k) ^ k == p</code>, decryption is the very same operation as encryption - you reapply the key. That is exactly why <code>65 XOR 42 = 107</code> and <code>107 XOR 42 = 65</code>.
</p>
<p>
The observation that makes the key recoverable without knowing it is the periodicity of a repeating key. With a key of length <code>k</code>, the byte at position <code>j</code> is always encrypted with key byte <code>j mod k</code>. 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 <code>k</code> 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 <code>26^k</code> full keys, I solve <code>k</code> 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Frequency_analysis" rel="noopener noreferrer" target="_blank">frequency analysis</a>: natural English is dominated by <code>e</code>, <code>t</code>, <code>a</code>, and <code>n</code>, so the candidate byte that produces the most of these is almost certainly correct. The overall complexity is <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(26 * n)</a> for <code>n</code> ciphertext bytes - negligible.
</p>
<h3>Solution Approach</h3>
<h4>Frequency-Scoring Slice Attack (Python and C, index 0)</h4>
<p>
Both files implement the same algorithm and differ only in language idiom. It proceeds in four steps.
</p>
<p>
<strong>Step 1 - Parse the ciphertext.</strong> The input is a comma-separated list of decimal ASCII codes. Python uses a list comprehension, <code>[int(x) for x in ...split(",")]</code>. 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 <code>get_text_file</code> helper.
</p>
<p>
<strong>Step 2 - Build interleaved slices.</strong> Given key length <code>k</code>, slice <code>i</code> holds ciphertext bytes at positions <code>i, i+k, i+2k, ...</code> Python expresses this directly with extended slice notation: <code>encrypted[i::key_length]</code>. C uses a two-pass approach: a first <code>j % key_length</code> 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.
</p>
<p>
<strong>Step 3 - Score each candidate byte per slice.</strong> For each candidate byte from 97 (<code>'a'</code>) to 122 (<code>'z'</code>), and each slice, I XOR every element with the candidate and count how many results appear in the supplied list of common letters (<code>eEaAnNtT</code>). The highest-scoring candidate becomes that slice's key byte. I deliberately chose a plain count against a short alphabet rather than a full <a class="reference-source" href="https://en.wikipedia.org/wiki/Chi-squared_test" rel="noopener noreferrer" target="_blank">chi-squared test</a>: 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.
</p>
<p>
<strong>Step 4 - Compute the answer.</strong> 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 <code>--show</code> - a valuable sanity check, since the bare answer 129448 gives no confidence the decryption is real English.
</p>
</article>