Forgemasters Folly

Challenge Overview

We are presented with a standard RSA setup $(N, e, c)$ but with additional “artifacts”: a large integer $A$ and a small integer $k=256$. The flavor text hints that one of the prime factors was “built upon an ancient foundation” but has a “flaw,” suggesting we know the high-order bits of a prime factor $p$ and are missing the lower $k$ bits.

Mathematical Analysis

The parameters imply that the prime factor $p$ has the following structure:

$$p = (A \cdot 2^k) + x$$

where $x$ is the unknown “flaw” (the lower 256 bits).

Since we know the upper bits of $p$, this is a classic Partial Key Exposure vulnerability. Because we know approximately 75% of the bits of $p$ (given $N$ is 2048-bit, $p$ is 1024-bit, and unknown $k$ is only 256 bits), we can use Coppersmith’s Method to recover the remaining bits. This method finds small roots of polynomials modulo a divisor of $N$.

Solution Logic

We utilize the provided SageMath script (solve.sage) to perform the attack.

Step 1: Polynomial Construction

We model the problem as a polynomial equation over the ring $\mathbb{Z}_N$. The script initializes a polynomial ring and defines the equation based on our knowledge of $A$:

$$f(x) = (A \cdot 2^k) + x \pmod N$$

This is represented in the code as polynomial = (A * (2^k)) + x.

Step 2: Lattice Reduction (Coppersmith’s Method)

We know that for the correct value of $x$, $f(x)$ will be a multiple of $p$ (specifically, $f(x) = p$). We need to find this root $x$.

• Bound ($X$): The unknown part $x$ is known to be a $k$-bit number, so the search bound is set to $X = 2^k$.

• Beta ($\beta$): Since $p$ is a prime factor of $N$ and roughly the square root of $N$ ($p \approx N^{0.5}$), the parameter beta is set to 0.5.

The script executes the attack using the small_roots function:

roots = polynomial.small_roots(X=2^k, beta=0.5).

Step 3: Factorization and Decryption Once the small root $x$ is found, the script reconstructs the full prime $p$ by adding the recovered lower bits to the known upper bits: p = (A * (2^k)) + int(x_found).

With $p$ recovered, the script performs standard RSA decryption:

1. Calculates the second prime $q = N // p$.

2. Computes Euler’s totient $\phi = (p - 1)(q - 1)$.

3. Derives the private decryption exponent $d = e^{-1} \pmod \phi$.

4. Decrypts the ciphertext $c$ to retrieve message $m$.

Step 4: Flag Extraction Finally, the script converts the decrypted integer $m$ from hexadecimal to a byte string to reveal the flag.

import binascii

N = 0xa3074c17853a5eaffcbbd28b924e82a7ff62d9489145db4840bccb15c89d04c0bffba11baa7386f773b91e27f0f8c1e3441650b6231a750c85491d60e9861c38cdced63ee2bdf16dc140b5e471a1b1137ad4c5d068ae3aa357b6d54eefa6bf9c62bfac79a360ea74c5c78ac8eb5034059a2af623423496c294884d6568201edd5bcd6b8eb3db6ab55af7f8823d33638cd1d39df33af7b522e8933dc51c23f527b16d704218f651bd34683d0745849a07452d8b1223c4aee91010db2ea74a365d7c2eb9a37645ed2b992a62a3ea73f75960cdf73e22c774a08ed9b7e1669b0af500e3e28e96587d2301213e0862ecb18abbf040f6e52cfa8955dec1cfa5fbd9dd
e = 65537
A = 0xcea9b77b0da2ed20c6d2808f0d142e360fdfb49fe98652168d0dc2f302ff676123a0940175161b256b9f40c79bae0b5e88905e66970b671a3379fdac5b38a526c7e63f11318b0fcad695ba63c242ec96fd3caa7c60ff64928fddd259e429ddf5
k = 256
c = 0x5825cd657fc74e7ae3dff2854b4eb99f93d28e90cdf50c17787debf604c46e5f750f456f9146a06acee51301d7544edd377b46e49971f35b38b3478c368e8d49cf73b7e2b8e6327f47286cda20a870f705310f44b2732a507ded8e362f82308005f102d09c268d530552008b60e236c3aa37a6d023638ec3133e04be37beb2dcd7b2e1057c55c7dc7fee272c2e67e8216a4295e39ba39161c7ecc86e32460fac5d426a2ea397aa200e5f97dd4a80d9ca2babf0848d313a3b2b31fde740831e8affd2e64b3dc1b877a871f30eb810d214a5cfd00842ca199fbd924cda49eb4236bdf569d0d570962fd053ffb6f0c648eb9582cd87b16095c75e41ee32e59ae7ef

print("[*] Initiating Coppersmith's Short Pad Attack...")


P.<x> = PolynomialRing(Zmod(N))


polynomial = (A * (2^k)) + x

print("[*] Running LLL lattice reduction...")
roots = polynomial.small_roots(X=2^k, beta=0.5)

if roots:
    x_found = roots[0]
    print(f"[+] Found small root x: {x_found}")
    
    p = (A * (2^k)) + int(x_found)
    
    if N % p == 0:
        print("[+] Factorization Successful!")
        q = N // p
        
        phi = (p - 1) * (q - 1)
        d = inverse_mod(e, phi)
        m = power_mod(c, d, N)
        
        try:
            flag = binascii.unhexlify(hex(int(m))[2:])
            print(f"\n[SUCCESS] Flag: {flag.decode()}")
        except Exception as err:
            print(f"[!] Decryption math worked, but decoding failed: {err}")
    else:
        print("[-] Reconstructed p is not a factor. Check assumptions.")
else:
    print("[-] No roots found. Parameters might be off.")