Secret correspondence

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

Summary

Task: RSA with e=3, two ciphertexts with related messages differing by known suffix. Solution: Integer cube root attack since m^3 < n (no modular reduction).

Secret correspondence — CryptoKids 2.0

Description

RSA with e=3. Two ciphertexts provided, messages differ by known suffix.

Analysis

• RSA with e = 3 (small public exponent)
• Two messages: m1 = m + suffix1, m2 = m + suffix2
• Messages are small enough that m^3 < n (no modular reduction)
• Simple integer cube root recovers plaintext
• This is related to Franklin-Reiter related message attack concept

Solution

When e=3 and the message is small (m^3 < n), the ciphertext c = m^3 mod n = m^3 (no reduction). Simply take the integer cube root. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
# RSA e=3 cube root attack

import gmpy2

def integer_cube_root(n):
    """Compute integer cube root"""
    root, exact = gmpy2.iroot(n, 3)
    return int(root), exact

# Given
n = ...  # RSA modulus
e = 3
c1 = ...  # first ciphertext
c2 = ...  # second ciphertext
suffix1 = b"..."  # known suffix for message 1
suffix2 = b"..."  # known suffix for message 2

# Try cube root on c1
m1, exact = integer_cube_root(c1)
if exact:
    print(f"c1 cube root exact!")
    plaintext1 = bytes.fromhex(hex(m1)[2:])
    print(f"Message 1: {plaintext1}")
    
    # Remove suffix to get base message
    if plaintext1.endswith(suffix1):
        base_msg = plaintext1[:-len(suffix1)]
        print(f"Base message: {base_msg}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Try cube root on c2
m2, exact = integer_cube_root(c2)
if exact:
    print(f"c2 cube root exact!")
    plaintext2 = bytes.fromhex(hex(m2)[2:])
    print(f"Message 2: {plaintext2}")

# Alternative: Franklin-Reiter for related messages
# If m1 = m + a, m2 = m + b, and we have c1 = m1^e, c2 = m2^e
# Can use GCD of polynomials to recover m

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