MPolyCipher writeup (Tokyo Westerns CTF 2019)
We are given a binary implementing some cryptographic scheme, a public key, and an encrypted flag. After some reverse engineering in IDA, we could restore the scheme, which can be described as follows:

First of all, we operate in the field $\mathbb{Z}_p$, where $p = 2^{32}  5$.
 Key generation:
 Generate random matrices $X_0 \in \mathbb{Z}_p^{8\times8},\,A^\prime, B^\prime \in \mathbb{Z}_p^{4\times8}$.
 Obtain $A, B \in \mathbb{Z}_p^{8\times8}$ as rows of $A^\prime, B^\prime$ plus some their linear combinations.
 Obtain $C = (A X_0^2 + B X_0)$.
 Finally, $X_0$ becomes a private key, and $\langle A, B, C\rangle$ becomes a public key.
 Encryption:
 Encode the plaintext message as $M \in \mathbb{Z}_p^{8\times8}$.
 Generate a random matrix $R \in \mathbb{Z}_p^{8\times8}$.
 Obtain $A_e = R A,\, B_e = R B,\, C_e = R C + M$.
 $\langle A_e, B_e, C_e\rangle$ becomes an encrypted message.
 Decryption:
 Obtain $M = A_e X_0^2 + B_e X_0 + C_e$.
 Decode $M$ as a plaintext message.
The key idea of this cryptographic scheme is to consider a quadratic matrix equation
\[AX^2 + BX + C = 0.\]The decryption procedure works because we can cancel out the random $R$ using the property that the private $X_0$ satisfies this quadratic equation by construction of $C$:
\[\begin{aligned} A_e X_0^2 + B_e X_0 + C_e &= \left(R A\right) X_0^2 + \left(R B\right) X_0 + \left(R C + M\right) \\ &= R \cdot \left(A X_0^2 + B X_0 + C\right) + M \\ &= R \cdot 0 + M \\ &= M. \end{aligned}\]The matrices $A, B$ are generated the way that almost surely $\operatorname{rank} A = \operatorname{rank} B = 4$, so $A$ is not invertible, which prevents us from completing the square and scaling through by $A^{1}$ to solve the quadratic equation effectively.
However, we can actually cancel out the $R$ with another equation which we can solve effectively, for example, the linear one:
\[\left(A + B\right) Y + C = 0.\]Since $\left(A + B\right)$ is invertible, $Y_0 = \left(A + B\right)^{1} C$ is obviously the solution of this linear equation, hence
\[\begin{aligned} \left(A_e + B_e\right) Y_0 + C_e &= \left(R A + R B\right) Y_0 + \left(R C + M\right) \\ &= R \cdot \left(\left(A + B\right) Y_0 + C\right) + M \\ &= R \cdot 0 + M \\ &= M. \end{aligned}\]Another way to look at this trick is to notice that
\[\begin{aligned} R &= R \cdot I \\ &= R \cdot (A + B)(A + B)^{1} \\ &= (RA + RB)(A + B)^{1} \\ &= (A_e + B_e)(A + B)^{1},\\ M &= C_e  RC \\ &= C_e  (A_e + B_e)(A + B)^{1}C. \end{aligned}\]Anyway, we can decrypt the flag using only the public key $\langle A, B, C\rangle$ and the encrypted message $\langle A_e, B_e, C_e\rangle$:
TWCTF{pa+h_t0_tomorr0w}