Intercepted Transmission

Challenge Overview

We are provided with an intercepted transmission containing standard RSA parameters:

Modulus ($n$): A large hexadecimal integer.
Public Exponent ($e$): $65537$ (0x10001).
Ciphertext ($c$): The encrypted message in hex.

The goal is to recover the plaintext flag by factoring $n$ to find the private key.

Vulnerability Analysis

In standard RSA, the modulus $n$ is the product of two distinct, large random primes $p$ and $q$. The security relies on the difficulty of factoring $n$.

The Theory: Fermat’s Factorization

Fermat’s factorization method is based on the representation of an odd integer as the difference of two squares:

$$n = a^2 - b^2 = (a - b)(a + b)$$

where:

$$n = p \cdot q$$

$$a = \frac{p + q}{2}, \quad b = \frac{p - q}{2}$$

If the primes $p$ and $q$ are very close to each other (i.e., $|p - q|$ is small), then their average $a$ will be very close to $\sqrt{n}$.

Standard factorization algorithms (like GNFS) are slow for large $n$.
Fermat’s method is extremely fast when the gap between $p$ and $q$ is small because the search for $a$ starts at $\lceil\sqrt{n}\rceil$ and finds the solution almost immediately.

Solution Walk through

Step 1: Initialization

The script converts the hexadecimal strings $n$ and $c$ into integers.

Step 2: Factoring $n$

The script implements Fermat’s algorithm:

Calculate the starting point $a = \lceil\sqrt{n}\rceil$.
Iterate by incrementing $a$ and checking if $b^2 = a^2 - n$ is a perfect square.
Once a perfect square is found, we calculate the factors:

$$p = a - b$$

$$q = a + b$$

Step 3: Deriving the Private Key

With $p$ and $q$ found, the script calculates Euler’s Totient function $\phi(n)$:

$$\phi(n) = (p - 1)(q - 1)$$

It then computes the private decryption exponent $d$:

$$d \equiv e^{-1} \pmod{\phi(n)}$$

Step 4: Decryption

Finally, the script decrypts the ciphertext using standard RSA decryption:

$$m \equiv c^d \pmod n$$

The resulting integer $m$ is converted to bytes to reveal the flag.

Script

PYTHON

import math
from Crypto.Util.number import long_to_bytes

n_hex = "0x960bcec7c3e916f780a571d9edb68947539cdef4d37dee92a80d6bf96e0b63200a83fb392d356bd1c5febdd7be5784d789be2cd72111660aebaa1dae248a79f43912c6b98f13b25b131e0e0c117a2ff0df15902069967d4a4faae79a88042e080200ed7cd6dbae82ab87e1a45db04b936e50683cca21e1d7a788df7c15666c52657d99d24afc6a667d650222ea9a2029bc1aac8c39f340f59ff75f9391f464e72820f9b757b870c9d0695bf62400d0f0b45af2f0aa25a4ff984497896f135644540ba1b547d1ca41b7543295d8b0df1e7e993d1882d18e88435ae2dd9df779dedb631e868d542923bc2cf16d4cf6d3fa415384552a03c82715c9f39e635d1969"
e = 65537
c_hex = "0x20e37039be1783bacbabb577e690def51515f5e4944ead045037783227f02d93fe6637c5d507bdb5faae17f165532eee089e5465a303924bb56f62fa0bfa6d5dd2087ec0cfc5183242d0255adbb47cb680cf2582b32d8df271c3cb716202b514cc9fd34c1cbe680acc923fb8bad1a4f42adc7a2d1a536c866c525f9d86efc9ce488ff9608e8ca00735d3aaf54fc8d8046c5d757c578012f9fc282a74f752ecfa5251eb3de6a9bd4287fa1fed8ce0cbb3b3502d7711ed33c19105a356ebeb322c4fe1d50d9443e672b51de58b015f2c198bddd1be6b3415dd3153982e277e86220f54886aec21b01df644492f85be2b58ed5d57a22a4f9bcf1451801def49f227"

n = int(n_hex, 16)
c = int(c_hex, 16)


def fermat_factorization(n):
    if n % 2 == 0:
        return 2, n // 2

    a = math.isqrt(n)
    if a * a < n:
        a += 1

    b2 = a * a - n

    while True:
        b = math.isqrt(b2)
        if b * b == b2:
            break
        a += 1
        b2 = a * a - n

    p = a - b
    q = a + b
    return p, q


print("[*] Attempting Fermat's Factorization...")
try:
    p, q = fermat_factorization(n)
    print("[+] Factors found!")
except KeyboardInterrupt:
    print("[-] Attack timed out. Primes are likely not close.")
    exit()

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)  

m = pow(c, d, n)

try:
    message = long_to_bytes(m).decode()
    print("\n[SUCCESS] Decrypted Message:")
    print("-" * 40)
    print(message)
    print("-" * 40)
except Exception as err:
    print(f"[-] Decryption successful, but decoding failed: {err}")
    print(long_to_bytes(m))