Reply To: !
@Gen_ruikt
Let’s assume we know the matrix that was used for the encryption process. When we encrypt a message, each block of n letters is multiplied by an n x n matrix, which is invertible. So to decrypt the message, each block is multiplied by the inverse of the matrix which was used for encryption.
The simplest case is probably a 2×2 matrix. Consider this example below from the 2023 9A which used a 2×2 hill cipher, this is only a short section of the ciphertext, but hopefully it’ll help illustrate the decryption process:
XOLIM IHAZE
Now, the key matrix for this cipher was
[1 1]
[0 1]
Now, first we convert each of the letters of the ciphertext into numbers. So we have X = 23, O = 14, L = 11… and get:
23 14 11 8 12 8 7 0 25 4
The next thing want to do is invert the 2×2 matrix, which is 1/det * (ad-bc). I’m assuming you’re familiar with determinants and finding inverses to matrices here. So the inverse of the matrix above is:
[1 -1]
[0 1]
Which is equivalent to
[1 25]
[0 1]
if we did all the entries in the matrix mod 26.
Now that we have our inverse and have converted the ciphertext, we want to multiply the numbers split into n blocks (which in this case is 2) with the inverse of the key matrix and mod 26. So our blocks of numbers would be: (23, 14), (11,8), (12,8), (7,0), (25, 4), and the calculation would be as follows:
[ 1 25] [ 23] = [ 1 * 23 + 25* 14 ] = [373 mod 26] = [9 ]
[ 0 1 ] [ 14] = [ 0 * 23 + 1 * 14 ] = [14 mod 26] = [14]
[ 1 25] [ 11] = [ 1 * 11+ 25* 8] = [211 mod 26] = [3]
[ 0 1 ] [ 8 ] = [ 0 * 11+ 1 * 8] = [8 mod 26 ] = [8]
[ 1 25] [ 12] = [ 1 * 12+ 25* 8] = [212 mod 26] = [4]
[ 0 1 ] [ 8 ] = [ 0 * 12+ 1 * 8] = [8 mod 26 ] = [8]
[ 1 25] [ 7] = [ 1 * 7+ 25* 0] = [7 mod 26 ] = [7]
[ 0 1 ] [ 0] = [ 0 * 7+ 1 * 0] = [0 mod 26 ] = [0]
.. And so on for the remaining pairs.
After the matrix multiplication, you need to convert the pairs of numbers (9,14), (3,8).. etc. back into letters. So:
9 = J, 14 = O, 3 = D, 8 = I, 4 = E, 8 = I, 7 = H, 0 = A..
So the start of the decrypt reads: “JODIE IHAVE” and that’s it!
You can see that when we start multiplying and adding numbers, we’ll get results bigger than 25, and out alphabet in this case only goes up till 25 (0-25 is 26 shifts). So we need a way to “wrap around” back into the range 0-25. And that’s exactly what mod 26 does. It’s essentially the remainder you get when you divide the number by 26. So 373/26 = 14 remainder 9. So think of it how many times you need to go through the entire alphabet to get to the same number.
You might’ve seen a similar thing in the affine cipher in one of the earlier challenges. Affine are in the form of ax + b (mod 26), and the hill cipher is just that but we’re dealing with matrices instead. You could also have an affine hill cipher which combines both affine and hill. I’d suggest you look up clock/modular arithmetic.
Does this make a bit more sense?
It does to us! Thank you for a nice explanation! The Elves