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:
    1. Generate random matrices $X_0 \in \mathbb{Z}_p^{8\times8},\,A^\prime, B^\prime \in \mathbb{Z}_p^{4\times8}$.
    2. Obtain $A, B \in \mathbb{Z}_p^{8\times8}$ as rows of $A^\prime, B^\prime$ plus some their linear combinations.
    3. Obtain $C = -(A X_0^2 + B X_0)$.
    4. Finally, $X_0$ becomes a private key, and $\langle A, B, C\rangle$ becomes a public key.
  • Encryption:
    1. Encode the plaintext message as $M \in \mathbb{Z}_p^{8\times8}$.
    2. Generate a random matrix $R \in \mathbb{Z}_p^{8\times8}$.
    3. Obtain $A_e = R A,\, B_e = R B,\, C_e = R C + M$.
    4. $\langle A_e, B_e, C_e\rangle$ becomes an encrypted message.
  • Decryption:
    1. Obtain $M = A_e X_0^2 + B_e X_0 + C_e$.
    2. 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}