## Intro

There are a total of 12 crypto problems in this CTF, and I solved all of them except 'fried_rice'. I'm going to breifly explain the easier ones, and provide detailed solutions and scripts to the harder ones. The problems are ordered by the number of solves.

## Babies

### fibinary

Skipped.

### 4096

It's an RSA with \(N\) being the products of multiple 32-bit primes. We can factorize \(N\) by those powerful tools (or even just bruteforce and let the program run for 1.5 hours, which my teammate did) and solve the challenge.

### dividing_secrets

The arithmetic operations here are under \(Z/pZ\), and the \(p\) is known. We are given \(g\) and \(g^{flag}\). We can input at most 64 \(div\), and it tells us \(g^{\lfloor \frac{flag}{div} \rfloor}\).

We can calculate \(\left(g^{flag}\right)\left(g^{\lfloor \frac{flag}{div} \rfloor}\right)^{-div} = g^{flag \bmod div}\), if the chosen \(div\) is small enough, we can bruteforce the discrete log, meaning we can retreive the value of \(flag \% div\). Choosing \(div\)s to be distinct 20-bit primes (10-bit is probably enough), we can perform CRT to recover the flag.

### supercomputer

This problem is pretty much testing if people know Lifting the Exponent. In this case, since \(n = rp^q\) \[v_p(a_1^n + (n - a_1) ^ n) = v_p(a_0 + (n - a_1)) + v_p(n) = 2q\] with an exception of \(p \mid a_1\), which is really unlikely to happen.

### babyrsa

It's a classic coppersmith. Recommend reading (4.2.2 ~ 4.2.4 for this specific challenge).

### babypad

Classic padding oracle.

### babyrand

Given \(p\), \(x < p\), we have to recover \(a\) and \(b\) by \((ax+b) \bmod p\), where \(a\) and \(b\) are both an approximation of \(p \oplus x\), formally, \(|a - (p \oplus x)| < 2^{200}\) while \(p\) is a 512-bit prime (and \(x\) is randomly chosen).

Let \(a' = a - (p \oplus x)\) and \(b' = b - (p\oplus x)\), by some math, we can get \((a'x+b') \bmod p\) from \((ax+b) \bmod p\). Now transform this into a closest vector problem (CVP): consider the lattice \[\begin{pmatrix} x & 1 \\ p & 1 \\ \end{pmatrix}\] and find the closest vector to \((a'x+b \bmod p, 0)\). Multiply the first row by \(a\), and subtract by the second row multiplied by \(\lfloor \frac{ax}{p} \rfloor\) should be really close, so we can recover \(a\) and \(b\) by solving the CVP. (Be aware that multiply the second row by \(\lceil \frac{ax}{p} \rceil\) is also a possibility, but can be handled in a similar way)

### bank

We can measure and apply some gates to control the qubit to the place we want (no matter where the initial position is). Combining it with powerful 'verify' operation, we can check if the bill is a '0' by moving the qubit to '0' and measure. We believe that it is a '0' if it is verified 10 times in a row. Similarly, apply this to '1', '+', and '-'. Therefore, we can recover the bill.

### leave_it_to_chance

The arithmetic operations here are under \(Z/pZ\), and the \(p = 4k + 1\) is known. Let the root of \(p \mid x^4 - 1\) be \(\pm 1,\pm a\). The problem provides a signing oracle, where the signature of \(x\) is \(f(x)^4\) and \(f\) is a polynomial with degree \(31\). As there are four possible \(f(x)\), while signing, we also get hints that two out of the 4 possible value is not the actual \(f(x)\) (these two numbers are chosen randomly among the three fake ones).

First, notice that \(f(x)^4\) is also a polynomial, but with degree \(124\), so we can ask for \(124\) signatures and get \(f(x)^4\) with Guassian elimination. Then square root \(f(x)^4\) twice to get a possible \(f(x)\). To square root a polynomial, we need tonelli-shank to get the first coefficient, and the rest is simple math. After getting the possible \(f(x)\), the other 3 possibilities are \(-f(x)\), \(af(x)\), \(-af(x)\). We can use the hints to eliminate the fake ones, until only one is left.

Credits to nakov for the tonelli-shank implementation

1 | from pwn import * |

## Non-Babies

### LCG-k

We are given a typical signing oracle, but the \(k\) is generated by LCG with coefficient \(a\) and \(b\). We are allowed to sign 4 messages, and have to find the private key.

Let's say we sign 4 messages \(m_1\), \(m_2\), \(m_3\), and \(m_4\), we have

\[s_i = \frac{1}{k_i}(H(m_i) + dr_i)\]

and

\[k_2 = ak_1 + b, k_3 = a(ak_1+b) + b, k_4 = a(a(ak_1+b) + b) + b\]

The unknowns are \(a\), \(b\), \(k\), and \(d\). As we have 4 equations, we really have the chance to solve it! First we move the terms a little bit

\[k_i = \frac{H(m_i) + dr_i}{s_i}\]

the idea is that \(k_i\) is the LCG output, so it's better to not put it in denominator. Also, the right hand side has only an unknown \(d\). Now we have

\[k_{i + 1} - k_{i} = \frac{H(m_{i + 1}) + dr_{i+1}}{s_{i+1}} - \frac{H(m_i) + dr_i}{s_i}\]

No matter how ugly the right hand side looks, it is just \(\alpha d + \beta\) for some constant \(\alpha\) and \(\beta\). The reason we do this is because for the left hand side, we have

\[\frac{k_{i + 1} - k_i}{k_i - k_{i - 1}} = a\]

by the idea that \(k\) is exponentially growing regardless of \(b\). Therefore, by

\[\frac{k_4 - k_3}{k_3 - k_2} = \frac{k_3 - k_2}{k_2 - k_1}\]

or

\[(k_3 - k_2) ^ 2 = (k_4 - k_3)(k_2 - k_1)\]

We derived a quadratic equation for \(d\). As the modulo is a prime number, we can solve the equation with tonelli-shank.

### mystery_stream

In this problem, we need to decrypt ciphertext that is encrypted by a LFSR stream cipher (the problem use GF(256) instead of xor, but it is not really important). The key generation process hinted that the output of LFSR is periodic, though the period is unknown. This reminds me of Vignere Cipher, but the period can be big, and the trick mentioned in cryptopals probably won't work (after solving, it turned out that bruteforce the period is do-able), so here we made some observation based on generating function.

Let the output bits of LFSR be \(b_0, b_1, \cdots, b_n, \cdots\). Consider the polynomial (the coefficient is in \(GF(2)\) so \(-x\) is the same as \(x\))

\[b_0 + b_1x + b_2x^2 + c\dots = \frac{g(x)}{f(x)}\]

where \(f(x)\) is the LFSR polynomial. To find the period \(t\), it must satisfy

\[\frac{g(x)}{f(x)} = \frac{h(x)}{1 + x^t}\]

so we can factorize \(f(x)\) and looks for the suitable \(t\). It turned out that \(t = 255\) and \(gcd(f(x), 1 + x^{255}) = x^8 + \cdots\). Therefore, \(g(x)\) needs to cancel out all other \(f(x)\) factors other than \(x^8 + \cdot\). Now we know that \(g(x)\) has a degree-56 factor (\(f\) has degree 64), as \(g(x)\) has degree at most 63, there's only 256 possible \(g(x)\). A \(g(x)\) means a key, after bruteforcing the key, we can recover the plaintext.