a fact of CTF

The challenge description says: The very first challenge ever completed for AlpacaHack was never released because we adjusted the difficulty for the first Crypto round. (Organizers' note)

We are given the archive files, including chall.py and output.txt.

The challenge script multiplies powers of small primes. Each character of the flag is encoded as the exponent of one prime.

import os


flag = os.environ.get("FLAG", "not_a_flag")

# all prime numbers less than 300
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
assert len(flag) <= len(primes)

ct = 1
for i, c in enumerate(flag):
    ct *= primes[i] ** (ord(c))

print(hex(ct))

The provided ciphertext is a huge hexadecimal integer stored in output.txt:

0xadb88e47d531cdb104013d7aa8a21e6f5bfb841d2ff5d5090d735f9a1d9f6bb2dc0ad6d19efca47ec943e5a8b685f295be56d3531fcb49e41d5d02dd6113e3fcd369a5c25098b38e540fc865e2f1078292efc89778b5f29e74b188c87afcdeb9f4c58d77d1314271646bc1043c63e62b76396f1349b914a0d489df9c211c6e551969694c1a930f8e04379a589869c4a838d0db71168f61b8ff38c6107fca44d2b5064ed42a4b8bbd774025f43907275317679daa0fb58e4127eac72eedb6be263fc0897f6d791eb3b301321b1e0ed37234b92249fe164f5b1a85981e7b52d65e50315520bfcf9c45f86e6d9c899e7aaefa936fa1a7f14dbb9bc9d9615dc9d97e7aecf162549866488b99d6903586f0cbdabfa0de664e66b8e36dadc2fec12d09a6ac3d33b6cdd8aaeccf58f7a3abbc2bcce34652f08617b33583568a1c5335a13d1530c69284d13df513314aa5b12db052529faf61461107d088008658730bce9af8ac9a9b262df3f1e9c84334f3616e9ed9d6598c4a70e9894b47ad73b415713371a5ced21f2853e02f0cce55969ff3101fb9da00c6f48932fa8696ee474bee89d462e08038566ea125f56733f029f40d13ea98a92ddbfcd7b0c900e8b1c7bc65124ae620279e7ae00fb8ef65f835665e344d570325330f90c85326571fd96ba2883fc7b2b6615f35d555948acf3c0ae684a0af323011d209dd8374649dec9bbdaa0ab7068af63fdaacbc5177fd75b457e91fec461a33a0fcb55754d655f2fb9e198d81df64009e9e1e34bddb349955d0792d9717161ba4538b564d85fb6630e2acb4bc95130f6c9d31d6f53aeaecd4c023c50df0b8e2e50c84db4051261abaf38f7020b2964ba6ad05932e22428ae773e78dc83014e674261859b65bd7c9d4b328dd9abbae1067f735006d4400f8c595ee01904fcbdf54c34f983826c24876877f76b9ee14327ddb6b7a7a2625a65a92c2ea757f42d0a3a6fb824d00c9ad4fb4cb2b2c77b0d66b89fc4846b5448df3bfa8977a8e42e9ea4ec5948264f0cd8efeec387c0344b56017657679605b1d0bc32fb1742b1cb8f2426e35e1e673c6af6ae5f3d3bda56b4de192f994f3aef809ae92dda1ab20aef0a948c9bdfecb896727856a0d8a0d9af81661ba53c7927223b2389a168c8adc04f1e7a07499d308bf9cdbe55220a5fa392879d644f3c25949c7d4d6aee482525ad22c3bde07e16fcc1788362bf365c0e12db42e0ad2ce29d666bed43f24dadfec45008b6c1dd96649c2afbbd392e635b5185fe5c8f9374eb6c7418cd5c4400a8025eb989e1ca66943e02e7d54b2744c51e17de2a919972c7deac0735501ce812b9453e2e14d22ec1dd2e87af06d47e8118c27a6357e006d774f053f977619347b62c6f01bf810369924295c4e097a6e8586eef1e310e787d870b0c4bee2e0d0a63b1dde4ef656213788dad7214e61d76c5b850c13836fc35ce85840ca5c450459753295ed628af60fb102c26208ac7bd09f5b02f9b4800eb486e41e4bfe780e02993a3259a5e310b404069bc15d2230b26a7f5e3d53df96ece4d51086444cb5bd24fb507f31869b248facccff49d5cf43643013f144af758c41405a02fd70564bea480b3a157059c1fab45e89bfd7caf543e2605d0d7e06ddb343cf2d03377355a12d818b430b8614687834a37bb0442197d9803fdab84129c864708031959b99abebbe013c221f5397d25750a9b8fd7d004a017646f0792c87ade48e6138bd554fdb2df57b980bdb073c805f99754affbcca377a37c9383c68add373c879ab309efc144234a1b55b44012bc5fad42e2b9c7ca13421cffb68b3dbfe6d5b6d009e02ae27bd45203c1db0bf250c22ffbc689f21b8b503ca5091465ef28295e307084cffb00f3af88bb0ffecaaa10496c866aceedd97059731b6defc3501b399ad7b8ff57f66872ad49573df06aeffe097ae904914d78991ba6008de217fb7f766044ab7a1fd79878f87df9fb3ad74024bfadc4a3a781216b141e2ac6c34ce76f0cf60a33a0c44a9a31770c279e7b11b87380de18406b5cd7c4892cb49ff5a8ef07c95a4c669eff91f424308342f68bb558c240c8a66393a561d659ada61b0fd595a155bca28054b13fe3aef57ba3fff5a39c92c0f4b8c5e3f8ef8aaa27aef70c1a065d10c107f2354f117b7f00db658326e07b8c3c6c833a3742a98a99e40ec978b71c656612da7c232575685e0f00c4fa51c0f13d064798b82db23a192bb6b8db0319fc3924929b350fbef650395d408df85e6fc5b63294ea8f36f98473f5a4b273e1a0a4b9545512547e8aabe1381989b6e241d47fd121f51478829a6557ab83bfa3579940c2d08201b24b09d209928f3914672ae60d1be1aa1dd20d7908d68da91c49523109a64bc553b4d89aa704f1628c9cca45b2ad157a874eb3afbd7d5e34bc958bf46bd455b2899a3033743af16d467eda2fd0c9b7f8892a82a8763c41c1fb112f2ecad17ae30da44db3d8f8a9a61510354fc5e072fe12b556f98edb933c9319e232451fa422d7cfed27af993fdd40913c6ddbfe9a89f1ae37c7ee8c2b058870daa04127f56ad5acafdb6accfd9fe66b49d653a39ccecf3dbade95b7eea178fdc82a7e6e5e3f118c9b800f96ab85a9109379dbf56a84ffe6fad6fc3bda0bc9968e231d34aacd5bb8c7f72630ca9cba7d7764c8abe5aa545cf9975dc163302ceee56865e4306accc9011e80134378f131fb6255c8af6d2d94d5f3e73b3c0cd2c6a86fd97e016641ea05bb61f97d701e413ecc376c07395fa5b7d615c6a32cc3fd3cad5669c925bedacf102f1f611f82a157a7362c01c095432c13e75707605e07d39d6caaa1693b06e266fbeb29be640125361071fa98c6e9c236c12ca5d0c88ad45ab8e2d6d2962ea454c30572d6347b13670d4ee9f75e1c17a71edd79fbd0c58ff3ba2eec6a5cd017187fb85cb396490012155ec40a2f002a38dca1396affafd43b6fa28f54e42eaef83982f4050b8c70b6091e07a08ac8d5b74bd7cd2fc86014e174e8d1f53cfd9277858ed4e16833daf3fb4902b8b782d7bab0cdabcfa6c0d922baf5cefa7bc110434a474d9de2c3312ddd7cf457a837cd762d2f3444054ff7389d81bc52a6bdb9731bd34a77f48bc8fc383f1bdd46ef5666df0d2f41ba359c8168ae5bd0d5ec36a85b9ec5a1469af81ef4f5254fb4b0e7d31c64ea4fc9975f157872b7f178d792877be60a014622a7594746017fea2e8c50926a36c0294249cd2d1b3ffb060eaa8050b906f4adb6acbf8446e9b22256d3e32dc63dbde922f0296b66d57c32f4d8ad5382d3159f787e4474f48a5d1033ba4760b9f74b66751efc7375b48c55ab3817458ca71ac52b8360da2f512f247e4b99fea2a43f423fcd76bfb9e64a2a0fcd69a3876c517ecaab5a4efffa8e957ba647eea810953e1554345872488a7b7b60735689c20e3ac9d5345c935bfaf80c3a6fafd1cd551457e3f8c4caa24568443b5afd0bd6eeda07938838bcb946460c9e882b3af29ca787b7a0b03ac3318cd720f7b08169096aee70c26bb59f3fcb39fef1d02140f43c4e6ba06e8eaf87f20685962fbbf1609216be320168e05b3ea734687779e8453ee4b44e793ccce8a541ec26781d980a58ec6625f194b7485bfd980f61ddcdc18626cc60b7754951520256f1676a35b64ee4d3f46c8a992fd824a425019b90c5ceb90c5feec0d3ba970f46cb5736f8e2673fabc8b40ea71730ca6e7dc45efff9126528f3e8c976ae1c1c2a9ed1f09fc848e986a8e2a771865424a16f8f3f8fd86e5c9c7bec7f7f698ddcd45b33f7b82b2973b075e46b07d415f50a845eb214d49f975b03c471fa4f8bd3c73261c4037eed7815f388c4e454737cff44fa12d358336ad5f0f8df8da4ba572a0e71012bcb776c41ea29bbab45c2645c880d4108f1de20a867464513414d5aeab3621a2cc08ce9370a2d64a0dbc0aff5f0722cdabfc3d90dfc2ac63b65f4a6e9111ae0595b1c03e7d55d16449d6f8b1ae6328cd3b29189ed9eb34ad5b1541f8596f302d0254c32ee04a555d1ba9567c47fafdfdb05b98783e04d2052d4594f8c7549b048c11477229228e3be8cdb214218e9069a2f21ed370b12df6708357db5b3e8dbf1895ea167c77ec4b6beb93fa7d6fb61737b61beffadf5f3b533be8730caec2ef1fe47bbee3d204ae007bd2c0b7a1c1784a71e0d85d6317111079a5d4e74c62304f6c91ba32b8e5f62ac68811cc0d67d9707173129c5ce874d6d52c1178b6eb86a739df6c27020ebb489224f1d5ca08ada416f5dad9f224a795b475ceca4fedceef605e96c5cb939ec6c361463bc86bdfc6c5c5f24b42888b59e229082b024f78eb28b9190beb46a2802dfef1f9019511118cd8dd338b1e3ac04235cb6a31afb49b27fee71da3a387a1904acd74799ce5211e3c2c43b66ad6a050b70b28a2dac3294abc1d53cb9df334546ef70f7aa29e93a0902fd23b0a554570e0271a49b8c548b5cf846c04f80dd922749b53f4f0db901e4c97c1209236adf891e184564a6b94f3da00e2fb548fb581c204eec117f8381a735f2fcecfd69c31d15342b053d5681fc97644c51e604f99299c7679727b25f73d863f83e0bc2288255af7c0720bd3b0f1820e60895a0d37f60ee05b928f7311f97434dd527fc2f4a33c8d0f4e4e3f7e160afa1a2731c522eef280702dd4eba358370cd6c9386c196d351f2ef8935045efb196d6b6a11e42209f0a4b64f4aea7b830ee131bd46d33d36f42dcfe833e5fddf59ea417c5ddb8a80c50957e3eec9177277483d1231d0e5f40aea3bfa9eec670bf19a72e0b96a3f9be8a8c63cca7960c374d2196881aafef24d32b2d582bd562dfd8d1996f1e7f73e412e3690ae5a492e11d173f04ba9e68d8d9cfaaf322eec828f95be3fe7e4c8dfc156993edb40321d40fb59cba71775581b2186fdd0271c04d85373e1022be81e21998a360bc1ba46dfd69bfb4dbedf43f9688483cab2002de982ec8e9ced314aac88b37694fcb63a41b7f245425c0455c146dfad31cd56174e92fcc6eb7e0000000000000000

The core idea is visible in the encoder: for every character c, the script computes primes[i] ** ord(c). That means the flag is hidden inside the prime factorization of the final number.

So we reverse the process in four small steps:

1. Convert the 0x-prefixed value from output.txt into an integer with int(..., 0).

2. Increase Python's integer-to-string safety limit with sys.set_int_max_str_digits(10000) so printing the huge decimal value does not fail.

3. Factor the number using the same ordered list of primes. For each prime, count how many times it divides the ciphertext. That count is the original exponent.

4. Convert each exponent back into a character with chr(count), because the challenge originally used ord(c) during encoding.

In other words, the challenge turns text into prime^ASCII, and we simply recover the ASCII values from the exponents.

A small example makes the encoding clearer. The flag starts with Alp..., and the first primes in the list are 2, 3, 5, 7, ....

So the challenge does this:

ord('A') = 65   ->   2^65
ord('l') = 108  ->   3^108
ord('p') = 112  ->   5^112
ord('a') = 97   ->   7^97
...

Then all these powered primes are multiplied together into one giant number. Because prime factorization is unique, we can always split the number back into the same primes and recover the same exponents.

The reverse direction is:

2^65 * 3^108 * 5^112 * 7^97 * ...
        |
        v
prime factorization
        |
        v
{2: 65, 3: 108, 5: 112, 7: 97, ...}
        |
        v
chr(65)  = 'A'
chr(108) = 'l'
chr(112) = 'p'
chr(97)  = 'a'

So ord() is used during encoding to turn characters into integers, and chr() is used during decoding to turn those integers back into text.

import sys

sys.set_int_max_str_digits(10000)

with open("output.txt", "r") as f:
    number = int(f.readline(), 0)

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]

