Symbols

5 minutes to read

We are given the Python source code used to encrypt the flag:

from secret import FLAG
from random import randint

p = 307163712384204009961137975465657319439  
g = 1337


def encrypt(m):
    bits = bin(m)[2:]
    encrypted = []

    for b in bits:
        r = (randint(2, p) << 1) + int(b)
        encrypted.append(pow(g, r, p))

    return encrypted


def main():
    flag = int.from_bytes(FLAG, 'big')
    encrypted_flag = encrypt(flag)

    with open('output.txt', 'w') as f:
        f.write(str(encrypted_flag))


if __name__ == '__main__':
    main()

And we also have the output of the script:

[262572825599060034366823166754605661914, 278939195996652589877947177553005352651, 143903433690815278490045256112999587058, 300451267455419863329482966468297972155, 104391404897614206052312212627024948439, 86772372701052708391385443135522397486, 288172316186606630456779345005927009239, 288661407733088959033566739646806014288, 180798004639152373887590530832145012629, 218290632647516283426156111326639007623, 299748479638388046863746374873139411473, 298179633390217841891695751768105583772, 140134785680718139014940509535196057921, 268333651096063780946124751448239043889, 282590460646612308531589301882983616571, 300999437566124027320734099141572375964, 124745125188008977024187394550325903821, 36948705089073339683170078089406671972, 187954759150870674461200587789611963820, 141733053674242574818723742414216723359, 187866697379171274225579976720944824915, 186273618399045934440808830944387099930, 224156244892464952549924654268353197497, 224970784148757781895082433051249134167, 110252533912502518081501539408054665914, 122350678753343809276805213190223127554, 33433386126817118913542464516882557582, 53466438995220411764805763134931237303, 148360474956018079350986138749388248643, 89084102284769009270772789298437060131, 17078025100976422940768973546434565901, 97380707976676013736707789717204352477, 85514744733067918434450155921968536814, 30271424945038928609680646995759300620, 96913098437453150505458640315261222334, 71608654696192487551954114631044590912, 227834163856140337583183844809484396935, 101532183549966644667169274951947261891, 23657921352646025937556819987483561867, 80282009966975968329291268092337049016, 277972718351530543659042073235033527618, 110670376477185275669190099253325576937, 298620645445050749379667290398101583690, 279050098907838085672038483822980095854, 32580216377510611679378689327893317437, 83078671923761003829909456851782156926, 292533454439187505235477306696981681187, 189265381835777019539683225593613002358, 237945170017459196370666284915274494340, 265998641126700023207478245739978026246, 54889288603477633260829554811052486862, 31409273533421087497493982284207301758, 202307720658758226630349817319537208129, 210672407765994696048864408205046576999, 253252248388360656236830970737613228157, 184245187446375859552639808563818808988, 160716781837050293287708766002887835331, 72577120042424090310013688630701390542, 292412698134247377811776644156471936274, 15722773455403573624542888076314998674, 191240464056960631737496776322535334803, 107795878750172063377432566188750962564, 286193338867802265738827097299721314894, 140437192772680410922082788218855396416, 114453614764766910484538140288272591538, 280311289247437558305657264765122276181, 98287989328832830289571754264586135265, 273833334331807803909944803549554387168, 215155463817649959410839089067708521807, 239844295235942259005518532859050128371, 178074367560046571009062818833234677615, 195596658089255170418528939309785047053, 39110249160752770077113191646387991871, 179490918684174038192260899336551021380, 176929008505341156366154707413904526679, 203638449193333263493050292292168000894, 17421761072938798102303282735311286343, 105603558284934312170024801106343081202, 63815521384588676512711840866102063268, 288614671883623818741009056316706346560, 182296655238137940315780670408014747929, 160242756561434460129485802444745785549, 300657809341843092324794469590087084322, 157456353172387262200545282152521055885, 180460844729413922901015865690794271913, 171610116212519468615940461160073296202, 4650202839464313536995035455431697101, 148066093348842527886956117258382185876, 26725853722234770892257065263602207066, 220057524464914768022410639942066278726, 22432304995539526159529386991549603531, 138491544005281459568822369259294769716, 64965075216228404365393388843320633656, 189934842061185128356112326511154725194, 158222984228747934004917350872253450054, 33548425763481171743954622796989847850, 227017260093264974137203679652749738701, 228890004195473250946981171320339321566, 6725590713642849724212517179117088053, 289979483775316819563827470166063410880, 100947153862658871459404343760179267001, 304798527417921037884149800192212022284, 77626378243040442291068951856082715359, 196913071142939043342316360547350798438, 94154421645297699943843514976195473511, 101036271179914596913340966044942985268, 199798275369272495707245168783049045455, 11450846366755910976344425095242488571, 185146727415340134209889286791417861834, 125011597568275235335678182284380327190, 94342321881898026600158631919565788862, 155555419768497674879378112059021938005, 113120007484046273590906985390087158585, 64394171105463760451760174021703862521, 29682814718820814482382811245817762377, 111095942885360420636953606827211745898, 265425470523721005418048234033167008359, 132794118530719522777821631300868460870, 124518938915165553551960997841903273460, 222349397829414033861380878024022499083, 132643007672707816097154978785968979921, 261368760188858470002474628801494567212, 115095157181813928892802789050203246027, 127928969521194705053896729988779426067, 147817110964886086695335272427201894909, 241948701147700518734189834333664195136, 59100431723990890603012326314901658907, 211784145877315013753647286989845569008, 261081330687202629942070249912533742829, 192629713006782102177196040028853468613, 283360846633663057218352474075627468753, 40941989434259496486327526579449263225, 102437054835991384541709764099738938373, 237409377663929111025702089049321722892, 65023926667105515916637555057044845133, 135258469591154674222420532387799831389, 94690214186065155706351413324316678255, 63258996922044253371992452584645278171, 149754651872003117913784525873585212121, 287140166421801129480650361114397481092, 262247068896431367262855010590945568536, 89545156732197500533457874551915355839, 132105949116012957349478733024278546488, 61860822995106994176665741442286380159, 206398703607878800019920587498592295192, 279037261687974648174047100382641150743, 151488571883380330339417925842249987424, 152242994304128578309008571687171702526, 45945840161614795410242116286473066114, 10113493690991419120087413294161607595, 3124530762778996106382305903899731622, 5998288718439761509878837247793048755, 128824443646770316448650024628648395609, 135187974794770298819740959530814163794, 163840693710961665316349275026233880780, 248964606927106204190246868965956936172, 257008797368309522971411269121199077590, 59649128594889430330076082884621272389, 290371126915726419228114654740433699825, 305993486009051077288435926328544764971, 130288591393743839160351184520603502498, 204353550131424655397295532878721059659, 178896475437492001194876766840281836834, 290855176016200081249739596516245543310, 132781134024758219054405389463431082189, 173392487600109138226864432863426989874, 91077397293246702308627273134490336558, 236007541646559960783808696325677657225, 108700053375660026060470811465181942503, 70755530456224290931236590773328449611, 16404231868659090806149534356412544033, 116688938386656400973059062413610847756, 242762529048907826773326561202644442852, 94130932742974626103822127940706278857, 226783087160025736928381613516132571100, 103407236847827426960672716328134116157, 63921272648174859140804397036550821339, 244513742759151598385167864951760932876, 92302070762023624118563738223927713792, 176523037630384762071629744679426692929, 81266145838916416093506794215976236426, 228371642505996728976354726796887777350, 147184945328524751064957968101345038881, 180434692526879629483773949434633295493, 10621907588254955415476080144366081559, 15226693621227756426084043767870849251, 67673186121648722008787364996836823684, 108741924475519464160263749741202796737, 41550506030234434781759292789078907821, 66533922374608024386259393649666460367, 147384135073596209672342249526511591865, 191040463199985177371421563432066101046, 265010702214052049243090013318516767987, 131814021698993486119428548675814245651, 5787578400434715591420302008213684511, 294546601889274004704009396450175107672, 203667461273771575573524500374135672975, 210183727671693023281854263789638413510, 188804484670404777097747366548587019880, 69355587135998888987690518851658718931, 65103708752180797008533289215591214928, 91875179266362032201164795417930740031, 247498341035325621751317096011953255135, 261255537252917709444080853249165168313, 45825512101500558217914898799343244749, 281019559503745776896655575297779871369, 106276316723126741085391493908419034976, 8449597622268152860998298122518732254, 192788079751465508706484432062429018518, 58476159041918351436042095488635431166, 303604872218308521457438723879365903477, 141469376950178710128586220021801286131, 108474507277584001526346410364535096419, 100617264101737367315711227460456326807, 303029155938423028648420249296139257579, 211026895057484998157182714814673228572, 198987981458347129456720240309850148208, 38476260694898655560992556425657723061, 65845847527699789141149092641113552002, 141677647649151416547986433531122881988, 4091942363249454577859060703194006261, 109763850503245510374049032983387189447, 197094977384275217730955333776547586750, 234520181750735610483101643825193698446, 103052658855432468767936280442490621180, 16759110998138500728951058088798000208, 10697415320110537151737085564238678997, 253036751210750085908003499696951159996, 262929704256193609305774660603783824401, 147391938475559963658822195007622156971, 112601320228233572942067858469750449856, 183948343786572234284818446460190602674, 20205952552784827633054753147403995622, 201662574426461718875506391624591430744, 181780533090238319974344083098875230955, 228693981487002894636516745642003366512, 96069617500808786359067089655049460567, 284979481908434912695005729712571348955, 180944967601021208674361489765398217397, 294629383271249204320178969256741985510, 291192964257156917103611817471283391854, 301324909133376271488264820018563798486, 91005369320093928434315438532761713213, 255368348211342905203040082309986511376, 209496870695552480282512548581080594893, 166427535711192353023950842945471853061, 63355113551217503783319572983502520781, 75740553352947074070983506660974510718, 9386422962331834142062737955846244288, 196772126637253785950015639576073263740, 207797345759834260604759500598441061754, 134435244026583432056701906841538466479, 144475271659653801064978816241614863544, 238798490500178238475380028928683139365, 187247310092445827099631842813761387453, 92692273195787829185970690015215141459, 15695379204995261980808253918137831430, 301775005361456403819721902606582955516, 196285178487792250838855463745267735682, 302710489636580771607661281362091849349, 306745902076136884170055453929000815540, 153885934098405242959701206636539510489, 140023711682013577466360719439409725735, 305018416543729381966417086199016277141, 222321166222871403308358175318386849055, 111626713762593542633092696000032091161, 43822615068145205587278937461141655994, 13180139775053039858021371179743741548, 63262309652692512989824620251429053149, 14230063794810570732327319336891015292, 234557452587673964294498036906786014923, 156755589627800844426934567283969685359, 123023009728610084180082626561321172869, 108377422964961932506183129914145575614, 86677029453676299120996356732063158269, 189488752373296276764476360711945629223, 180085555839189904801737110976365140630, 112512804989245106676058946893229712165, 156061513415137504285882494322109345561, 62218534243734893473287245609867280718, 260311288976877930143929034020810946666, 169147981108130046250904378527067034366, 291005522519419464476431295758250273463, 93361513268605238253798548703646224232, 151798048713711416359292224102779154625, 249684912702135808297477747017608586078, 199999735155550055932868654370076219285, 227745901798924408079283202489224685348, 262538682600111885980629701097938096862, 53653875625654527362187018866190383445, 19489420364277211413382129009297783322, 295882635294338486398772610646294148380, 109822438318770041200026834865624189418, 225714249476064892660499439849473660999, 11266657540081361947021655624592786301, 245055478724292989330811423275661302872, 132967590758954112376275876273102600834, 118051934734754799582916084528049999779, 226465316104303799156644947497497794334, 96792341757171035458866357506922541071, 28741117611432539559593661842654450914, 298148011153510123982075997460557192684, 75869713030305102318461101309731518554, 295441737729514109829864322930140602826, 50383791451023544119010329548618174240, 302070669723940612583665917163673883442, 283138688414803273197472443620652000948, 34779180312752312027938010921336758638, 42088901696675148294332761847983655558, 157469328458408226416557786586646542255, 24700923520947358485243054321033987806, 270613289961764342637089810771997116290, 73898265213327193629058056723498137525, 20803894759892964167827762547854915768, 158164858380695516001060779341848030001, 240726912502174481760909365325599159279, 80990799787598853410006427502500015034, 63298878163954451201129286320343483226, 290574033927474353083508000112134332266, 199392751352979964913198807554100545729, 149457714140422700232422788007867797791, 69389178390428580499587967496742875392, 37305129540069950604752918951865572826, 304809577945515636948455567998979089102, 135947490614111221312882202085896103891, 50402608265435103744074968506967992471, 79598916778284790223689486550298772017, 109298685877978406560646152914174057996, 250251883119414584633892198808340046143, 94029422916736724951140906090845538666, 182733705111183814935462478814966725144, 109869352685182155362364906677398744636, 181085224867831290446394531592609987182, 103298999178580253383779702617826075498, 118649056592219632352019294276059689987, 137113509403326192501072244449826655820, 302875375203828383184480420986942365039, 290889168048682586400847708957262413534, 112196159154682688072789999777081598534, 51174412178993318503855619671766310058, 89245645280495267938994113355236270920, 218964806855877341692379028649543760987, 242068976102477536366695223824526902794, 140056024203758886625891945307857210276, 169867421887529162171217297852031468767, 291222077385992471836205255196999219314, 218432856514572829341937728867298080046, 258174281098999554615170168438024573090, 84147471132193766922553458992181634118, 148965892163445531950103773246599850456, 287419756763326447392728782956765422164, 145265271350108684063345277600322041940, 205727597154010873918489291536815252315, 147627745738391649973916715446728321956, 14561111345966888337667531217404341575, 106524564482141462709480897903780383950, 208402855852596838808236121308886729740, 179863460979364868664897495508913046372, 26283694547926457817911873281737204134, 1751190182828681463966913487064811883, 56121915052666404918122334525505785729, 38733174563002131538568828508985076247, 220353968628112296309148306925927873010, 80366435042477429413993914241777235802, 298040146951687822008177475038180210248, 280698747301268325577882593837950802852, 143868056817204909460071799765375109635, 292867935925067625533155401531237706998, 93506799443033695759482957586314905295, 230756721173675584311277391476762558396, 292089771839636180863018685070700933226, 58355351646233998660159938383061348734, 78117857037250820093466941062858112882, 59472422264880489351175051552858148623, 55516497069005724800197796300496368984, 222425920087303270649172942411037252875, 260184134779985464755965005378807528129, 170660558030661162333726363672493376359, 291107793253318664753672533758071609076, 257737373469913216778000749792582625045, 300791037029786283415436854850891395001, 21636927709121252223148981442667501482, 33177188822203683689311725891088510814, 129876878830406481581043873542794972703, 175122546025176231600040330964976109905, 84966628159775581861587592415473549268, 181365308364771768890855133098870606192, 77323536216055112938156471908856897327, 79179133247005215522249276417562312109, 220415658307472639506909441888578449982, 135219998158222388017194695183214255477, 228794357036797413899929840531163614129, 121875284428575149995048440035759343797, 99668951138204698043829339525284938910, 101116688430629910756317487912625839013, 246220714299537149142251336019042012202, 4319791386402748552182138759751773110, 142969792014205997725319404904457484838, 215352598499740488777795666635931729646, 64841601615689949600421366800545958432, 52105620521604927379360224487818262453, 103772885722199494627016418003004509209, 14256569830796971240356316455037427207, 73468317830712315705792231966873822903, 156374143530939021755320709591836503848, 149904598646330721480597376190239491561, 115619008296066422242347666046084061648]

