Tuwaiq Nights Ctf F13ld

F13lD — Crypto

Category: Crypto
Difficulty: Medium
Author: Flagyard

Challenge Overview

In this challenge we are given an RSA encryption system where part of the prime p leaks.

We are provided with:

• RSA modulus N
• public exponent e
• ciphertext c
• partial bits of the prime p

The goal is to recover the RSA private key and decrypt the flag.

---

Provided Code

from Crypto.Util.number import *

flag = "FlagY{REDACTED}"
flag_int = bytes_to_long(flag.encode()) 

Kbits1 = 120
Kbits2 = 493

p = random_prime(2^512-1, false, 2^511)
q = random_prime(2^512-1, false, 2^511)

N = p*q
e = 0x10001

Pdigits = p.digits(2)

leaky_p = [0]*19 + Pdigits[19:Kbits1] + [0]*19 + Pdigits[Kbits1+19:Kbits2]

c = pow(flag_int, e, N)

print(f"(c, e, N) = {(c, e, N)}")
print(f"leaky = {leaky_p}")

---

Understanding the Leak

The important line is:

leaky_p = [0]*19 + Pdigits[19:Kbits1] + [0]*19 + Pdigits[Kbits1+19:Kbits2]

p.digits(2) returns the binary digits of p in LSB-first order.

Meaning:

index 0 = least significant bit

So the array leaky_p reveals most bits of p except for specific regions replaced with zeros.

---

Missing Bit Regions

From the construction we can determine the unknown bit ranges.

Bit Range	Size
0 – 18	19 bits
120 – 138	19 bits
493 – 511	19 bits

Total unknown bits:

19 + 19 + 19 = 57 bits

However the first two blocks can be combined into one variable.

---

Reconstructing the Prime Structure

We can write the prime p as:

p = known_part + x + (y << 120) + (z << 493)

Where:

• x = lower missing 19 bits
• y = middle missing 19 bits
• z = highest missing 19 bits

Combine the lower unknown sections:

u = x + (y << 120)

Then:

p = known_part + (z << 493) + u

Where:

u < 2^139

---

Why the Attack Works

We know:

N = p * q

So:

p | N

If we fix a guess for the top bits z, then:

p = a + u

where

a = known_part + (z << 493)

Thus:

f(u) = a + u ≡ 0 (mod p)

Since u is small relative to N, we can solve this with Coppersmith’s small root method.

---

Attack Strategy

1. Rebuild the known bits of p
2. Guess the high 19 bits (z)
3. For each guess:
   • construct polynomial
   • find small root u
4. Recover p
5. Compute q = N / p
6. Compute the private key
7. Decrypt the ciphertext

---

Solver

from Crypto.Util.number import long_to_bytes
from math import isqrt

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

known = sum(int(b) << i for i, b in enumerate(leaky))

XBOUND = 1 << 139

center = isqrt(N) >> 493

for z in range(center-200000, center+200000):

    a = known + (z << 493)

    f = x + a

    roots = f.small_roots(X=XBOUND, beta=0.49)

    for r in roots:

        p = a + int(r)

        if N % p == 0:

            q = N // p

            phi = (p-1)*(q-1)

            d = inverse_mod(e, phi)

            m = pow(c, d, N)

            print("p =", p)
            print("q =", q)
            print(long_to_bytes(int(m)))

            exit()

---

Recovered Primes

Running the solver yields:

p = 8051756861756880956382175410584358410371545064302560076653962554258969975909211805747777805706374702868869290907947867303214066936130786147766575249582771

q = 8180307310467942728283154341177854621065359177434794958713388382359196331593623102083263200902297974211278921817621314643714228356761932612110210250992739

---

Decrypting the Flag

Compute the private exponent:

d = e⁻¹ mod φ(N)

Then decrypt:

m = c^d mod N

Result:

FlagY{e19f6dd985e0e31cde1b27f05e7593de}

---

Final Flag

FlagY{e19f6dd985e0e31cde1b27f05e7593de}