Writeup: Árvore Genealógica- upCTF (Crypto)

Challenge: Árvore (Family Matters CTF) Category: Crypto Description: Só primos atrás de primos atrás da fortuna do papi cris. Flag: upCTF{0_m33s1_é_p3qu3n1n0-zJ3KApbvffbddffc}

Reconnaissance

The challenge presents a family tree themed around "Papi Cris" (Cristiano Ronaldo). The main page contains a genealogy tree with family members, each holding clues. A "Cofre do Banco" (Bank Vault) page accepts a secret code.

RSA Parameters (from Papi Cris)

n = 625884537996922021301000341433932506927375585765524880339408244299388166616607970182814658884261038589890375258726352401200713142307149681483775252604692104227832166709807990289415964013032746766172102239270024433627974944278194240214614719847340322457045111198478821355004842741718270057503827331434371408025925605481105486995996528014519769908400670772699182920499677705809631318990058839592839709710458652675562071292900519774414030358230173117805552929123198203307

e = 0x10001 (65537)

c = 62318722105864475633070267247974102130492586860223395750014121141640728228140922787683482348993303220123956188779410980859089837155685153563184703318488138798553149093011757720494639060509132811288893681789241883011105101728028235229519920858485960028687937326165670672221777501503866767604530227335608355547324683970157050707878702259507869498079204990540446272961682199498306150812336216294150630212362402674654569608827746982122255526272178602585754110118148113502

Gathering Hints

Two family members provide critical hints:

Primo Ricardo (The Mathematician)

"Se pudesse escolher um numero da sorte seria 777 entao tenta procurar um valor perto de 2**777"

Translation: "If I could choose a lucky number it would be 777, so try to look for a value near 2^777."

Takeaway: One of the RSA prime factors p is close to 2^777.

Prima Sofia (The Investigator)

"O papi Cris dizia que ate 100000 era perto e que basta 'descobrir um que o outro e obvio'"

Translation: "Papi Cris said that up to 100000 was close and that 'discovering one makes the other obvious'."

Takeaway: The prime is within ±100000 of 2^777. Once you find p, q = n / p is trivial.

Solution

Step 1: Factor n

With n being 1554 bits and the hint pointing to 2^777 (778 bits), we know n = p * q where p ≈ 2^777. We brute-force offsets from 2^777:

n = 6258845379969220...  # full value
base = 2**777

for offset in range(-100000, 100001):
    candidate = base + offset
    if n % candidate == 0:
        p = candidate
        q = n // p
        break

Found at offset = -85839:

p = 2^777 - 85839
q = n / p

Step 2: RSA Decryption

Standard RSA decryption:

e = 65537
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
# b'S3cr3t_to_p4pis_f0rtune'

Step 3: Submit to Bank Vault

POST the decrypted code to the bank API:

curl -X POST http://46.225.117.62:30008/api/verify-code \
  -H 'Content-Type: application/json' \
  -d '{"code":"S3cr3t_to_p4pis_f0rtune"}'

Response:

{
  "success": true,
  "flag": "upCTF{0_m33s1_é_p3qu3n1n0-zJ3KApbvffbddffc}",
  "message": "Bem-vindo ao seu cofre secreto, papi cris!"
}

Key Takeaways

• Weak RSA key generation: When one prime factor is close to a known value, n can be trivially factored by brute-force search.
• Read all the clues: The family tree members each held pieces of the puzzle. Combining Ricardo's hint (near 2^777) with Sofia's hint (within 100000) narrowed the search space to a trivial brute-force.
• The challenge title "Árvore" (Tree) and description about "primos" (which means both "primes" and "cousins" in Portuguese) was a clever double entendre.