#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
	def __init__(self):
		self.g = self.a = self.b = 0
		self.e = 65537
		self.factorGen()
		self.product()

	def factorGen(self):
		while True:
			self.g = getPrime(500)
			while not gmpy2.is_prime(2*self.g*self.a+1):
				self.a = random.randint(2**523, 2**524)
			while not gmpy2.is_prime(2*self.g*self.b+1):
				self.b = random.randint(2**523, 2**524)
			self.h = 2*self.g*self.a*self.b+self.a+self.b
			if gmpy2.is_prime(self.h):
				self.N = 2*self.h*self.g+1
				print(len(bin(self.N)))
				return

	def encrypt(self, msg):
		return gmpy2.powmod(msg, self.e, self.N)


	def product(self):
		with open('/flag', 'rb') as f:
			self.flag = f.read()
		self.enc = self.encrypt(self.flag)
		self.show()
		print(f'enc={self.enc}')

	def show(self):
		print(f"N={self.N}")
		print(f"e={self.e}")
		print(f"g={self.g}")


RSAEncryptor()

# sage
from sage.groups.generic import bsgs
from Crypto.Util.number import *

N =
e =
g =
enc =

nbits = 2049
gamma = 500/nbits
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, (2**(cbits-5), 2**(cbits+5)))
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N
    print(p)
    print(q)

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(enc, d, N)  
print(long_to_bytes(int(m)))

from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1] 
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

from sympy import symbols, solve
from Crypto.Util.number import *

def recover_pq(sum_pq, n):
    x = symbols('x')
    eq = x**2 - sum_pq * x + n
    solutions = solve(eq, x)
    return solutions[0], solutions[1]

hints = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n, e = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247

sum_pq = hints

p, q = recover_pq(sum_pq, n)
phi_n = (p - 1) * (q - 1)
d = inverse(e, phi_n)
decrypted_flag1 = long_to_bytes(pow(enc1, int(d), n))
print(decrypted_flag1)

import itertools
from Crypto.Util.number import *

