!

[the_cryptographer_formerly_known_as_madness]

I think you will have to explain the twist; I don’t think I can guess it. Thanks/Cheers

[Gen_ruikt]

So is that a no go harry or am i aloud them cos i get that the rules evolved but its not exaclty a clear answer pls say they are I dont rlly fancy seatching for possibilities in a dictionary lol

It is certainly a “No!” if you want to be eligible for prizes! Harry

[AndGiggles]

@the_cryptographer_formerly_known_as_madness Fair enough. I was trying to give you the nature of the twist with “about Galileo lacking the French sulphur for his area of study”, which depending upon how big a fan of crosswords you are may not have helped. The cipher uses a Galois field to encode the letters with matrix multiplication being carried out normally apart from this. Finite fields have order p^n, for some prime p. This is why I said that 25, 27, and 29 could work (5^2, 3^3, and 29^1), whilst 24, 26, and 28 (3*2^3, 13*2, and 7*2^2) couldn’t. As you said, it’s a 3×3 Hill cipher just that (somehow) everything is done in GF(5^2) rather than Z/25Z (I’ve always thought it would be better if there were a prime number of elements in the alphabet and this is the next best thing).

@Gen_ruikt I wouldn’t bother with this cipher, if I were you. It relies more on noticing some numerology than ability to solve ciphers. As madness pointed out, Kerckhoff’s principle (and certainly my own aesthetic taste) says that ciphers which just rely on the secrecy of the encryption scheme are rather rubbish. I seem to recall that one of the previous years challenges themed around the Roman period had a hill cipher as its final challenge, and that is probably a much higher quality and more conventional place to start with these.

[the_cryptographer_formerly_known_as_madness]

@AndGiggles,
No one would guess that in this forum. And are there not several ways to map 0…24 to the elements of the field?

You have left me no choice: I challenge thee to a duel at dawn. Be sure to write down everything you know beforehand.

[AndGiggles]

@the_cryptographer_formerly_known_as_madness Perhaps not, but I had hoped that you (or one of the other regulars) might be able to have a shot at it.

You are correct that there is no canonical way to chose the assignment (I would argue this is still somewhat a problem with the standard hill cipher, as ideally we would want that a change of alphabet indexing plays nicely with the matrix algebra). The encryption was done using this (terrible) python code:

######################
import numpy as np
import galois

alphabet = “ABCDEFGHIJKLMNOPQRSTUVWXY”
F = galois.GF(25)

text = “”.join([i for i in “??????”])

