!

[Crackerjack_404]

@AndGiggles

I’m going to be completely honest here – I learned how to solve a 3×3 almost a decade ago, but I never really stopped to think about why the algorithms worked or the maths behind them. I remember wanting to learn blind-solving a few years back but never quite got around to it… and now, after reading your post, I actually want to pick it up again and explore the maths properly this time. So just wanted to say, thank you for the inspiration, and I can gladly say I’ve now once again assigned myself a side quest on learning how to blind-solve!

I’m not that familiar with group theory, so would really appreciate some reading resources!

[Gen_ruikt]

Ive ried solving blind folded dont really understand it so i set my goal to solve the biggest one i can get ahold of 21×21 is what im saving for but im like £1000 off having enough lol

That sounds horrifying! Harry

[Gen_ruikt]

Big cubes arent that bad to be honest if you understand the concept for a 5×5 due to both being odd number and even number sided cubes being able to have paritities as you increase in size its just rinse and repeat for alot kore pices

[Gen_ruikt]

Also can anybody explain hill ciphers to me because as they have been brought up im rlly confused about it i understand matrix multiplication which isnt that bad on it own but the things im reading about it i think overconmplicate things

[AndGiggles]

@Crackerjack_404 That’s good to hear. Your first successful solve will feel amazing.

Group theory is a really beautiful area which is ubiquitous in modern mathematics and in particular in modern cryptography. As for which book I would recommend, it really depends on how much maths you have seen. I personally learnt algebra from the first volume of Jacobson’s Basic Algebra, but I already knew some linear algebra and had enough free time that I could struggle with a hard book. The benefit of using Jacobson is that you can use the second volume to learn more advanced material, however the second volume is much more sophisticated than the first and arguably the presentation could have been improved by giving a more categorical view of things throughout volume 1, rather than just doing this in the second volume.

The other undergraduate level algebra text with which I am most familiar is Artin’s Algebra, which I used for a course at university. It is an okay book and (I seem to recall) introduces at the start the linear algebra which you will need. Both this and the above require a decent amount of mathematical maturity and I would not recommend them unless you have a decent amount of maths experience beyond the school curriculum, e.g. olympiad experience.

Whilst I can’t personally vouch for it, one of my algebra friends worked through Armstrong’s Groups and Symmetries when they were in high school and seemed to like it. Looking over the contents, it seems to be much slower paced and whilst it only covers Group theory it seems to have a good covering of the standard topics in an introductory course.

Really, your best bet is probably to ask Harry or someone else who is involved in maths outreach / pedagogy for a suggestion.

[Crackerjack_404]

@AndGiggles

Thanks for the book recs! I’m a first year maths student so have done some linear algebra and have had the occasional exposure to group theory when watching 3b1b videos. I’ll have a look at Artin’s Algebra before Jacobson’s Basic Algebra! (Unless Harry would like to add some other suggestions!)

I guess I could wait until I get to the point of learning group theory in my course at some point the future, but the incredibly impatient part of me wants to learn right now.

[Crackerjack_404]

@Gen_ruikt
Which part of the Hill cipher are you finding confusing? Is it like the encryption, decryption, the block size..?

[the_cryptographer_formerly_known_as_madness]

@Crackerjack_404

MacLane & Birkhoff – Algebra

video lectures by Michael Penn on youtube

[Gen_ruikt]

@Crackerjack_404

So I understand matrix multiplication is it possible if you would be able to explain most of it for decryption if u can thx if possible

[Gen_ruikt]

Also is anybody able to explain mod 26 as im not quite understanding it

BTW my hear dropped when i thought id forgotten to do a cipher from the challenges it was a false alarm

[AndGiggles]

THIS IS GETTING VERY NERDY! FOR THE SAKE OF MOST OF OUR COMPETITORS I SHOULD POINT OUT THAT THE CORRESPONDENTS ARE OLD TIMERS AT BOSS, AND WE DO NOT EXPECT MUCH OF THIS CONVERSATION TO MAKE SENSE TO YOU. AT LEAST NOT YET. IF YOU HANG AROUND LONG ENOUGH MAYBE YOU TOO WILL BE TALKING ABOUT THESE THINGS LIKE A PRO! JODIE