n,e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244
hints = [18167664006612887319059224902765270796893002676833140278828762753019422055112981842474960489363321381703961075777458001649580900014422118323835566872616431879801196022002065870575408411392402196289546586784096, 16949724497872153018185454805056817009306460834363366674503445555601166063612534131218872220623085757598803471712484993846679917940676468400619280027766392891909311628455506176580754986432394780968152799110962, 17047826385266266053284093678595321710571075374778544212380847321745757838236659172906205102740667602435787521984776486971187349204170431714654733175622835939702945991530565925393793706654282009524471957119991, 25276634064427324410040718861523090738559926416024529567298785602258493027431468948039474136925591721164931318119534505838854361600391921633689344957912535216611716210525197658061038020595741600369400188538567, 22620929075309280405649238349357640303875210864208854217420509497788451366132889431240039164552611575528102978024292550959541449720371571757925105918051653777519219003404406299551822163574899163183356787743543, 20448555271367430173134759139565874060609709363893002188062221232670423900235907879442989619050874172750997684986786991784813276571714171675161047891339083833557999542955021257408958367084435326315450518847393, 16581432595661532600201978812720360650490725084571756108685801024225869509874266586101665454995626158761371202939602347462284734479523136008114543823450831433459621095011515966186441038409512845483898182330730, 23279853842002415904374433039119754653403309015190065311714877060259027498282160545851169991611095505190810819508498176947439317796919177899445232931519714386295909988604042659419915482267542524373950892662544, 16542280976863346138933938786694562410542429842169310231909671810291444369775133082891329676227328401108505520149711555594236523078258701726652736438397249153484528439336008442771240980575141952222517324476607, 17054798687400834881313828738161453727952686763495185341649729764826734928113560289710721893874591843482763545781022050238655346441049269145400183941816006501187555169759754496609909352066732267489240733143973, 22115728663051324710538517987151446287208882441569930705944807337542411196476967586630373946539021184108542887796299661200933395031919501574357288914028686562763621166172668808524981253976089963176915686295217, 19324745002425971121820837859939938858204545496254632010818159347041222757835937867307372949986924646040179923481350854019113237172710522847771842257888083088958980783122775860443475680302294211764812636993025, 17269103712436870749511150569030640471982622900104490728908671745662264368118790999669887094371008536628103283985205839448583011077421205589315164079023370873380480423797655480624151812894997816254147210406492, 17365467616785968410717969747207581822018195905573214322728668902230086291926193228235744513285718494565736538060677324971757810325341657627830082292794517994668597521842723473167615388674219621483061095351780, 20823988964903136690545608569993429386847299285019716840662662829134516039366335014168034963190410379384987535117127797097185441870894097973310130525700344822429616024795354496158261293140438037100429185280939, 19068742071797863698141529586788871165176403351706021832743114499444358327620104563127248492878047796963678668578417711317317649158855864613197342671267006688211460724339403654215571839421451060657330746917459, 20089639597210347757891251257684515181178224404350699015820324544431016085980542703447257134320668961280907495580251880177990935443438799776252979843969984270461013888122703933975001704404129130156833542263882, 22344734326131457204500487243249860924828673944521980798994250859372628295695660076289343998351448667548250129358262592043131205967592613289260998148991388190917863322690137458448696392344738292233285437662495, 22688858027824961235755458925538246922604928658660170686458395195714455094516952026243659139809095639584746977271909644938258445835519951859659822660413616465736923822988993362023001205350387354001389518742538, 21286046487289796335501643195437352334100195831127922478044197411293510360710188581314023052580692810484251118253550837525637065385439859631494533102244585493243972819369812352385425700028640641292410326514111, 21542729548465815605357067072323013570796657575603676418485975214641398139843537820643982914302122976789859817102498484496409546012119998359943274203338400776158986205776474024356567247508744784200354385060666, 22319592382753357951626314613193901130171847776829835028715915533809475362288873045184870972146269975570664009921662023590318988850871708674240304838922536028975978222603171333743353770676344328056539379240160, 25195209191944761648246874631038407055240893204894145709996399690807569652160721616011712739214434932639646688187304865397816188999592774874989401871300784534538762135830014255425391132306536883804201055992313, 18257804244956449160916107602212089869395886846990320452133193087611626919926796845263727422042179229606817439442521540784268169177331707314788427670112999551683927934427716554137597798283300120796277229509678, 20293403064916574136692432190836928681820834973375054705153628740577159076332283715581047503287766236543327123639746352358718218140738999496451259789097826888955418315455420948960832865750253988992454128969953, 15967654820584966012628708475666706277218484919923639492431538068059543232562431059752700377242326527417238151501168940191488179144049286512652111172149113549072003881460743035279388672984805823560897688895124, 25144187979876039024245879200325843092774389926620026124061775431569974232758799200333888039013494603721065709195353330350750055309315207499741437181094874894647736904055829877859906318073991986020178158776286, 15736932921640444103019961538951409924080453868073105830403926861058056351553271238438325117113945341892868641345117717666354739204401152657265824568724844930574396801692131746182948347887298330990039956813130, 18831072673439732764722762485733622234889447953507582396819704359771208236721692820362137219509611319088756045211407777880521726782697895768017460064889670066178710804124631128581556314122255564861269062385337, 23800437561684813552661749774840752013501533683948618798811470214669024646396165487093720960221009038817909066075238937189371227098032581450466402462014437421254375846263830927945343485988463525070074913720710, 24402191070622494792723290726249952159888270689258801831518209605331984684494095167423722682814769395395011136124403802097229547003802312444913008194461779426175966774202219703164060353710247619639616444797670, 20215481513831963554421686543560596857659844027486522940060791775984622049024173363533378455076109165728144576719015392033536498353094895564917644840994662704362121549525329105205514332808950206092190939931448, 18384453917605955747212560280232547481041600196031285084598132475801990710125754705645482436436531608696373462641765399622296314590071558616193035939108523357020287896879479452040171765916716377102454266933226, 21890401344164908103930010123434944359446535642544335610455613014563290097498740447164765588532234051104173227090428486681237432196639010849051113283297943367655458678533223039415083212229970648958070799280218, 18379893441293694747570620009241814202936873442370354246029979042247705730610190888710981918183390028386451290137755339890329474403224043675724851314770861939082447728194632548864823398818221526652331319263027, 18715827130228986951360013590464775001019026913384718876134449689773600060962392738619405370033085704046027397895627933844824630723286144367800484157574548819065406118338665931032779491897783504790669824301288, 13588739911708699123450670852772302012518315143187739886523841133752009403411431627334135210166268158490674049617489193734568451811305631563767138879895461211915128972052001136464325219117009268526575020143259, 18506039912943821193373920483847347155611306173368341979655092778147169768984477236224526786441466933360500418090210912574990962709452725122792963919616633389125605160796446674502416801964271004625701238202575, 22167985517547342184812919437069844889650448522260359154086923601900060998572245598167213217022051141570075284051615276464952346620430587694188548679895095556459804921016744713098882496174497693878187665372865, 21507363933875318987283059841465034113263466805329282129011688531718330888226928182985538861888698160675575993935166249701145994333840516459683763957425287811252135418288516497258724668090570720893589001392220, 20250321586608105267884665929443511322540360475552916143405651419034772061789298150974629817817611591100450468070842373341756704300393352252725859102426665187194754280129749402796746118608937061141768301995522, 16104259151024766025645778755951638093681273234415510444173981198301666343334808614748361662637508091511498829253677167171091582942780017355912433497214576425697459483727777273045993446283721290714044600814203, 14560242181138184594433372530956542527312169507277535425067427080573272033961044062335960097446781943943464713852520415535775461964590009720592053626735276833191667395201287169782350381649400286337671320581068, 16239347596615402699390026749150381714807445218767496868569282767673828662340774349530405347667558555781433774705139593469838946201218537641296949822639509296966092138954685186059819628696340121356660166937131, 21344472317634795288252811327141546596291633424850284492351783921599290478005814133560171828086405152298309169077585647189366292823613547973428250604674234857289341613448177246451956695700417432794886277704716, 16053809990112020217624905718566971288375815646771826941011489252522755953750669513046736360397030033178139614200701025268874379439106827823605937814395162011464610496629969260310816473733828751702925621950679, 18917855883623050190154989683327838135081813638430345099892537186954876489710857473326920009412778140451855952622686635694323466827034373114657023892484639238914593012175120540210780102536003758794571846502397, 22690171278715056779052233972642657173540399024770527983659216197108042021644328773010698851143953503599329885607621773816718008861742027388432534850163666629476315340137626681994316866368449548292328156728206, 21087818524872480052313215092436868441694786060866149491087132591272640372512484925209820065536439188250579925233059144898601140234767300574307770064543499923712729705795392684173268461519802573563186764326797, 18439753470094841291394543396785250736332596497190578058698960152415339036714664835925822942784700917586270640813663002161425694392259981974491535370706560550540525510875465091384383255081297963169390777475352, 20105719699015744146039374208926740159952318391171137544887868739518535254000803811729763681262304539724253518465850883904308979964535242371235415049403280585133993732946919550180260852767289669076362115454200, 17251599484976651171587511011045311555402088003441531674726612079301412643514474016351608797610153172169183504289799345382527665445027976807805594288914226822374523878290416047130731166794970645275146679838899, 23027331991437585896233907022469624030630702237261170259290872847355304456043379238362120518409085840638396736666056992747627271193089116095167049248270541979716594671069985183070290375121270398623215587207529, 18158149685496169798299129683009221264185608469410295069411669832919646968324946121757411511373498747604679198739125835462814352243797919744572086307939585501566092705355693015625009717017077302201663788208609, 18276153196656501517216055049560959047263892309902154534799806637704337317207294332426798932144785240877892837491213916540255237702169595754963908689566362060228840286531616263506272071630209104758589482803348, 19830654702835464289082520892939657653574451119898587213320188332842291005863699764597454403874285715252681820027919359194554863299385911740908952649966617784376852963552276558475217168696695867402522508290055, 15349828226638644963106414986240676364822261975534684137183044733508521003843559094515387144949811552173241406076270015291925943459603622043168219534080772937297911323165839870364550841685270125556125756627553, 20923687596111161976478930953796496927811701530608223491138786355445002217973253897724452954815797952200740069102515860924306246841340715110620719064010080520601890251137419840158983682372232110885549732743013, 21095748006022412831703352650023882351218414866517568822818298949510471554885207645049385966827210564667371665855668707424105040599599901165292360321667007968065708796593851653085339928947755081203265281357013, 20136320433636422315432754195821125224777716034031656342233368000257459497472596860252592531939146543685406198978058242599116859263546329669263543660114747385041549283367183026001454445297981439938401547228229, 16496919752274418275948572022974868132658743151124597724312835413857298109100258912203517423633396955060591787380445877361136405137884456764770035346437177846666365911942996404514058688909577420388537479730705, 13788728438272498164727737074811797093818033799836159894472736480763530670013682288670889124484670336660448907074673625466218166413315342420667608074179975422284472184048790475129281850298519112884101776426380, 24852871485448795332267345793743281093931161235481251209948049584749441451621572752080662697610253315331335180611651946374137068256112152253681972406000252076016099200912670370417045090034045383991812756120791, 18663346319122078996775762643035864683521213720864038756854558668694021987970601131985163948257100423991091156649638455828855082098689641225427227191064496066436196910238564311309556938903101074363279783438714, 21400068681031931459396470039651524575262457489792894764406364952394476440804779651233022862527636114968325782197380721095406628084183336358459476006267416033892771932528688312375109463803215034905281657962293, 16044158155847172030103761204572942507195578382208455423846603003318483484698088948486132040995746837257705704187725306831142305215342467016564452582165866039427184607605673304595194959499145031211096109534167, 16518253246325822837502418827700493807621067058438396395472266350036385535241769917459657069911028720968654253735107131282350340465691670072304718987805883113410923109703284511709226857412404454224134480632696, 22032469066601123287586507039704080058983969235246539501189720236880312024198451198788699002335010120658564926677243708367430773661097221076615953342733896063909953602379936312639192315223258556134958059637605, 17474611942177808070315948910226643697957069578572244709354155010512694059987765040746148981545760660371360975936526076852619987733316042847813177383519241505024635332293992920023420060610648140841369822739716, 20097265939024591617239874622716452182434300498447992668997438018575636772416262543204370899462096267444545094719202447520254303983442269757551626971917981420832391886214473318353984504467919530676605744560570, 18170251482705061226968041449812078923477452841162650888922564215790088545936753453513162197661916172215859504545409274440450807677845894292177296835154674774694992388033874349807244020099167681146357128785394, 18084007437523118129421476751918491055914528331902780911288404344016551650138679157754567938593688369062981279371320169939281882307797009116458871503759873023914718337944953764426183937635379280572434676575757, 17001811604221128900675671565539617923973183364469396458234914432162200119518252971721448274846235879320362924206656971472493711107677598961463553324277826426691784458674010708635756004550789902368338633272118, 20217009574515126619724139485885721324936960849401637840860565569588595992087537454744066905387396266844236387315004915383456736142307523960394594650088663019228826091309049211780607761862663242437656610298243, 25534440916970201550118006203706860249111087748000550226680885431006136131742280963090650607632467666558508520152535105122661615376298673454198064361094319699307084117001019115669670029195171047304283891069792, 18871869316294018605789169171879572816494092699556970507058691345095743053290043643010965660058888064972257990750611470141816041727746767146945121588515830427165739580791663951175220638901672353681640741068573, 20173968537913641339915058056878181363456579537994317562789857397928196160113042659777558550242315788417022891612723148843142958668959046890197219991727894451795438138592005695329607326086644956073759609743066, 20601943394990265144021144365970164017319737300436518536503270346147112565303361487668388700369636611354280332841812324530501569200031186584749278453651172121161814207025650519637781007286435981682228528706305, 16397528630087028144645213166977866073543422560337716097539091258081008408890966764995645782823950721804205427713461441138000880478364026137452291234097219085473748076681729365744710225699866258812642458184750, 21373350333568141000876969785296802670776508778278005158047105058430550665787088265486222905402690421155861103648370249249790560185790723042867282734693553039477436055775198037042047438047898227097749354619822, 17767469767416052322357795736899648760868316512079849340028040817353808899589201201338152114229279980849491049574543361275046276135253417685681262008211582060955974064559129311524323185960856955462761555353091, 22148352529815091269441663541923247974004854058764556809596705832663604786920964849725772666340437231503146814919702525852955831173047034475925578238466977606367380212886384487294569287202762127531620290162734, 21663842528026621741414050256553652815372885707031383713657826718944735177083300302064509342116651731671570591336596953911570477161536730982887182434407761036442993588590230296643001682944654490645815177777455, 20219077358929317461660881724990436334639078047412693497584358963241840513748365548465302817975329987854784305275832045889690022909383530837382543579292451297269623663257098458645056099201050578472103957851128, 18255302182526662903763852563401346841065939531070045000414364747445988455597258924280193695407035356029557886165605853810182770534711966292253269625917149411889979307227493949293798772727125069093642134972336, 24926064145128749429079117171467042019887257504329103038171762786986349157515552927216574990423327013202735544601170247730647598931030432792167867343343213411600516855009788294067588153504026267213013591793027, 22369607314724468760253123915374991621544992437057652340350735935680183705467064876346663859696919167243522648029531700630202188671406298533187087292461774927340821192866797400987231509211718089237481902671100, 16994227117141934754898145294760231694287000959561775153135582047697469327393472840046006353260694322888486978811557952926229613247229990658445756595259401269267528233642142950389040647504583683489067768144570, 21758885458682118428357134100118546351270408335845311063139309657532131159530485845186953650675925931634290182806173575543561250369768935902929861898597396621656214490429009706989779345367262758413050071213624, 20156282616031755826700336845313823798147854495428660743884481573484471099887576514309769978525225369254700468742981099548840277532978306665910844928986235042420698332201264764734685502001234369189521332392642, 23291765247744127414491614915358658114280269483384022733002965612273627987872443453777028006606037159079637857473229879140366385523633075816362547967658930666106914269093225208138749470566410361196451552322613, 19807792217079652175713365065361659318870738952921195173619551645956745050506271953949139230097128034416815169649874760890189515620232505703162831090225715453502422905418824316957257395992121750661389503495033, 22074209373194902539215367382758486068533032275912313703269990627206774967653336496619231924013216321042649461711292555464574124714934511202231319963361912937842068483700298097209400217869036338644607607557860, 19678336511265998427322297909733474384702243426420286924671444552444079816707773485084891630780465895504253899943221044355971296122774264925882685351095921532685536165514189427245840338009573352081361238596378, 24746314790210393213546150322117518542380438001687269872679602687597595933350510598742749840102841364627647151669428936678130556027300886850086220074563664367409218038338623691372433831784916816798993162471163, 19346137206512895254202370018555139713690272833895195472766704715282164091959131850520571672509601848193468792313437642997923790118115476212663296111963644011010744006086847599108492279986468255445160241848708, 22739514514055088545643169404630736699361136323546717268615404574809011342622362833245601099992039789664042350284789853188040159950619203242924511038681127008964592137006103547262538912024671048254652547084347, 21491512279698208400974501713300096639215882495977078132548631606796810881149011161903684894826752520167909538856354238104288201344211604223297924253960199754326239113862002469224042442018978623149685130901455, 19381008151938129775129563507607725859173925946797075261437001349051037306091047611533900186593946739906685481456985573476863123716331923469386565432105662324849798182175616351721533048174745501978394238803081, 19965143096260141101824772370858657624912960190922708879345774507598595008331705725441057080530773097285721556537121282837594544143441953208783728710383586054502176671726097169651121269564738513585870857829805]

