The challenge comes with this text file:
Along with two hints:
- This uses the affine cipher, as clued by the title and description, but with an added modification.
- Each pair of letters decodes the next.
Hmm…affine cipher. How does that work, exactly?
Well, in layman’s terms, the affine cipher is a caesar cipher that takes two keys (a and b) instead of one. We define a space of possible and “legal” values (in this case: being all ASCII digits, followed by all ASCII lowercase letters, and an underscore). Then, using it for each letter/number/whatever in the legal values, we locate that plaintext’s index in our legal values array, and perform the equation:
Ciphertext = ((a*plain) + b) mod len(legal_values)
This ciphertext (another index in the legal_values array), will then be used to get the element located at that new calculated value, and that will be the encrypted char.
The process can be explained in more detail here. I’d highly recommend reading it before continuing, to atleast understand the algorithm better.
Anyway, we obviously don’t know “a” and “b”. But this is where hint #2 is useful. A pair of letters/digits/etc is obviously two values. Well, there are two keys used in the affine cipher. So, what if, hypothetically, “a” and “b” aren’t the same for the entire encryption, but are rather just the plaintexts of the pair of letters/chars before?
Let’s test it out with the next ciphertext pair “bx”. We know what the plaintext is (it’s “ac”), so let’s mimick encryption and see what our results are.
So, now, let’s design a script that will decrypt our data for us. Since we basically know “a” and “b” now (it’s the previous plaintext pair, the first character being “a” and the second being “b”), we basically have all we need in order to successfully decrypt everything and get the flag.
#modular inverse
from Crypto.Util.number import inverse
#import the charset
from string import digits,ascii_lowercase
charset = digits+ascii_lowercase+"_"
ord = lambda c: charset.index(c)
#the key is the two plaintext letters before our ciphertext. the first is variable "a", the second is variable "b"
#variable "m" is `len(charset)`
#we then compute (ord(a)*ord(CT) + ord(b)) mod m to get our new index in the charset
#to decrypt, we need to get the modular inverse "c" of "a" with respect to modulus "m". we then multiply this value by (ct-b) mod m
current_key = "bc"
for current_char_c in "bx 6e z_ un uf i3 bm 0r 0x eb".split(" "):
#print out the decrypted data
print(current_key, end="")
#define the vars
a = ord(current_key[0])
b = ord(current_key[1])
m = len(charset)
#get c
c = inverse(a, m)
#perform decryption for each character in the ciphertext
decrypt = lambda ct: charset[(c * (ord(ct)-b))%m]
current_key = decrypt(current_char_c[0])+decrypt(current_char_c[1])
#print out the final plaintext
print(current_key)
That’s our flag right there. bcactf{g2b_npjs3p4d65k1}