Cryptography, 200 points
Ram has something to show you, which can be of great help. It definitely contains the piece of text "pctf" and whatever follows it is the flag. Can you figure out what it is?
We are given a ciphertext :
along with a Python script :
So this clearly looks like a Hill cipher with a 2x2 matrix. The key matrix is randomly populated with integers up to 4 digits, but it doesn't matter since all the operations are done modulus 26 ; it is equivalent to search for a matrix whose coefficients are in .
Here is a little reminder on the Hill cipher : choose a matrix
with coefficients in such that its determinant is invertible modulus 26, i.e there exists such that .
You split the plaintext in groups of two letters, and for each pair of letters (consider A = 0, … Z = 25), the encrypted pair will be
In order to decrypt the ciphertext, you need to run the same calculations but with , the inverse matrix of (mod 26), which is here
Now we could just brute-force all the possible decryption matrices (we know there are less than which is easy to brute-force). We can do much more intelligent though, using a KPTA (Known Plain Text Attack) that only runs once through the ciphertext.
Indeed, let's denote by a pair of letters from the plaintext and their encrypted form. Same thing for and which are the next two letters (for instance, "PC" and "TF"). We have :
and if we let , and
we thus have .
Now if we choose a decent enough quadruplet , the matrix has a determinant which is invertible modulus 26. Actually, choosing the crib "PCTF" does yield which is invertible ().
Now, we simply have to compute on each couple of letters in the ciphertext to have a candidate for the encryption matrix, which greatly reduces the amount of matrices to try out.
Here is the final script.
Here is what it outputs.
This contains the original plaintext, as well as the flag. Enjoy!
(yes, I do know brute-forcing all the matrices would have actually been faster to code but I think this solution is way more elegant :p)