V = hints
k = 2^(512+100)
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]

for s, t in itertools.product(range(100+1), repeat=2):
    T = s*B[0] + t*B[1]
    a1, a2, a3 = T[:3]
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    if 1 < kq < n:
        print('find!')
        print(kq)
        break

p = kq
q = n//p

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c, d, n)  
print(long_to_bytes(int(m)))

from Crypto.Util.number import *

p = 8112940945910485817171807897687451701452029959677470272197529542411816926233172848066074195817612280582244564398252967013953964546888998662975298338523549
q = 9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231
e = 65537
c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755

n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c, d, n)  
print(long_to_bytes(m))

import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
    A = random.randrange(0, 2**128)
    wa = w(A)
    B = 0
    try : exec("global A; global B;" + command)
    except : exit()
    if A == wa:
        success += 1

if success == 100:
    print(flag)

B=A>>1;B=B&113427455640312821154458202477256070485;A=A-B;B=A&68056473384187692692674921486353642291;A=A>>2;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;B=A+B;A=B&20016609818878733144904388672456953615;B=A>>8;B=A+B;A=B&1324055902416102970674609367438786815;B=A>>16;B=A+B;A=B&5192217631581220737344928932233215;B=A>>32;A=A+B;B=A>>64;A=A+B;A=A&255;

