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 = Me (mod  n). Usually, Me is much larger than n. However, if Me < n, then the modulo operation has no effect, and c = Me.

Solution

Since c < ni 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 Me when Me > ni, 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}