Darling

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: integer_cube_root, known_padding, rsa_small_exponent_attack

Summary

Task: RSA with small exponent e=3 and null-byte padding. Solution: Since m^e < n, modular reduction doesn't occur; remove padding factor algebraically and extract integer cube root with gmpy2.iroot().

Darling — cryptokids20

Description

RSA with small exponent e=3 and null-byte padding. The flag is padded with zeros to 128 bytes before encryption.

Analysis

Encryption Scheme

 python read-only • copy allowed Copy
# From the challenge source code
padded = flag.ljust(128, b'\x00')  # flag + zeros to 128 bytes
m = bytes_to_long(padded)
c = pow(m, 3, n)  # e = 3

Key Observation

If flag is short (~30 bytes), then:

• padded = flag || \x00 * 98 (98 null bytes on the right)
• m = flag_int * 256^98 (shift by 98 bytes = 784 bits)
• Since flag_int is small, m^3 < n — modular reduction does not occur! ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Attack Mathematics

c = m³ mod n
c = (flag_int × 256^98)³ mod n
c = flag_int³ × 256^294 mod n

If flag_int³ × 256^294 < n, then:

c = flag_int³ × 256^294  (without mod)
flag_int³ = c × (256^294)^(-1) mod n
flag_int = ∛(flag_int³)  # integer cube root

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import long_to_bytes

# Parameters from the challenge
n = ...  # large modulus
e = 3
c = ...  # ciphertext

# Remove padding: c = flag_int³ × 256^294 mod n
# Compute the inverse element for 256^294
padding_factor = pow(256, 294, n)
padding_inv = pow(padding_factor, -1, n)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Get flag_int³
flag_cubed = (c * padding_inv) % n

# Integer cube root
flag_int, exact = gmpy2.iroot(flag_cubed, 3)
assert exact, "Root is not exact — check the logic"

# Decode the flag
flag = long_to_bytes(int(flag_int))
print(flag.decode())

Alternative Approach

If the exact root cannot be extracted, you can iterate over small additions:

 python read-only • copy allowed Copy
for k in range(1000):
    candidate = flag_cubed + k * n
    root, exact = gmpy2.iroot(candidate, 3)
    if exact:
        print(long_to_bytes(int(root)))
        break

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Concepts

RSA Small Exponent Attack

When m^e < n, RSA encryption becomes simple exponentiation without modular reduction:

c = m^e mod n = m^e  (if m^e < n)
m = e-th root of c  (integer root)

Known Padding Exploitation

If the padding format is known (e.g., flag.ljust(128, b'\x00')), you can:

1. Express m in terms of flag_int and the padding constant
2. Algebraically remove the padding from the equation
3. Solve for flag_int ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