from Crypto.Util.number import getPrime,bytes_to_long
from secret import secret,flag
import random
import time
import os
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 300
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

random.seed(secret + str(int(time.time())).encode())

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getPrime(128)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)  

    def get_public_key(self):
        return (self.n, self.e)
    
    def get_private_key(self, blind_bit=None, unknown_bit=None):
        if blind_bit is not None and unknown_bit is not None:
            blind = getPrime(blind_bit)
            d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
            return (d_, blind)
        else:
            return (self.d, 0)
    
    def encrypt(self, m):
        if type(m) == bytes:
            m = bytes_to_long(m)
        elif type(m) == str:
            m = bytes_to_long(m.encode())
        return pow(m, self.e, self.n)
    
    def game(self,m0,m1,b):   
        return self.encrypt([m0,m1][b]) 


rsa = RSA()
token = os.urandom(66) 

print( "[+] Welcome to the game!")
print(f"[+] rsa public key: {rsa.get_public_key()}")

coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

blind_bit = 40
unknown_bit = 365

d_,blind = rsa.get_private_key(blind_bit, unknown_bit)

print( "[+] Now, you have permission to access the privkey!")
print(f"[+] privkey is: ({d_},{blind}).")
print(f"[+] encrypt token is: {rsa.encrypt(bytes_to_long(token))}")