counts = {}
for prime in primes:
    count = 0
    while number % prime == 0:
        count += 1
        number //= prime
    counts[prime] = count

flag = ''.join(chr(count) for count in counts.values() if count != 0)
print(flag)

Running the script recovers the flag directly from the exponents.

The actual output of running the solve script is:

797715619504257874916394846157717696155332674465160192716622941224922171444999018504769916754249473522008485215199349901566042371013059239365430857677137095894125776268190202124107931001828007783436290771605244860661333596904496139597023795648772390951276895923773513075160918729702143536010260594721737519838697967442023217220826056056874916032685253206435725136788324953829797180728292272764985280806969776329376733517251915772554095666257517934934436018525833266557779527553266913056725951646861723171616571697285371526086130957055107028181477679615348689875167588999916723472332186388350931920154808395288756482611052120429139755866124868366088123750040402906414264047309866466685169383787328318130829801659266263663305941771490098992113965468801258025240507987568955490129351420349138368569590175972879983118647780832648230553544951044129676998734771705072121720322909484315169491421796432348127849532633558260154236034066172388532979148895517841399619493590732673069317811700700954090615346699321297080379758726001228192089858608326918152770346065780515835913717109031674365376132759052145277574182177359938156482455990999966435905101596354307512236279751264323013925520407087292170991659781492387271727611373410695401700629286470254281602368206337013102685965555944130563303867150307097824245795710343485742598387242206868318358021941393611364141673041974606096742063239466034705351168436398380942113984553874606008544431167313813805687219094898840975545309125537965776402184910093938645705992611192389737170960939590580951252751461444203150684878408764191099922476429489337153422557472103464508139578142313342781741428116294507902275684417914790995320413931338710900471683605494468409193353221477726205537529491901512303695772961899132012065551832251061023648072644954250611225390610222065994220476513355643811031463980794134410549393243050550598116041267616364127286823223305129832878996749385611129132268453590625147504384833661997560369229144239824135679204259347265801694047644834684218279797371294019554184229628375767696635390859176100604922287620578774652679143247145752051266572051243507818230953580545888246463220660971284142363495533324912781114176159619605832767865728963030758578892941119936245231622087716554428110504740612690051359349606338744114043266524260202078586562631370552045030726686962550018536604611413953140432709186406324518371797080977732008219534811206194025640637136866923552531345623048934721420867172034373872981932474331718925852341751265077468544477716841273675207398069183657146498512713655823669060114523992646964848132539292136954421359072230828304014236951806755388289630485853112583217979347210751793423179339357883228459282849428612634277144524709339782256731134950966220489408397973306298815204568419466538542132704759715921479570181420913331035830537301159260647530133216538560986270710575454465056302339137919925861867167238037336749453812708540450936134725073908814806004733752836083369463903013939722035558652742009838791524292188233614093344687457171302504038849093703595979229454466123756832870758221104468532191157671264415166280192965263867839620141965617476878469334879933064243339413792946273991888044636072962822074999372633342568308174525951181748273983435762474612275932514542759477639333935722735024615312155967420515382773640387888355767520087233403840218548612469746480926332782508328852712880394339053314884487864501153122578779215034212393918488369627690928457040727829411074177992398974637676312363725743955852323228857356740311052576375633134161292886499948586329974958946102017437306639928018059486330707901053112895222066553663268329850992283733422437323035737934195600141736165735203562349591110472377385667520117643986836890859613235725527496285051269634461688344575398536702966640354279443438956057462049627450805533322525635130597031766945348694261663632051262791576734380387094162327263351871046512508612514118564907102550340137644461725528472757546147439291001319034036145220872417523714178945585873040920040546319349813456020262436834934208298739569500709701020981541408504949002513798519229300204816933563287185946816333692994912667011810570076595238407649585401165334971802386859593101428244634288097619175128577879554583264799027582910166342529855901258737215482957564310465063024122970016645067753131781298660837710077448236026055052964641019464191738032491812138593847931797227911686380003129229854548589079739747244261069032708802180352141196982417325264065045863966244945426073663030747933617257190459246054627915363573616687964804545679418401076696157476410409650641666143145702580541045394802003542733905449582134657572641759708555376317163976573939684394243522013902930383043938748896396432820860165025125479745890617933599625274501437205402784550266601592323436726574673196841626750232776504197629821947833402733771538087684421948648560392042952809538278595149137762107481128584993984771498298313214409025686232536125490582725192974167797263195492523069612043693976351338177913992393898944433356438056077626003002406705436340161875112704976992121587257761468844664375705864147801577071591880539006602785470689990747299060610812979130850221913534900384536407506313465315760344141642352049614356187975312766303270185609621048859268532551842718925164593855056501278995264402554902539546348452689065877781699641783214843070969219772176903253905972843685843241609976552948988539650158473126702518239674544033881948619257282119170038174357506818850457086841846747203115791609290811207587948312279976269635435788825424748827711469564132989895784776853052054618024114188725207803742106232848497574499055291452105280099709764335419129374428313808952489581683213898484247885354418237452235782968897202323910194524995998434885247741575747985187403297157551226923947043168133374335999308726140494412800732573789986658508008921918494981496454912788866393799379064893940635297754788928888682018241992357138838384625996515614283516304854150872021305838511638775213067376776533706143095841309141052552402178765313509834886996607935543999364547038249515375100748837474716333053248646707088082739897308908905059226678360994749385017972781544049572950441796900610119416744893455791448205373687756794458857906302998188937668150159231606676268526094820273812140537219132412364990185208268356989652387540380366761674475139980441678692614808022215398797800463730991657482039553743884566486352310130410356998201782389314022747577463753641893545678385425383741206677816306658788625668881356813822262818367200017439537970757259239890292798024015279620494865437664385815492076734993467052363469497649538040011380234714940631806980366752344614886022555784358356906691338320068305948959827245312370080859387452395131202765734825387383996799781504930780502334163300520406318937641793184067614513650222104802100894641522132295638476775412679337944359156852244971027635326966257498618118168673422476016412273599355331042288252240006585634395855541218697602448972424207744042046520333814934278950015155065537075707949937303526123117486850778315039274702100726963662214989147777918108435312235145955492931390322669795936736423055407460729620275375355377339599841336695456470909780992835049086196840805859887472294095987509143905697294350278907387695253616174424395717539903858701314562254021075081378099922592301991652431737708403844468467171718071370923347539294208333868696049529836944484938471817450891258106002318171256251951831069846860499579781451011548702946273086639008897694369534199156870639661751409717286876141169673806603641371685754036744772876489954159221291420895947357971796744427872036506238812396072808455030099621298068041676511533512757476116949229109763170520203001145981451925524887498152021884702513942123145847736441626186573457276838331459161493051821738877235776242041976627796844318547651552283141099360072295091956969284107370579625570256506750209430238724164707360778953229649777083172582226700770013143223439519445590053262346801014916647599470742593412258945290934469993591795057167178081965734580464290879618768187385487679038090793475301124679062937813198076643341202043354257859600665561369301210341390063942538241935992386762568346433900626582428365784266507482425822675172821888121665558999558061509795355926737241208022741131650749165440243461552110334872892110485779656854393330938810536300255851646971936288875201662769440660981237411707205032014096161432808394337526392748002297677333454637243770018643265228988287086207537601357388271498848288508903297035530119713698872061252426231014868271532168327654816071759261321787448650866281241178512573242187500000000000000000000000000000000000000000000000000000000000000000
{2: 65, 3: 108, 5: 112, 7: 97, 11: 99, 13: 97, 17: 123, 19: 112, 23: 114, 29: 105, 31: 109, 37: 101, 41: 95, 43: 102, 47: 97, 53: 99, 59: 116, 61: 111, 67: 114, 71: 105, 73: 122, 79: 97, 83: 116, 89: 105, 97: 111, 101: 110, 103: 95, 107: 115, 109: 111, 113: 108, 127: 118, 131: 101, 137: 115, 139: 95, 149: 101, 151: 118, 157: 101, 163: 114, 167: 121, 173: 116, 179: 104, 181: 105, 191: 110, 193: 103, 197: 125, 199: 0, 211: 0, 223: 0, 227: 0, 229: 0, 233: 0, 239: 0, 241: 0, 251: 0, 257: 0, 263: 0, 269: 0, 271: 0, 277: 0, 281: 0, 283: 0, 293: 0}
Alpaca{prime_factorization_solves_everything}

Alpaca{prime_factorization_solves_everything}