This crypto challenge is basically an RSA-like encryption service.
First the program prints the encrypted version of the flag prepended by X: and 68 bytes from urandom (thus those have supposedly high-entropy). The encrypted hex-string are always about 1024 bit long.
After the encrypted flag, the challenge let you type in maximum 100 input to be encrypted. The inputs must be in hex-string representation and the maximal length is 15byte (after hex decode). The trick in the encryption is the padding, as all of the inputs are prepended with the X: characters. This effectively means if you input x, then the challenge will process (0x583a20 << (len(x)*8)) + x.
The real twist of the challenge is the fact, that there's no obvious way to obtain even n (the modulus) or e (the public exponent). From the source code it seem like n, e, d are read from a file, but d not used at all (as there is no decryption). Those things made us think that the real challenge is to obtain n and it should have some very obvious "vulnerability", thus it can be factorized.
In normal cases, when e has a conventional value (like 3 or 65537) it is easy to compute n, because the m^e is computable as we know m (our input, even if it has a prefix) and e as well. But now this isn't the case.
An other way of gettin n, is to use enc(m1), enc(m2), enc(m1*m2) triplets. Now consider enc(m1)*enc(m2) - enc(m1*m2) = (m1^e)%n*(m2^e)%n - ((m1*m2)^e)%n. Expanding the last term: (m1^e)%n*(m2^e)%n - ((m1^e)%n*(m2^e)%n)%n. And that means A*B - (A*B)%n = x+k*n - (x+k*n)%n = x+k*n-x = k*n, so the difference of the product of encrypted messages and encryption of the product is divisible by n.
Thus now the task is to find number like m1, m2, but the prefix makes things a little bit difficult: m1, m2 and even m1*m2 must start with 0x583a20. I couldn't find easy number like these, so the initial idea of m1, m2, m1*m2 have been extended: enc(m1)*enc(m2) == enc(m3)*enc(m4) (mod n) numbers are also make a valid equation.
Also it is very easy to construct those numbers: let's consider h1*h2 = m1, h3*h4 = m2, h1*h3 = m3, h2*h4 = m4. Furthermore we know that all m number must be start with 0x583a20, so try with hi ~= sqrt(0x583a20 << (8x) | 0x80 << (8(x-1))) terms (the first bit after the prefix should be set because that means we are taking the middle of the range of 0x583a2000...00 and 0x583a20fff...ff). For 0x583a2080000000, use h1 = 157587146, h2 = 157587147, h3 = 157587148, h4 = 157587149.
Computing the enc(m1)*enc(m2) - enc(m3)*enc(m4) difference we got a huge number 68189034945254682721348132935321922217472089094452012371594413240780642470900592369028997593724535485130250119465062607558574550394040861423961565623579407700000483324593454896541158247074205059654499034693295866976362053932949877214962671587490652648019318445427394630629271715281874887506383038905067354349673747303439910949176070015173127870085780855111284983837069653534985377027408910999060656648849327738518274006244835448097247061739112233450739579563295943440691264159205128224468142841486812764427782617265545905609695267080813684428801995658905753988205110806768899600277100680297190712676494007056, and trying to factorize with yafu (but manually stopping after 1 minute!):
...
C305 = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157
P9 = 252925763
P16 = 2182361588712163
***co-factor***
C273 = 266211978177346307504869137055862108844856419206068153821565219277889092653183685383026674596998368808416725320765861948160692634087337195312841300379311445436993885714776825426024556454190567937880284790763092617336088428759864583461324499148013296234948962106481877436171
We can't really tell apart which one can be n, C305 or C294. So try with and other h = 157587142..157587145 quadroplet:
...
C305 = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157
***co-factor***
C294 = 403718784087780331312400396169391174789602745124217754604975499181770263357014981424374337774224326970277361003894329362963045717527084192853489426478407078124905075390247656638470364425214150096856124835722891216897489304249153555801296453190743872665743267583012675016724466769689867924297433
Based on the GCD of many quadroplet, we can reasonably sure that n = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157.
Now we assumed that there's some vulnerability of n, but yafu can't factorize it, and manually searching on factordb also didn't provided result (http://factordb.com/index.php?id=1100000001371107107 it seems like the factorization was uploaded before the contest on October 12th...). But later turning to RsaCtfTools relatively quickly found the factors:
python ./primefac.py -s -v 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157
Z305 = P152 x P153 = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523 x 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159
By now we arrived at a discrete logarithm problem, namely we know m, c and n, and want to compute e, for such m^e=c (mod n) holds. For some concrete values we choose m = 0x583a20 (well, just pressing enter for X input value) and got c = 0x093154d3bc2ee766e732131990322d0e606b5265dc8163295ba79a73ada7379a59b0ba25ef79efcb8ce22f0f767984156f7b9c9e75b287173e3244474931237d31d7627c04938344e7ab00cdbddaed00acddea37bcb142b97c60036da7f92da99d9b1567e48525f4e5cac3b740c0165c1b0d94581339a36a5acd6f8f9d5c19
With the help of sage calculate a discrete logarithm problem on the bigger prime (q) ordered modulo ring.
R = IntegerModRing(q)
e = discrete_log(R(c), R(m))
Thus we obtained e = 375469807216214245, and from p, q and e d can be easly computed, which will be the key for decryption: d = e^-1 (mod (p-1)*(q-1)), so find the multiplicative inverse of e for modulo (p-1)*(q-1).
d = inverse_mod(e, (p-1)*(q-1)) = 5263540386876049691956526991324162293052917406966752449523806386127198070283649548692509691301691195708849854597000736912809611506985013515094656915799036635226820542815209458416953820782217451756415039162188633793030213177684231895492966752648006052355491286253704219233961970008439647640566249793224613
And finally restore the flag by decrypting with d:
c = 0x0127708d4dac956d10c03609cf64b26a628edf4188a7661a7e625b6cfe73c6f00cde6a30d36cbbb89c8f37a037a14657e117985d64891d3560e7587f7efbd875aa6f8c4148078899365f9bd76e518ee8678942c67c38d9f92325b8ba9237c9719dfc4bbbd8f3d75d56216257fa6624b9d8a15254aaf24f6e90eed6f6e6922d
flag = pow(c, d, n)
(flag = 220108903031950718621615306059297321010036394998787409570150318089633888507114344797177284078257542243985011997732457260970157568389123289054262986802405734085350770381740027021716407074996286154041360020491650052893590826989003792405614844161085797927709025260656911319348849792796409326501130)
binascii.unhexlify(hex(flag)[71*2:])
And the flag is hitcon{@@@_5m00thneSS_CAN_give_y0u_everything_@@@}\n (even they left a new line character in the flag :D)