Skip to content

Latest commit

 

History

History
32 lines (26 loc) · 3.39 KB

solution.md

File metadata and controls

32 lines (26 loc) · 3.39 KB
Raw

Challenge

That's an interesting looking substitution cipher...

Setup

Source code: substitution-cipher-ii.sage
Output: output.txt

Solution

Analysing the source code, we see that a character set of length 47 is created, which means the variable n is assigned 47. Then, a Polynomial Ring bounded by a Galois Field (GF(47)) is created, and a 6-degree polynomial with random coefficients (from 0 to 46) is generated. Then, each flag character's index in CHARSET is substituted into the polynomial equation and the output is used as an index in CHARSET to retrieve a new character and append it to an output string.

Basically, solutions to a galois-field polynomial equation (say P(x)) are generated by substituting them directly into the equation and then applying the relevant modulus (for GF(47) this is mod 47). The modulus in Galois Fields are always prime. One important thing to realise is that our flag must start with the characters DUCTF{ and end with }, which, in order, correspond to indices of 0, 1, 2, 3, 4, 5, 6. Notice that if we take P(0), all non-constant terms will cancel out. Since the first output character (U) in output.txt has an index of 1 in CHARSET, the constant term of our polynomial must be 1. Now, if we take the indices of the output values corresponding to the characters we know and subtract 1 from them (UCTF{} -> jyw5d4), we find the solutions to x = 1, 2, 3, 4, 5, 6 (for our new polynomial P(x) without the constant term) to be: [19, 34, 32, 41, 13, 40].

Now, to solve for the coefficients of our polynomial equation, we have some simultaneous equations with coefficients a, b, c, d, e and f:

a + b + c + d + e + f = 19 mod 47
(2^6)a + (2^5)b + (2^4)c + (2^3)d + (2^2)e + 2f = 34 mod 47
(3^6)a + ... + 3f = 32 mod 47
(4^6)a + ... + 4f = 41 mod 47
(5^6)a + ... + 5f = 13 mod 47
(6^6)a + ... + 6f = 40 mod 47

Note that P(x + 47k) = P(x) in GF(47) since, by the binomial theorem, (x + 47k)^n will have n terms multiplied by (47k)^t for t = 1 to n, which will all evaluate to 0 in mod 47, and one term which is x^n. This means we can reduce all of the exponential components in our simultaneous equations (2^6, 2^5 etc.) to smaller values in mod 47.

One method of solving these equations would be to create a matrix of coefficients, take its inverse and multiply it by a column matrix of the output values, however this will not work in a modulus of 47. Another method is to use Gaussian elimination, which we can find the code to here. We must make a few modifications however:

  • All assignment operations must first have modulus 47 applied to them
  • Division must be performed by taking the multiplicative inverse of the divisor in mod 47 and performing multiplicating by that number instead
Finally, with the full polynomial, we can bruteforce through each of the possible 47 characters until the solution to one of them matches each character of the output file, and then append it to a flag string. The solution code can be found [here](solve.py).

Note

For whatever reason, it appears that the output flag instead generated was DUCTF{go0d_0l'_l4gr4fg3}. We can intuitively figure out that the leetspeak is referring to the mathematician Joseph-Louis Lagrange and replace the "f" with an "n".