Source code analysis

Basically, the script takes the bits of the flag to output some numbers that depend on whether the bit is 1 or 0:

def encrypt(m):
    bits = bin(m)[2:]
    encrypted = []

    for b in bits:
        r = (randint(2, p) << 1) + int(b)  
        encrypted.append(pow(g, r, p))

    return encrypted

In mathematical terms, let $(b_i)_{i = 0}^n$ be the sequence of bits of the flag (where $b_i \in {0, 1}$). Each of the bits is used to generate the $i$-th element of the sequence $(r_i)$, which is used to generate $(e_i)$, the sequence of output numbers:

$$ \begin{align} r_i = 2 \cdot \mathrm{rand}(2, p) + b_i \\ e_i = g^{r_i} \mod{p} \end{align} $$

Solution

If we substitute $r_i$ into the expression of $e_i$, we have

$$ e_i = g^{2 \cdot \mathrm{rand}(2, p) + b_i} \mod{p} $$

Notice that we can express the above as

$$ e_i = \left(g^{\mathrm{rand}(2, p)}\right)^2 \cdot g^{b_i} \mod{p} $$

As a result, we have some kind of oracle, because

$$ e_i = \begin{cases} \left(g^{\mathrm{rand}(2, p)}\right)^2 \mod{p} & \text{if} \quad b_i = 0 \\ \left(g^{\mathrm{rand}(2, p)}\right)^2 \cdot g \mod{p} & \text{if} \quad b_i = 1 \end{cases} $$