blocks = [text[3*i:3*i+3] for i in range(len(text)//3)]
nums = F([[alphabet.index(j) for j in i] for i in blocks]).transpose()

key = F([[?,?,?],[?,?,?],[?,?,?]])

encrypted = key.dot(nums).transpose()
encrypted_matrix = [[alphabet[int(j)] for j in i] for i in encrypted]

encrypted_text = “”.join([“”.join(i) for i in encrypted_matrix])
###########################

As to your suggestion of a duel, I am normally quite opposed to them (you could say I am dual to them). But how dare you refer to me with “thee”. Thou hast dishonored me and shalt be striken down.

OK chaps, we are all for a little friendly rivalry, but duels are definitely beyond the pale. Let’s all keep our honour and avoid any strickening! Remember, the Elves work for Santa as well as BOSS and no-one wants to end up on the naughty list (Santa’s OR Harry’s!)

[Crackerjack_404]

@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.

[the_cryptographer_formerly_known_as_madness]

@Gen_ruikt, to follow up on what Giggles said:

2005-7B-morse-hill3x3
2007-7B-hill2x2+constant
2012-7B-hill2x2
2014-6B-hill2x2
2016-8A-hill2x2

Harrys_Game_2010-7A-hill3x3
Harrys_Game_2012-1-hill2x2
Harrys_Game_2012-3B-hill3x3

[upsidedown]

md5(“upsidedown” || uppercase plaintext of @AndGiggles cipher) = 32069090179049ad3919feb43cd01044

I can’t say I fully (or even mostly) understand the maths of GF(25).

Finite fields are fascinating. The arithmetic of GF(256) is fundamental to the algorithm underlying the advanced encryption standard and I have a few students just learning about that now. It is way beyond GCSE level, but an important part of undergraduate maths and these fields (GF(p^k) for p prime) are fundamental objects in number theory and algebraic geometry. Harry

[AndGiggles]

@upsidedown Yes, well done. As Harry said, finite fields are very useful and a pretty cool things to study. An explicit construction involves writing it as a quotient ring. A quotient you can think of as a generalisation of modular arithmetic. To get the integers modulo 5 (Z/5Z) we start with the integers and enforce the condition that things which differ by a multiple of 5 (e.g. 11 and 1) are the same. Similarly we can form a quotient of polynomial rings: for instance we can take the set of all real polynomials and make the identification that things which differ by a multiple of x^2 + 1 are the same (e.g. x^2 + 2 and 1 or x^3+2x+1 and x+1). By the division algorithm, everything in this quotient can be written as a + bx for some a, b in R. One can see that this quotient is equivalent to the complex numbers (you can think of this as extending the reals with a root of the polynomial x^2 + 1). To construct finite fields one can do a similar thing where we quotient GF(p)[x] (polynomials in the integers mod p) by an irreducible polynomial. This is a very brief description and skips over most of the technical details, so it is okay if this doesn’t make any sense.

@Harry, I would be interested to hear your recommendations for textbooks on more modern cryptography. I have read Rational Points on Elliptic Curves up to the section on Mordell’s theorem, but this is at a rather basic level. How much modern Algebraic geometry is needed for this stuff, because frankly a lot of that scares me; it seems everyone I run into who works on it is a total genius whose bedtime reading as a child was Bourbaki’s commutative algebra.

[upsidedown]

@AndGiggles thank you for that explanation, that’s very helpful!

[Gen_ruikt]

cheers Harry good thing i used pen paper and a dictionary even though it was painstakingly slow

[the_cryptographer_formerly_known_as_madness]

https://golem.ph.utexas.edu/category/2023/05/galois_fatal_duel.html

[the_cryptographer_formerly_known_as_madness]

@AndGiggles,
Unfortunately, I compulsively install everything from source, and to install galois sends me into what they call “dependency hell”. galois requires typing_extensions (not a big deal) and numba, which in turn requires llvmlite, which in turn requires that I install a complete C/C++ development chain in addition to the one that I have.

[Edited by Harry]
could you please just send me addition multiplication tables for your implementation of GF(25)? Or, if you can find out, the irreducible polynomial or the primitive element used to generate the implementation? Thank you so much.

P.S. I posted a link to a story about Galois’s duel that ended him, but the elfs have not released it. [They have now! Harry] I hope that you understood the reference when I challenged you to meet me at dawn.

[AndGiggles]

@the_cryptographer_formerly_known_as_madness Yes, I did get your reference, ’twas most amusing. And it’s nice to see an n-category cafe link. John Baez is a really great communicator. [P.S. Some of you may enjoy reading Tom Leinster’s articles on cryptography related issues on n-category cafe].

The irreducible polynomial used was $x^2 + 4x + 2$.

[the_cryptographer_formerly_known_as_madness]

OK, good.

@AndGiggles, md5(“madness”+PLAINTEXT) = 696ac075f6dbc875fd75fe9483e00254

@Everyone, here are some links to the stuff by Leinster on Galois theory, which is actually and entire on-line course:

https://webhomes.maths.ed.ac.uk/~tl/galois/
https://arxiv.org/abs/2408.07499

And if anyone is interested, here is a Python implementation of GF(25) using the same modulus. The mapping from integers to elements of GF(25) is the stupid one, or the standard one, where you just evaluate the polynomial at the modulus, i.e., p(5).
`
class z5(): # integers modulo 5

def __init__(self,n):
if type(n) == z5:
self.value = n.value
elif type(n) == int:
self.value = n % 5
else:
raise Exception(“invalid initialization of an element of Z/5Z”)

def __str__(self):
return str(self.value)

def __repr__(self):
return self.__str__()

def __eq__(self,other):
if type(other) == int:
return self.value == other
return (self.value == other.value)

def __add__(self,other):
if type(other) == int:
return z5(self.value + other)
return z5(self.value + other.value)

def __neg__(self):
return z5(-self.value)

def __sub__(self,other):
if type(other) == int:
return z5(self.value – other)
return self + (-other)

def __mul__(self,other):
if type(other) == int:
return z5(self.value * other)
return z5(self.value * other.value)

def __invert__(self):
if self.value == 0:
raise Exception(“0 is not invertible in Z/5Z”)
return z5([0,1,3,2,4][self.value])

def __truediv__(self,other):
if type(other) == int:
return self * ~z5(other)
return self * ~other

def __int__(self):
return self.value

class g25():

def __init__(self,a,b): # coefficients of a polynomial over Z/5Z: ax + b
self.coefs = [z5(a),z5(b)]

def __str__(self):
return “(“+str(self.coefs[0])+”,”+str(self.coefs[1])+”)”

def __repr__(self):
return self.__str__()

def __eq__(self,other):
return (self.coefs == other.coefs)

def __add__(self,other):
return g25(self.coefs[0] + other.coefs[0],
self.coefs[1] + other.coefs[1])

def __neg__(self):
return g25(-self.coefs[0],-self.coefs[1])

def __sub__(self,other):
return self + (-other)

def __mul__(self,other):
temp = [self.coefs[0] * other.coefs[0],
self.coefs[0] * other.coefs[1] + self.coefs[1] * other.coefs[0],
self.coefs[1] * other.coefs[1]]
while (temp[0] != 0): # the modulus is x^2 + 4x + 2
temp[0] -= 1
temp[1] -= 4
temp[2] -= 2
return g25(temp[1],temp[2])

def __invert__(self):
if self == g25(0,0):
raise Exception(“0 is not invertible in GF(25)”)
for x in range(5): # the dumb brute-force way every time
for y in range(5):
z = g25(x,y)
if self * z == g25(0,1):
return z

def __truediv__(self,other):
return self * ~other

def __int__(self):
return int(self.coefs[0])*5 + int(self.coefs[1])
`

[Author]

Posts