# guess-the-bit (crypto) by freed
```crypto/guess-the-bit!freed
I'm trying out for this new game show, but it doesn't seem that hard since there are only two choices? Regardless, I heard someone name Pollard could help me out with it?
nc lac.tf 31190```
### Source Code:We got a python script:```#!/usr/local/bin/python3
import randomfrom Crypto.Util.number import getPrime
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651
a = 6
print("n = ", n)print("a = ", 6)
for i in range(150):    bit = random.randrange(0,2)    c = random.randrange(0, n)    c = c**2    if bit == 1:        c *= a    print("c = ", c)    guess = int(input("What is your guess? "))    if guess != bit:        print("Better luck next time!")        exit()
print("Congrats! Here's your flag: ")flag = open("flag.txt", "r").readline().strip()print(flag)exit(0)
```By looking at the code we see, that we have to correctly guess "0" or "1", 150 consecutive times, where the only clue is that "c" is multiplied by 6 if the bit is "1". 
When we execute the script we get:```n =  43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651a =  6c =  1410132788608602763158396295624793759904655068051423981654157408858516026643980786856015619052298024807772928582489337691467942913156648729914931486795307951043818464031117288130179675799373821086788361878963242640731127560775267553300797276590046325077916983342153282725870806303932237803398185892655978024005382393197627845440584640158085873863438715977431270918091974946191705315979525940276484143527850043259370577160815242392335466977633709148891754549875667790088878329357384980261534051937286670977696831607765415121400667438479466496843247444740737689841014683444173927090709875884586976983787960903008800682080998624903829642633288754059748302392804655391341909383708326141414538118706706193002866326200907188769586264734937048444005702348541967340602885269784331311114178318613496397173661613650164549737500854189221532106801126563074403397990825351801004596417821801104738103953469714525263238105010960618179916170944313252522209199260608056099722100087218029189691725628387132589723192354630001293643477579628697822084503351723020388065247018710912728049752095530572151655528210320574613101568566631349290814504466543787365308284621127890546203499258501497921210098334717912419847132348899737023840376088480068924340126667045094What is your guess? ```and are prompted for an input. If we guess correct we get another input, else it stops executing.
Since we get c printed in every iteration, my first thought was to check if c / 6 is an integer (and not a float) and then check the same for the squareroot of the result.
### Solve ScriptWith my first try I encountered the problem of the numbers being too big for python to handle so I set the challenge aside but came back to it later thanks to my colleague.With a quick search I found the "decimal" library to handle big numbers and wrote the following script:```from pwn import *import decimal
# function to check if a number is an integer (and not a float)def isInt(x):  if x%1 == 0:    return True  return False
proc = remote("lac.tf", 31190)
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651a = 6
proc.recvline() # receives "n"proc.recvline() # receives "a" 
log.info(f"{n=}")log.info(f"{a=}")
decimal.getcontext().prec = 2000 #defines the precision with which to handle numbers
for i in range(150):  c = (proc.recvline())[4 : -1].strip() # receives "c" and strips it of "c = " and the newline  #c = recv[4 : -1] log.info(f"{c=}")  proc.recvuntil("What is your guess? ")
  # handle "c" as a decimal object  c = decimal.Decimal(int(c)) 
  calc = c / 6  # check if "c" can be divided by 6 (and is an integer)  if isInt(calc):    # check if the squareroot "c" is an integer    if (isInt(decimal.Decimal(calc).sqrt())):      proc.sendline("1")    else:      proc.sendline("0")  else:    proc.sendline("0") proc.interactive()```
### Executing:The script iterates over all 150 guesses and spits out the flag:```[*] c=b'6379556576818693476369652866915677377894413664645382309301046455530350313139827129026846449494475147450731648674871386465561190560881760544434252973905184998040779242274724137559921251802376149876047770962192322136011026031759129519388371222799582697342394927282160454467050064239172830827064982617817916765430915280461553093988461788535096830251310062487858833260064754131490708505294695001627827459963566392063942637563391480440641587416365725231721767342990858613705671645430779221321661576064018147470503132703573690569406345476551084447152873929870226766169407602537799916516459358727305881894446739481824907493101771532823203181529285829652651946506724328146183512313412023176965096663100649684186075991234406802656214153681998369180788285773901356468222885287272369202768139169438185333271146557270387060308971440789929111988491595436646666114288010993725911690744430390504835053338292404143911651834228370248273827881655858411596671372928064517440745261111412661679694629015085332978109036673981210845423451990686744969976947180174463621257122381650087097071960264711047734964803372453372631394536146795698349408032673863338309434066801671063071954162980181366564780183827187245533775694383130630158378130517918884259829343471484934'...[*] c=b'6038670922528791006574237845246172509058837062551726491217358038095981690407070072180666580087324570715456435143466739702698882251273209366460724417208218488018591826065629909759434492037599591554602290059411179571690837723775347405485130120576664469078054827418647881117411271802609149492164629723597746961448546436781397396595293646024452910052788072169315058767747784475138892627915404370736615318593760966907449530258439343918390321549846788258812549565618914834121173186784027463338010685511385899363775586734638617912400115420586078383678300340717277346087687529265000384996748663271464528159538150425841122659226596410887335693057292714056690527167287989839980984643430259292180475013549084543750720342000610935829910517486298660403339002914736158937030590002718742108102534829881266984508458887611829499901141774951542746589113997806246676334770327926189552974086732835924208174769412480622008687207634048594740090234092165088255872231601018555153579886508313574779316164514095783855237901879516111612535536680613134042848496708388807132346594459326812877728486597189592281687906594985176565014487243306028283741554012966908508482726256106692353541554789556765995305308824660115129770791259589401609404176154281095543838522252854656'[*] Switching to interactive modeCongrats! Here's your flag: lactf{sm4ll_pla1nt3xt_sp4ac3s_ar3n't_al4ways_e4sy}[*] Got EOF while reading in interactive$ ```It was a fun challenge which I almost missed due to the hardship with large number operations in python.