KalmarCTF 2026 Writeup - RBG+++

This is a writeup for a difficult crypto challenge from KalmarCTF 2026 called RBG+++. Basically, it is an advanced version of lance-hard? from last year’s KalmarCTF, so make sure you have read Neobeo’s writeup for lance-hard? before starting this one.

Description#

RBG sometimes stands for Random Bit Generator. I didn’t really like a challenge that was required to guess Dual_EC_DRBG.
This is a revenge challenge of RBG from Daily Alpacahack.

1
from Crypto.Util.number import *
2

3
PBITS, NDAT = 137, 137
4

5
with open("flag.txt", "rb") as f:
6
  m = int.from_bytes(f.read())
7

8
N = getPrime(PBITS) * getPrime(PBITS)
9
e = getRandomRange(731, N)
10
print(f"{N = }")
11

12
lcg = lambda s: (s * 3 + 1337) % N
13

14
for i in range(NDAT):
15
  print(pow(m, e:=lcg(e), N) + pow(m, e:=lcg(e), N))
16

17
  # Internal audit
18
  e = getRandomRange(731, N)
19
  print(f"[DEBUG] {e = }")

Analysis#

The challenge first gives us a modulus $N$ which is a product of two 137-bit primes. After that, it generates 136 pairs of $e, r$ , where $r=m^e + m^{e'} \pmod N$ and $e' = 3e + 1337 \pmod N$ .

It is obvious that the modulus $N$ is not large enough, and we can easily factor it to get the two primes. The main problem is that we can’t directly find the roots of $r=m^e + m^{e'} \pmod N$ even if we know the factorization of $N$ because $e$ is too large.

Let’s can first try to simplify the equation. Since $e'$ is almost the triple of $e$ , we can set $x=m^e$ . If $e<\frac{N}{3}$ , then we get

x+x^3m^{1337} \equiv r \pmod N

Although $m^{1337}$ is still unknown, it is a constant across all pairs. If we can find another relation between these equations, we can cancel out some variables and get a “low” degree univariate equation.

But we don’t want $z=m^{1337}$ to be the coefficient of $x^3$ because it is annoying to handle a non-monic polynomial. So Let’s first do some arrangements. Let $N<3*e+1337<2*N$ , we have

m^e+m^{3e+1337-N} \equiv r \pmod N

which is equivalent to

m^{e+(1337-N)/2}+m^{3(e+(1337-N)/2)} \equiv r \cdot m^{(1337-N)/2} \pmod N

Now we can set $x=m^{e+(1337-N)/2}$ and $z=m^{(1337-N)/2}$ , then it becomes $x^3+x\equiv r\cdot z \pmod N$ . We can solve the equations seperately on $\mod p$ and $\mod q$ to reduce the degree complexity.

Similar to lance-hard?, the first step is to find small coefficients relations between $m^e$ ‘s.

Finding small relations#

Since $m^{p-1} \equiv 1 \pmod p$ , we can use LLL to find $\sum_{i=1}^k c_ie_i\equiv 0 \pmod{p-1}$ with small $c_i$ ‘s. Thus we get

\prod_{i=1}^k (m^{e_i})^{c_i} \equiv 1 \pmod p

In addition, we can also add $z$ to the LLL because $z=m^{(1337-N)/2}$ is also a power of $m$ . Then the equation becomes

\prod_{i=1}^k (m^{e_i})^{c_i} \cdot z^c \equiv 1 \pmod p

We can heuristically guess the degree of the final polynomial is proportional to $3^k \sum |c_i|$ . After some experiments, the best parameters are $k=8$ and there’s exactly 4 positive $c_i$ ‘s and 4 negative $c_i$ ‘s, which balances the degree on both sides.

Reduce to univariate polynomial#

Now we have 8 equations of $x^3+x\equiv r\cdot z \pmod p$ and one equation of the products of $x_i=m^{e_i}$ and $z$ .

A straightforward way is to use resultant to eliminate $x_i$ and get a univariate polynomial in $z$ . However, the computation of resultant is very expensive, and the degree of final polynomial will explode very fast. By our previous heuristic guess, the degree will be about $2^{28}$ , which is impossible to compute. So we need to be more careful about how to eliminate variables.

Remember that we have 4 positive $c_i$ ‘s and 4 negative $c_i$ ‘s, we can rewrite the product relation as

\begin{align*} t&\equiv\prod_{i=1}^4 (m^{e_i})^{c_i} \cdot z^c \pmod p\\ t&\equiv\prod_{i=5}^8 (m^{e_i})^{-c_i} \pmod p \end{align*}

For each part, we first reduce it into a bivariate polynomial of $t$ and $z$ , then use a resultant to eliminate $t$ and get the final result.

Algebraic Number Tricks#

As we already know that $x_i^3+x_i\equiv r_i\cdot z \pmod p$ , we can think of it as an “algebraic number over $\mathbb{F}_p[z]$ ”¹

A famous result about algebraic numbers is that the sum, product of algebraic numbers is still an algebraic number. Similarly, we can do the same thing in our case, which means $t$ is also an algebraic number over $\mathbb{F}_p[z]$ .

Prop. For a degree $d$ algebraic number $f(\alpha)=0$ over $\mathbb{F}_p[z]$ , $t=\alpha^k$ is also a degree $d$ algebraic number.

Let $M$ be the companion matrix of $f$ , then $\alpha$ is the eigenvalue of $M$ . Thus $t=\alpha^k$ is the eigenvalue of $M^k$ , whose characteristic polynomial is degree $d$ and has $t$ as a root.

Prop. For two algebraic numbers $f(\alpha)=0$ and $g(\beta)=0$ over $\mathbb{F}_p[z]$ , $t=\alpha\cdot\beta$ is also an algebraic number with degree $\deg f \cdot \deg g$ .

Let the roots of $f$ be $\alpha_1,\alpha_2,...,\alpha_m$ and the roots of $g$ be $\beta_1,\beta_2,...,\beta_n$ .² Then the polynomial $\prod_{ij}(x-\alpha_i\beta_j)$ has $t$ as a root and the degree is $mn$ .

Note that the coefficients of $\prod_{ij}(x-\alpha_i\beta_j)$ are still in the field $\mathbb{F}_p[z]$ because they are symmetric polynomials of $\alpha_i$ ‘s and $\beta_j$ ‘s, thus it can be computed by the elementary symmetric polynomials, which is exactly the coefficients of $f$ and $g$ .

Now I’ll introduce an efficient way to compute the coefficients of $\prod_{ij}(x-\alpha_i\beta_j)$ .

Def. The power sums are defined as $p_k=\sum_{i=1}^m \alpha_i^k$ and $q_k=\sum_{j=1}^n \beta_j^k$ .

Clearly,

\sum_{ij}(\alpha_i\beta_j)^k=\sum_{i=1}^m \alpha_i^k \cdot \sum_{j=1}^n \beta_j^k=p_k\cdot q_k

On the other hand, we can quickly convert elementary symmetric polynomials from and to power sums using Newton’s identities. Therefore, we can compute the coefficients of $\prod_{ij}(x-\alpha_i\beta_j)$ in $O(mn)$ time. Since we only consider $m,n\leq 9$ , this is much more efficient than any other fancy methods.

Exact degree prediction#

Now we have a way to compute the polynomial of $t$ without computing any resultant. The final polynomial of $t$ and $z$ is a degree 81 polynomial for $t$ with thousands degree for $z$ , which is still impossible to compute resultant.

Again, we can use the trick in lance-hard? to map $\mathbb{F}_p[z]$ to $\mathbb{F}_p$ by substituting $z$ with some random value, and interpolate later.

Notice that all of these “algebraic numbers tricks” will not break the coefficients of polynomial, i.e. the coefficients are still polynomials of $z$ . Thus, the only thing we need to do is to approximate the degree of the final polynomial.

Since the analysis is very hard, I just did some experiments to find the pattern of degree growth. The result shows that the degree of the final polynomial is about $3^kc+3^{k-1}\max\{\sum_{i=1}^4 c_i, \sum_{i=5}^8 -c_i\}$ . Now we can use it to choose the best LLL candidates and predict the degree of final polynomial, which is about $2^{25}$ .

Solve the polynomial#

Fast Lagrange interpolation#

Since we can free choose the evaluation points, we can use consecutive xs for interpolation. We can easily compute it in $O(n)$ time.³

Finding roots of univariate polynomial#

In general, the best method to find roots is first compute $gcd(f, z^p-z)$ and then factor the result. However, the degree of our polynomial is about $2^{25}$ , which is too large for NTL to run FFT, so it failed.

Thus we have to compute two final polynomials and run gcd on them. Thanks to NTL and half-gcd and FFT(?), this time it doesn’t raise error and finished in about 20 minutes.

After getting the gcd, I find that it contains a large factor of $z^i$ , so it could be faster if we remove the factors of $z^i$ before computing gcd and interpolation.

The rest is simple as we have got $m^{(1337-N)/2}$ .

Conclusion#

My final solution is written in sage mixed with pyx⁴. The overall running time is

LLL: single thread, ~1 hour. This is not optimized at all.
Compute many $z$ ‘s: multi-thread, ~2 hours per polynomial. We need 4 polynomials in total.
Interpolation: single thread, ~50 minutes per polynomial.
GCD: single thread, ~20 minutes.

So the total running time is about 10 hours, which is quite long but still acceptable for a hard crypto challenge. It is still possible to optimize the code further, but I will leave it for future work.

Please be aware that the real definition of algebraic number is the root of a non-zero polynomial with coefficients over integers. But here we use it in finite field and the coefficients are polynomials of $z$ . ↩
No need to worry if the roots exist in the field, these are just symbols over some unknown extension field. ↩
Thanks Neobeo for the implementation in lance-hard?, and check grhkm’s blog for more details about the algorithm. ↩
I was surprised that sage supports load("file.pyx"), which will automatically compile the pyx file and load it. ↩