guess_token = bytes.fromhex(input("[-] guess token:"))
if guess_token == token:
    print("[+] correct token, here is your flag:",flag)
else:
    print("[-] wrong token")

coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

random.seed(secret + str(int(time.time())).encode())

from hashlib import sha256
from pwn import *
context.log_level = 'debug'
import re
import gmpy2
import libnum

a = remote('47.94.237.181',30782)
b = remote('47.94.237.181',30782)

b.recvuntil(b'rsa public key: ')
pubkey = eval(b.recvline())

for i in range(100):
    a.recvuntil(b'[-] b:')
    b.recvuntil(b'[-] b:')
    a.sendline(b'1')
    if b'correct' in a.recvline():
        b.sendline(b'1')
    else:
        b.sendline(b'0')

b.recvuntil(b'is: ')
privkey = eval(b.recvline()[:-2])
b.recvuntil(b'is: ')
enc = eval(b.recvline())

b.recvuntil(b'guess token:')

print('n = ',pubkey[0])
print('e = ',pubkey[1])
print('enc = ',enc)
print('d_ = ',privkey[0])
print('blind = ',privkey[1])

b.sendline(input().encode())
b.recv()
b.recv()
b.recv()

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getPrime(128)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)  

    def get_public_key(self):
        return (self.n, self.e)
    
    def get_private_key(self, blind_bit=None, unknown_bit=None):
        if blind_bit is not None and unknown_bit is not None:
            blind = getPrime(blind_bit)
            d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
            return (d_, blind)
        else:
            return (self.d, 0)

dh = (d_ >> unknown_bit) // blind
dl = d_ % blind

dh = d_ >> (unknown_bit + blind_bit) << (unknown_bit + blind_bit)
dl = d_ % blind

