For the GPNCTF I wrote a crypto challenge. It was called Trapdoor and at least I thought about using advanced mathematics to solve it.

This is not your typical post where I show you my code and tell you why you are stupid and should start using Sage (you should, but that is not the point). I will explain some ideas and mathematics I looked at when writing the challenge and when solving it myself. Be warned, it’s certainly not the most efficient or simplest solution. Also, I stopped when it worked and did not dig any further, so there may be some bugs and oversights that just work somehow. The relevant part for now was as follows: The challenge looked like this:


    flagFieldElem = a^expo
    #all output below here is intended for solve
    print(f"Field Base:{K.base().order()}")
    print(f"Field Expo:{log(K.order(),K.base().order())}")
    print(f"NumElems:{K.cardinality()}")
    print(f"gen:{K.modulus()}")
    minpoly = flagFieldElem.minpoly()
    print(f"Hash is:{minpoly(EVAL_VALUE)}")

The flag was encoded as an integer and a group element was generated by computing \(a^{flag}\) in a Galois field. But what is a Galois field, how does it work, and how does it relate to polynomials?

Why more math

Obviously because it is fun. Joking aside, you probably know that \(^{\mathbb{Z}}/_{p\mathbb{Z}}\) is a field if p is a prime. A field in this context means that for all elements (except 0) there is not only an additive but also a multiplicative inverse. And you may have heard your professor or your friends talking about the fact that there are finite fields for every power of a prime number. But when you tried to construct such a field with, say, 25 elements, you (hopefully) failed because you simply could not find the “right way” to define your operations: Consider \(^{\mathbb{Z}}/_{2\mathbb{Z}} \times ^{\mathbb{Z}}/_{5\mathbb{Z}}\). What would your \(\mathbb{1}\) element be? \((1,0)\) or \((1,1)\), neither will work (if you don’t believe me, try to find out where, it’s a great exercise).

Polynomials for the win

We won’t worry too much about how to construct such fields in detail. The only thing we need to know for now is that we construct such fields L as extensions of other fields K. (Written \(L | K\)) This means that we start with a known field K (e.g. GF(5)) and then add new elements, for simplicity say we add only one element \(a\), more formally we add elements and then consider the smallest field containing the old field and the new elements we added. The incredibly useful thing (at least for computer people) is that the new field is then (at least in our case) equivalent to \(^{K[X]}/_{(m_a)}\), where \(m_a \in K[X]\) is the minimal polynomial of \(a\) in K[X]. The latter just means that all coefficients of \(m_a\) are in K (and that it is normed, but we don’t care about that) and \(m_a(a)=0\) and the degree of m is minimal. Cool, now we have a way to represent such finite fields as polynomials modulo another polynomial.

How is this related to the challenge ??

To be very “wrong” and imprecise for a moment: The thing is, we have seen that field extensions are just a fancy way of talking about polynomials and long division. Polynomials are vector spaces, and some vector space things can therefore also be done using field extensions.

Consider the map for an \(a \in L\): \(L \rightarrow L |K \ \ x \mapsto x \cdot a\) and look at the determinant of this map, this is called the field map \(N_{L|K}: L \rightarrow k,\ \ a \mapsto N_{L|K}(a)\). This map has many cool properties like being multiplicative (i.e. a homomorphism of the unit groups) and if you consider an element \(a \in L\) with \(m_a = X^n \cdot \alpha_n + ... + \alpha_0\) then \(N_{L|K}(a) = \pm \alpha_0\) the sign depending on the degree of the extension and the degree of the minimal polynomial. This was a step I had in mind when I created the challenge. Using this, and the fact that we have multiple instances, we can reduce the key space enough to iterate the remaining possibilities to find the flag.

Iterating the possible values

Galois Theory tells us even more (this was the initial starting point for this challenge…): \(N_{L|K}(a) = \Pi_{\sigma \in GAL(L|K)} \sigma(a)\). To explain what Galois groups are would go too far but for finite fields we know that they are generated by Frobenius homomorphisms. This means that they are generated by \(x \mapsto x^p\) with p being the characteristic. Thus the norm boils down to \(N_{L|K}(a) = a^\alpha\) for the right \(\alpha\) which can simply be calculated or just be looked up on e.g. wikipedia. Thinking about this a bit longer (you want to get yourself familiar with the concept of primitive roots) we find out that solutions to equations of the form \(y = x^\alpha\) can be altered by the unit group. More formally, if \(\omega\) is a solution to the equation above and \(\phi^\alpha=1\) then \(\omega \cdot \phi\) is indeed also a solution. Personally I am not totally sure about the number of “nontrivial” solutions (or any other detail), so you might want to look this up for peace of mind.

If we now go back to the challenge we get that for one instance the possible values for the flag are a line. If we took two instances and they would intersect we would have found the flag. Sadly they don’t (again I don’t remember that part of the solve that well, so it is left as an exercise). But this essentially means we can combine multiple instances to get an iterator that skips more elements. This construction is basically a kind of Chinese remainder theorem. My solve script especially the last part is hideous, so I won’t publish it, but I have included the challenge handout here so feel free to try to solve it yourself.

If you want to know more about Galois theory, consider visiting a university course if you have the chance, otherwise there are many great online resources and books, such as this (be warned that most of Galois theory is not about finite fields), but you will probably want to start with an introduction to groups and algebra in general first.