This means that if $b_i = 0$, the number $e_i$ is a quadratic residue modulo $p$, because it is kind of a “perfect square”. In other words, it is the square of another number.

Otherwise, if $b_i = 1$, there is no number that squares to $e_i$. As a result, we say that $e_i$ is a quadratic non-residue.

Legendre Symbol

The way to determine if an arbitrary number is a quadratic residuo or a quadratic non-residue is the Legendre Symbol. We only need to compute the following operation on an the number $a$ we want to test:

$$ a^{\frac{p - 1}{2}} \mod{p} $$

The above can only have three values, and it has the following expression:

$$ \left(\frac{a}{p}\right) = \begin{cases} -1 & \text{if} \quad a \quad \text{is a quadratic non-residue} \mod{p} \\ 1 & \text{if} \quad a \quad \text{is a quadratic residue} \mod{p} \\ 0 & \text{if} \quad a \quad \text{is a multiple of} \quad p \end{cases} $$

Proof sketch

The proof is easy, because if $a \equiv b^2 \not\equiv 0 \pmod{p}$ then

$$ a^{\frac{p - 1}{2}} = \left(b^2\right)^{\frac{p - 1}{2}} = b^{p - 1} \equiv 1 \pmod{p} $$

Where we have used Fermat’s Little Theorem.

If $c$ is not a quadratic residue, we can take $c^2$ as a quadratic residue, so

$$ (c^2)^{\frac{p - 1}{2}} \equiv 1 \pmod{p} $$

This means that

$$ \left(c^{\frac{p - 1}{2}}\right)^2 \equiv 1 \pmod{p} $$

As a result, $c^{\frac{p - 1}{2}}$ can only be equivalent to $-1$ or $1$. But we assumed $c$ is a quadratic non-residue, so $c^{\frac{p - 1}{2}} \not\equiv 1 \pmod{p}$.

Implementation

Now we can define this short script to determine the bits of the flag based on the Legendre Symbol of each output number. Once we have all bits, we just convert it to bytes and print the flag:

#!/usr/bin/env python3

with open('output.txt') as f:
    encrypted = eval(f.read())

p = 307163712384204009961137975465657319439

pt = int(''.join('0' if pow(e, (p - 1) // 2, p) == 1 else '1' for e in encrypted), 2)  

print(bytes.fromhex(hex(pt)[2:]).decode())

Flag

If we run the script, we will get the flag:

$ python3 solve.py
HTB{qu4dr4t1c_r3s1du3s_l34k_t00_much_1nf0rm4t10n?!}