picoCTF
B00tl3grsa3 [450 pts]
Challenge Description:
Why use p and q when I can use more? Connect with nc jupiter.challenges.picoctf.org 51575.
Connect to the service. It should give you a ciphertext c, public exponent e, and modulus n. (Will be different from mine).
c: 220792980926665952349137945422980809172624804899864094250764791782429607681801478483617625687698622071517694855526973786583346039286711280160114528046761974588266123571872772061217767272059869596140567864416404924571566752282735212867405007443133346440116648682519116499518033820233673443307106541635517163619023226561727281924065361517060360805
n: 220848494312633873550521434540121092930061340151464516933090739180958672744573572743283820177719895953925048006257256536170101279602930663475213347031056671032581122523492568975625503483106059704596362545831377237700567156400822789247606369915232646209382014685512845075233921827028600695287414634190330763282597268045444077737019192890820994831
e: 65537
The problem implies that n is actually the product of more prime numbers. If you use additional prime numbers in creating n, that means the average order of magnitude of the prime numbers decreases. Think about it like this: 31 * 59 = 1829 and 7 * 13 * 17 = 1547. Notice how the average magnitude of the prime numbers decreases when we add more. The same applies here.
Thus, it is suitable to attempt to factor n into its prime numbers, as we won’t have to brute force to as high of a value anymore. Using an Integer factorization calculator for large numbers, we can factor our n value and get the Euler’s totient function value, \(\phi(n)\).
Using \(\phi(n)\), we can calculate the private exponent d, since \(ed\equiv 1\;(mod\;\phi(n))\), by calculating the modulo inverse of e in python. Once we calculate d, decryption becomes simple since \(c^{d}\equiv m\;(mod\;n)\).
c = 2207929809266659523491379454229808091726248048998640942507647917824296076818014784836176256876986220715176948555269737865833460392867112801601145280467619745882661235718727720612177672720598695961405678644164049245715667522827352128674050074431333464401166486825191>
n = 2208484943126338735505214345401210929300613401514645169330907391809586727445735727432838201777198959539250480062572565361701012796029306634752133470310566710325811225234925689756255034831060597045963625458313772377005671564008227892476063699152326462093820146855128>
e = 65537
phi = 22084849374459049618475528357227834081741289671639417675318855667210885003422597061298533641693294625742329948030881495479931241881272659993920173457868914712893479865298232877203964273466330025865362290366546406093512174292624039254763191720560193052500535037177>
d = pow(e, -1, phi)
m = pow(c, d, n)
m = format(m, 'x') # convert to hex
print(m)
ascii_str = bytes.fromhex(m).decode("ASCII") # convert to ascii
print(ascii_str)
picoCTF{too_many_fact0rs_0731311}