## pppp (117 pts, 70 solves)

### Finding nth root of certain upper triangular matrix.

Solved by: grhkm and TWY

Source of the problem: SECCON CTF 2021

## Problem Statement

Great research on witch has made it possible to split and duplicate messages.

problem.sage 8df65d6861d69ed6d461c5cd70b7157040534a0c

output.txt 2cf4e086b11751dfe9eaf758d26f8f0a765458d2

## Solution Outline

We found a (partial) general formula for exponent of an upper triangular matrix and solved the equations by comparing the entries.

## Initial Observations

We are given a matrix version of RSA. Essentially, we were asked to solve the matrix equation

$$R^{65537} = \begin{pmatrix} r_{11} & r_{12} & r_{13} & r_{14} \\ 0 & r_{22} & r_{23} & r_{24} \\ 0 & 0 & r_{33} & r_{34} \\ 0 & 0 & 0 & r_{44} \end{pmatrix}^{65537} = M,$$

where

$$\begin{cases} p, q < 2^{512} \\ a_i < 2^{768} \\ m_1, m_2 < 2^{256} \\ R = \begin{pmatrix} p\cdot a_1 & p\cdot a_2 & p\cdot a_3 & p\cdot a_4 \\ 0 & m_1\cdot a_5 & m_1\cdot a_6 & m_1\cdot a_7 \\ 0 & 0 & m_2\cdot a_8 & m_2\cdot a_9 \\ 0 & 0 & 0 & a_{10} \end{pmatrix}\end{cases}$$

First observation we had was that since $n$ is $1024$-bit and $m_i\cdot a_j\approx 2^{768 + 256} = 2^{1024}$, if we can recover two entries of $R$ on the same row, say $r_{22} = m_1\cdot a_5$ and $r_{23} = m_1\cdot a_6$, they will be reduced under $pq$ by a few times, and we can directly take $\gcd$ and recover $m_1$ and $m_2$. In other words, we don’t have to recover the entire $R$, but rather just a few entries.

Naturally, we started by playing around in Sage. Very quickly, we found that the diagonal entries of M are simply $r_{ii}^e$:

sage: A = Matrix([[r11, r12, r13, r14], [0, r22, r23, r24], [0, 0, r33, r34], [0, 0, 0, r44]])
sage: [(A ^ 50)[i][i] for i in range(4)]
[r11^50, r22^50, r33^50, r44^50]


Recall that in matrix multiplication, we have $(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj}$. Now observe that since $R$ is upper triangular, $R_{ij} > 0$ only when $j\geq i$. Then we have

$$(R^e)_{ii} = \sum_{k=1}^4 (R^{e - 1})_{ik}R_{ki} = (R^{e - 1})_{ii}r_{ii} = r_{ii}^e.$$

Therefore, we already have $M_{11} = (p\cdot a_1)^e = p^e\cdot a_1^e\mod pq$. Since $M_{11}\neq 0$, it must be divisible by $p$, and we can recover $p$ by calculating

$$p = \gcd(N, M_{11}).$$

sage: p = gcd(n, ct)
sage: q = n // p
sage: is_prime(p) and is_prime(q) and p * q == n
True


Now that we have factored $N$, we can actually recover all $r_{ii}$ from $M_{ii}$ by Chinese Remainder Theorem and standard RSA decryption:

sage: diag =  * 4 # diagonal entries r[i][i]
sage: for i in range(4):
....:     crt1 = Integer(Mod(ct[i][i], p).nth_root(65537))
....:     crt2 = Integer(Mod(ct[i][i], q).nth_root(65537))
....:     diag[i] = crt([crt1, crt2], [p, q])


## The Final Step (??)

Now that we have the diagonal entries, let’s try to recover $r_{i, i + 1}$. Applying the matrix multiplication formula, we have for $i = 2, 3$

\begin{align*} (R^e)_{i, i + 1} &= (R^{e - 1})_{ii} r_{i, i + 1} + (R^{e - 1})_{i, i + 1}r_{i + 1, i + 1} \\ &= r^{e - 1}_{ii}r_{i, i + 1} + (R^{e - 1})_{i, i + 1}r_{i + 1, i + 1} & a := r_{ii} \\ &= a^{e - 1}b + f(e - 1)c & b := r_{i, i + 1} \\ &= a^{e - 1}b + {\color{cyan} (a^{e - 2}b + f(e - 2)c)}c & c := r_{i + 1, i + 1} \\ &= \cdots \\ &= a^{e - 1}b + a^{e - 2}bc + a^{e - 3}bc^2 + \cdots + abc^{e - 2} + f(1)c^{e - 1} \\ &= b(a^{e - 1} + a^{e - 2}c + a^{e - 3}c^2 + \cdots + ac^{e - 2} + c^{e - 1}) \\ &= b\cdot\frac{c^e - a^e}{c - a}\end{align*}

So we can recover $b = r_{i, i + 1}$ by calculating $M_{i, i + 1}\cdot\frac{c - a}{c^e - a^e}$:

sage: superdiag =  * 3
sage: for i in range(3):
....:     a = diag[i]
....:     b = ct[i][i + 1]
....:     c = diag[i + 1]
....:     superdiag[i] = Integer(b * (c - a) * pow(c^e - a^e, -1, n))


Finally, we take the GCD and obtain the flag:

sage: bytes.fromhex(gcd(diag, superdiag).hex() + gcd(diag, superdiag).hex()).decode()
'SECCON{C4n_y0u_prove_why_decryptable?}'


## Remarks

I read some other writeups such as this by @9host1st, which seems to directly compute $M^{e^{-1}\text{mod}\ \phi}$ and obtain the entries… I thought about this approach but thought it won’t work after my Sage hangs computing M.multiplicative_order(). Oops…

Built with Hugo
Theme Stack designed by Jimmy