kashiCTF 2026 - Broadcast

Posted on In Views: Disqus:

We sent the same announcement to three servers for redundancy. Each server has its own RSA key. Intercept all three — maybe you can piece something together.

Initial Analysis

The challenge provides an output.txt containing an exponent \(e=3\), three moduli (\(n1, n2, n3\)), and three ciphertexts (\(c1, c2, c3\)). By examining the data, we notice:

  1. Low Exponent: \(e = 3\) is very small.
  2. Identical Ciphertexts: \(c1 = c2 = c3\). This means the raw message \(M\) was not padded differently for each server.
  3. Magnitude of \(c\): The ciphertext \(c\) is significantly smaller than any of the moduli \(n\).

In RSA, the encryption process is \(c = M^e \pmod n\). Usually, \(M^e\) is much larger than \(n\). However, if \(M^e < n\), then the modulo operation has no effect, and \(c = M^e\).

Solution

Since \(c < n_i\) and \(e=3\), the message \(M\) can be recovered simply by calculating the integer cube root of \(c\): \[M = \sqrt[3]{c}\]

Implementation

Using Python and the gmpy2 library, we can solve for \(M\):

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from binascii import unhexlify

# Intercepted ciphertext
c = 475436441896018898725156479190091126537849994697426945980826369000641892902004477923335055269088235139492237640527487698088281484953901383579636883543216552932099156009006828723690550706326538736801225046068870773990108130474408522838234755277972911893744937243892927414355347438993698991261629557719442242861719577879055371620865465785392597257968132649494474946507819896785671106833645551504301840437212737125

# Calculate the cubic root
m, exact = gmpy2.iroot(c, 3)

if exact:
    # Convert integer to hex, then to ASCII
    flag = unhexlify(hex(m)[2:]).decode()
    print(f"Flag: {flag}")

Note: This challenge is a simplified version of Håstad's Broadcast Attack. While Håstad's attack typically uses the Chinese Remainder Theorem (CRT) to solve for \(M^e\) when \(M^e > n_i\), the small size of the message relative to the key size here allowed for a direct cubic root calculation.

Flag

kashiCTF{h4st4d_s4ys_sm4ll_3xp0n3nts_k1ll_RSA_br04dc4sts}