rosehacks@pwny$ cat binary_basis.txt Our task starts with a story set in a mysterious tomb, where a cryptic puzzle guards an ancient relic. We're provided with an output.txt file containing variables n, e, c, and treat, as well as a Python script source.py that generated this output. Our objective: decrypt the message c to reveal the hidden flag.
Initial Analysis
The source.py file shows how each variable in output.txt was generated: • n: Product of 16 randomly generated 128-bit prime numbers. • e: The public exponent, set to 65537. • m: The plaintext flag, converted to a long integer. • c: The ciphertext, calculated as c = pow(m, e, n). • treat: A specially structured sum of powers of two, each multiplied by the primes used to generate n.
The challenge boils down to leveraging treat to recover the 16 primes used in n, allowing us to factor n and derive the private key for decryption.
Strategy
The key to solving this lies in treat. We notice that each term in treat has the structure: treat=∑(primei×2power_factors[i])\text{treat} = \sum (\text{prime}_i \times 2^{\text{power_factors}[i]})treat=∑(primei×2power_factors[i]) where each prime is multiplied by a distinct power of two. This unique structure lets us isolate each prime by dividing treat by each descending power of two.
Solution Walkthrough
- Extracting Primes from treat:
- We sorted the list of power factors in descending order. For each power factor, we divided treat by 2factor2^{\text{factor}}2factor to extract each prime and then adjusted treat by subtracting out the prime’s value.
- Calculating phi(n):
- With all 16 primes recovered, we computed phi(n) as: -ϕ(n)=(p1−1)×(p2−1)×⋯×(p16−1)\phi(n) = (p_1 - 1) \times (p_2 - 1) \times \dots \times (p_{16} - 1)ϕ(n)=(p1−1)×(p2−1)×⋯×(p16−1)
- Computing d:
- We computed the private exponent d as the modular inverse of e modulo phi(n).
- Decrypting c:
- Using d, we decrypted c to recover m, then converted m from bytes to reveal the flag.
Solution Code
Here’s the final code that accomplishes these steps:
from Crypto.Util.number import long_to_bytes
from sympy import Integer
from math import prod
# Given constants
n = 352189612438784047320754903106372002809877965719588610950180565262740960705788381566578345723325074804073747981488556714699194183628557150903839852453543700776971896448650422022044960974232637963499485064773137220336653165714273408753468196975611814144214482908258123395290626550717602601895666745644709508591571302894106487383195731091217527995774179358090943421864881850666765491934935419093710096767868514339375941764521600704560564724716373816013966194185050357691082654919969371044174479415710416530800029987261822155401485231590655607419352265580910531638967882492680615189164541617995862933344817766381378089
e = 65537
c = 258206881010783673911167466000280032795683256029763436680006622591510588918759130811946207631182438160709738478509009433281405324151571687747659548241818716696653056289850196958534459294164815332592660911913191207071388553888518272867349215700683577256834382234245920425864363336747159543998275474563924447347966831125304800467864963035047640304142347346869249672601692570499205877959815675295744402001770941573132409180803840430795486050521073880320327660906807950574784085077258320130967850657530500427937063971092564603795987017558962071435702640860939625245936551953348307195766440430944812377541224555649965224
treat = 33826299692206056532121791830179921422706114758529525220793629816156072250638811879097072208672826369710139141314323340868249218138311919342795011985307401396584742792889745481236951845524443087508961941376221503463082988824380033699922510231682106539670992608869544016935962884949065959780503238357140566278743227638905174072222417393094469815315554490106734525135226780778060506556705712260618278949198314874956096334168056169728142790865790971422951014918821304222834793054141263994367399532134580599152390531190762171297276760172765312401308121618180252841520149575913572694909728162718121046171285288877325684172770961191945212724710898385612559744355792868434329934323139523576332844391818557784939344717350486721127766638540535485882877859159035943771015156857329402980925114285187490669443939544936816810818576838741436984740586203271458477806641543777519866403816491051725315688742866428609979426437598677570710511190945840382014439636022928429437759136895283286032849032733562647559199731329030370747706124467405783231820767958600997324346224780651343241077542679906436580242223756092037221773830775592945310048874859407128884997997578209245473436307118716349999654085689760755615306401076081352665726896984825806048871507798497357305218710864342463697957874170367256092701115428776435510032208152373905572188998888018909750348534427300919509022067860128935908982044346555420410103019344730263483437408060519519786509311912519598116729716340850428481288557035520
# Constants for decomposition
power_factors = [0x1337 - 158 * (2 * i + 1) for i in range(16)]
# Extract primes
primes = []
treat_integer = Integer(treat)
for exp in sorted(power_factors, reverse=True):
prime = treat_integer // (2 ** exp)
primes.append(int(prime))
treat_integer -= prime * (2 ** exp)
# Calculate phi(n)
phi_n = prod([p - 1 for p in primes])
# Calculate `d`
d = pow(e, -1, int(phi_n))
# Decrypt `c` to get `m`
m = pow(c, d, n)
flag = long_to_bytes(m)
# Output flag
print("Flag:", flag.decode())
Conclusion
By leveraging treat and reconstructing n’s prime factors, we uncovered the private key and decrypted the message to reveal the flag. This challenge demonstrates the importance of carefully handling large integers and modular arithmetic in cryptographic applications, especially where prime factorization and modular inverses are involved.