PlaidCTF 2020: A Plaid Puzzle
===
This challenge is solved with _@R3x_ and _@mahaloz_ as a part of Shellphish. Thanks _@toshi_ and _@perri_ for reviewing and giving me suggestions on this write-up.
## Challenge Summary
A Plaid Puzzle is a RPG game written in _PuzzleScript_. In the game, you are able to control as the player and you could move around and mess with a string. The game is available online on [PuzzleScript.net](https://www.puzzlescript.net/play.html?p=a7e867c17405726eb0962b6483f51e4b). Below is a screenshot of the game:
Wait, where is the player? Although it is invisible, you can easily spot him out as he is always surrounded by the blue arrows.
Moreover, the source code of the game is available over there. After all, we are able to deal with it in white-box.
This is what we can see in the source code:
```puzzlescript
title A Plaid Puzzle
author PlaidCTF 2020
homepage https://play.plaidctf.com
zoomscreen 47x3
again_interval 0.01
run_rules_on_level_start
========
OBJECTS
========
...
right [ mbruhbqkghxlzicg | zymzkxpvqeigckuv ] -> [ nnfwxckidvzgtghy | ] again
right [ pengzuapnhrankjc | dhjpocrmwhdesxge ] -> [ nmtqhhkcnxcvmojy | ] again
right [ uypacbgkuqmaanio | izzrteczimtxowhf ] -> [ tgykpmrvaltbuokz | ] again
right [ ouvalcnmotlggryc | uzbyqxbhokkhlodp ] -> [ hllxyajxgrguibng | ] again
right [ ktapmqnouetfmsxx | izzrteczimtxowhf ] -> [ kalmsmalpgkzhrpv | ] again
right [ msrtxpphlevvdwkt | wuhwqgdgdbrevani ] -> [ dvojbwoiaearhqqx | ] again
right [ kynpohbftvgxdhed | zymzkxpvqeigckuv ] -> [ btujcwnspxcqtcgf | ] again
right [ kwyemxqbttvwszqq | ikewikkccpumwsgm ] -> [ hbufavpezfamcjlw | ] again
...
.⍦⍿⍉⍅⎕⍿⍶⎉⍌⍫⍓⍓⍶⍓⍉⍏⌾⍷⍀⎚⍭⍇⎌⍂⎕⎇⍮⎃⎠⍰⎌⍼⌺⎉⎀⎤⍏⍱⎛⎅⎉⎚⎙⌺⎠⎐
.⌼⍟⎫⎌⎌⍾⍂⍌⍟⍰⎌⍆⎅⍚⎈⍷⍭⍰⎛⍏⎈⍾⍩⎇⌼⍮⎃⌼⍏⌾⍉⌶⍇⍼⍮⍑⌺⍂⎡⌾⎡⍇⎌⎢⎭⍊
.⍗⌸⍃⎇⍮⍗⌼⎎⎃⍼⎛⍼⎙⍄⍅⌶⍱⎥⍢⎥⌾⍏⎎⍷⎥⍶⎒⍆⍢⍧⎙⍟⎉⎌⍂⍑⍑⍱⎏⍷⎠⍶⍉⍰⍃⍽
.⎏⎫⍚⍗⎎⍼⎏⎭⎗⍶⍿⍿⎥⍷⍟⍶⍮⎡⍡⍷⎛⌾⍷⎈⍧⍡⌶⌸⍓⌾⍰⎈⎫⎞⎚⎏⍉⍗⍓⍟⍅⍆⍭⍓⎩⌷
.⎭⌾⍾⍦⍚⎌⎢⍌⎡⍩⎥⍀⌺⍠⍵⌳⎠⎌⎢⎫⎩⍼⎌⎏⌼⎥⍼⍶⍀⍗⍡⍉⎭⎥⍱⎎⍓⎞⎥⍗⍠⎈⎈⍠⎛⎨
.⎕⍭⍵⍼⎇⍫⍵⎭⍑⍓⍶⍗⍀⎗⍧⎠⎕⎗⌳⌺⍿⌰⌳⌺⍧⎎⍡⍃⎈⍦⍱⌾⍶⍱⍂⎗⎛⎞⍇⍑⍂⎗⍾⎩⎀⍍
...
```
We will get into the details in the story.
## Solution
### Part I: Making sense of the source code
What is this gibberish thingy above? It looks obfuscated, and those weird symbols at the end of the script looks fishy.
I was late to the party. I didn't try to understand the source code from the documentation, but instead messing around with the source code. There is the line that caught my attention:
```r
[ fljldviokmmfmqzd | iawjsmjfczakueqy ] -> [ fljldviokmmfmqzd | ] message Good flag!
[ ywmxqezdfjsufycd | iawjsmjfczakueqy ] -> [ ywmxqezdfjsufycd | ] message Bad flag!
```
Luckily @R3x and @mahaloz had already done enough to simplify the script. They have come up with a summary that helped a lot:
```
each variable is a space
[ ] have a condition
[ v1 | v2 ] => v1 next to v2
[ v1 v2 ] => v1 on top of v2
-> represents the action to be performed
[ if ] -> [ then ]
both if and then need to have same amount of spaces
[ v1 | v2 ] -> [ v1 | ] => destroy v2 when v1 next to v2
[ v1 v2 ] -> [ v1 ] => doesn’t destroy v2 since they are on top
[ > v1 | v2 ] -> [ v2 | v1 ] => swap is next to
[ v1 v2] [ v3 v4 ] -> [ ] [ ] => multiple conditions
left [v1 | v2] -> [v1 | ] => delete v2 if v1 is left of v2
again => execute these instructions once again after an instruction
Action => keyword activates when we press X
* if we define v = v1 or v2 or v3 => [x1 | v] contains applies on all
* Objects on the same collision layer can't be on top of each other
* Legend contains the initial positions of each of the "variables"
* again commands execute only if there was some modification before
* if we need to apply action to multiple objects we use action on both sides
* better to call each variable an object
* Rules apply repeatedly until they no longer can be applied. (Therefore there is no execution order)
```
If the character `fljldviokmmfmqzd` is standing next to `iawjsmjfczakueqy`, `iawjsmjfczakueqy` will be eliminated and we are informed having the correct flag.
On a contrast, it would be bad if `ywmxqezdfjsufycd` is next to `iawjsmjfczakueqy`.
In this stage, we have four main characters in this RPG game: `fljldviokmmfmqzd` (the _yes_), `ywmxqezdfjsufycd` (the _no_), `iawjsmjfczakueqy` (the _terminator_) and me. I searched for the occurrence of those characters. These are the points I summarize:
1. We are able to find a bunch of lines in the below format.
```r
[ fljldviokmmfmqzd | tgykpmrvaltbuokz ] -> [ ywmxqezdfjsufycd | ] again
yes ************ no *************
# Found 63 times
[ ywmxqezdfjsufycd | kalmsmalpgkzhrpv ] -> [ ywmxqezdfjsufycd | ] again
no ************* no *************
# Found 64 times
[ fljldviokmmfmqzd | kkavwvmbabfuqctz ] -> [ fljldviokmmfmqzd | ] again
yes ************ yes ************
# Found 1 time
```
Interestingly, those are exactly the lines right above the lines giving the verdict.
2. It seems that there is an area drawing the characters.
```
fljldviokmmfmqzd
transparent
ywmxqezdfjsufycd
transparent
iawjsmjfczakueqy
transparent
```
I think it is inhumane to make our main characters transparent. Let's make them visible again!
```
fljldviokmmfmqzd
green
..0..
.000.
00000
.000.
..0..
ywmxqezdfjsufycd
red
..0..
.000.
00000
.000.
..0..
iawjsmjfczakueqy
blue
..0..
.000.
00000
.000.
..0..
```
This is how it looks when I begin to check the flag. It was changed into red after a while - and we are told having the wrong input after a moment.
But there is one more thing: `kkavwvmbabfuqctz` is the only character that makes the green icon intact. We are labelling it as well!
We see that yellow stars are randomly blinking now.
At this moment, @R3x has made the source code more readable by replacing the character names into something less random (bye, `fljldviokmmfmqzd`!).
### Part II: The code structure, for real
After having a basic insight on what we have right now, let's read the code line by line. Better not - there are around 10k lines to read and it doesn't sound fun at all! It is better for us to grasp the idea on what's going on.
#### ~~The header~~ The prelude
```r
title A Plaid Puzzle
author PlaidCTF 2020
homepage https://play.plaidctf.com
zoomscreen 47x3
again_interval 0.01
run_rules_on_level_start
```
This is just the header for the script - it contains a bunch of configuration and metadata that is rather self-explanatory.
#### The objects
```r
========
OBJECTS
========
Background
White
Player
transparent
PlayerUp
Blue
.....
..0..
.0.0.
0...0
.....
...
x_57
Black
0000.
0....
000..
...0.
000..
...
var_91
transparent
var_24
transparent
...
```
This segment describes the characters - I am not sure if they support multiple colors, but at least you could do single-color pixel arts if you wish to. In short, there are in the below format:
```r
character
color
pixels (optional)
```
#### The legend
_Oops. This is not funny at all..._
```
=======
LEGEND
=======
⍙ = val_142
⍡ = val_0
⍊ = val_23
⍤ = val_9
⍵ = val_45
⌶ = val_65
```
This aliases the characters into one character so that we are able to define them in levels.
```
p = Player and x_0
```
...and we can define the properties of characters as well.
#### Rules
It consists of a bunch of rules. It will be described later.
#### Levels
```
.F.............................................
.⍑⎙⎎⍵⍉⍟⎗⍩⍭⍶⌸⍿⎒⎢⍃⍭⍚⎡⍷⎞⍂⍏⍮⎇⍢⍭⍃⎙⎅⎥⍂⍠⎎⍩⎥⍶⍫⌳⎭⍓⎅⍰⍢⍓⌺⎄
.⎀⎇⎙⍼⌰⌶⍩⍶⎫⎚⎥⍰⌳⌸⍅⍆⍗⎀⎩⎭⎀⎇⌺⍾⎫⎤⎈⎕⍀⍷⍡⌰⍌⍚⎤⍑⎈⍩⎙⍱⍼⍇⎥⎉⎉⎑
...
.⍭⍧⌳⍼⎢⎩⎅⍇⍡⌶⎠⌶⎭⎕⎅⎢⎞⍩⍓⌸⌺⎕⌳⌰⎡⎌⍾⎯⎏⎈⍟⍀⍼⍅⎥⍀⎅⍶⍫⍇⍧⍓⍏⎙⍌⍳
C⍱⎌⎯⍾⎛⍦⎢⎅⎗⎥⍃⎛⍵⍟⎇⍡⍂⍡⎙⎛⍑⍉⍵⎢⍌⎗⎈⍩⎃⎕⎚⍾⎒⎭⎀⍉⍟⍠⎠⍌⌰⍡⎫⍱⎥⍔
###############################################
Xp00000000000000000000000000000000000000000000X
###############################################
```
This is the actual map you can see in the game. It maps with the legend - and this is the actual characters in the map:
```
background v_final background ... background
background val_81 val_58 ... val_167
...
background val_165 val_46 ... val_143
v_ok val_113 val_146 ... val_161
wall wall wall ... wall
imp_3 player x_0 ... x_0
wall wall wall ... wall
```
They are very packed indeed and should practice social distancing.
### Part III: How we are misled
I would surely not define myself as a reverser. I was so tempted to consider the whole game as a black-box. At some time I tried to send `PCTF{AAAA...AAA}` - There is a larger delay for the green character to become red! We were excited and would try a timing attack.
Turns out it isn't the right way to go. If I have to reason why this happened, I would think the clock was a bit unstable, causing such an illusion.
### Part IV: ~~More reverse engineering~~ random walk, fast forwarded
We have been playing around with the source code since then. The first advancement happens when we make two changes to the code:
```diff
- zoomscreen 47x3
+ zoomscreen 47x50
```
Changing all the occurrence of `transparent` into `gray` - liberate all the characters!
It was so satisfying that I have watched the animation for more than 10 times during the CTF.
In the source code, there are three type of rules which seems important:
```r
[ val_135 | x_56 ] -> [ val_50 | x_56 ] again
# 4096 instructions - "conversion"
right [ val_125 | val_70 ] -> [ val_111 | ] again
# 4096 instructions - "elimination"
[ v_no | val_180 ] -> [ v_no | ] again
# 128 instructions - "final"
```
There is a bunch of final instructions that converts `v_yes` (the green character a.k.a. `fljldviokmmfmqzd`) into `v_no`. Why don't we label them red, indicating that they are bad?
Woah. So they are all initially on the rightmost of the board. We tried a bunch of things: encode them into runes, classify the characters into classes... and we end up with this amazing thingy:
We have to explain how can we classify characters into groups. Recalled from two minutes ago that we have three types of rules:
```r
[ a_i | x_k ] -> [ c_j | x_k ] again
# 4096 instructions - "conversion"
right [ c_k | b_i ] -> [ b_j | ] again
# 4096 instructions - "elimination"
[ v_no | b_i ] -> [ v_no | ] again
# 128 instructions - "final"
```
Mathematically, we have $A$, $B$ and $C$ being three classes of characters. In particular, $b_0\in B$ is the only element that keeps `v_yes` intact.
1. **[Conversion]** When $a_i\in A$ meets an input character, it will be replaced into some $c_j\in C$.
2. **[Elimination]** When $b_i\in B$ meets $c_k\in C$, $c_k$ will be eliminated. And $b_i$ will be replaced to some $b_j\in B$.
3. **[Final]** When $b_i\in B$ meets `v_yes` or `v_no`, it will be consumed. `v_yes` will remain unchanged only if the $b = b_0$.
I've labelled $A$ in brown, $B$ in red (except $b_0$ which is in green) and $C$ in blue.
It looks like $b\in B$ would consume an entire row of $c$'s while it moves to the left. That makes me thinking: is it equivalent to a system of linear equations?
:::warning
**Why?** I don't know... I think there must be a relationship between $b$ and $c$. Otherwise, we will be unable to find an efficient algorithm to solve for the flag.
:::
### Part V: Let's get mathy
I have just assumed that it is a linear system. But how can it be related? To begin, reimagine what actually are _conversion_, _elimination_ and _final_. Here comes a linear system:
$$
\begin{cases}\begin{matrix}
a_{11}x_1 &+& a_{12}x_2 &+& ... &+& a_{1n}x_n &=& b_1 \\
a_{21}x_1 &+& a_{22}x_2 &+& ... &+& a_{2n}x_n &=& b_2 \\
&&&& \vdots &&&& \\
a_{n1}x_1 &+& a_{n2}x_2 &+& ... &+& a_{nn}x_n &=& b_n
\end{matrix}\end{cases}
$$
Take a look on the map below. Is there a similarity?
_The cursor is mine. Forgive me for not removing the cursor inside the picture._
_This is the first frame when the game starts verifying my flag. Again the cursor is mine._
The brown runes are $a_{ij}$'s, the red (or green) ones are $b_i$'s in the linear system. The blue runes are evident now: they represents $a_{ij}x_j$'s. Therefore,
1. the _conversion_ property (that changes brown runes into blue when it meets a character) is a **multiplication**,
2. the _elimination_ property is a **summation**,
3. the _final_ property is to **verify** if the summation equals $b_0$.
We can now convert those instructions into math:
```r
[ a_i | x_k ] -> [ c_j | x_k ] again
# a_i * x_k = c_j
right [ c_k | b_i ] -> [ b_j | ] again
# b_i + c_k = b_j
[ v_yes | b_0 ] -> [ v_yes | ] again
# assume that the summation equals 0
```
---
How do I know if my guess is correct?
I was first looking for the _elimination_ (or _summation_) instruction. To be exact, I want to find invariants:
```r
right [ c_k | b_i ] -> [ b_i | ] again
# *** *** those are equal
```
It is made possible by the regex `right \[ c\d+ \| b(\d+) \] -> \[ b\1 \| \] again`.
There are 64 matches. Here are some of the results:
```r
right [ c44 | b7 ] -> [ b7 | ] again # c44 + b7 = b7
right [ c44 | b21 ] -> [ b21 | ] again # c44 + b21 = b21
right [ c44 | b8 ] -> [ b8 | ] again # c44 + b8 = b8
right [ c44 | b31 ] -> [ b31 | ] again # c44 + b31 = b31
...
```
`c44` appears in all of the matches! If $c_{44} + b_i = b_i$ for all $i$, we can imply that $c_{44} = 0$.
With this piece of fact, we can find the `i`'s and `j`'s with `a_i * x_j = c_44 = 0`. There are 127 matches, including:
```r
[ a46 | x23 ] -> [ c44 | x23 ] again # a46 * x23 = c44
[ a46 | x63 ] -> [ c44 | x63 ] again # a46 * x63 = c44
[ a46 | x48 ] -> [ c44 | x48 ] again # a46 * x48 = c44
[ a40 | x36 ] -> [ c44 | x36 ] again # a40 * x36 = c44
[ a4 | x36 ] -> [ c44 | x36 ] again # x4 * x36 = c44
...
```
From the matches, I can see that `a_i * x_j = c_44 = 0` if and only if `i = 46` or `j = 36`.
As there are 64 distinct elements, I could think of two possibilities: Either it is taken under modulo 64, or it is operated under $\text{GF}(2^6)$ (the finite field of 64 elements).
However, it is definitely not under modulo 64. The multiplication property shows $ax = 0$ happens if and only if either $a=0\ \text{or}\ x=0$.
This is not the case for operations under modulo 64. There are non-trivial solutions (where $a$ and $x$ are both non-zero): When $a=32$ and $x=4$, $ax = 32\times 4 = 128 \equiv 0\ (\text{mod}\ 64)$.
Eliminating the possibility being modulo 64 operated, we are assuming that the linear system is taken under $\text{GF}(2^6)$.
:::warning
**What if $\text{GF}(2^6)$ doesn't check out as well?** Well... that means my instinct is incorrect. This whole part is then redundant and meaningless.
:::
We can safely assume that $b_0 = 0$. We have already deduced that $a_{46} = x_{36} = c_{44} = 0$ as well. Knowing all the pairs of $(i, j, k)$ with $a_ix_j = c_k$ and $b_i + c_k = b_j$, we can find a mapping between $A, B, C, X$ and $\text{GF}(2^6)$.
Note that $g$ is a generator element for $\text{GF}(2^6)\setminus\{0\}$ and can be any element from the set. We can write $\text{GF}(2^6) = \{0, 1, g, g^2, ..., g^{62}\}$.
:::warning
**How?** We can assume that $a_p = 1$, $a_q = g$ and $x_r = 1$. This would allow us to find every single element of $A, B, C$ and $X$. We can find a correct solution by brute-forcing $p, q, r$ (there are less than $2^{18}$ combinations), and more importantly, there are multiple (a lot of) correct answers.
:::
For example, this is one of the possible solutions:
```
┌ g^48 g^16 ... g^28 ┐ ┌ g^56 ┐
│ g^60 g^61 ... g^7 │ │ g^50 │
A = │ g^15 g^62 ... g^26 │, b = │ g^14 │
│ ... │ │ ... │
└ g^10 g^46 ... g^20 ┘ └ g^6 ┘
```
### Part VI: The finale
Converting the whole thing in Sagemath, it is:
```python
F.<g> = GF(2^6)
A = Matrix(F, [
[g^48, g^16, g^2, g^22, g^57, g^3, g^17, g^36, g^27, g^23, g^33, g^56, g^54, g^9, g^30, g^27, g^1, g^21, g^39, g^53, g^37, g^44, g^4, g^61, g^0, g^27, g^30, g^16, g^59, g^20, g^37, g^26, g^2, g^36, g^20, g^23, g^35, g^58, g^62, g^32, g^59, g^49, g^0, g^32, g^28],
[g^60, g^61, g^16, g^19, g^29, g^40, g^36, g^23, g^50, g^34, g^20, g^49, g^58, g^33, g^31, g^13, g^41, g^60, g^6, g^62, g^60, g^61, g^28, g^14, g^50, g^45, g^52, g^11, g^51, g^39, g^8, g^29, g^12, g^1, g^45, g^48, g^52, g^36, g^16, g^10, g^19, g^5, g^20, g^7, g^7],
[g^15, g^62, g^4, g^13, g^17, g^7, g^34, g^54, g^59, g^57, g^31, g^56, g^44, g^31, g^37, 0, g^60, g^47, g^20, g^4, g^48, g^34, g^46, g^51, g^43, g^26, g^12, g^3, g^5, g^53, g^53, g^12, g^54, g^19, g^32, g^2, g^45, g^52, g^60, g^22, g^28, g^17, g^20, g^23, g^26],
[g^15, g^53, g^53, g^50, g^55, g^59, g^15, g^17, g^36, g^57, g^6, g^57, g^10, g^13, g^6, g^10, g^12, g^60, g^52, g^56, g^51, g^19, g^50, g^32, g^20, g^50, g^50, g^60, g^26, g^15, g^34, g^61, g^48, g^10, g^58, g^40, g^41, g^6, g^57, g^50, g^29, g^48, g^24, g^21, g^44],
[g^62, g^16, 0, g^54, g^45, g^56, g^52, g^0, g^43, g^4, g^13, g^26, g^43, g^15, g^20, g^22, g^45, g^36, g^6, g^54, g^3, g^52, g^59, g^57, g^23, g^30, g^17, g^42, g^48, g^1, g^3, g^18, g^20, g^37, g^42, g^32, g^19, g^19, g^47, g^46, g^27, g^54, g^21, g^30, g^26],
[g^53, g^57, g^11, g^1, g^5, g^0, g^17, g^2, g^40, g^26, g^43, g^55, g^28, g^39, g^62, g^31, g^35, g^55, g^0, g^31, g^9, g^58, g^20, g^18, g^8, g^5, g^45, g^38, g^48, g^36, g^37, g^33, g^14, g^56, g^1, g^39, g^1, g^7, g^32, g^17, g^54, g^2, g^4, g^19, g^6],
[g^26, g^26, g^43, g^15, g^39, g^28, g^47, g^24, g^58, g^5, g^5, g^4, 0, g^4, g^39, g^11, g^44, g^62, g^45, g^11, g^20, g^51, g^61, g^4, g^59, g^21, g^8, g^17, g^54, g^15, g^37, g^62, g^12, 0, g^53, g^44, 0, g^23, g^42, g^3, g^31, g^7, g^56, g^9, g^1],
[g^11, g^57, 0, g^24, g^4, g^33, g^33, g^52, g^60, g^23, g^44, g^36, g^5, g^46, g^24, g^34, g^21, g^44, g^6, 0, g^21, g^62, g^60, g^4, g^16, g^32, g^10, g^59, g^45, g^42, g^37, g^35, g^20, g^35, g^7, g^18, g^58, g^27, g^30, g^16, g^23, g^52, g^32, g^62, g^61],
[g^14, g^19, g^33, g^37, g^2, g^43, g^47, g^11, g^60, g^16, g^31, g^1, g^43, g^15, g^57, g^5, g^27, g^49, g^20, g^14, g^36, g^10, g^42, g^41, 0, g^43, g^55, g^62, g^26, g^55, g^38, g^50, g^57, g^3, g^59, g^7, g^4, g^19, g^48, g^9, g^47, g^33, g^4, g^16, g^20],
[g^47, g^49, g^25, g^32, g^46, g^34, g^62, g^50, g^29, g^14, g^12, g^35, g^17, g^30, g^9, g^35, g^54, g^38, g^8, g^25, g^5, g^62, g^4, g^10, g^49, g^26, g^56, g^15, g^35, g^40, g^61, g^40, g^49, g^27, g^11, g^31, g^19, g^42, g^2, g^17, g^55, g^29, g^40, g^25, g^26],
[g^20, g^51, g^60, g^46, g^33, g^10, g^13, g^8, g^20, g^31, g^14, g^52, g^29, g^35, g^14, g^30, g^19, g^36, g^4, g^6, g^17, g^30, g^45, g^13, g^55, g^36, g^54, g^37, g^51, g^25, g^53, g^37, g^7, g^46, g^38, g^39, g^48, g^59, g^26, g^40, g^32, g^25, g^3, g^46, g^21],
[g^47, g^39, g^22, g^21, g^21, g^23, g^27, g^11, g^13, g^22, g^61, g^36, g^48, g^19, g^57, g^34, g^50, g^47, g^52, g^49, g^42, g^59, g^9, g^54, g^52, g^61, g^50, g^30, g^52, g^29, g^27, g^28, g^16, g^13, g^13, g^28, g^25, g^3, g^19, g^53, g^19, g^58, g^41, g^33, g^23],
[g^15, g^32, g^4, g^13, g^10, g^38, g^24, g^27, g^9, g^6, g^33, g^24, g^27, g^23, g^26, g^12, g^31, g^30, g^46, g^23, g^17, g^16, g^58, g^37, g^0, g^2, g^30, g^45, g^18, g^11, g^36, g^21, g^4, g^8, g^36, g^25, g^56, g^28, g^18, g^11, g^36, g^27, g^12, g^62, g^61],
[g^52, g^56, g^35, g^34, g^42, g^36, g^33, g^51, g^56, g^44, g^56, g^39, g^3, g^3, g^7, g^6, g^19, g^54, g^37, g^17, g^13, g^13, g^1, g^1, g^55, g^36, g^15, g^55, g^16, g^22, g^16, g^21, g^33, g^38, g^41, g^7, g^47, g^22, g^14, g^6, g^59, g^43, 0, g^49, g^52],
[g^11, g^25, g^24, g^11, g^37, g^5, g^48, g^62, g^24, g^54, g^33, g^31, g^35, g^22, 0, g^4, g^34, g^39, g^4, g^54, g^20, g^31, g^45, g^44, g^21, g^59, g^9, g^60, g^43, g^60, g^47, g^7, g^15, g^38, g^34, g^40, g^8, g^1, g^3, g^1, g^45, g^16, g^43, g^33, g^4],
[g^30, g^58, g^45, 0, g^43, g^33, g^40, g^25, g^15, g^22, 0, g^43, g^57, g^31, g^12, g^38, g^14, g^32, g^21, g^16, g^14, g^38, g^61, g^44, g^40, g^22, g^37, g^4, g^52, g^51, g^51, g^1, g^9, g^23, g^54, g^49, g^51, g^7, g^36, g^6, g^37, g^41, g^17, g^60, g^54],
[g^41, g^0, g^20, g^32, g^20, g^45, g^48, g^5, g^35, g^0, g^59, g^58, g^58, g^40, g^13, g^1, g^57, g^62, g^2, g^7, g^61, g^55, g^53, g^18, g^17, g^9, g^46, g^54, g^11, g^13, g^28, g^61, g^21, g^52, g^25, g^10, g^44, g^8, g^49, g^4, g^17, g^19, g^6, g^44, g^33],
[g^26, g^6, g^60, g^54, g^33, g^62, g^11, g^24, g^30, g^13, g^36, g^25, g^35, g^7, g^58, g^13, g^38, g^59, g^31, g^12, g^57, g^45, g^33, g^62, g^58, g^34, g^21, g^44, g^47, g^20, g^16, g^48, g^53, g^38, g^17, g^44, g^51, g^47, g^46, g^51, g^11, g^28, g^5, g^54, g^7],
[g^7, g^23, g^11, g^10, g^30, g^15, g^45, g^22, g^33, g^36, g^8, g^60, g^0, g^36, g^25, g^12, g^41, g^14, g^3, g^10, g^51, g^48, g^1, g^2, g^13, g^39, g^38, g^54, g^25, g^62, g^1, g^21, g^33, g^48, g^14, g^38, g^7, g^42, g^3, g^5, g^51, g^45, g^40, g^54, g^46],
[g^12, g^16, g^62, g^41, g^30, g^43, g^20, g^52, g^4, g^24, g^9, g^17, g^22, g^18, g^36, g^42, g^4, g^14, g^62, g^17, g^12, g^62, g^15, g^58, g^29, g^25, g^12, g^38, g^32, g^19, g^20, g^9, 0, g^53, 0, g^31, g^22, g^40, g^56, g^37, g^46, g^8, g^55, g^52, g^10],
[g^54, g^3, g^36, g^36, g^51, g^9, g^7, g^23, g^58, g^32, g^47, g^47, g^48, g^62, g^6, g^6, g^58, g^4, g^14, g^15, g^22, g^4, g^9, g^9, g^21, g^61, g^36, g^10, g^8, g^15, g^49, g^11, g^41, g^41, g^0, g^18, g^61, g^28, g^33, g^44, g^40, g^56, g^3, g^14, g^28],
[g^8, g^35, g^51, g^18, g^36, g^46, g^31, g^18, g^40, g^43, g^62, g^21, g^21, g^8, g^9, g^34, g^26, g^50, g^62, g^58, g^22, 0, g^12, g^36, g^44, g^36, g^22, g^48, g^46, g^61, g^48, g^51, g^61, g^12, g^43, g^38, g^14, g^52, g^62, g^25, g^15, g^25, g^28, g^1, g^33],
[g^21, g^50, 0, g^25, g^55, g^5, g^47, g^5, g^52, g^62, g^47, g^18, g^43, g^24, g^52, g^6, g^35, g^16, g^46, g^0, g^3, g^15, g^2, g^58, g^23, g^41, g^58, g^12, g^34, g^24, g^36, g^5, g^0, g^56, g^34, g^10, g^41, g^29, g^39, g^28, 0, g^46, g^21, g^7, g^39],
[g^18, g^19, g^55, g^10, g^33, g^62, g^59, g^15, g^17, g^40, g^23, g^25, g^6, g^0, g^53, g^21, g^0, g^5, g^42, g^24, g^16, g^44, g^24, g^20, g^31, g^33, g^41, g^19, 0, g^49, g^22, g^20, g^42, g^36, g^23, g^28, g^53, g^6, g^23, g^49, g^1, g^3, g^57, g^37, g^43],
[g^19, g^52, g^60, g^43, g^11, g^42, g^32, g^52, g^26, g^61, g^13, g^43, g^56, g^50, g^31, g^34, g^17, g^28, g^18, g^38, g^39, g^62, g^39, g^62, g^5, g^35, g^22, g^55, g^6, g^43, g^62, g^51, g^15, g^36, g^54, g^62, g^58, g^49, g^37, g^8, g^36, g^48, g^18, g^45, g^6],
[g^45, g^59, g^24, g^18, g^28, g^49, g^7, g^46, g^27, g^14, g^15, g^37, 0, g^47, g^54, g^57, g^21, g^38, g^35, g^57, g^12, g^57, g^55, g^3, g^50, g^15, g^51, g^18, g^26, g^8, g^25, g^56, g^45, g^9, g^33, g^5, g^6, g^20, g^57, g^60, g^32, g^8, g^8, g^20, 0],
[g^39, g^2, g^60, g^1, g^28, g^12, g^5, g^54, g^56, g^32, g^10, g^43, 0, g^32, g^47, g^10, g^57, g^32, g^48, 0, 0, 0, g^23, g^16, g^3, g^2, g^23, 0, g^3, g^34, g^36, g^30, g^44, g^31, g^54, g^35, g^47, g^58, g^18, g^5, g^47, g^29, g^33, g^19, g^18],
[g^56, g^30, g^16, g^54, g^38, 0, 0, g^0, g^39, g^9, g^0, g^35, g^52, g^29, g^26, g^11, g^10, g^60, g^49, g^23, g^61, g^23, g^44, g^39, g^47, g^52, g^1, g^12, g^45, g^7, g^54, g^11, g^59, g^1, g^56, g^4, g^39, g^32, g^34, g^49, g^2, g^48, g^44, g^49, g^59],
[g^47, g^49, 0, g^59, g^19, g^8, g^5, g^15, g^44, g^26, g^23, g^19, g^39, g^36, g^53, g^12, g^11, g^20, g^30, g^52, g^54, g^46, g^48, g^31, g^46, g^8, g^35, g^40, g^42, g^54, g^22, g^14, g^62, g^4, g^51, g^1, g^42, g^45, g^58, g^57, g^6, g^29, g^41, g^15, g^24],
[g^45, g^14, g^13, g^0, g^49, g^23, g^13, g^8, g^12, g^14, g^9, g^10, g^8, g^11, g^29, g^12, g^26, g^43, g^43, g^26, g^38, g^32, g^14, g^54, g^51, g^14, g^44, g^40, g^5, g^27, g^48, g^36, g^19, g^19, g^15, g^0, g^1, g^20, g^36, g^11, g^3, g^50, g^26, g^5, g^12],
[g^62, g^30, g^0, g^31, g^34, g^23, g^18, g^7, g^29, g^57, g^24, g^54, g^5, g^24, g^57, g^23, g^3, g^41, g^34, g^37, g^29, g^59, g^28, g^11, g^41, g^4, g^52, g^40, g^58, g^21, g^19, g^51, g^42, g^54, g^9, g^25, g^49, g^8, g^46, g^19, g^60, g^18, g^16, g^26, g^59],
[g^54, g^47, g^51, g^37, g^12, g^15, g^47, g^61, g^10, g^62, g^44, g^44, g^52, g^25, g^56, g^56, g^58, g^54, g^32, g^15, g^22, g^11, 0, g^39, g^6, g^11, g^58, g^14, g^33, g^39, g^0, g^32, g^61, g^12, g^14, g^32, g^12, g^3, g^16, g^32, g^4, g^28, g^61, g^47, g^30],
[g^39, g^46, g^27, g^3, g^36, g^31, g^6, g^50, g^6, g^14, g^4, g^51, g^22, g^15, g^4, g^35, g^11, g^62, g^8, g^11, g^9, g^34, g^57, g^39, g^59, g^19, g^22, g^0, g^45, g^6, g^43, g^32, g^61, g^35, g^53, g^61, g^16, g^23, g^39, g^51, g^59, g^33, g^49, g^51, g^55],
[g^21, g^46, g^34, g^45, g^59, g^34, g^59, g^39, g^11, g^49, g^62, g^11, g^49, g^0, 0, g^23, g^56, g^39, g^43, g^8, g^14, g^27, g^6, g^59, g^24, g^51, g^51, g^27, g^27, g^52, g^44, g^47, g^49, g^28, g^50, g^60, g^5, g^34, g^19, g^58, g^56, g^17, g^21, g^16, 0],
[g^21, g^35, g^12, g^29, g^3, g^42, g^41, g^56, g^17, g^50, g^29, g^22, g^50, g^46, g^7, g^37, g^6, g^39, g^61, g^57, g^37, g^21, g^21, g^16, g^52, g^62, g^59, g^33, g^18, g^58, g^16, g^61, g^14, g^62, g^7, g^14, g^20, g^33, g^24, g^60, g^55, g^53, g^1, g^31, g^23],
[g^27, g^0, g^51, g^38, g^35, g^20, g^4, g^18, g^33, g^33, g^36, g^5, g^39, g^45, g^26, 0, g^39, g^23, g^54, g^50, g^56, g^27, g^38, g^7, g^61, g^30, g^46, g^10, g^12, g^27, g^26, g^26, g^52, g^13, g^33, g^7, g^47, g^26, g^33, g^34, g^21, g^46, g^62, g^27, g^4],
[g^43, g^56, g^57, g^31, g^11, g^56, g^23, g^7, g^12, g^35, g^32, g^32, g^23, g^32, g^57, g^44, g^18, g^39, g^51, g^34, g^27, g^5, g^46, g^37, g^11, g^61, g^4, g^38, g^42, g^49, g^46, g^19, g^28, g^7, g^60, g^45, g^44, g^10, g^55, g^59, g^7, g^34, g^16, g^28, g^42],
[0, g^3, g^50, g^46, g^46, g^14, g^37, g^12, g^3, g^49, g^46, g^13, g^59, g^1, g^52, g^39, g^27, g^49, g^55, g^44, g^52, g^14, g^36, g^61, 0, g^4, g^38, 0, g^44, g^18, g^57, g^40, g^5, g^19, g^4, g^48, g^28, g^37, g^21, g^18, g^21, g^5, g^46, g^9, g^62],
[g^41, g^33, g^30, g^61, g^4, g^41, 0, g^2, g^38, g^19, g^55, g^19, g^16, g^25, g^31, g^40, g^10, g^20, g^0, g^20, g^18, g^44, g^2, g^39, g^20, g^23, g^54, g^13, g^0, g^24, g^16, g^3, g^7, g^46, g^37, g^48, g^48, g^10, g^47, g^39, g^42, g^23, g^57, g^49, g^30],
[g^47, g^50, g^1, g^41, g^2, g^19, g^47, g^62, g^17, g^23, g^56, g^56, g^20, g^39, g^3, g^23, g^4, g^21, g^8, g^39, g^55, g^18, g^39, g^52, g^24, g^8, g^40, g^33, g^32, g^18, g^49, g^52, g^50, g^53, g^34, g^47, g^57, g^41, g^32, g^3, g^31, g^13, g^27, g^32, g^6],
[g^62, g^18, g^14, g^43, g^1, g^46, g^9, g^12, g^21, g^36, g^20, g^51, g^28, g^26, g^22, g^58, g^42, g^46, g^9, g^50, g^6, g^19, g^46, g^47, 0, g^20, g^19, g^23, g^51, g^41, g^8, g^57, g^62, g^20, g^10, g^2, g^32, g^53, g^20, g^41, g^26, g^52, g^52, g^26, g^55],
[g^11, g^27, g^22, g^19, g^61, g^35, g^22, g^62, g^48, g^32, g^23, g^41, g^51, g^17, g^24, g^42, g^11, g^17, g^58, g^28, g^56, g^29, g^58, g^28, g^24, g^2, g^8, g^30, g^52, g^43, g^10, g^18, g^23, g^10, g^37, g^17, g^55, g^53, g^5, g^48, g^37, g^17, g^14, g^6, g^60],
[g^21, g^60, g^45, g^40, g^15, g^10, g^21, g^46, g^36, g^1, g^15, g^31, g^17, g^5, g^18, g^2, g^9, g^43, g^40, g^4, g^46, g^59, g^0, g^10, g^48, g^49, g^36, g^11, g^55, g^1, g^49, g^15, g^6, g^5, g^17, g^24, g^55, g^56, g^36, g^62, g^2, g^20, g^5, g^40, g^8],
[g^27, g^24, g^58, g^19, g^9, g^6, g^59, g^5, g^8, g^40, g^42, g^40, g^62, g^11, g^59, g^9, g^53, g^36, g^32, g^33, g^28, g^11, g^58, g^29, g^21, g^46, g^14, g^15, g^47, g^52, g^3, g^51, g^19, g^31, g^20, g^51, g^59, g^23, g^35, g^5, g^24, g^32, g^44, g^16, g^12],
[g^10, g^46, g^15, g^14, g^55, g^43, g^9, g^59, g^17, g^20, g^30, g^55, g^22, g^3, g^61, g^8, g^37, g^8, g^16, g^55, g^48, g^57, g^22, g^9, g^12, g^17, g^52, g^36, g^38, g^11, g^34, g^14, g^54, g^62, g^60, g^57, g^3, g^26, g^42, g^12, g^29, g^8, g^50, g^10, g^20]
])
b = vector(F, [g^56, g^50, g^14, g^21, g^25, g^57, g^14, g^24, g^28, g^15, g^55, g^30, g^39, g^24, g^35, g^49, g^0, g^58, g^42, g^36, g^8, g^18, g^53, g^4, g^53, g^59, g^50, g^53, g^48, g^57, g^20, g^6, g^37, g^10, g^45, g^46, g^27, g^48, 0, g^2, g^47, g^0, g^46, g^25, g^6])
# this means that "A" is a g^0, "B" is g^16, "C" is g^48, etc.
list_x = [g^0, g^16, g^48, g^60, g^37, g^51, g^56, g^1, g^21, g^11, g^52, g^46, g^54, g^44, g^17, g^61, g^28, g^27, g^53, g^59, g^19, g^55, g^25, g^12, g^50, g^5, g^20, g^45, g^33, g^18, g^58, g^23, g^4, g^24, g^41, g^36, 0, g^47, g^39, g^34, g^3, g^13, g^8, g^10, g^32, g^29, g^6, g^43, g^9, g^62, g^40, g^38, g^42, g^14, g^2, g^7, g^49, g^26, g^30, g^22, g^35, g^31, g^57, g^15]
charmap = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789{}'
```
Finally we have revealed what $a_{ij}$'s and $b_i$'s are. We can solve the linear system with Sagemath and it will return the corresponding vector $(x_1, ..., x_n)$ - and this is our flag!
```python
sol = A.solve_right(b)
''.join([charmap[list_x.index(c)] for c in sol])
# PCTF{CTFs4R3Ju5TPuzZLeHUnTSWi7hM0reCoMPut3R5}
```
{%youtube _qNSBe-_3D0 %}
Well, that was it! I spent a good 7 hours on solving it and I had a lot of fun. We gained insights by patching the programing and visualizing stuffs. Thanks PPP for the game!
###### tags: `CTF`
Sign in with Wallet
Connect another wallet