Tags: group-theory linear_algebra sagemath math 

Rating: 5.0

**Warning: group theory ahead.** You may find it useful to skim Chapter 1 of [https://venhance.github.io/napkin/Napkin.pdf](https://venhance.github.io/napkin/Napkin.pdf) (pp 41-52) before reading.

## Problem Statement

Upon accessing the server and bypassing the MD5 hash check

```
MD5 for 3b4urk4e0gvVtZXdRwGaWm0jZYytvTRS if you may!
2b0e5128503834314bdce94132cbd7d1
```

we're presented with the following text:

```
The goal of this challenge consists in retrieving the intersection of the generated sets related by the provided operation in the given table
Input:
p : dimension of the table
line of p element: the header of the table
p lines of p elements: the operation in table form
n: number of elements of first set
n lines of strings (each line is an element of the set)
m: number of elements of second set
m lines of strings (each line is an element of the set)

The operation defines the sets, meaning you can create new elements of the set by combining them
with this operation.
Be careful. The table might be a bit messy, use the line of p elements to help you.

Consider the strings as arrays and apply the operation from the table elementwise to crate new elements

The intersection is defined as the elements shared between the two sets

Provide the answer as emojis separated by spaces for 15 times to get the flag.
```
![f](https://imgur.com/FF4Cm5Y.png)
## Observations
Now how do we make sense of this?

### The group G
So for this test case, we're given an operation table, delightfully obfuscated by way of emojis.

![](https://imgur.com/FyQ6QWC.png)

We're told that `The operation is given by table[i][j] = header[i] OP header[j]` -- so we're essentially dealing with the following operation table:

![](https://imgur.com/N5ndRfi.png)

where the top row and leftmost column are the `header`.

Now we make a few observations:
- Each emoji appears exactly once in each row and exactly once in each column of the grid, ignoring the headers (i.e. the grid is a Latin square).
- There is exactly one row and exactly one column that match exactly the elements in the header (i.e. there is an 'identity' emoji).

So wishful thinking would seem to suggest that this operation table might be a group... let's just assume associativity holds. Let this group be $G$.

### Intersections of subgroups
Now what are we actually doing with this group? Well, we're told the following:

```
For each couple of arrays A, B the resulting array is C[i] = A[i] OP B[i]. From a given set of arrays you must repeatedly apply the operation and add the result to the set.
```
Let's take a look at the sets we've been given.

![](https://imgur.com/MOHpzNu.png)

Now each element in the sets $a$ and $b$ is a tuple of 18 elements in $G$ -- each element is a member of the _product group_ $(G\times G\times G...\times\, G, \cdot)$ (in dubious notation this is $G^{18}$), whose group operation is as follows:
$$(a_1, a_2,\,...\,a_{18}) \cdot (b_1, b_2,\,...\,b_{18}) = (a_1\cdot b_1, a_2\cdot b_2,\,...\,a_{18}\cdot b_{18}) \in G^{18}$$

We're told that we want the `intersection of the generated sets` -- in other words, we want the intersection of the subgroup generated by $a$, $\langle a \rangle$, and the subgroup generated by $b$, $\langle b \rangle$.

Our first thought might be to attack the problem with brute force -- i.e. naively generate all elements in $\langle a \rangle$ and all elements in $\langle b \rangle$, à la [https://math.stackexchange.com/questions/1758649/an-algorithm-to-find-a-subgroup-generated-by-a-subset-of-a-finite-group](https://math.stackexchange.com/questions/1758649/an-algorithm-to-find-a-subgroup-generated-by-a-subset-of-a-finite-group).

There's a little problem, though... as $\left|G\right|=11$, $\left|G^{18}\right|=11^{18}\approx 6\times 10^{18}$... so our generated subgroups could be a little on the large side.

But we can make another observation... if we connect to the server a few times and stare at the groups really carefully, we might notice that all the sizes of groups seem to be prime -- in other words, by Lagrange's theorem, $G$ is simply the cyclic group of order $n$ ($\mathbb{Z}/n\mathbb{Z}$), otherwise known as 'the natural numbers modulo $n$'.

## Reinterpreting the problem
Let's relabel the elements in $G$ and finally get rid of those annoying emoji...

![](https://imgur.com/mU5I5M2.png)

We first find the identity element:
```python
mapping = [-1 for _ in range(len(ops))]
identity = table.index(ops)
mapping[identity]=0
```

Then without loss of generality we can map the first non-identity element to 1:
```python
oneel = 0 if identity != 0 else 1
mapping[oneel]=1
```

Now notice that (as there is a bijection between the cyclic group of order $n$ and the natural numbers modulo $n$), if $a\to 1$ for some $a\in G$, then $a\cdot a\to 1+1=2$ ... and so $a^n\to n$. So we can relabel our elements as follows:

![](https://imgur.com/WniPJs8.png)

Let's relabel our sets $a$ and $b$ as well:

```python
def getVal(emoj):
return mapping[ops.index(emoj)]

opsnum = [getVal(x) for x in ops]
tabnum = [[getVal(x) for x in y] for y in table]
setanum = [[getVal(x) for x in y] for y in seta]
setbnum = [[getVal(x) for x in y] for y in setb]
```

Our set $a$ is now as follows:
```
[[4, 6, 5, 10, 8, 6, 6, 4, 8, 0, 4, 9, 1, 6, 6, 1, 6, 4],
[1, 8, 0, 3, 4, 10, 8, 7, 9, 6, 9, 4, 6, 6, 3, 1, 6, 10],
[5, 8, 7, 9, 6, 1, 6, 2, 7, 0, 5, 5, 0, 4, 8, 1, 5, 7],
[3, 10, 3, 5, 9, 5, 3, 6, 9, 5, 4, 5, 5, 3, 5, 1, 2, 4],
[10, 8, 3, 7, 5, 8, 1, 5, 6, 8, 10, 6, 8, 7, 6, 2, 9, 9],
[9, 5, 2, 1, 1, 9, 9, 7, 10, 8, 7, 10, 8, 5, 4, 2, 8, 4],
[10, 7, 5, 9, 10, 2, 3, 1, 5, 7, 4, 0, 10, 2, 5, 1, 1, 4],
[2, 3, 9, 4, 10, 0, 4, 6, 5, 8, 3, 7, 7, 3, 10, 4, 5, 1],
[1, 8, 8, 3, 10, 4, 9, 1, 6, 1, 7, 9, 7, 0, 6, 5, 8, 0],
[2, 6, 1, 2, 6, 9, 10, 4, 6, 8, 8, 10, 0, 5, 2, 1, 1, 3],
[2, 1, 0, 0, 4, 1, 2, 1, 7, 1, 1, 0, 9, 10, 8, 10, 3, 9],
[1, 6, 7, 1, 10, 2, 7, 3, 5, 2, 6, 5, 8, 6, 3, 0, 8, 2],
[6, 8, 10, 7, 9, 7, 9, 2, 3, 5, 4, 4, 10, 2, 8, 5, 2, 9],
[1, 10, 8, 8, 2, 1, 1, 9, 4, 0, 2, 3, 3, 8, 6, 3, 4, 1],
[8, 9, 6, 1, 7, 5, 2, 2, 8, 5, 4, 10, 3, 6, 10, 6, 6, 6],
[9, 4, 1, 6, 5, 10, 6, 8, 1, 2, 0, 1, 10, 10, 3, 1, 5, 7],
[10, 3, 4, 2, 3, 1, 3, 10, 3, 10, 8, 7, 3, 4, 5, 6, 10, 1],
[0, 9, 0, 5, 6, 4, 5, 3, 1, 2, 9, 3, 2, 2, 3, 5, 10, 0],
[1, 4, 4, 0, 10, 1, 8, 4, 8, 7, 0, 9, 5, 4, 6, 9, 10, 3],
[1, 9, 7, 2, 10, 2, 10, 6, 5, 6, 8, 8, 3, 0, 5, 10, 1, 8]]
```
and our set $b$ is
```
[[10, 0, 6, 1, 1, 2, 3, 4, 1, 8, 10, 0, 5, 4, 6, 0, 8, 7],
[3, 9, 6, 6, 0, 0, 1, 4, 2, 8, 1, 4, 7, 2, 3, 9, 1, 9],
[10, 7, 4, 6, 9, 0, 9, 6, 8, 9, 10, 5, 1, 10, 7, 3, 3, 9],
[1, 1, 2, 3, 6, 5, 1, 5, 6, 7, 6, 6, 1, 7, 7, 2, 4, 3],
[3, 3, 10, 9, 10, 1, 5, 3, 10, 0, 2, 7, 7, 10, 4, 2, 1, 5],
[7, 9, 8, 8, 3, 9, 6, 5, 7, 2, 4, 10, 0, 3, 0, 8, 4, 3],
[8, 4, 5, 6, 3, 2, 0, 4, 10, 5, 8, 3, 0, 1, 0, 5, 0, 1],
[10, 3, 10, 7, 5, 3, 0, 1, 2, 10, 1, 7, 10, 2, 8, 7, 9, 0],
[1, 6, 2, 10, 8, 8, 0, 6, 9, 3, 8, 0, 2, 3, 7, 5, 6, 7],
[0, 6, 0, 2, 0, 2, 3, 5, 10, 8, 8, 6, 5, 8, 0, 1, 9, 9],
[4, 6, 8, 4, 10, 9, 2, 1, 1, 0, 0, 6, 4, 3, 8, 9, 2, 1],
[1, 7, 9, 3, 2, 6, 9, 1, 1, 1, 9, 3, 2, 8, 1, 3, 9, 1],
[9, 7, 3, 10, 4, 1, 8, 5, 5, 8, 0, 4, 10, 8, 5, 1, 2, 0],
[6, 7, 10, 0, 5, 9, 0, 1, 2, 5, 7, 10, 1, 3, 3, 4, 0, 7],
[1, 8, 3, 6, 6, 8, 8, 1, 2, 6, 3, 10, 8, 1, 10, 6, 0, 4],
[1, 4, 1, 8, 6, 4, 1, 8, 3, 10, 5, 2, 9, 8, 8, 9, 7, 5],
[0, 8, 9, 0, 8, 6, 2, 2, 9, 8, 7, 6, 0, 3, 3, 7, 9, 10],
[8, 7, 9, 10, 9, 8, 7, 3, 3, 9, 4, 10, 9, 7, 9, 4, 1, 5],
[3, 2, 5, 2, 6, 10, 4, 9, 10, 1, 9, 1, 3, 10, 4, 1, 6, 1],
[5, 0, 3, 4, 7, 1, 1, 8, 3, 0, 9, 3, 2, 2, 4, 5, 0, 3]]
```

Notice that the group operation on $G^{18}$ now becomes _element-wise addition_: in other words $$(10, 0, 6, 1,\, ...,\, 8, 7) \cdot (3, 9, 6, 6,\, ...,\, 1, 9)\\\\ = (10+3, 0+9, 6+6, 1+6,\, ...,\, 8+1, 7+9)$$

This makes life a lot easier... so all possible elements in the subgroup $\langle a\rangle$ are simply linear combinations of $a_0,\,a_1,\,...\,a_{19}$ (where $a_i$ denotes the $i$th element in the set $a$, using the ordering given in the array above... notationally dubious, I know), and likewise for $\langle b\rangle$.

Let's be a little more precise about what we want to find now. Any element in the generated subgroup $\langle a \rangle$ can be represented as $a_0^{p_0}a_1^{p_1}...a_{19}^{p_{19}}$, and likewise any element in $\langle b \rangle$ can be represented as $b_0^{q_0}b_1^{q_1}...b_{19}^{q_{19}}$ for some $p_i, q_i \in \mathbb{N}$ (notice that order doesn't matter as addition is commutative / the cyclic group is abelian).

This is equivalent to saying that any element in $\langle a \rangle$ can be represented as $p_0\mathbf{a_0} + p_1\mathbf{a_1} + ... + p_{19}\mathbf{a_{19}}$, and any element in $\langle b \rangle$ can be represented as $q_0\mathbf{b_0} + q_1\mathbf{b_1} + ... + q_{19}\mathbf{b_{19}}$, if we treat $\mathbf{a_i}$ and $\mathbf{b_i}$ as vectors.

So we want to find suitable values of $p_i$ and $q_i$ such that $$p_0\mathbf{a_0} + p_1\mathbf{a_1} + ... + p_{19}\mathbf{a_{19}} = q_0\mathbf{b_0} + q_1\mathbf{b_1} + ... + q_{19}\mathbf{b_{19}} \mod |G|$$ or in other words $$p_0\mathbf{a_0} + p_1\mathbf{a_1} + ... + p_{19}\mathbf{a_{19}} - q_0\mathbf{b_0} - q_1\mathbf{b_1} - ... - q_{19}\mathbf{b_{19}} = \mathbf{0} \mod 11$$
## Linear Algebra
So now our problem turns into one of linear algebra. We have the following simultaneous equations we want to solve:

$$\begin{aligned}
p_0a_{0,0} + p_1a_{1,0} \,+\,...\,+\, p_{19}a_{19,0} - q_0b_{0,0}- q_1b_{1,0} \,-\, ... \,-\, q_{19}b_{19,0} &= 0 \mod 11\\\\
p_0a_{0,1} + p_1a_{1,1} \,+\,...\,+\, p_{19}a_{19,1} - q_0b_{0,1}- q_1b_{1,1} \,-\, ... \,-\, q_{19}b_{19,1} &= 0 \mod 11\\\\
...\\\\
p_0a_{0,10} + p_1a_{1,10} \,+\,...\,+\, p_{19}a_{19,10} - q_0b_{0,10}- q_1b_{1,10} \,-\, ... \,-\, q_{19}b_{19,10} &= 0 \mod 11\\\\
\end{aligned}$$

Alternatively, we can write this as a matrix-vector multiplication:
$$
\begin{bmatrix}
a_{0,0} & ... & a_{19,0} & -b_{0,0} & ... & -b_{19,0} \\\\
... & & ... & ... & & ... \\\\
a_{0,10} & ... & a_{19,10} & -b_{0,10} & ... & -b_{19,10} \\\\
\end{bmatrix}
\begin{pmatrix}
p_0\\\\...\\\\p_{19}\\\\q_0\\\\...\\\\q_{19}\\\\
\end{pmatrix}
=
\begin{pmatrix}
0\\\\...\\\\0\\\\0\\\\...\\\\0\\\\
\end{pmatrix}
\mod 11
$$

A slight issue is that this equation has multiple solutions (a trivial solution being to set all the coefficients to 0).

At this point we note that the question says `If multiple answers are possible, send the one beginning with chr(128514)` -- in other words, we need to add another condition such that the first element of $p_0\mathbf{a_0} + p_1\mathbf{a_1} + ... + p_{19}\mathbf{a_{19}}$ is equal to $x$, where $x$ is the natural number we mapped the element `chr(128514)` to. More precisely, we want $$p_0a_{0,0} + p_1a_{1,0} + ... + p_{19}a_{19,0}=x$$

So let's add this as another equation to our matrix:

$$
\begin{bmatrix}
a_{0,0} & ... & a_{19,0} & 0 & ... & 0 \\\\
a_{0,0} & ... & a_{19,0} & -b_{0,0} & ... & -b_{19,0} \\\\
... & & ... & ... & & ... \\\\
a_{0,10} & ... & a_{19,10} & -b_{0,10} & ... & -b_{19,10} \\\\
\end{bmatrix}
\begin{pmatrix}
p_0\\\\...\\\\p_{19}\\\\q_0\\\\...\\\\q_{19}\\\\
\end{pmatrix}
=
\begin{pmatrix}
x\\\\0\\\\...\\\\0\\\\0\\\\...\\\\0\\\\
\end{pmatrix}
\mod 11
$$

Now we just need to generate the matrix and solve for $p_i$ and $q_i$.

The first part can be done with some Python:

```python
def transpose(m):
return [[m[j][i] for j in range(len(m))] for i in range(len(m[0]))]
setanumt = transpose(setanum)
setbnumt = transpose(setbnum)
mat = [setanumt[0]+[0 for _ in range(len(setanumt[0]))]]+[setanumt[i]+list(map(lambda x:-x,setbnumt[i])) for i in range(len(setanumt))]
vec = [x]+[0 for _ in range(len(mat)-1)]
```

To actually solve the simultaneous equations, we open ~~our grimoire of dark arts and arcane magicks~~ SageMath. After some Googling I came across [https://ask.sagemath.org/question/37146/solving-modular-systems-of-equation/](https://ask.sagemath.org/question/37146/solving-modular-systems-of-equation/), which gave me the following:

```python
A = Matrix(GF(11), mat)
b = Matrix(GF(11), vec).transpose()
v0 = A.solve_right(b) # p0...p19,q0...q19
vals = v0[:len(setanum)] # just p0...p19
print(vals)
# [10][ 6][ 6][ 6][ 8][ 9][ 8][ 9][ 1][ 9][ 0][ 0][ 0][ 0][ 0][ 0][ 0][ 0][ 0][ 0]
```

where `vals` contains our coefficients $p_0,\,...\, p_{19}$.

Now all that needs to be done is reverse the $emoji\to \mathbb{N}$ bijection to recover our answer:

![](https://imgur.com/0Yvskk5.png)

## Solution
Stringing this all together, we get the following:

```python
import socket
import string
import hashlib

def readln(sock):
r=b""
while True:
c = sock.recv(1)
if c != b'\n':
r += c
else:
break
return r

clientsocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
clientsocket.connect(('challs.m0lecon.it', 10002))
received = clientsocket.recv(4096)
clientsocket.send((hashlib.md5(received.decode().split("\n")[0].split(" ")[2].encode('utf-8')).hexdigest()+"\n").encode())
for i in range(21):
received = readln(clientsocket)
while True:
num = int(readln(clientsocket))
table = []
seta = []
setb = []
ops = readln(clientsocket).decode("utf-8").split(" ")
readln(clientsocket)
for i in range(num):
table.append(readln(clientsocket).decode("utf-8").split(" "))
anum = int(readln(clientsocket))
for i in range(anum):
seta.append(readln(clientsocket).decode("utf-8").split(" "))
bnum = int(readln(clientsocket))
for i in range(bnum):
setb.append(readln(clientsocket).decode("utf-8").split(" "))
mapping = [-1 for _ in range(len(ops))]
n=len(ops)
identity = table.index(ops)
mapping[identity]=0
if identity==0:
oneel = 1
else:
oneel = 0
mapping[oneel]=1
curr = oneel
num = 1
while num<len(ops)-1:
num+=1
curr = ops.index(table[oneel][curr])
mapping[curr]=num
def getVal(emoj):
return mapping[ops.index(emoj)]
opsnum = [getVal(x) for x in ops]
tabnum = [[getVal(x) for x in y] for y in table]
setanum = [[getVal(x) for x in y] for y in seta]
setbnum = [[getVal(x) for x in y] for y in setb]
def transpose(m):
return [[m[j][i] for j in range(len(m))] for i in range(len(m[0]))]
setanumt = transpose(setanum)
setbnumt = transpose(setbnum)
x = mapping[ops.index(chr(128514))]
mat = [setanumt[0]+[0 for _ in range(len(setanumt[0]))]]+[setanumt[i]+list(map(lambda x:-x,setbnumt[i])) for i in range(len(setanumt))]
vec = [x]+[0 for _ in range(len(mat)-1)]
A = Matrix(GF(n), mat)
b = Matrix(GF(n), vec).transpose()
v0 = A.solve_right(b)
vals = v0[:len(setanum)]
ans=" ".join(ops[mapping.index(sum(vals[i][0]*setanum[i][j] for i in range(len(setanum)))%n)] for j in range(len(setanum[0])))
clientsocket.send((ans+"\n").encode())
print(readln(clientsocket).decode("utf-8"))
```

Plugging this into [https://sagecell.sagemath.org/](https://sagecell.sagemath.org/) gives us the following:
```
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-1> in <module>()
20 received = readln(clientsocket)
21 while True:
---> 22 num = int(readln(clientsocket))
23 table = []
24 seta = []

ValueError: invalid literal for int() with base 10: b'ptm{V3ct0r_m4th_w1th_3m0ji1_i5_fun}'
```
and we're done :)