# step1 calculate k
k = (e*dh) // n + 1
# step2 dh
# step3 recover the MSBs of p
S = n + 1 - ((e*dh - 1) // k)
D = gmpy2.iroot(abs(S**2 - 4*n),2)[0]
ph = int((S + D) // 2) >> (512 - 105) << (512 - 105)

# step4 calculate p+q % blind
s = inverse(k,blind) * (1 + k * (n+1) - e*dl) % blind
R.<x> = PolynomialRing(Zmod(blind))
f = x^2 - s*x + n
res = f.roots()
may_p_mod_blind = [int(res[0][0]),int(res[1][0])]

# step5 calculate p+q % e
k_inv = inverse(k,e)
s = (n + 1 + k_inv) % e

# step6 factor n
R.<x> = PolynomialRing(Zmod(e))
f = x^2 - s*x + n
res = f.roots()
may_p_mod_e = [int(res[0][0]),int(res[1][0])]
moduls = int(blind) * int(e)

for p_mod_e in may_p_mod_e:
    for p_mod_blind in may_p_mod_blind:
        pl = crt([p_mod_blind,p_mod_e],[blind,e])
        th = (ph - pl) // moduls
        PR.<x> = PolynomialRing(Zmod(n))
        f = (th + x) * moduls + pl
        for i in trange(240, 246):
            roots = f.monic().small_roots(X=2^i,beta=0.49,epsilon=0.02)
            if roots != []:
                p = int(f(roots[0]))
                if n % p == 0:
                    print(p)
                    q = n // p
                    d = inverse(e,(p-1)*(q-1))
                    m = pow(c,d,n)
                    msg = long_to_bytes(m)
                    print(msg.hex())
                    break

from Crypto.Util.number import *
from tqdm import *


################################################################################# data
n, e = 85326799303014496026064371730108772674311332235197622668632563161991602151711567135121280447576711444698674128128361298108919951648223986067215747231280671858955299505770967232491254103263536714363392698361887554304255293991522369123049450389169430042203506125207632731477059899911948136482137033584148217327, 254105853966712863308295955275449077351
d_, blind = 21378651607895524021279554589638483737491146093477974150650211288463988209605132503571807152155799637952833578907915487652394101057156932695702372344185513500134378667094923442647974423915643213700386663283702204046537471425141802799603607927835879677131664511051343930330150649244588933823965535065854996174,1033378191583
c = 53742732129028328063112055299975805421399396945032126712022723372351554830940247890238890674346304685771599765645061449905866414886468887177488826724343823941484173305683401484367061591100780027467534437239106132736115748345075082986831034406103970493456683245813494600511020286115561513979129441895596164513


################################################################################# get k,dh,dl
blind_bit = 40
unknown_bit = 365
k = (e*d_ - 1) // n + 1
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind


################################################################################# LLL
M = e*(2^unknown_bit*blind*dh+dl) - k*(n+1) - 1
K = 2^(513-unknown_bit)
L = matrix(ZZ,[
    [K,0,e*blind],
    [0,1,k],
    [0,0,M]
])
L[:,-1:] *= M
L = L.LLL()
L[:,:1] /= K
pqh = L[1][1] // (e*blind) * (e*blind)
pql = L[1][1] % (e*blind)


################################################################################# copper
############################################### get ph
PR.<x> = PolynomialRing(RealField(1000))
f = x*(pqh-x) - n 
ph = int(f.roots()[0][0]) // (e*blind) * (e*blind)
############################################### get pl
R.<x> = PolynomialRing(Zmod(e))
fe = x*(pql-x) - n
rese = fe.roots()

R.<x> = PolynomialRing(Zmod(blind))
fb = x*(pql-x) - n
resb = fb.roots()

for i in rese:
    for j in tqdm(resb):
        nlist = [e,blind]
        clist = [int(i[0]),int(j[0])]
        pl = int(crt(clist,nlist))

        ############################################### get p
        PR.<x> = PolynomialRing(Zmod(n))
        f = ph + e*blind*x + pl
        f = f.monic()
        res = f.small_roots(X=2^(512-105-167+3), beta=0.499, epsilon=0.02)
        if(res != []):
            p = int(ph + e*blind*res[0] + pl)
            q = n // p
            phi = (p - 1) * (q - 1)
            d = inverse(e, phi)
            print(long_to_bytes(int(pow(c, d, n))).hex())
            assert n % p == 0
            break

import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality() #取得模数



    f /= f.coefficients().pop(0) #最高次项系数化为0，coefficients是多项式的降次幂排列系数
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())

    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i #收集基多项式

        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    # print(G)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n=72002775317113688540285467671785030264214376134969177894386312150568554267864510238114124791103314081013890542077634384796996108441641259367491852737439283875815904913961193178967651247603461327324881612452957271602668892013627196968069470178106537853725618118244679187226724369629568003877232335388143025421

d_=51922392037054965957994618792545191283979879052769311017420397943569729387241291615967860347543490837943194867963559620326233806950203605430695561698099370379711352056567716185665995739452373593820321078614603310911807288759647808038104413677259085086482871151447742963730089791217336473149711277887953445987
blind=1022253789881
e = 315877627939914682167275979171048924911

k = (d_>>365<<365)*e//n+1
print(k)
d0 = 305686942495898399049381993768424633072311512220602994167415931983633446942350*blind+d_
print((e*d0-1)//k)


PR.<t,y> = PolynomialRing(Zmod(n))
dh = d_>>365
dl = d_%blind
dd= d_+t*blind

f = e * dd-1+k*(y+)-k
for i in range(3,8):
    for j in range(3,8)
    res = small_roots(f,[2^365,2^513],m=j,d=i)
    print(hex(res[0]))

from Crypto.Util.number import *

d_ = 35543944120330116255735518733645489603573091842911907294542145633663234716786783315679867957932690565524695409353902407238230794612110053347977693435578424147992257282456254035309964691562747903421859204068006443325340570360806343392553225754316397967193324090858612423946304818214259628194263287347469670466
blind = 757679866771
enc = 19853765442007775876887241200871445335873698995336480258510762108568698654347239404466018587258683380716257697287810506470119048708570691810417483606733656269976330892819998306493425545055270250642091136316635340047265544394031708296941054865358649424861323618308881521370980854619709646182020458999169008788
n = 58273981186201544662497686603513109679871732872710290794332222899533972577334318295883065181401468548089995964427612249110216775058749030840477167325648156157792476414639983292885697153441817705191116555945635579175171648010932408400320937775056359336717949119846917473695481683831886468389055754689273767107
e = 311238058411019550438393569886672869203

blind_bit = 40
unknown_bit = 365

k = (d_>>365<<365)*e//n+1

PR.<y> = PolynomialRing(GF(e))

f = e * d_-1-k+k*y-k*n
f = f.monic()
ans1 = (f.roots())[0][0]
g = y*ans1-y^2-n
ans1 = (g.roots())

PR.<y> = PolynomialRing(GF(blind))

f = e * d_-1-k+k*y-k*n
f = f.monic()
ans2 = (f.roots())[0][0]
g = y*ans2-y^2-n
ans2 = (g.roots())

pl = []
for i in ans1:
    for j in ans2:
        pl.append(crt([int(i[0]),int(j[0])],[e,blind]))

print(pl)

sh = 43455964700998276860477800987643389941075455294569061
sh = sh*2^170*e*blind

kbit = 242
R.<x> = PolynomialRing(RealField(1000))
f = x*sh-x^2-n


print(f.roots())
for i in (f.roots()):
    ph = (int(i[0])//(2^kbit*(e*blind)))  
    for j in pl:
        R.<x> = PolynomialRing(Zmod(n))
        f = ph*2^kbit*e*blind+x*e*blind+int(j)
        f = f.monic()
        ans = (f.small_roots(X = 2^kbit,beta = 0.4,epsilon = 0.02))
        if ans:
            p =  ph*2^kbit*e*blind+int(ans[0])*e*blind+int(j)
            q = n//p
            phi = (p-1)*(q-1)
            d = inverse_mod(e,phi)
            m = pow(enc,d,n)
            print(hex(m)[2:])

import tenseal.sealapi as sealapi
from random import randint
from signal import alarm
import base64

g = 5
poly_modulus_degree = 8192
plain_modulus = 163841

def gen_keys():
	parms = sealapi.EncryptionParameters(sealapi.SCHEME_TYPE.BFV)
	parms.set_poly_modulus_degree(poly_modulus_degree)
	parms.set_plain_modulus(plain_modulus)
	coeff = sealapi.CoeffModulus.BFVDefault(poly_modulus_degree, sealapi.SEC_LEVEL_TYPE.TC128)
	parms.set_coeff_modulus(coeff)
	
	ctx = sealapi.SEALContext(parms, True, sealapi.SEC_LEVEL_TYPE.TC128)
	
	keygen = sealapi.KeyGenerator(ctx)
	public_key = sealapi.PublicKey()
	keygen.create_public_key(public_key)
	secret_key = keygen.secret_key()
	
	parms.save("app/parms")
	public_key.save("app/public_key")
	secret_key.save("app/secret_key")

def load():
	parms = sealapi.EncryptionParameters(sealapi.SCHEME_TYPE.BFV)
	parms.load("app/parms")

	ctx = sealapi.SEALContext(parms, True, sealapi.SEC_LEVEL_TYPE.TC128)

	public_key = sealapi.PublicKey()
	public_key.load(ctx, "app/public_key")

	secret_key = sealapi.SecretKey()
	secret_key.load(ctx, "app/secret_key")
	return ctx, public_key, secret_key

def gen_galois_keys(ctx, secret_key, elt):
	keygen = sealapi.KeyGenerator(ctx, secret_key)
	galois_keys = sealapi.GaloisKeys()
	keygen.create_galois_keys(elt, galois_keys)
	galois_keys.save("app/galois_key")
	return galois_keys

def gen_polynomial(a):
	return '1x^' + str(a)

def f(a, b):
    return (pow(g, a-b, plain_modulus) + pow(g, b-a, plain_modulus) + pow(g, 3*a-b, plain_modulus) + pow(g, a-3*b, plain_modulus))%plain_modulus

def check_result(ctx, decryptor, a, b, pos):
	plaintext = sealapi.Plaintext()
	ciphertext = sealapi.Ciphertext(ctx)
	ciphertext.load(ctx, "app/computation")
	decryptor.decrypt(ciphertext, plaintext)
	assert plaintext[pos] == f(a, b)

def send(filepath):
	f = open(filepath, "rb")
	data = base64.b64encode(f.read()).decode()
	f.close()
	print(data)

def recv(filepath):
	try:
		data = base64.b64decode(input())
	except:
		print("Invalid Base64!")
		exit(0)

	f = open(filepath, "wb")
	f.write(data)
	f.close()

def main():
	ctx, public_key, secret_key = load()
	encryptor = sealapi.Encryptor(ctx, public_key)
	decryptor = sealapi.Decryptor(ctx, secret_key)
	
	a, b = [randint(1, poly_modulus_degree - 1) for _ in range(2)]
	poly_a, poly_b = gen_polynomial(a), gen_polynomial(b)

	plaintext_a, plaintext_b = sealapi.Plaintext(poly_a), sealapi.Plaintext(poly_b)
	ciphertext_a, ciphertext_b = [sealapi.Ciphertext() for _ in range(2)]
	encryptor.encrypt(plaintext_a, ciphertext_a)
	encryptor.encrypt(plaintext_b, ciphertext_b)
	ciphertext_a.save("app/ciphertext_a")
	ciphertext_b.save("app/ciphertext_b")
	galois_used = 0

	alarm(300)

	while True:
		try:
			choice = int(input("Give Me Your Choice:"))
		except:
			print("Invalid choice!")
			exit(0)

		if choice == 0:
			print("Here Is Ciphertext_a:")
			send("app/ciphertext_a")
			print("Here Is Ciphertext_b:")
			send("app/ciphertext_b")

		elif choice == 1:
			if galois_used == 1:
				print("No More!")
				exit(0)
			try:
				elt = int(input("Please give me your choice:"))
			except:
				print("Invalid input!")
				exit(0)

			try:
				galois_key = gen_galois_keys(ctx, secret_key, [elt])
			except:
				print("Invalid galois!")
				exit(0)

			print("Here is your galois key:")
			send("app/galois_key")
			galois_used = 1

		elif choice == 2:
			try:
				pos = int(input("Give Me Your Position:"))
				assert pos in range(poly_modulus_degree)
			except:
				print("Invalid position!")
				exit(0)

			print("Give Me Your Computation")
			recv("app/computation")
	
			try:
				check_result(ctx, decryptor, a, b, pos)
			except:
				print("Incorret Answer!")
				exit(0)

			flag = open("app/flag", "rb")
			print(flag.read())
			flag.close()

		else:
			print("Invalid choice!")
			break

# gen_keys()
main()

from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import * 
from base64 import b64encode
from random import * 
from secret import flag
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 66
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def qary_trans_to_int(x, q):
    return sum([int(x[i]) * q**i for i in range(len(x))])

def encode(f, q):
    try:
        return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
    except:
        return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
    while True: 
        f = R.random_element(degree=n) 
        while f.degree() != n:
            f = R.random_element(degree=n) 
        if f.is_irreducible():
            return f

def generate_sparse_irreducible_polynomial(R, n): 
    x = R.gen()
    while True:
        g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
        if (x**n + g + 1).is_irreducible():
            return x**n + g + 1

def random_polynomial(R, n, beta):  
    return sum(randrange(-beta, beta) * R.gen()**i for i in range(randint(0, n))) + R.gen()**n  

q = 333337
n = 128
beta = 333 
chance = 111
polyns = beta//chance
bound  = 106
R = PolynomialRing(GF(q),'x')

F = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q**n, name = 'a', modulus = generate_sparse_irreducible_polynomial(R,n).monic())
k2 = GF(q**n, name = 'b', modulus = F)

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 

print("F:", encode(F,q).decode())

win_count = 0
for _ in range(chance):
    opt = randint(0, 1)
    if opt:
        As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
    else:
        As = [k2.random_element() for i in range(polyns)]
    
    for i in range(polyns):
        print(f"As[{i}]: {encode(As[i],q).decode()}")

    opt_guess = input("Guess the option[0/1]: ")
    if int(opt_guess) != opt:
        print("Wrong guess!")
    else:
        win_count += 1
        print("Correct guess!")

if win_count >= bound:
    print("You are so smart! Here is your flag:")
    print(flag)
else:
    print("No flag for you!")

from flag import M, q, a, b, select
import hashlib
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
import sys
import ecdsa
from Crypto.Util.Padding import pad, unpad
from ecdsa.ellipticcurve import CurveFp,Point
from math import ceil
import os
import random
import string

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'
assert len(flag) == 136

BANNER = '''
 GGGGG   OOOOO   DDDDD   DDDDD    GGGGG    AAA    MM    MM EEEEEEE 
GG      OO   OO  DD   D  DD   D  GG       AAAAA   MMM  MMM EE      
GG  GGG OO   OO  DD   D  DD   D  GG  GGG  A   A   MM MM MM EEEEE   
GG   GG OO   OO  DD   D  DD   D  GG   GG  AAAAA   MM    MM EE      
GGGGGGG  OOOOO   DDDDD   DDDDD   GGGGGGG  A   A   MM    MM EEEEEEE 
 '''

NNN = []
def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.buffer.readline()

def Rng(k):
    ran = random.getrandbits(k)
    NNN.append(ran)
    return ran


def ADD(num):
    NUM = 0
    for i in range(num):
        NUM += Rng(32)
    return NUM

def secure_choice(sequence):
    if not sequence:
        return None
    randbelow = 0
    for i, x in enumerate(sequence):
        randbelow += 1
        if os.urandom(1)[0] < (1 << 8) * randbelow // len(sequence):
            return x

def xDBLADD(P, Q, PQ, q, a, b):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P, q, a, b)
        if k >> i & 1:
            R, Q = Q, R
    return Q

def shout(x, d, q, a, b):
    P = (x,1)
    Q = xMUL(P, d, q, a, b)
    return Q[0] * pow(Q[1], -1, q) % q

def generate_random_string(length):
    characters = string.ascii_letters + string.digits
    random_string = ''.join(secure_choice(characters) for i in range(length))
    return random_string

class ECCDu():
    def __init__(self,curve,G):
        self.state = getRandomNBitInteger(512)
        self.Curve = curve
        self.g = G

        self.num = Rng(32)
        d = 65537
        self.Q = self.num*self.g
        self.P = d * self.Q

    def ingetkey(self):
        t = int((self.state * self.Q).x())
        self.updade()
        return t%(2**250)

    def updade(self):
        self.state = int((self.state * self.P).x())

    def Random_key(self, n:int):
        out = 0
        number = ceil(n/250)
        for i in range(number):
            out = (out<<250) + self.ingetkey()
        return out % (2**n)

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
    _hexdigest = sha256(proof.encode()).hexdigest()
    pr(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
    pr('Give me XXXX: ')
    x = sc().rstrip(b'\n')
    if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
        return False
    return True

def main():
    pr(BANNER)
    pr('WELCOME TO THIS SIMPLE GAME!!!')
    ASSERT = proof_of_work()
    if not ASSERT:
        die("Not right proof of work")

    pr('Now we will start our formal GAME!!!')
    pr('===== First 1💪: =====')
    pr('Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()')
    p1 = int(sc())
    if not 250<=p1.bit_length():
        die('Wrong length!')
    curve = CurveFp(p1, 12, 17,1)
    pr(curve)
    pr('Please Enter a random_point G:')
    G_t = sc().split(b' ')
    Gx,Gy = int(G_t[0]),int(G_t[1])
    if not curve.contains_point(Gx,Gy):
        die('This point is outside the curve')
    G = Point(curve,Gx,Gy)

    for i in range(500):
        ECDU = ECCDu(curve,G)
        m  = 'My secret is a random saying of phrase,As below :' + generate_random_string(119)
        Number = ECDU.Random_key(1344)
        c = Number^bytes_to_long(m.encode())
        pr(f'c = {c}')
        pr(f'P = {int(ECDU.P.x()), int(ECDU.P.y())}')
        pr(f'Q = {int(ECDU.Q.x()), int(ECDU.Q.y())}')

        pr('Enter m:')
        m_en = sc().rstrip(b'\n')
        if m_en != m.encode():
            die('This is not the right m,Please try again')
        else:
            pr('Right m!!!')
    pr('Bingo!')
    new_state,new_state1 = ADD(136),ADD(50)
    
    random.seed(new_state)

    pr('===== Second 2💪: =====')
    curve1 = CurveFp(q,a,b,1)
    pr(f'{int(curve1.p()),int(curve1.a()),int(curve1.b())}')

    pr("Enter a number that does not exceed 1500")
    number = int(sc())

    pr(f'You only have {number} chances to try')
    success = 0
    for i in range(number):
        Gx = secure_choice(select)
        R = Rng(25)
        pr('Gx = ',Gx)
        pr('Px = ',shout(Gx, R, q, a, b))
        R_n = int(sc().rstrip(b'\n'))
        if R_n != R:
            pr(f'Wrong number!!!,Here is your right number {R}')
        else:
            pr('GGood!')
            success += 1

    if int(success)/int(number) <= 0.262:
        die('Please Try more...')

    random.seed(new_state)
    iv_num = ADD(2000)

    iv = hashlib.sha256(str(iv_num).encode()).digest()[:16]
    key = hashlib.sha256(str(new_state1).encode()).digest()[:16]
    Aes = AES.new(key,AES.MODE_CBC, iv)
    C = Aes.encrypt(pad(flag,16))

    key_n, iv_n = int(sc()), int(sc())
    iv1 = hashlib.sha256(str(iv_n).encode()).digest()[:16]
    key1 = hashlib.sha256(str(key_n).encode()).digest()[:16]
    Aes_verify = AES.new(key1,AES.MODE_CBC, iv1)
    C_verify = unpad(Aes_verify.decrypt(C),16)

    if C_verify == flag:
        pr('Congratulations🎇🎇🎇!!!!')
        pr('Here is your flag😊：', M)
    else:
        pr('Maybe you could get the right flag!')

if __name__ == '__main__':
    main()