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 L(x,p), which returns -1 or 1.
So we got p, g and h=gy and the ciphertext (c1,c2) which is (gy,m⋅hy). h is a generator in p, therefore is L(hy,p)==L(gy).
Now we choose our numbers m1 and m2 follow the conditions L(m1,p)==1 and L(m2,p)==−1. L(c1,p)=L(gy,p) will give the same result as L(c2,p)=L(m⋅hy,p)=L(m,p)⋅L(hy,p), if m was m1.
Using this knowledge, we ended up in the following python script.