Весёлый RSA (Funny RSA)

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-02 | Status: Solved Techniques: Small modulus factorization (trial division), Standard RSA decryption with computed private key, SHA256 hash computation for flag format, Verification across multiple ciphertexts

Summary

Весёлый RSA (Funny RSA) — HackerLab

Description

Боб шифрует для трех сторон одно и то же сообщение с помощью RSA. Узнайте сообщение, отправленное Бобом. В флаге укажите SHA256 от сообщения.

Bob encrypts the same message for three parties using RSA. Find out the message sent by Bob. The flag should contain the SHA256 hash of the message.

Files

• funny_rsa.txt - Three sets of RSA parameters (e, n) and ciphertexts C

Data

e1,n1 = (5, 59911)
C1 = 7721

e2,n2 = (7, 363241)
C2 = 244800

e3,n3 = (13, 470369)
C3 = 76794

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

Analysis

Initial Thought: Håstad's Broadcast Attack?

The task name and description ("the same message for three parties") hint at Håstad's Broadcast Attack. The classic attack applies when:

• One message m is encrypted for k recipients
• All use the same public exponent e
• If e ≤ k, m can be recovered via CRT

However, here e values are different (5, 7, 13), so classic Håstad is not directly applicable.

Actual Solution: Small Moduli

The moduli n are very small (5-6 digits), which allows easy factorization: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

After factorization, we can compute φ(n) and the private exponent d for standard RSA decryption.

Checking gcd(e, φ(n))

For correct RSA decryption, gcd(e, φ(n)) = 1 is required:

• n1: φ(n1) = 180 × 330 = 59400, gcd(5, 59400) = 5 ≠ 1 (problem!)
• n2: φ(n2) = 448 × 808 = 362048, gcd(7, 362048) = 7 ≠ 1 (problem!)
• n3: φ(n3) = 646 × 726 = 468996, gcd(13, 468996) = 1 ✓ (works!)

Only the third parameter set allows standard RSA decryption. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""Funny RSA - Small modulus factorization attack"""

import hashlib

# Challenge data
e1, n1 = 5, 59911
C1 = 7721
e2, n2 = 7, 363241
C2 = 244800
e3, n3 = 13, 470369
C3 = 76794

def factorize(n):
    """Trial division for small n"""
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return i, n // i
    return None, None

# Factorize n3 (the one where gcd(e, phi) = 1)
p3, q3 = factorize(n3)  # 647, 727
print(f"n3 = {p3} × {q3}")

# Calculate phi and private exponent
phi3 = (p3 - 1) * (q3 - 1)  # 468996
d3 = pow(e3, -1, phi3)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Decrypt
m = pow(C3, d3, n3)
print(f"Message m = {m}")

# Verify with all three ciphertexts
assert pow(m, e1, n1) == C1, "Verification failed for C1"
assert pow(m, e2, n2) == C2, "Verification failed for C2"
assert pow(m, e3, n3) == C3, "Verification failed for C3"
print("All verifications passed!")

# Compute SHA256 hash for flag
message_str = str(m)
sha256_hash = hashlib.sha256(message_str.encode()).hexdigest()
print(f"SHA256('{message_str}') = {sha256_hash}")
print(f"\nFlag: CODEBY{{{sha256_hash}}}")

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

Output

n3 = 647 × 727
Message m = 168
All verifications passed!
SHA256('168') = REDACTED

Flag: CODEBY{REDACTED}

Verification

Verifying that m = 168 indeed encrypts to the given ciphertexts:

 python read-only • copy allowed Copy
>>> pow(168, 5, 59911)
7721  # = C1 ✓
>>> pow(168, 7, 363241)
244800  # = C2 ✓
>>> pow(168, 13, 470369)
76794  # = C3 ✓

Theory

Why must gcd(e, φ(n)) be 1?

In RSA, the private exponent d is computed as the modular inverse:

d = e^(-1) mod φ(n)

The inverse exists only if gcd(e, φ(n)) = 1. If gcd > 1, then:

• Modular inverse does not exist
• Decryption is impossible via standard method
• Alternative methods are needed (e-th root, Rabin, etc.) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Alternative Approach for n1 and n2

For cases where gcd(e, φ(n)) ≠ 1, you can use:

1. e-th root in ring Z_n: if m^e < n, then m = C^(1/e)
2. Hensel lifting: to recover m mod p and mod q separately
3. Brute force: if m is small, enumerate all possible values

In this task, it was sufficient to use n3, where standard RSA works.

Related Tasks

• RSA Basics 1 - RSA with known prime factor
• Håstad's Broadcast Attack - when e is the same for all recipients ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