Affine Ciphers with a Twist

A prize awaits you, intrepid programmer, if you are able to crack the cipher given to you. Your pirze has been encoded as an Affine cipher with a twist.

Affine Ciphers, by example

To encode a piece of text using an Affine cipher, you first need to pick a multiplier m and an adder a. Note that for this application of the cipher, m must be relatively prime to 255 (i.e. share no common divisor other than 1 with it). Suppose you were to encode the following with m = 7, a = 3:


First, you convert each character to its ASCII codepoint.

[99, 48, 111, 108, 33]

Then you multiply each codepoint by m and add to that result a. Once this is done, take the remainder when dividing by 255 (take the result mod 255).

[186, 84, 15, 249, 234]

This is the result of the application of the Affine cipher. If you need a more-detailed explanation, Wikipedia provides a pretty good one. At this point it would make sense to convert back to ASCII, but that’s too easy.

The twist

Next, you convert each number to binary strings of length 8. What this entails is converting the number to binary and then left padding it with zeroes if its length isn’t 8. You then join these strings together.


It is here that another variable comes into play. You now shift all of the binary digits to the right, wrapping around digits going past the end to the beginning, by a variable s. In this example, s = 5. This yields the resulting binary string.


Then, starting from the front, you take groups of 8 binary digits and convert them to hexadecimal. This gives the resulting ciphertext:


Your task is to do the inverse: to decode a piece of ciphertext, and a much longer one, too.

A helpful note

Much of the plaintext in the encoded cipher is in the English language. If you were to use some sort of aid (what aid that is I leave up to your interpretation), you would be able to filter outputs that don’t make any sense. Pay attention to punctuation and case: an English word is still valid if it’s capitalized oddly or has punctuation at its end (for example, a comma or period following it).

Test Cases



what could this message be?

The input is pretty long. This ought to be a good benchmark of how well you'll b
e able to crack it!

Your Input

Note that while the ciphertext contains newlines, this is just because of it wrapping around. Ignore them when parsing it as input.

A reasonable implementation should be able to solve this in under a minute.



All hints except the first and last are obfuscated by taking their ASCII codepoints and adding 1 to them for all characters then converting them back to ASCII. They are ordered from least to most impactful. As with before, newlines are there to make sure the text stays formatted nicely.

Is there any redundant work being done? Specifically, are there computations you could be avoiding?


If you still have difficulty, the following is the sum of the encoded digits of the cipher (that is, the sum of the numbers you get after encrypting the text but before doing any shifts). I encourage you to do the puzzle without relying on it.


Other Notes

If this challenge was up your alley, check out Advent of Code.

<pre> tags were used to circumvent default syntax highlighting which is why the test cases look formatted different from other code blocks (because they are).