Reply To: !
@Gen_ruikt
If you want to get into brute forcing, I’d suggest starting with the general technique used to brute-force many classical ciphers, mainly hill climbing and a fitness function. There are of course other brute force techniques, but with hill climbing, instead of trying every possible key, you let a scoring function guide you toward better keys.
The idea behind the algorithm is fairly simple (although it does take time and patience to implement and experiment with the parameters):
1. Generate a random key
Every cipher you brute force has some structure you’re trying to guess. For a substitution cipher the key is a permutation of A–Z. For a hill cipher it’s an nxn matrix mod 26, for a vigenere cipher the key is a short string, etc.
Hill climbing starts by randomly generating one possible key, which probably isn’t going to be correct, but that’s fine
2. Decrypt text with key
3. Score how close to English the result is
This is where the fitness function comes in and pretty much replaces the need for scrabble solvers.
English has very reliable statistical patterns, like how often pairs of letters “th”, “he”, “in” appear. So if you count those frequencies (bigrams/trigrams/quadgrams) in a corpus (i.e. a big piece of sample text) and compare them with the frequencies in your decrypted text, you get a score that tells you how close you are to real English. The more the decrypted text looks like real English, the higher the score.
4. Make small changes to the key
This is the hill climbing part. You’re basically making small changes to the key and seeing if that change improves your score. For a substitution cipher, it could be swapping letters, or changing one element in a matrix for a hill cipher.
5. Decrypt with new key and re-score the text to compute a new fitness score
If the score improves, then you accept that key and continue the hill climb.
6. Repeat the process thousands of times
Iteration gradually shuffles the key toward the one that produces readable English. And eventually, the decrypted text becomes more and more English like that you can recognise it.
That same method works for a lot of other ciphers too like substitution, vigenere, transposition, etc. So learning it once pays off again and again. Hill ciphers are basically case of matrix based polyalphabetic cipher. So once you understand the general hill-climbing approach, you only need to change a few details like how you represent the key and how you score the output to be able to brute force other ciphers.
I appreciate this may be a lot of info at once, and you don’t need all of it straight away. The more ciphers you try, the more familiar these ideas become, and it’s great programming practice too. Madness’ book is very good for practising as it has lots of problems you can work through with hill climbs attacks, and each section has a summary of how to implement the attack for that cipher too.