@the_cryptographer_formerly_known_as_madness I’ll need to check that out. I really like MacLane’s exposition in Categories for the Working Mathematician, and I spent a while researching universal algebra and lattice theory (the fields which Birkhoff laid the foundations of). Even though universal algebra has a few nice results – for example Malcev conditions and Birkhoff’s theorem on the equivalence of algebraic varieties and equational classes – I never really came to see what the abstraction gets us.

I don’t really follow the field, but my understanding is that classical universal algebra is quite an unfashionable research area now, and that its unifying approach to algebra has now been taken up by that of category theory, in which one thinks of an algebraic theories as monads over the category of sets (with the perhaps amusing result that compact Hausdorff spaces are viewed as algebras). Category theory people seem to also have the notion of a Lawvere theory, which probably has some relation to the monadic approach which I am too stupid to understand. It’s interesting how picking the right abstraction can be so useful, universal algebra has (maybe) produced some nice theorems but it has been nothing like the revolution that category theory has been for modern mathematics.

[Crackerjack_404]

@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

[Crackerjack_404]

I also forgot to mention for the hill cipher- if you didn’t know the key or the the block size used for encryption, there are few ways to go about it.

One of the first things to look out for would be cribs (commonly known plaintext words/phrases). So if you know the text is likely to contain the words “Harry” or “Jodie”, then you can start by experimenting with some combinations of those and form equations and solve them for the entries of the matrix. You can also find the block size by doing some IoC analysis on digrams, trigrams, etc. Unit 87/88 in Madness’ book explains how to attack the hill cipher with cribs in more detail if you’re interested.

The other thing you can also do is to write a brute force algorithm which works well if the block size is small to loop over the invertible matrices and compare the output generated with something like the IoC or quadgram scoring.

[Gen_ruikt]

Quick question regarding scoring so say on part a which is scored on accuracy and i had solved part of it and wanted to check what i was doing was right would that lower my score or not?

Resubmitting can never lower your score, but we don’t give any usable feedback unless you submit a largely correct solution in order to discourage brute force attacks, so what you suggest might not actually help! Harry

[upsidedown]

@Crackerjack_404 describes using brute force search over the set of inverse matrices to break a hill cipher. This only works “quickly enough” for small matrices, perhaps up to 3×3.

Assuming we are working mod 26, there are something like 26 to the power of n squared inverse matrices to search. Of course, many of these are not invertible, but I know of no way to efficiently iterate the invertible matrices.

In python, this might look like this (you can do this more neatly with itertools but this example illustrates the point):

m = 26
for a in range(m):
  for b in range(m):
    for c in range(m):
      for d in range(m):
        try_matrix([a, b, c, d])

This will run in O(pow(26, pow(n, 2))) time, where the matrix has size n × n.

There’s actually a brute force attack that runs in O(pow(26, n)) time, a substantial speedup: take a look at the matrix multiplication for the decryption operation below. By the rules of matrix multiplication, U = AX + BY + CZ, so it’s possible to work out the first letter (or the second, etc.) in each block in terms of only one row of the inverse key.

  Inverse   Cipher    Plain
  matrix    block     block
╭         ╮ ╭   ╮     ╭   ╮
| A  B  C | | X |     | U |
| D  E  F | | Y |  =  | V |
| G  H  I | | Z |     | W |
╰         ╯ ╰   ╯     ╰   ╯

     ... therefore ...

            ╭   ╮ 
╭         ╮ | X |     ╭   ╮
| A  B  C | | Y |  =  | U |
╰         ╯ | Z |     ╰   ╯  
            ╰   ╯

We can do a brute force search through the pow(26, n) possible inverse matrix rows, which will necessarily include all three rows of the actual inverse matrix.

When we decrypt with each of the possible rows, we get a potential slice of the plaintext (every nth letter). The slices can be evaluated using a scoring function that works on non-continuous samples of a plaintext, like the index of coincidence.

We can then take a selection of the best inverse matrix rows using a threshold (or just taking the top 2n rows) and try to fit them together to make a matrix that is invertible mod 26, and take the overall highest scoring invertible matrix. The runtime complexity of this step varies depending on the number of possible rows we obtained from the first step; practically this lets us solve for larger matrices much more efficiently.

[Author]

Posts