Then it came back with some numbers for El Gamal encryption

12345678

p=[27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727]g=[5]h=[26696554507908936438901890298746521910116296076837428579598027758704709599232074507792938304523038408818681479609235663274765869367622544690060477308012386594561731089364385195276126756738284266122817618656603247291387364232479968970841292097873094163406337052697171975191525997649688128083237295019571966329903444521571029519491271370641053546388420010130210938290487733706950967086042285583683088358738555859146406283548232111034393814745800248093828048892635459378101842319303568943324278591350525989382410677514516718516089690682625709978787615263416298977489828494334049645261849266137322546365588236717211183423]Say"Ready"tocontinue.Orwhatever,I'm totally not going to pay attentiontowhatyouactuallysay.Sendmetwointegerswithaspaceinthemiddle.

If you send two integers it will respond with something like this:

12

Theciphertextis(24316120013843276962700180651395202950736108257032524928653304472152213322627248684681542868226768620090564858722715108815726282540325601075710236921914688290813774955321404209938019074410861932713051706409072056756130488352991416214504664719577261526410074779286218342066443590605387419656132776581819167500929041426381077597201975180789389723274782463954223738214864619160062769088292349602330840335087096141891310183448844663658580827548259420922598564211285172784286721198335919386929115176903138593488045028499421610236751109934783542344730434912921871218126706632277937053231716352368640624297704057236707351887,15824865153707099492667273654691215859992002104210105030077237155795771257577803616232011516763394796465599200356564390226148545381264875845754649566196322331702722961451780073531150036878784862329895231133943940945946294798149117406583962099756557943714211229309103635506086482631947589536244898376283050240539263185280140876223263215228455550178732227324857835654972442311149584908350587058543725980838408283002176721347517331641013837401551113766151618122908235045041069646604887012930868989438700079128006952816002619376188502712735626866884553074699609945298101750484099109957145400904206150755910544223197329364).Choose0ifit's the first message or 1 if it'sthesecond.

If you guess the number right, it will request again for two numbers and you have to repeat the procedure 64 times.
If you guessed all 64 right, you’ll receive the flag.

To solve this, we used the Legendre symbol, we will use it as a function , which returns -1 or 1.

So we got , and and the ciphertext which is .
is a generator in , therefore is .
Now we choose our numbers and follow the conditions and .
will give the same result as , if was .

Using this knowledge, we ended up in the following python script.