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:

c0ol! 

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.

1011101001010100000011111111100111101010

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.

0101010111010010101000000111111111001111

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

55d2a07fcf

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

Ciphertext

Plaintext
b068cbc8ab264615de33ab08a8c12b2b413b3b0bdb812b190107

what could this message be?
5ee8c12b36389355c8ab363b2b136dc108888b2b1e06389ba56b1ee8f63b2b0615dba8c8ab08862b
19012b0beb1b860633ab190138a668eb4bedd0eb060e6b28c6306b30411e1e2b0b0615c85e1e2b19
012b0bd91e012b08862b266dcbe650eb3608b8

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.

9b4c96fae42fb5b4a18c48ffe81ee47c2ea18de896fe7cfb8dbb8ce59bb4978ca19a398c9781199a
a18c1ee4fe058d66962eca97e98ccafeb01f8cfeb18ca19a398c7d9b80441f8d9a6d818cfe1f8c2f
4de8962e7ca18ce41e1fb4043515146c6c6cfae43966494c964839807d4c96fa639b6714cafeb01e
b73296a083e8db8001e404e5e5383fe41f0fef04a6fb8ce063

Hints

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?

Dpotjefs!xibu!wbmvft!pg!n!bsf!bqqmjdbcmf!jo!buufnqujoh!up!efdjqifs!uif!djqifsufy
u/!Xibu!wbmvft!bsf!bduvbmmz!sfmfwbou!up!vt@
Tqfdjgjdbmmz-!xibu!epft!sfmbujwf!qsjnbmjuz!ibwf!up!ep!xjui!uif!ijou!bcpwf@
Xibu!jg!zpv!vtfe!b!ejdujpobsz!up!ifmq!efufdu!wbmje!pvuqvut@!Dpotjefs!ftqfdjbmmz!
vtjoh!b!Ibti!Tfu!gps!mpplvqt!)mppl!vq!xibu!b!Ibti!Tfu!jt!jg!zpv!epo(u!lopx!pg!ju*/
Ipx!nboz!ujnft!ep!zpv!offe!up!tijgu!uif!cjobsz!tusjoh!cz!cfgpsf!zpv!hfu!uif!tbnf
!joufhfst!gspn!ju-!cvu!jo!b!tmjhiumz!ejggfsfou!psefs@!Dbo!zpv!vtf!uijt!up!qsfwfo
u!evqmjdbufe!xpsl@

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.

17421

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).