20210821-祥云杯-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 102k Reading time ≈ 1:33

 

Guess

很多是非预期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
from Crypto.Util.number import (
    bytes_to_long,
    getPrime,
    long_to_bytes,
    getRandomNBitInteger,
)
import random
import hashlib
from math import gcd
import socketserver


KEYSIZE = 512
WELCOME = "welcome to my funny challenge !!! Can you guess right 32 times in a row? "
String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


def invert(a,p):
    x, y, q = exgcd(a,p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p

def lcm(a,b):
    return a*b // gcd(a,b)

def proof_of_work():
    STR = "".join([String[random.randint(0, len(String) - 1)] for _ in range(16)])
    HASH = hashlib.sha256(STR.encode()).hexdigest()
    return STR[:4], STR[4:], HASH


def keygen():
    # part 1
    p, q = getPrime(KEYSIZE), getPrime(KEYSIZE)
    n = p * q
    g = n + 1
    LAMBDA = lcm(p - 1, q - 1)

    # part 2
    _key = open("key", "r").read()
    key = []
    for i in _key.split("\n"):
        for j in i[1:-1].split(" "):
            if int(j) not in key:
                key.append(int(j))
    assert len(key) == 80
    assert key[0] == 119 and key[1] ==  241 and key[2] ==  718 and key[3] == 647
    return n, g, LAMBDA, key


def enc(n, g, m):
    while 1:
        r = random.randint(2, n - 1)
        if gcd(r, n) == 1:
            break
    c = (pow(g, m, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)
    return c


def dec(n, g, LAMBDA, c):
    L1 = (pow(c, LAMBDA, n ** 2) - 1) // n
    L2 = (pow(g, LAMBDA, n ** 2) - 1) // n
    m = (invert(L2, n) * L1) % n
    return m


class server(socketserver.BaseRequestHandler):
    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg, bytes):
            msg += b"\n"
        else:
            msg += "\n"
            msg = msg.encode()
        self.request.sendall(msg)

    def handle(self):
        print("Service start.")
        START, END, HASH = proof_of_work()
        self._send("SHA-256(?+{}) == {}".format(END, HASH))
        RCV = self._recv().decode()
        if RCV != START:
            return
        flag = open("flag", "rb").read()
        self._send(WELCOME)
        # step 1. KeyGen
        for _ in range(32):
            self._send("round " + str(_+1))
            n, g, LAM, KEY = keygen()
            self._send("Step 1 - KeyGen. This is my public key.")
            self._send("n = " + str(n))
            self._send("g = " + str(g))
            # step 2. Phase 1
            self._send(
                "Step 2 - Phase 1. Now, you can give me one ciphertexts,I will return the corresponding plaintext."
            )

            self._send("Please give me one decimal ciphertext.")
            cipher = int(self._recv().decode())
            plaintext = str(dec(n, g, LAM, cipher))
            self._send("This is the corresponding plaintext.")
            self._send(plaintext)

            # step 3. challenge
            self._send(
                "Step 3 - Challenge. Now, you must give me two decimal plaintexts(m0,m1), I will encry them and return a ciphertext randomly"
            )
            self._send("Give me m0.")
            plaintext1 = int(self._recv().decode())
            self._send("Give me m1.")
            plaintext2 = int(self._recv().decode())

            if (
                plaintext1 <= 2
                or plaintext2 <= 2
                or len(bin(plaintext1)) != len(bin(plaintext2))
            ):
                return
            R = 2 * random.randint(0, 39)
            I = random.randint(0, 1)
            cipher1 = enc(n, g, plaintext1 * plaintext2 * KEY[R])
            cipher2 = enc(n, g, plaintext1 * plaintext2 * KEY[R + 1])
            self._send("This is a ciphertext.")
            self._send(str([cipher1, cipher2][I]))

            # step 4. Phase 2

            self._send(
                "Step 4 - Phase 2. Now, you can give me some ciphertexts,I will return the corresponding plaintext.But you can not give me the ciphertext that I give you in step 3."
            )
            self._send("Please give me one decimal ciphertext ")
            cipher = int(self._recv().decode())
            plaintext = str(dec(n, g, LAM, cipher))
            if int(plaintext) == plaintext1 * plaintext2 * KEY[R] or int(plaintext) == plaintext1 * plaintext2 * KEY[R+1]:
                return
            self._send("This is the corresponding plaintext.")
            self._send(plaintext)

            # step.5 Guess
            self._send(
                "Step 5 - Guess. You must tell me which ciphertext was I give you in step 3, 0 or 1(m0 -> c0 , m1 -> c1)?"
            )
            Guess = int(self._recv().decode())

            if Guess == I:
                self._send("Good! You are right")
            else:
                self._send("Sorry!")
                return
        self._send(flag)

class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", 10001
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

key.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getRandomNBitInteger

while 1:
    A = []
    key = random_matrix(ZZ, 20, 4, x = 100, y =1000)
    for i in range(20):
        for j in range(4):
            if key[i,j] not in A:   
                A.append(key[i,j])
    if len(A) == 80:
        break
hint = Matrix(key * vector([getRandomNBitInteger(1024) for _ in range(4)]) for _ in range(12))
open('key','w').write(str(key))
open('hint','w').write(str(hint))

hint

1
2
3
4
5
6
7
8
9
10
11
12
[269865700520122549144762599745168447135899292447636617756605602545212728167797447445787398106779613741477733230173614340453529478006749280203791219240495545320784253247776438152444000193996715061172344898960798274898870276035746116096626771403981985377907323596813517124099024451197742946526103390328807831246256 351825797459362105605308649037214670594688383340169438930434420259269928275998050547973935801446674821508093953928259345972518243250576886209287947085399150853100589302713875591726622523078239591200598436879752732176246887916248939358959982281252327937943016323841545720179709080112518678442049362350981509034718 263649494857153084116592322640026892708704523757635879704627428861744239824087544706911427923497181418081141799670872495368713195091290104184732226016053955456080069924363050718931449355663612295983210728462521014504883613920516962136372253488247300322354664463901602570541318156197056622985692829393446426824638 453400473599186415430546643705275038528777172686002821040599810743439930425207458033941717472852507386860793929840595207225134962986513734506356764693655438618941180687198445634254053696966577360482969943538482461972582638716434085445938134971492342779462032414137699485112547903822163588315191244265946324218228 221827206659930588955100802225668305862545149941640820857015107405314701820405616518433413575662470655465592803570411353938784340140188287733921352831214120360424367473260917811334848500233701311695438235451684226463170984345521338680563403806364662014170986174411732503648583380588103055128943038500134530643916 262203710827134666754393441371926810666786719624203864995763104952378827035382567436334257544099220873788181813028566666315029478997429146874858602787070177245600709015255267085423481719645325028750498589844959751577586557620102816409584289798347398835894955523264261758402589145048117452982723970755642721185948 449549947180605498384084224904383747663117854129634140960197279513891658001908553899154409208608867208695858453347485738326065752599578853421177093646899183717259826566392731977061092066943083219101516409628761436417329565252863717622046112713719560452994438641997826306366514591051557604666293190256180831457338 427882301208025139610114439882502441914598510240693844044902667415035988021658089285061603431657599603331045335448467272333422417626837392018638001129889364932929941669822436427404546395551452209585894226820734770968204014611476942151983657836762789688274393777314450201198374683092768582274185754609711412304708 206110709892941001547312247977630809641839341262123534620411119329846379553052343003462513763026898611550676850103678046155244343919504874675861711356256906122323272209951451243624891037181757295933079679771758786258823164385868611152404813858000740881052355543339622168479080269444970004478675521293416826708518 376172049695479754397279304655900327678015926783104795566699104261135819399512659621342636669298191140461316867639169744791504345311783942430174703887150776382877123936598986072421903671214609751973940119880560010023509512099294872489902196710299820192154670761462699775769831592820505043876853866377139051584700 354989144495191036439184720296945551786270296981167948019894874956969763278354891643393993638515549874937620037229446883785428867336828993393766325205264827014803398207234817979275257572341689686447010646631351076260136309756747006523828716693825921688154934832911308097472833298941167446737019496978821483004142 247657418221571455680808477138957290356931207729656804527032245580960429841816418251851497488948400261671314674513219816337747752077679968835580384381624054897709324089163678294189901105831869992119099572932762170016838924353956530516871378196167792087986296536436978303095420850688527841398649861755287315252914 267323214115576739778291260842843721623810532694699738318490243647729313782577235628052607303271826513284836885625483822163201361517891012567791817503099871180988597553316105403148790626072424557099203065132199859082058328832860860922184801132168393385984454558438841623269013769064186695669122926428112192958058 380213264649117070874301733758703992957052936843733186492527715942930662173593880870634301175054838023249481317633718679161000064110300930539209764959721575720322049712443403460593162873330727228662863503060615472077497723046998024646756953852274720572607225890476747502455930116669002121964715413052946067842934 299711354673898453867309253202762657296007144693008209662952150647212243688991887703988087318065032988637761345182760379040409182402949915825642302147237357969028446441002244872828954397547768452078685431997252342287035745022966033862847782615826742413561561692110959439029229515697207807688051683325604252733440 365249518697738703288761077464962564211784565489625880111214981001160495801883728584481549266513708874054054791287952319568149514368408201453178732248585813844809011050888061672886805741661833747721896023077257558372204817368398292194245959048942083958342665661675547822068884852334483336260109462386159088016564 234545469963164507706928881332558698102265602045874001492102111685872459757456367592469441102854212705510654825387325257074993658404998100908565444353109631283461873240676108320629040289352814544349197599373184745156814420454658805665114789039742029196643533194690810954176812644128288344876173839305663050924382 403528775485460422299177022688931715589694738265629775672770507924611837945109216220772816017023088114143940075372156298028685445638442326378577113339902407365411497947122572348948969051001772973442806880840187883877046852394584867407634101961472289147829591393511113697557028915654508582063486155060434533238994 257705800389350838171655930137607990615821847049495140599547431163884933722120908882943391518805467092890646138176976972348577478608553204931604995997522105267077845561071320509003102531223852713962266895091989335267822143524572493690679315729733459055455391559009207758735308530559987072982151466476819761020810 294949037304356424643319498923044835942305224417122064436278068994313693511819494043317635677951522630682156447848037907726136749360723795280554225964785571884704746898469546462623102938030066073650709553136937483623297572165996272004599095405260872411154410637266055198871382378758905668626258164495032515036494]
[217534291096450557418605644329012201990988348409906457319287678554915925894947301861717541644670085607409235030173401559150664390021730839885707888404987638847406390129353689271928708526356828238643715318740422146095140701498238775116704950720225577726668847683499154400939600609750127635123433777452322777505227 299985741024239594894449078286932412567756086541003255987190288861977092270282614087578628286408345564778408351869829222184480350244263438562642836143147598451076082486921011240502417579240298068263254931979242127830353349341014204856656884947990874174425313394061542099067174524956545137639257473364416433658881 202798307055619603766849973722145880157913653763022075733739076450676579422515351434937835406954615276624274180127714975408416717925158095809144438515576641919168824386041408539675535153571509996509034452563279153551561613043824473011875804430630058828272859506931119823192349545016541214481806449936957017139624 389310826706777274276911050261903604293890010616195108559326393397696368170474525732224622570706077939217279951515243147950244123347990622569516155887612174310555805572560188840523261084250032644888189570384108432003910826060308095892754475947207739390002921110221318616334502800034305012953814034847609706533077 203750320520032087070282509875347793385534115831337719800765070532648634372576282725518814470184053436812961567099199811932106843102270863860541469755649705183607691967165638623921191767126661879649518715669386777465488292371025020507624829918457270108829202803995162934708154191296070026531568338961996208110048 246003199342064966386401037705588240768208614981963140051279769565414972694797823454998131744842783649451891709418306504304402320537094504325507991601767982926463576218944515469429112620016175469150530949871499197711380790599877680084689037713630817667894785846039010935515297139556217795662789191857699713614906 360983300970873646446073533403501696580355055785364410317501020679519582788611415310963465838597845805664649316851808504517843797749518292830980215171622621205159624652891327948407130214972909780527253992062663110647664308404422758392098321995110552691917342836832205721272403286917597580095098651874548339463609 346478159177074963259437964339822461784513243998314962408004959068444112972399676764212593817525806206696987806792468658850901920767278509883896439165614652876786381976760050222499515051926465406141723351617158818091124821399489777244871029721795642578077427229441141826850529088908985846490867396362927716688286 197680206070014699231490316927331366998086142378440815071078703634573654593834598808270372452579194991910383709516802387381321088452153195316819182813413769785059291457162955350173538937816599111850170441571471496544471904660258742954853421171917854504086402083478772023209931012965852218877947283611271526401198 296631043850009203419659983311930573809629678772341749062787393964359893718109467046442662966026499706086545142255043411998881715087081855677529672395960837029306820222658456378090669061498322702114290385701430783075064487069483669145205939951718863800735708637812976394412302231844870056666133219257739430760968 321543282348107948350055502171575639099268924765096431063152442639503890254386857898365425346040085065342164235914627880959686478644492435471757717113325055833119367639694568802973084926518805729154508673861270707498771559300909198595446912306988975584592344283489868303120334700133625162045848988934620901461993 214090528273468022503375776302079468133087404753811502071599284693445210853001990757698700272812877965356697610518134538252580290612007704077116620605771830925281588116014082867148479841483602922262335863005345547476709431441732010439590493281165124884438233913304562549722668416689677460604919567354748221404912 241666077951781283582896942380640928699605206380583388225154069843486416875463645685615141884324888238571267442168839137738716812282064922917118155079159799172960314190949527320951291443101285486457896072320723881914696200889269442594897784837333018264627709588861917290363567254925451931178339176942948212636593 331850523995675825011323308492275338141722763618064691292454731685667611730544613778991298283594068778593758995718897816765236585031069054849658916057090995272321201320112154704829503887391200648415314722913437246891924069059764056730613895739014825034117009201549557661098644931414323511812539461605865379692343 236042766580184732222601164086098414706808846304687002421555113475494060741427248441203801818487899323318243934592488266037957100672575181087996578752812885684103764241382853949521333940929405218935587731190775960794457147897483182129284579880989985743933591845677123125316322317886170268589725788509218609593244 341763544218428372748254816927796249696395728712218602447558457377380952562503982560225546883279147440590074311597484907080666223477792382995535855123480939311167761645054470862443523464710771074985050799640629285011724074725425018257237732707998162820843655444807571674179160109826392342290622155152526257265227 211607090982758438628935080173138052993338669471937123226084916705798928250527009735674248881190048026583991630958714245540055922845019879821774521306316231739876967123533161088937817738447627945879558419645895780706890780008504738673797440094904764128301197968226753538270778926330396046724466687020073201891134 353468035200784514632038910012415545085659045031011250348642569916845051750155661624535765315386371885057641641219421513561327099984118295635648108899510203857714467400528923387597512643281613982061904225310223869094246373173198490515523480092904333746235819322870526818300828738688985039204673835182927431172587 260339807090378011417857571831489576132261101738739504650256968916784012340260947244000429443283502012231205932924952416091793950739605889052631990460184066349381284668933774868501173041464947967135870247973887882126594777586714134883633276152142276219529499956074760484970897654417303880631112629397993011077281 269154968451127052630262641315485325223979622272464224773851984019253984786425576797413014459788229026167475768642869432142187813136915392188127172722630622350674532909602881148423610943725553222015853217843963747964806936405906965108545866027403692463504426889608795440704447734200108398516766743882127710694803]
[230500872306222307001825875101395641532927440021809513056982563510212416782216053058938283419144048246964827940917148509989045775025890583354803921784661868507728439447831997229956377388029242130414466834079339965592501725398532239961930596571634615842073136023681216821553465626632658844365902345054389313038139 319346637404219736680728003286854336892379991065623561574672500255190656571896337914014867841474437221810317994650064511808905834043624736858152276018069018965342749387344156368355256724949932688360634582111559027251177779775031481353035547492513097485684556097279731089085659030106759027672918474091395168578874 234957631420970441820984646090802556610977901703319448395532916876941066380222140695271048078996963810899891187648525594751146463854168125827195189406794729082962547465178629891493490925251634515054139818052338516373584876651147375811090892169629116851879016868842240486293358556113268007647155607145360557344409 411159806520123046533001645015422004388920814325712411496309073869262703780418414111023027132745627711545340807954152104569382960186903503630242932622809451559370654328711458879487536767627170725696263426877646412076755018238087552160366162020763171921060084671235719184157729375796733229337263074628444849871477 218022932188513061167495981218103095470710772702595412801217669828953834875023349287519621389916294297267211310080353911456027126130140894991555523025581619415957884476931871051777921934261031813240799460046825061579942486274420802041606635038675165682174803265989895433473239328041627604173532502504270118932408 260662424805397985005189891104002572797182747874375200867946211546195982434350940517327133205152494880457722492985582879441227154349179431988225448302417473193286389062825781311331536646927719794660730412983817706793885414283832137471479011539923492363834359680840103834325638455689973259863750543596416390338902 395777966895020452594378072036143782334452650322689849378441443018449964592854134951497008147431095151062086583995389375861707727530311071811384419039852105335962813231767516452724156701764849736010488990406448904696156240056278064928471311302859658447912112615653333999841365194430973112898020075246356322538318 386955932162346587771928618272931448626492050753771840404078415136854443611669701947443563013092902011768448379790009607374010612731087587819302699095270552237258793534679735602231407804420807964442201449903352731720280074556201403511201076563286272663561894571104850363510342362707278510533018131873807704981324 208036780828782987737063274188679595121994982276055014197591900582427740596216128991690117163088804991957874317050675936704015001983633888289029673031460139042623788876695621443105631886649749091546878360347864198963943910413848194749494488931188085504922302699187333663114232736863882347490926106029939205561829 341589894651050479531036917174155733919462609215507347999563225035713382382200692091609499042988983238564772822710808307419825844394136850613004933138939583002433506810158689961631012224226297703338922353105047624463884521053809891117049648442342516317976925011623754683296400246452550638112958345237565074757088 361372629819847226513296671769920664145819443478655564486775439909024250835739475565740387353131648256820156267861669177846191892975439256809339192673526480188944086118138055953538700439271466926654910978678496031375725168911205682705597796616305863110064180722285891255177456256167458499046770704113628211768288 231708784588880631526684852667610873117487444554165664801852237683515457377335450178781727108115629923213878999215079127159007887477542653355654992059772536370228678717490415614576940623400997504422073038065278536222799144348090177878546482203961046921805244124417170911606214521134452087278983328048332479212633 257235139565129234499042727583079214642841214582856189527189873119887066629959079586669035344941646476645030009934845390987766930327957701258179898162908733608073211460576776430056800045897025730880969404634773143876871807586943537331692983873858248723886199402160454905126949738368925348623283312517526591695752 356020430268478880524797818835686286994214915370621922409194366447198224524932467208747517052467318622350623632154333760908665605417010030377788773367908353337247902987225177123395582283364248224939607169694882975658160126668840991035137392122637009849659397532430790961051980885405244154585542485553311974099244 254225250527649628082877884339906179422257819290544067818197505372210151119293014878871748558301685102937530147926809655160495972224167209766662254054187244984430794164489184601099442792388825235100048798375939489261780456340936588813171965717660616088598785157593944806423887132425613418200540810576661959014604 355226420187757326809206768274119387711588033115904032980817599953798687173473510216984941316130152592798434552915218895478016917055717113826113088455414899485371296647249196600565096432746955149339273507771306137301727637257330198023976364348847016715217224842002123311454625951897874150820775871818136216576461 226366538116279752656341822501419807657493291510341585427979495028272788181888145418214988559269538107541089142690476649099623146281902619554418525284090015388915576735365210681623206570071194234608076890305304323568065781623166549612150579143967434653271036993387630008944774771317084201577842144142605257711789 379361101594183194320051157256291695648816154681350290397853223411897749826316506158706132709526031473733220390200149819880421461375942473005208510552966132369930357933817031012133436058108644107820964506786414784437708593945666069399045141034094008701434267605910603695829807537241738316501763751855506523452998 260263026117153931157445602762809787609734805322533947091451577078053683780698380697146037341725217760416441196657984950873089029645750683667988322226901441254574619049916654767502708904384073404538891924059487889141553756629885540154548261331382654816699774700463437719775308170915710209849719868076739559826318 294513137327359822445559900278154162338797334209712381785463830587230365249681570469647502193559837345608592517462180241084136617761056542083595083625828665506425175724190844559447492339624510120098445183252772294710137038798667015176053786088400795588661962971811578424998618320047008511247583866184478578499222]
[258097046649332123822467811465439621220162684890056534228529304115290040200831339183348929061370549814142316561397669245981450300412274825770881758742625277704363429039568923983019117782192796304554268618085789445481491288169398524786358166201091375721917261328722878631393591271974237575746452838503203776340487 323044329288962081980829632151293259293609865523333055981116371298402955680942234093697119616443607423097972127453658771700105670546569673109807415402848091721988037413307976624321782955668826739405107274515385681771058021107412452580877024344446019752645997039306429499591991731212695917832990281690960038942948 240098445413308968101412069891968569616875267465189735403222873142327590701843691134680837368527525762864626633416239430636763277941392259833090579384708617684451758698876562803119900504933306185880589743323787880248299935477107899252190995378319576027245196817150474173651719573944797376151421670288860866316700 438185621960104118443780994842317492398718983830421796973463024141398070871425396389071474882364982973379098549919678338866229964100826477343622850012688029967448100549237392542323001036628177205873005350082304820339985171072985884829515533516115135864089002830755156194331342269343223144025674365035266671914291 206785762586073193761321768271456794671074725748102953054599204948390834388621677816953569526584249667830470249591153643775350429559125647872404086805902717860824131270716051714743975954190316065124751942095154732815677180910550803421796032924099505340944196421073151195879303784317812026753268872178148358172455 266120256610108877981179580856176705554261176883719838019405593344703688032714840472278469506217013515514255683261858262573895530125455960683253594664912334647977098873841550823973260407940114500621844089445391281188475895392877389175977426463697992366891940584588929975856788360155822183744364822541347695242314 427259963688540552946031233846018077241925636891322295620011833667322844416049960740180858265808935556337094551082381559798689081480138214474599763458569997136416997854888351533636232880239722119675871537747971869936591271948585774274666201783876674636664311296679926494394311032029934194184169164148601270209697 402824086108237678600789571227311298208591656327241493019992497022814693193086482004568609409480546097763420215218154211029769119028876172015322831482022025202725797741358704537921526865067418849578287266138070178892637025209029280319597652034944633328928112096082851818084918323151669817526778528343345872240253 216359109709894151187123433929738261712433246932432325771423795270069876567890537017873495572909955925317922167648505968404994034737391241490968103251633930176963999729874644055426385836736199904931071232964046711730646854013982173960754135830558545152658153878836263258778499815509629684545770525184693766653397 359042856151353106297876428356375402899244999841049748959342598693583016655354068756633772485810593555224930878989297328611782104374620377109241843193443024295110057342252039317345677602982735010109047515170320213062476638901193545002992255115272954758342889384905170631966739146922761600254821681971945613571652 352647366747544437245522881062960849861007105374967373729350657901838652975995684474837678690265260186588754102587951432596495149847115792503365676276792660450758602589908819976549316180723470002631581023713861723102665347555778303628223301328509425869118098773014385147114902252009211078458530633236852721771023 212151224937878751258117742924576383722116070991864585226692916651928332250330593822297061766117623986818871868187368783282279546041806876701754726135150388559598395560348153970201576790092629346192204387797861892575323470304894156350866944248072075266286036948548164632270595142222430233760909764492678963036266 254245835604575332550494474245088717561049139474720410153376213694029360324093008280672470948671008718595536375431905996906107430118251917548889158314424828685226896019204868895418121257068962845493030374504019491791890312897849263588879358331259199339040074030343876759738805248961684872422441105072286940115265 406962449668446297768884451519868424326614373259530905779848196180884858864677794015603023934919561435478962673551313676612601797048493405639637112652318647250402371051273940300538208789230914297153512799423147281289939001732354197075966496255570071645473073725275079122946002297693678963485338717153485059513907 266847750871593912385507938486378901122539037964092090019771158728103831352405898844420563290665913341924262469687335683263506141418177239462297192795941708753314163856777358222639931459227106567887629451090366538238262038185483901516813721701290870140719290542177360299904836287545176504552500152589011552531651 398801750428523663427621385364601257620464273066769911128277400538227910787528374934585784832883177626116971588760815870505704597957094250417123357657130183539123160761936234514182409390607100826413188932295994705631899325156115792260020783339330682742529466636690722035513141495339491325217697764488565422354276 224826853007331401805750940205521326524185299741249471405689485010853469307318081139426219104820132496466477199123588627211297280639449445890323110898448038953493455576751196204027094469560506580159876711003417899332679283860069498525047577973153876155617917403857457501195222028610648042186981312644058491993341 380014419199985329419713671928036550119037256534665128488511143546490651258949525878180319619579976709796895824189734091656024491314853459263447377051221983366913675626517565910281369176546192863817557789004670024415291018058626383066358523168644994297051065787392101280217237925018014622886883822233479886620146 281289917201910723000679353084429735856597488902397275243085592808219428618511114686591719496189553681028650781969424060872760927344927363631220555803963845076242043164864973247108042037591961651648551220306954644131005248746826235352769057237547370382708157206335394122112282397753962229519010894276175061702889 309389371359395091097171202994612259221611454427786472867943987777068347390502531059685907277677630785364653871955586064180641888945830772969822776008207346418173724583649079780914874848127352372785354482296253246167328166241676284945672932226277975454387584886542989540451812697689789769404293995340241208937910]
[280024740134670004212292820376348124332053982881133804898565433908611163188412762126649055101144902585459386236806298938487822687193204080177612005843705236432150240762380268143162417176285122546000272164740337630148052559318352679563299853593086159828643126311546039499280101306371850404662401895236209091027255 357585885045952206380452871667426595632765787422158547288421344363971441271025192980619498727755022718500837991560659285221223512096355327072666529272207941296070883401913203579912929482435456764486332296646850042541597047535068875430750743203725929940341511137888017617312226305708977326806672713648751680242138 271047453021740004634754093390980565804069818306305155066415715350963852857843150771744442238561184447593029575568313067588756339470133925870456072872116947279085134000658360007770181549484553046044512106088498872843407890789192405327218192149622062462464433775091661769017758646115735097719763545639378071736792 474383086072681226050413237270694328310982948868507317605571493564280066556390896106637881058002361350015122381827272715995635723575475212112349567943614950936072293719009933430022659586054891898924376653418852075707051862761977791579979231581554480516311247946917584375863629928831489091096422039420317764589408 228662016104316288176091826521052201247669859864847891951698186436064244233720804631843553321936989266243567640395612884267194703501176752843068243381136449620083526135617455232585470496704249069634402309099639021939344821787776628044805621278981862690864864485780508970165440295036139399671411313729900566945464 284079421184732322434037716733526795728951031546499864874451524530635147361390761590874733863468879976759898508839609272072596716291664284315275796361037415324290263021289348764583840156391666437133740953927830103663941881696496327799045932648320504534606395077386071595194158555025503566884862217985193147571175 468555459958317280859929297296176560447247345076160210710681567091010631429008213041564678658263407141604372345526269811336880858199412930287426253009797751430480030617552074358884349733972444611819036504726869618721649801368230838915875667038424755558551679421680219753750697485532117847870119607206581182502178 445731574200512974501474110914379431812913941657269270719004280615168409726027702663388504167816291397711693332379006695885472184295799489848680446555179209243805173882567268637708319401982139155673739040393413480167565713735137666252672951210760069953938211025111086884365007546480915113024551127587793029229623 227835320519961005413932972778768138176707950009955708792075658451970826118029589580981725250641829522400788832125802852958691159607180725721386263058211867141836491371425900935418125338557358493243302186663872039210243551694043573709232190176400032890720771950204859018975358651555226406782429079658457886653944 397552585299433429396678274904730219988432387214151872834999413367461165787747726054535434756370419286241489137977020409345326105541093086389574620429967293375950522032093026959162159272540347087736974360594266428616751479181786330813127277701030848572399010708272792563116738889734998957338054094719843521573031 385053527936378864742881757348466257931007364785817833546268011845947772789738554974810970504451814706701541755139114382632675470617743648226244052073476894843695599812588009547021618777110572331672689952341923152702756592847444762978635028484188723526530112545586523027292529379672825347756797632908839169429162 242984260544455631059208278867010538459785698364205302900843727056276726915892162214228169762347000356682431053520797437168458767384469900741267789167070878282068921514555976861328148815859605662879914855792182177714307726846679640043146039072745876232260377645155453146141849419160073260995236972774340880190355 278248853957324787015540831693114810167864275342164541862002825775945791697751872085403332134547493678975151573680868400761468197575426232179624480553348702385836786620974168258242105135069584080114952448122270429974891337591004926600388914234604652594513513526117223776042209780653268653515871460106454167346871 425698874573254729231279880364408765587716835453670833860555799190874210117012637877134664715078204053110092814202497817477106154080693117668201961841947690110226238438290656184653809729996612268953690205369568070810685977754910219582791113267617232489022187671745190635361065946027284648876615569308924060759347 298896714155972796293718777379600116852061577224369227360579777043844174698157632228606020274355702932734785630575867328218154465007553167430947251023114925089236444974743389860595691535056672977930168876322541753382235540434560394747829955880147984600272035587254572880196882621202960031064851457415396132794493 412092024487041728712375155049158511858543937526462246768950573273230910115291148149891099120465155558591032175754572138837781147831813666565688093454686410096389851535479717346576297763287460079702790955258093376001569384351344234668582883963823133011819115347998941899805879522628669984537742486552268056852412 245593500517416772996683929839547908554315644201320733057384943202957840718550074940461647083237207782560838397614402078915256632216922242987430632090181080046971114944695991173719523549269334282086441901341771596762915347406109067105771749135037206944712692461137164950003296752531375988299522805694139611881274 417819953001341096378228484028719147298102239794372124997252084007875186256067660357694779046983512630361499269532610915398124753242141955773400150142737557695204539689680116596103690336388593485195484267179798826664303232590440911318895840934564463183868996082091782154810313196191572360393516696842248593758430 288593776118040616314766171352332182970917397991708526167873483430646926814369572449138075160876531006670010322754346127162592913390532878110516266780718165401132833183550676292105370645810584714405298038803253947481985465122982906581999540840036459990585623825359327735633867462892913211425824393567032421830570 328484441421970917256772156408377008898814832472624264081640534401357040641562205085658955855030111212409210153800573747215971593149942242637937610673982096571323570013781797984522328017978084674968963884240025718649195662365143511884901590431592571684699150088131358361668415906764288279386570665594476271529949]
[234941405478544537806439902602972109793256140401749807418760066831970902266784804135415855605558499988879943660144800777550252241375636037095595041552441375028547787936573414837033172529784314934826666166985236289941244475642889131486567102498766410483366965976059092283356702767106747093782473323132885864765095 291677502151781697169396805704790537452572236739817342348977408565398480892159044347789350385802650922195045000403538124235427732746451406657973513326525946903495596864917166525269397421847882337806230380881551838477833254258714384141045983126888756811493191481588971746231257100162392160366136492190032977842859 216569660786775015250064116265258102160811424030041666034800110963515922515494438517639728219229483299359989140925260356181713747361917657316667478071947150461405239889431920355244401518095468525999454907970927340166674062072546145973075589076816853159358448741031038118312758449570713709838718916497867239183635 391847464394006542562367709310575821012995508588057806291886133197507008731074962502160330963881230763304548557747685394226579847084277406609930737878569806235535164772734464915147738070524095375238303080739544539286507809953726925806818614599071198937538129853259337589374727067902351171347572319422596065585538 181647270791559884308461018783145677855209469257398612256194191154520961648709449746128767894642800568538851564980773362193176826843636790538652860182573280928136271576661753494016203605706892145621492961651941268505383273442113287868784317068209904092467959555929627053999464860511524624478047410988243993671160 229602043590529214685792361103915277729194233162313438434518448469621755059067514515223847995622626157171199844976111768730559566953264611748216471619431416616141313673911758307565105081355692784522521817054418327335900641986796458079766433053765783739186115397838135266923101553641744894968613070191489109821873 385164843546683846585267636759698947967010299010006672450214283581302184481023065740607519923065905507221930345996078875528895425997897678890419714478019452024782392688574841031639835611632230290987542076476311240955570192529401862936758824302182298614684225788826251404791021458824893027042753042111039981124991 360531311418336609045113951233515733190379507700376677886624697472286289061843162130006068680170713617123987989017895565691060790138614933808460498474110053090591208043213602608191819619733175883238345242242550232927678723368441905268201291886578981064419745146701147209044234505351385366181252144309317957545399 184894110101495577123261042894168255486446677250949566899806753922724978372093795827924135187258861899505856078497177382508628691215168625027950732472584934239402780979310186086034260981159882686430078865861467903663080701714646756086149278953597220289484651062884650555523255800389518825556121587128606486492409 319181497043527414147252445701707080083228636998825169711299385295267468322197487196004126341001328066733975971672308570580638903742793617790504554511341477358910999031097412574804372827385286976774777911276197925723993015061673157469926661516471343052534590228091340786226161671203299799563601725490781868665329 301311328473247169347984463999517510382081352225603630925847318028910115417604878073522635599161104941463115734455606530269195612841454564958819587736230271236178945778072728928697448985291550949664077332183562429073568515133232704943213437359435567088782995180532298964022874470776843767108011479751577546157341 192317094837872650600497967599667693434094097144071766794240577474084025875931836567888880779700085642839571850442431279655926758354965138423145336538092380858025585912675506420811657644207922840507838794124441107186664986163668319998576318868650405348264861967654159749396167945322854624451743349010564730898112 224059958268181081693635305615408576107433752030699992559836166482654674882770082939176331700135990177151006248749819923381516177631509575782129525368586463630836610167988709884977173264122512515454874376842400869278195832555938445526482391763001536056233554083639398337236581706254496889384920624565322036781200 353261945928503194570154720828350386853786352600901034699058776813240687888523747531385649416815561631973609720313335537783653925036634448473773636441144446962975794168516048008638119286920735207768202802305299718303091466411511632260056502947646277658223216019072713781182246447747127418797104297768924423814202 246930295423566502357206924807828391647960834228475446862077406361770140516706973015128062283531583607146507629472512152884420019929919921602994196458833122417564602125105754555592519800276504273484184002517760439050779153082916774730678953472009235590731664672061092646111798232721440868903533261470176860697587 342510721749803522308183274561448212075736303397755439571936575056953281248256151345344421713479320035329916461438735743159935798465245944866424331362543580483468029571884649072949472383694648861724656384811304086214753441328785486024501095422985189406956027022688945117139941604054246476668582196206818845274880 197557168277644910681244382655458880014350776351131459299229511340627341640173620168845939543244771006811766164164899726167454506104108254267851633165134245452333524176339226802054545228418274878271453211179234815753547330515826759597177430045653632763140178194956557396920142781089610484547938756833172449930303 337592856479567432745846196953880480543941174314591351553612721500748735433337069600356474726004254646869420181617057303987378961818708370819199683252535520173442608414076303836521731984251352669567733486886955711717275255750049326569648779877835664947552879104010021498191608353526116107345575213681003376273697 240062854309216908975812999487578709309099550225867237253627148959230503284495114763077522787812628620034245271488098815465696197844412670159346244443623530004141355429450336021354900817696443161378576167418951023809590645143641816815995754321969402789050472734344796838099375347113806626392844870579009848171215 264223532854544506222243514867228543175887221694656905016597603651018159647499125522388150398442571985750444593456208934899882997273496217700045640611080684802992195962470395828274925871895394225934655523828781673809462849991776921806979586417990675368603966821693233422575878620125759667142408984825286787061738]
[267868337426328883888075916801044965399584652571645099528558844185037509408970719987065800961588587254447252991352837535384747745849773084480995534981837572630791932111507785257631468727468232469008280233557540930846008279370386503690296982295878338569034056518790101543621842437025126181246485252569470810317747 335461833309323380937036816131116887260017914352360911897491187523050086172268320909701547327737152435938267519484289011063922933693371791939789611099211400943970562837818922898241848909610839056873028164406551855334862982034686396802011602484434658481699935860020943126723183901671337789670554794899264777892225 250927982745633295638197948301800976195219831472495421454445757253152154038120274295242973259237197414742157518851564465970240716416346255452594282008213966393582662034891180608118004681672557514910830644462832215253152589827038438356845433266726397708601697956940297905889583012145097499687107393251657033568465 452956575843689940549488705167817302379253542950146438400061465615324334922108772421036195764143745343695963162199221693191134106648009626252713648633236160381704053806381936592693961219745747003054158832649208097398493005989562394285146025654381827750006711461908814632628677638652848494919079662265902543511328 213604032063645184492715249076918262387277002247114686389635677914856707160293895295433623621346319851888155831324703563503932589210399432730821082466494535584599560476105460211614418954277167531353569564506834303325102549795041270909043564698699022163131362689377656687196820955168853585665471098063661392140650 272815508734704191088313479965242735162702800151713724726696485173858262504895027190094852522895672448850296988825639666742424480444986970747093768504656185972461596266859053994860289676594289300403822681868119327318378400819038071105397869672527445814299624750891780239183578130336577170677301566532281833286507 443832425845895059804820746231889934717604084483815658116085380335029403552551526752472065809341477704397267476521675161154148355947407929731674128372623781358484518549537409127728983613482951753908308609371042549187869006464499243082386421311989002601155106263531960231192551354455993357840810549214437352677939 418655063255146701483774085511629364175264204889139292649751282555910436713389358030831734004609955748945214861821715792987493285832096676416789840785320499096487683232602981181163384715922173058919722647357921949130661789095510407860276696585651313918951456286309729350679386976461245349315268974096746184191655 221012983838096005851305415714631043914717921870057434256087775580785745898956049964974241524091614679910844905037473779232599859435964737501019845405828410424527354839939402064905687819925712595157224180800922617138652595342384796201689716543616155314074963701750310638484858593032626427241681193036405928144417 373262215483568360111784846962467455649246410286201574375592044375948944635700667559602207106815946833835175999362477832095923364399403375393185982433689486102813415173072525470877467707344331381713380351648688592635796044955824730860724590940542156987482400932902547941186388591267101320632218925926023817522935 362893831966370762701487955958451525129578574669656767184241920974289080262262412739638309011864325908045640541708940578971101511222238655895676524890729265780078903105605093558026066419273233496178563476023512243859605937910106534396636434547295660376307376399585758536885648892470319975607423967286115211726865 221473400005361244441969916371109246276608791410243777580812933511160546827970264663127141442719899173661271398479391235098496338624757181978159001075905787020834384404047025547808527354397676760233605305510944786365109454710087732003476382882849030718627106576481654745376621985538153534484441262158653896764312 262442044246966641743994354396430786706060724399248127689361771936777733534046150324967976082319918797137314321920088258456336976041077571670817265334291254136498888694639657497269942419741122561977070180590164175530809030759951480274904161308095536349786160606456155694241392993432590377504896077179810643939018 417168468787111486443672222900835348041803303696297561873957496037275771776636352305641075205072155019729402342719120571794975905146971199151369053830539605532227403588383725574768878970638920442510118428475319575312394753194339880698956683100671723831534904581966206430223762788696916385633521257292700441482036 279005323179177859795277440704843039979058015803957229921250533452840320735748894297749693664829781790050935378918267615894405029634648758716594363191439618043892239974666831765631076691729729119919500575567350571386857360508093128510512321920973603467348796248178750894102575237750602701766225728387179212032935 406791804461390319046145657757195265623434920215681269201655398348753211152105608728596617105227288800600417723958186792125995279149104491495267050989631565227584369542772942857626890862357230174748250746537885383618341848532105813700154406888518504649373729464394015205058169367742467011656761073380112247987512 231966396443831126895045642437528214115212211959701137840122893076397658095354059924539868678870145091053204727673399257106006224356541605146673060626318481435388317009336236222001290128651519941431669627139066183661345899145379171001400327269450377430050723723515540738718197468025554899789832804105580235656203 393261511414099183285834039884802070528152817324578308637128916323942898773995680585448912873737069524525240521067770666292258512065397786401667780259130387550686708696442090699134059390274939446705912837264609523952572300222741005060856856620793312095716302125952359445967372851077931059844431674803910651701367 285721048699657917830904201021496180537256973660668662426723043224711618976473720515541440241808949511249096228097146346986099738666175896506709816332358956149172697650784335219720798325025050338981644961805005404418401149545587341841047309562263058233343353516615509365848200858967038029009808817416002999535795 316948689344948177041943198715466034541397713616192147684729172848509496735092786744002732126164107653243580685234047063659262268881806289533149117494157457284052619461035465157085705366159574882652811230002542699609073328428362116704167404922820923042349269074496032597693961306481383805547598078029816455094742]
[208925621634500479936368791790733707700049661921370136786621943080290973004934097209128104745710949035599834585576000955924990226531182170863092173754984549081987635002214645712010172666902838390020580057191001156593413583592145417716795486927508928816072492162893264161787883956701788112547698210996712908469812 277881869492592133533584348008592047704408971916300203279724436379641461730012166534379012556942308562480899264800984988727003987029191865562478443130179350252440028908896194338731756431773263395803834785646264977170008497632926714981794795101448868240770431527765434367096501146992714221738021223594792183096896 191392376227816016146742937864506504936009695158966680565768573893259103115783726254455703228891198264225730974296495444547518516492277372599420632677526944101297888604861663811070909668668285847106286671364907431633891133693214718274737966773208910655292536239827749730352122782001689189676250181635661534140662 373056357146783988324001261011290817990983733139928569486822804250969404663287810229094057517151508520325351979643505259566583255784308546671274359187540329810401789064405476120306086731580878687430571886487018022129970161122379763198933193393164082012874769856239153925184773245768999900007526148725685275215398 189151134426148278256409427071366413520188009676016079450677932819587006160588724353758434921769545666226931230267824305351217541812592065542758009713652120459530385929731704136259998404704062061516342696399828331167326571083479876669555943043053168047943740248299653029631568376909789939106248768517090647048144 240512512228719798356070959926466855223811682881052525290127024891651662922391789865967765496804085821110850993939702912837144062186314942968067803643004332795302193396404009082485618635264558073225834097841413081075677673516551306218697757264380114144493009296066239289151433414434039379017646061875649745707726 346912176048540452836334546034032960285022179236803788438251747480644343259868783485803477823211582731043628357050670291197009221306917234214679914252534326891991085563087599411610179740885924667596129961260429165752788601672169193829949202924835130279335075342143742167829496792703096448616636496760693010632952 331130373037972001102953031643382396979515964662489304624052488599160912795125160318234519866642862721633549672188701928861692419781039403840641254068539850798575561274690861739963655892301251695988981187925766294767450652522044825947072128307714211239079822531930197101207969937023517419925930409353825469456226 196704911547760567284050385731420674598076009873937693377568299640915328091276826164288794904728879719838179674854608315870562759589598280794236610105908731802053119302919824057716122846479842474006011859073682756262425348588662373737717717809493704161975650796417793773383864926652328614176077844057491179246910 288744198187345908570426813950261730896271408792096129336472163819416730502152105449025428248211255417197730015467772830248900326002936441227960684688864722516521525191672054152484703319784200271826100588335140247721191783466829259326414039557724063431691211227913699402111511918673142833813709806399089806975546 314160223766452128579861005172671000313971828439735851393262164809908257282848874122242764968523201114287538447091690854508720803096513486245768971488677977869350339315428637361871338292982643086514218979033892662963486391741214111508994566591061182896746561270891596005443031433846504367118107622229239977276052 189314236510821958625445430297109310134459612061711583414604331893732423721978047783341627397557474990718081085631468140162397553785849716100088347097532996712406961145718960009877973385090750342652920674969693743369930774328443450698143101676309961271021142165188231029831485825620637611121566388434213441041096 227639552218697766618035615326387746026843650066567132578875508883597082357592196162419744534440656044550494746125485842331141490201209016484918296246228621704119958599025229284474910953153640550818632543298036010211688361274429640306899078083556482685291746437500121569910687838704588261871609562916512113037410 341621018888240518807088960299048188172191849234245240565461351612311451713088355317382498839718740283303487813712545677438538191672307052718249730232826087575245580972526424458884227978317230336839594003104736635324065238353876804896463305487006586573048513769652818984397716990022803444704505403150568839937138 216123077597152132543630670055269355562199345931984977069037529561514448756215530084689405786635470262971143013769794858355361684212611373725736278526814079560912323372074535977186754304069656065912163601215527606484677744091044035587999329874182822695884930958986741304204631893956526941198447873806112347365238 350298204021132344257659928097604044921237222358378927732052872008584412852634064984624664344363578873080685686411093410611433994933116392788378589446822611880527091025930422852170519748147209094085814437888383833134133192292228128381066537995036728067660581836663906430414686433434109211476345307877724982369566 200569699342686680129903260344190813491599875824275561995415417992992364171175737877630396237878781295169082420288201968428809514772651346528112268662588646610825249833788236333925640063619265380075700566826814005955004973364289204520681989309350580566136586613470414932749986618410222681347403338516521993389274 332478634383163276191514436654984678626644628860495401127847164436988350622884185489705399320379025473215204548604537140222014597979209029412807609351867634340647611957419248676258721833190432147074075941996333693958169415292190320714238628052320125734309181334383282887490511035825947758674019710633863920336336 261481571288761610800515150486239610090331881249174640784108800313694626026841178466448957106989246864194399955219765857389028396266490104690730233453940025110318346160598377268827783341728983604303433320271296118655344082911605622359592868855357966088669746859470179508992926751243414162275611424954419765271272 271526861887128138669968046830048945304754693071589434955478245894201567706163208390117728390086337577629494954350030139407920028158811011700108620515049210346381025264312249863553010933610047283708909822728743415380489856722999944947873038916850860460362112591717191847137387215708856093149926440860889221400378]
[175623149805053197861616427683048878592469524974820452081294531183708188952375657046874812938982110631942350028046267697790338027114302841970500843978963469894314503492642840507622494347676184175962190032164434594555975061352399167713874115936399166570170307250393157272582473779794429786721454357428554055159828 246472611436373388239989661262173930524461618600029181504765699614474301970276617977851330684035970342072431179147767677367241532556896669908885117835754331334843727517471410398500159811450355927016592764707924286251133211055134972060347454783378181405300582327936758880369170633433008223405702509773222249658771 170377117647133131861289078713069922178957692045903085485564629374697887248831319867373965890439419910888947304840558380439836673832114066395431739843608354832983406132258122150538490567648312137683478888589773810236335287424835277153061506075401034916105107183827331687942412766694195145073944164864786465418793 318880184470507855794337241625696100876255739459264701724373627359616961808074072150679547673649825042488879425799140386442963254577946153120439178044973494562563957793474838949737206015100240847360824935865463095332048802516593999858232740720853073685342567934894566050276362805521406320588908095085794437655518 170877188206950702651638691126547231307661997097691500999883172125449255821553387294756734615448405424267054425178987576456044259468078157017008218367575690622832151059934884069768859955396839274914542608568258587793577885498892836078118559208149330317305585424678607528177529820782274439777715575337461380706616 206063782701414601378657104339844733567076877340250596380188623480511149894410345740302523035013420807252174879009909465492848072324709491924842595528733544155095032521446041004004338880847069376043875548470405766831552295017253969018349754977643264961787752465568281070481540959661907998749354350611803463427194 296902855337610822083670637491151564796725031836730507640114579121100759621016835208167001121556790196308667848787977067269971514621628384560398865788176665093040101150549146216915078889519516752791380364048646955401968897448644344227182351887267732056428733969213082815254850806687946171726768790110167709536447 288696280164728236166908851041294126515119598803028148975577739092543353072122368433038776520382101061701416136805797803029422344214691012190791756621766050907284654673202454318182027043589587147268298815665800645728242296352078713078969982360873210164364082622944104383788870742732002742431888753904166580845956 165736203294259897057860224941109788933753304107990451347556498450534345580318965824916311089496822921822336271570417438683256020041657954189552944520698938307096708718845505202544383230308227719320585778589882295006065300598538148699629449664102808980309933467806190864687514019591877476401183225646367359357939 249874714069496977802858983978269755231822334239693578113242758698060987334899957207653349381137467505217559841886198205698656243173634161018849158180165883314829935431977687561072757393068458812258609501850265110222383324683109878654345581064693931403813786926227157909942436884699913315358386420391348425202730 276185091021460126251403464203383531551270101223734429360714029909700118803908402648136835802798332818146339309387084338084778767840523849225812815989953543896488350336682093621179992593388836302388290066064653209415361696422734628833111685768822301310847196850362475040891843431422987423098238410429826347141057 178233425293726887379122401536860120178322308260626893660118992348808245101362815377642430952905493472258494231289246843918056624766587890675725838663192213990655769602268958410473789506042922545222536788380485727577290212477546807445792687920398621489120123019615942748507441603362226862253853822543116545385835 201318770379458483550884351829608639412343961437945452007135216858525000422747657723793875656466500557967284959547330862427397103520071968294206351756171979819157729166406831986566429836134587979891990023336453264404803183826997290507820050176872113724842252709186034367140199197200554850923230098368528091354727 275101003478066982297142226914802638801476022302467989552456610713198223325752945551523797097038370080012893545660861033428714922218051655619133103597797529647489096571635032556150305695917870642826560961039081483737278079868058119617191905211025704037908969151296010716469170979254288869817419337172909965664385 191249958163947446317734469465421081643380085390691894717888542781495296693984620850729830426974507061065442122276760345379784096335904357269709051257814975371286222262605797484327357943942136830524081458036826390915006444835238609374930032884999988873539314866370053141151568231199795915419316787054184559941630 282956767685374732684255505055321721541404064828514007992198656321848213210108304752569039041858075019113865418514589306981230705124516257723815726304348813185430791760354942068520172912031833198724227892758160303874210781537582304401386959233136874198846566732881678510136605198160541154389924372493390566790348 176674189063647946166661855123364607063564837999118994435761167829387950465557500962172651416083632955175717252656085414817120885100783500674404865386260348794097629591012031742941277217851738968060839882480813976573845233225224918480042050569618479847752577956637361266229050642559205888548899935869529919789287 293629454439938675665246149997295229780540641224058348104467608274064565127389468481157539830025313682073189415697778733776823698579272939265657643462398039106586916514045559978839231057880657927816845504452419329255147403629087612138586386196491856547187734111017683784372399627157138963836461318222943418486105 214682330124308024533638289687908875517563936766412556789208137260848655527240791264786452120718235046960492471701781470115047433128288077827315908726921960700779371308425360277049728613242474818106770056751163305492738270320109661267437252899321241565992339289983249509045957363772431428834812448408764831008567 228022702864658988969129022620419283010435522655071062902293956079551522596246345831856235014806281948127943570821740330290263903929956923207512216200564168868549687871485861205457540731003277927306702487900947751779614446042211492488056556189716450536869314181576767095238989836140137514924414849863116384707683]
[263802743125065611854663706068826473561435130056041380581155630159114016161797108738656054337301552361104745501626297744633677998346389065885445645225457392264402685256446732617410915726199518821525714030999876001288222121346036166521447173049410694650991543915554892354947398312698794503377416461200156805394371 320896134423422574520240291349147401639165979146192371278439880236522964304051823480657847175591625518422085492381476122103312288655761052752873859442484769169558817241190828341156841234335477900521098762932369961822782795332987578356546553091129465224263619589247264313390916497174987642177073698938428902840770 230464972367479080091313350804632442414768036789683466924014697404641380950005377670596402791035596590047124322259265099437564010465193833824987830791614121854733402779045590771445706674507821069394743283382958662653151758735070694245428140605405921624590397151426686885032916820611603150033788347481218566745273 421261585084920182446526495116643480392730469743827862006216040691491037160349188404172456435796440269635067480312266243739762324986305046947862269526406642811474224946858743837123817349029135138926502157998094768981502376251415436206392989253122792087156371410523822026858140041260169395691454120077192521149849 185418536811440205699072355965719607122795550862289332526528552739801300951966026705708542480834896336207347778790055231810444767897930754793773163859353636496571221348155463841169805294550379893738848892918721076975081924623189390447191060248314140980281056389234837461879760635375755455911003842191792795699836 222949724559345369515876742376324208474209224401745813603650618654941067496891076969113387600769334247281133503335610185231877298699232167392913882548246585496460081945346996617879304918670432568357795704162111628133186356553020806543056111488324767104871563625990468493103277705324264277570952424392190201115938 417249053603668860398638007724313631665518151980453893200754456866793289926569742846593268065826968812251298412432228047579953515503978207959604779316946038737170598679761205004141075158189151106860397601785647200476690891680045886950663791354463313670237037104139315333948309323177215513136677962596505855724482 380703131258698442484257295705282460138459501506258587963804780147303689301498863853181114417387375260509713819428913085369967503012855131562124116143919603142878461974086212048882400470582722117027508918953850900225592332853448851076539375095239472294957289814520378739330818569447425759157258662686334253355500 174769482355480588345311613010365968105647777227983215629383135386253956970539798754553852061207843036431767577299073223868970306308504095596195583150625655494261586095058072743229891433474993939942398453442773226310901826479117219151788620376072999054073000931518253447386312127143793652689063987632256694644897 327164800502570111999255169062214852289024650041204000955392696812938650601633308356122411433015318582625120285841145363750655096696094085909404926864951469926527492900081602416299690043335910528297439260535586701858449443390263596697025175513931804810020282888341740518192698006322684878974982369786387253681316 276439838719650764488760706539413808941389453025425230737995344354680683748291159898514158071497732848802350556863341028359281838520453819661935776752717598508065174375624156487099823622160156401934005153049531524751416677363022090927104928829311418942258423251999433232422284391368310998233207512721564461566556 212704186544971246222074331123597727663763455268551960984096797016253016572607107738345004231955896971368977347100937140263521419465021517581645826070200344547730659859242952260350574881399238499262239129867333898104370883831229865121085602266005715278431850604432546565292403574347428963378485409396018837106565 231137422991648931025191013127711640031515047110174466235597219684768405973493313199593637448742237427662518543563796364330721637222614008904215424565320301609005142351466971837943478984805812334326839891442190086073513302604672100631364143668945324150473253860772189723193828633877450731413154571181731485383640 346852671310986416620268341370428386760027918834948503130669645512096062908498635870610732389477638337172232861669770690949699384690517861680456761451942282251505556444345558964135302046566863123223076364168217803125255031661692235457299179688870858823807648198125758577241371873680194439823200696888713230902212 287263520323336668880280185765643127589437972686582801399161589015314791815648075056207418545231544009174107068734307569837848323966298363454768482796027048582738173591634259891835449428405948869830133193571961548167133122964174404800246571823699011968363185640067441086555205137097354790780403579717485627270428 329883055861881025727591665236381807383719074549752885591622161226411609685765134394593157735189825832630380022491502237968886970250397907315413692303541068768129070878124619704366859263263954300306812557267687229123228539052606395691784049866558707964342564260464000612180076523125192753373680388269270251292093 201692153923743022227927922047012721514180108981353368638070298812204958616153080716604722976256960296951889299093183379416088095323189536529677512957987101520044081457825018058425104385133680831223186160753040038771182132856411426923327440105070960271874601546071354133543964253783054427578572957912051207772513 354771700675583689488569097633266345033034292834823785723176682704096136540587857424377104859410919264303365927838937302098461729381745740962742266932049996634084571342813380437030001692639691503587914683483656386548814219223701731884065962930763473181936744247429314463543439726422938526232536731130027472637830 230943984818628219775424803943028701981262887753550449093347433635463647762108622471462562507767132209632555402602466878568574695007510860318898140196565498149897379414874244619642393298505525196971748179327488678703246568095898056962050502886150246314565883735935819566751219493409162211248339527899412213120834 244910871291180999540876131038224678232782647136061474463687643873084543167227132404515719210986376277025566516062270578690175262957119201647454438547850156698437789055774160524029594829257639261357142899164701080464003135214505418613322361259961533744317674692792378760082345835178991716760837668321047070430650]
[231102540504208683441278500770895450337994063758279044260909792393698116506583800640851716359612166617240329487078459778841086713848195408744926082983916425830805692662231680741038932462856578954369707740785537756521479763236859696269883824392264522940260726858607980820451940360570848863128174773820966893542712 265743734539653579066835004687831624350083553970235027604869801864636417556415826517642636904826103365256026528700260782452262279883815530182066276024124685278906142213910928844278925366115374824819693956067870537172894170375835301853399595095899259427582434932770426845870293172991775662360978643716901645727620 210349079405696356836538429147292337140360379103893119806144305020385537810464131226110659619069825547042724403301927985448569166987375224344116671622639914313998860456344048567428725234911738633657245695536663944656516106445205837360781053063252827728226509266208429994258965053096885963127408584682983838548084 370092127898495881883221131176739243404828188407936324478335445617644816968311072375693897341700102453800936942469264963561739173638500247105996819894999098733448347624476545606461484793983759760189221130816420100595493771321881846212596470412808302539426346257544008296437757331559126525153939418649272581792003 155843799780863429380712206517786331534603283457507603179350757031764349002066382081296339893951785831207307434330926859216544592273625218287709253187474640563451801142789872369433700787170933202626495936868489194039759368130295796694222122781856473407481019062743764408613678191642331547280835219937956830086253 208685660430718063023134818029600681694016927117366633238131132958445192019428111787150807087651421606387641544353440933789696906455720573039977965313759451536284368188362063603542263229302204204759430462874611474874693438431550965726670551232667004605117637529486443639284542463827061463666813013146069774596623 376495416003518639674417499958175701281929854694917681678531789462561603655488327795424699227219006166599077979577816057057415815525993272616746606687608525956800712326556097990469731933725132735734038748976627488163875926676975364618802603834953770499093436489566086645238136752039949240162647636828987179834579 346799239413999488110498971912233459911177299861483583332921749052093930592747061842509813134949357072475802378493682633518872240913782965807261631327544141893983294043896670884763376696794350429609524179289465879806052942382457120210869053530047151528132036231308034634997696854219478164213710400852077248821120 169705981594055626191526129703854602873762809855971515772741441032501696121273578085381028584987027704846182419400909557263824386366943105526662769950004781705890276127517431544466618726548271127228276365582823372401537605732731021620104320190337969973584939402421466369627565469352767040352557329922040477005195 314939568863760290384540118082752153809732004758279668349154520117091144948135424245524366340063324424008929024207003162245020293740471292239566910120785826581236198268357366087675220099414793533202441187685322391483201816424704819088053895597092471373867194127053233302646141670296885753306292240050902882067193 274501944416882995735758799555202391039362923348719225643877708282924068365040664503209219610043149528435249078029298305750485892232308481502453379425972726421550496575359608190796610287241500978967423412598029333421297963696957974765793580684264457336896386351474306901474091451058371162815205889658547288756613 162042852002525722516821528383186018278575449206566435454250047908141061435368036746325933601126615024491314927660133760096281320705776102244655820780663122601103393383949947351281931199892199251850719799714623843639554360811771032929325708611802494168688704327872997885604422684877382926752998081879550922673159 199186847050874310663711759065373319818497267251671468587770424206352468442476247991295451181041636866403183712299615853839562933931317404502686066913393985793556698127304344410066576991382378189507028571235204890091478641432426168888625939898268292807620365706172657484050320408998105779117927886741609753059306 354256837940358751229028023821326933124473022943665368069235748497806815006951251158634725639701700571512263598986222866058897650192202830132245087410002342397999093293483377281475490558826621520353888584868610041332064027926228150805277127860712298027363127401797551506511822135023888887056550951578462666401168 234330939937018332512234165522950453367160881291461134878469921151439507789729630447378709490321610875562768524667352209340414557186328790809853587586777294529691020063694501014064937325044229606219932489176634851086737384369314067274741216128951324322584695745812899005951037076673803633700002116900191518343104 332082029558565597759771105851214333635988265232527004414362567577413617394351558271692150498317158739732745705862594401942142069495962667568131355700265663419672348704206572928190457355848914210638948420335608466079295180163933469063321924973352389720524124550782071251683357371242157306460292201842796159597718 176986136483895554690418327829140706363382659137667608820689582879245220579777187328490743894561014022554001750978511533817549261532456394670700292294046329085693852890349308569443762100181849446497355153201880907487440309844376681147420667541370307460264411327087925505905262620386071002765983602129410981524825 306033578065708181892360605636488380307220653372422877388073952287817583833546967101487424935952427752988503478955261900401084739761751200955335173846876897288478246027251747140227411624609094450221789960283358822393959292926844401039921802250862735005064118599109755577207049891717698360790293581097903491018814 219314874918300986481829428174736339804584038904721479645481695499805419784152647017619171604955608496067000760324205776683331070846048793475354613648011507848178533546104483200182624615627611831889147775959481609079024343665913206339506497470471534463297926880205982018469713052772296925382623211807447844984467 251411658980176426424599861269457962905360409027060289781517026051694351718496780577508779445417678245301909030308343439327126522122700289297564268748528240372257642080980189466101294410540270453169210457925553360431225739589139247809993207475957612679571134629233136065652272322414452523211844945796568973495999]
[241061899028073988798790037741230393483942234086601336070745000327245876506533109773029357915901349628815872451441889563829064856413873527725718859869880048269099752637807588068089888054068969364294640041411106036524096059153691012518740485034056356062246082921852430278113420285101114711615424549249139277257522 324649731643599086115112993009519699452138031914097657036589002455757996538628271536312086027891113179012194983336641812429479724987783015151964019081755404469480800754838022457743380789954890634612176691117396518047463228921056260150822618165077435901312097677295072882034763535523532942532204433934684610043981 235254970787462219840404579655013559873788828426903153698865648656984467361490822488648895501016091744753460386479405178156171138845774327715705113786912265599410014203748341886209366676022693408156368163002599405494601590496989401198973552929276456687898371994794916975190041122391592774191440696356717294231885 425740880045791532523198846621983282509953016391567213186903868019913918759794287097305752661999887010700707627995323212438864509866508575502091321511540826163355631924563516051145246887413009375239895267200500759550085778323118221354084194236896509274319680974593889376664049241305285099994139673137299475989239 218691513540400821804549224498219066538131669904044585243726742849147890707633382757651080960290835528290337948081051248880519870334888312880595453864524810424852223683875213593288669664284711136053455521502919177926558970455107382642271908290895517253209256467433830518046957366395690737578182144983590102038485 268302619218865130271719033545009753399779053711844155079138523469992700794733191273489783510080694015540326749356237471601952640624690574647332040161941087090977941149395995577883320516589414044570632833251347023576508268184788428567463591494267298109046818940098510550915355847388894041086742208584657569920241 407336383942338740798174626239389115510448736801033328217610646742146225826124003788716755725647121531842265937484525828476656038527198785623700663154028773955096919034338929692107410713949725783634901653340966038961119651080922944892272587766538064084646021325484724541568127313549775873739584827773006445753640 393134681808112694975913596160448244240482981723630973356146031804916532236941181457510899673572218259277651984203628914738756762221755837644731654303750753476197281608744739922590010615338565608869292496306096877052448883659921270645325450515812730222672889593367986446631364900471069472193722736474834255002036 215985610462350960536839616461780541805901325846759115271248048215287698136361487020004528283989079601628886641948076104288189678081611169093333207280398109804824624795771554170650549004098320777411071055885304220606333844107189337640129908960147941269202033000097270450548214871844613318043993706884193566592242 346257259037055528063958283678684887823288869097971263870223136112022875717777736826173871208586562198755058112840232705464980999720904563887473827824133419842768406438046339340339959582840029978504197963610308123410599725432433522242213697754185538704211639401044451536292208819236994660059970571914124114271599 363246746808596148737210992794327846617357056818891810187521430179806831944113701788410216011602199287600811660665546421846554242509136889853836816039021455766143689619674758256794863013934396056281068369903404163406671974420976176790079516456790272028047801640717669827329331072466985218901215709420185800516476 228359797357492684759272370677578475406914608085297270343294942217355808434075355292324467198813215227688688362769136317178109975711230089700653102174151262564835348723399701993261280133408455332578461475024635686745323218522248731512202235490816229580164661361372292890652140155335039766689335306017058323699870 261073525188914242692884720274275113790550147800012726232648813501113485629042787747610119742164958912877580849092420435073309574603834046313181794097664949615030331077619160759088825143525257977326603290777510448929918569695246869201664075528458430758464117802684751708437328671301437881253087978552349557929227 377423095994193204578922189550375597310060100452415257679145216869152987932295320012532627260082665449818987730073474556374560322751066241641707700730565368688246016131410970218689748683166415305887428221617894893227940635682372402200646522705710629106816809097492815206152579668106759027411978172342124297112303 259137995605024246569067807228464978520111212301361385815260982586344554863475368048854803571456089002898762700215696227544178787894944543608617271366117854871387117184290022561543196044929075487901413409938350861993081883369167887211440599019001236665896078599620016292614112682026683285287944667378349567596682 377895600401386832627207473591231966722427474471978045257286932968025516883841438396371773330379400989122373108094619359580992354022500428350148393367120309907862372401833632609379756774123183371656856319067036230164053711297648196590505716602911948600987377951831975851533902097405199596765482628047101483695180 229923888278321507619955308253814201187825646322202404258155581951646311813859740021687863337140515937531198397962741508305877398164540330415865591188990653875351703558714013038074531074780496846384342682480155793583956273003471876034817892417654830968846443801102524499001760690758196360143326941316313005428764 385146020849542828762376295678872983417037260032909849077585933133727150028194380453576167080843313823221853494336578094737485648365841025909075506522610021346056261722697685735150058706447775324473174749709672319355587113103471390302308032073417731526776326495675395951587591860727897765554614275689077980788425 276479395595285600707058522756048895783507186318454062608303747878078415416637508566237782329945122675299190201507390456469318457913011040396520935462671813934491352484079874838580577796640954416628460793482556447364053471884684684531093453142733820253696024739578833329629972259929828470255438392962899864298928 304113742334779824637859934428402926505401880740389378433569048603311596599826036448865299394425292925430829973661203201761633383418875016143497844450341141334585646363757368824123351511948673572982552037453552797655001298458947196811495751443435574229011561264850603574487599877204387001096835704274170180520128]

在一次任务中我遇到了一个challenge，我的队友给我发了一个他截获的hint，你利用这个hint能帮我完成这个challenge吗？

先介绍一下题目中所用到的Paillier同态加密，之前做到一个GM同态的，参考InCTF-Gold_digger

  • 密钥生成

    1. 随机选择$p,q$且$gcd(n,\ \varphi)=1$；保证$pq$等长
    2. $\lambda =lcm(p-1,\ q-1)$
    3. 随机选择$g(g\in \mathbb{Z}^*_{n^2})$；保证$n|ord(g)$（不懂）
    4. 定义$L(x)=\frac{x-1}{n}$
    5. $\mu =L(g^\lambda\ mod\ n^2)^{-1}\ mod\ n$

    私钥为$(n,\ g)$，公钥为$(\lambda,\ \mu)$

    • 通常还有个简化版
      $g=n+1$
      $\lambda=\varphi$
      $\mu=\varphi ^{-1}\mod\ n$

  • 加密

    1. $ 0\le m< n$
    2. 随机选择$r(0<r<n,\ r\in \mathbb{Z}^*_{n^2})$，且$gcd(r,\ n)=1$
    3. $c=g^m\cdot r^n\ mod\ n^2$

  • 解密

    1. $m=L(c^\lambda\ mod\ n^2)\cdot \mu\ mod\ n$

稍微验证简化版的Paillier，$\varphi(n^2)=n\varphi(n)=pq(p-1)(q-1)$

由欧拉定理可知$r^{n\varphi(n)}\equiv 1\ (mod\ n^2)$，带进解密函数，注意二项式展开，$L(c^\lambda\ mod\ n^2)=L(g^{m\lambda}\ mod\ n^2)=L((n+1)^{m\lambda}\ mod\ n^2)=L((1+nm\lambda)\ mod\ n^2)$$=m\lambda$

又因为
$\mu=L(g^\lambda\ mod\ n^2)^{-1}=L((n+1)^\lambda\ mod\ n^2)^{-1}=L((1+n\lambda)\ mod\ n^2)^{-1}=\lambda^{-1}$

则$m=m\lambda\cdot \lambda^{-1}=m$

这就要引入两条重要性质，RSA和ElGamal是乘法同态，Paillier是加法同态

  • 加法同态
    $$
    E(x+y)=E(x)\times E(y)\notag
    $$
    取个解密
    $$
    x+y=D(E(x)\times E(y))\notag
    $$

  • 乘法同态
    $$
    E(x\times y)=E(x)\times E(y)\notag
    $$

比赛的时候推到由二三四步求出一个key，回顾一下

只知道c1c2其中一个，直接用同态性是出不来的（可以试试看），必须配合攻击者精心构造的发送数据

根据已知，假设我们知道的是c1，m0m1完全由我们构造，最小是9
$$
c_1=E(m_0m_1key_1)\notag
$$
在二四步分别提供我们一个解密的机会，但是第四步不准用来解密第三步得到的其中一个c，那很好，用同态性绕过：不准我们直接给c解密，那么我们将c稍微变化一下

比如在第二步的时候我们send一个2过去，这样就得到了D(2)​，第三步m0m1随便取，然后在第四步，将c*2给send过去，由于
$$
c_1\times 2=E(m_0m_1key_1)\times E(D(2))=E(m_0m_1key_1+ D(2))\notag
$$
将c*2给send过去是作为密文用来解密的，那么得到
$$
D(E(m_0m_1key_1)\times E(D(2)))=m_0m_1key_1+D(2)\notag
$$
我们知道D(2)，m0m1也是由我们构造的，所以在一个循环里面解出一个key是没有问题的

比赛中的思路到此戛然而止，因为对于key那方面，是一个矩阵的乘法，我毫无头绪

在复现中，我看到了关键的东西

1
R = 2 * random.randint(0, 39)

这是控制key的，显然R是偶数，所以如果知道全部的key，然后将第四步我们求出来的查表如果是偶数那么说明随机数I是0，如果是奇数，那么I是1

于是这就有了我看到的很多战队WP里写的，利用key不变的机制去重复断开连接断开连接，不断炼丹直到求出所有的key

但按照出题人的意图，这个应该是非预期解了，设计加密方案的一方完全可以将key每次都随机化或者R就取random.randint(0, 79)；所以还是想在赛后看看有没有通过hint和key.sage来求key的

先来看主代码中key_gen的part2部分

1
2
3
4
5
6
7
8
_key = open("key", "r").read()
    key = []
    for i in _key.split("\n"):
        for j in i[1:-1].split(" "):
            if int(j) not in key:
                key.append(int(j))
    assert len(key) == 80
    assert key[0] == 119 and key[1] ==  241 and key[2] ==  718 and key[3] == 647

从代码中我们获取已知条件，key是个长度为80，且元素不重复的列表，前4个元素分别是119 241 718 647

key的生成与之类似，顺便得知key元素的范围

1
key = random_matrix(ZZ, 20, 4, x = 100, y =1000)

已知的是

1
hint = Matrix(key * vector([getRandomNBitInteger(1024) for _ in range(4)]) for _ in range(12))

$$
\begin{bmatrix}
119 & 241 & 718 & 647\\
\vdots & \vdots & \vdots & \vdots\\
\cdots & \cdots & \cdots & \cdots
\end{bmatrix}_{20\times 4}\times
\begin{bmatrix}
v1\\
v2\\
v3\\
v4
\end{bmatrix}=hint\notag
$$

重复做了12次，有12个hint，每次vector里面的数据都是随机的

韩佬说可能要用十二组hint构造格，然后格归约求解，不会

myRSA

很多师傅是使用二分法做的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# myRSA
from Crypto.Util.number import getPrime,bytes_to_long as b2l
from math import gcd
import hashlib
import random
import socketserver


KEYSIZE = 512
alpha = 2.0314159265358979
WELCOME = 'Welcome to use my better RSA!!!!!!So, what do you want now?'
menu = '1. encry \n2. getflag\n3. exit'
String = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz'

def proof_of_work():
    STR = ''.join([String[random.randint(0,len(String)-1)] for _ in range(16) ])
    HASH = hashlib.sha256(STR.encode()).hexdigest()
    return STR[:4],STR[4:],HASH

def key_gen():
    while True:
        p, q = getPrime(KEYSIZE), getPrime(KEYSIZE)
        e = 0x10001
        if gcd(e, (p - 1) * (q - 1)):
            break
    key = [getPrime(int(KEYSIZE * alpha)) for _ in range(128)]
    return (p, q, e), key

# encrypto
def encry(message,key,p,q,e):
    k1,k2 = key[random.randint(0,127)],key[random.randint(0,127)]
    x = p**2 * (p + 3*q - 1 ) + q**2 * (q + 3*p - 1)
    y = 2*p*q + p + q
    z = k1 + k2
    c = pow(b2l(message),e,p*q)
    return x * c + y * c + z


# get flag
def getflag(flag,key,p,q,e):
    return encry(flag,key,p,q,e)



class server(socketserver.BaseRequestHandler):
    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    def handle(self):
        START,END,HASH = proof_of_work()
        self._send('SHA-256(?+{}) == {}'.format(END,HASH))
        RCV = self._recv().decode()
        if RCV != START:
            return
        self._send("I'm a CryptoRookie,so my Crypto system take time, please wait a minute XD!")
        (p,q,e),key = key_gen()
        flag  = open('flag','rb').read()
        self._send(WELCOME)
        self._send('This is my public key:\nn = {}\ne = {}'.format(str(p*q),str(e)))
        for _ in range(16):
            self._send(menu)
            COI = int(self._recv().decode())
            if COI == 1 :
                self._send('Give me your message')
                message = self._recv()
                self._send('Your encry message:')
                self._send(str(encry(message,key,p,q,e)))
            elif COI == 2:
                self._send('This is your favourite:\n')
                self._send(str(encry(flag,key,p,q,e)))
            elif COI == 3:
                self._send('Bye~')
                break
class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

我的第一次密码学导论作业, 参数的生成大家觉得怎样呢？

加密的过程其实简单，我们知道cx+cy+z

关于z，这是与key有关的，根据之前的经验没有必要知道key怎么来的，只需要知道key是啥；至于题目提示的参数，也就是知道这些数字之间的位数关系，z是1040位的，z>n，n是1024位的

比赛中推导出要解一个一元三次方程那里，也就是将x和y带入，设t=cx+cy+z，得
$$
t=c((p+q)^3-(p+q)^2+(p+q)+4n)+z\notag
$$
c我们是完全可以算出来的，所以要解密，大致的方向就是绕过z，求出p+q，联系方程组求出p，成功分解n（所以send一个b’’得到z并没有什么用）

先两边模c

$$
c(x+y)+z\equiv 0+z\equiv z\ (mod\ c)\notag
$$
由于z比n要大，所以肯定也比c要大，模c之后得到是一个z的近似，就设为$z_0,\ z=z_0+kc$

联想刚才我们那个比特差，这完全是可以爆破的

nc链接这里我们直接输入0，从字节转数字后是48

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 102216849365436215382697924706110458811930514492676972297707749802743855550173221018307625399833159477899481939208157339087054049976609580335655988542843751320232525212725188253172284097958271570601093708102334730018773991294621754198973615453247445854418322094753657026256442996256624353675259431618058069873
m = 48
xy48z = int(450598196470521201729638145452113029348556317197796881155043711358014330871436047647028445722146485815337297082414583140339423018492548153129219959722626240768144197737361486759977936811931098179802464569494368735770535145331711573991601967230786754264479211792290017487283155570172424436304991171550181462694341945090942595408994085351622030775911067608201899849483976554235818404368211044759737328469487348797618306191053975483123755715899624408944673166452085511225808970644524141442606260074195698665970921069220120499790094140467744114859479550895214898485493704330419766829998576629979339401250867858230499864955508881386228059060521591637918403999691833618755763870139199224654474706077813985939903700333433229365768180014529732361680254103667001711146673764660846)
flag = 367985298100355719470464399231673186210476786528427647015381713693383054303800225562530305612381740440475705158111682270638520430798691039460739446257988390587750201598500460072950141405575319038364158570766686647844910095823628097948621068785641459446019851231163137871477328456219566424198083174973732247237495461084926082266277081410422432938607771568853035687579097465681519337154130220264871789653076508116420535916151874053965039332568736131529947962054505231214027124076372907141537134424968348626325641916288587742730444306999317712276831635493902127340833105337864025712574859765211691309758411102254824704082007127728486818136325623609908896494330215565717506933184069079577152226666507972552002709428549241805751962129348112606965895053348951420741781534761708
e = 0x10001
c = int(pow(m, e, n))
z0 = xy48z % c
var('x')
for k in range(65537):
    z = z0+c*k
    t = (xy48z-z)//c
    sol = solve([x**3-x**2+x+4*n-t==0], [x])
    if 'sqrt' not in str(sol):
        print(sol)

以为sage可以帮我们直接算出来了，但数字大了，也变慢了，而且不确定解出来的是不是还带有sqrt

所以要写另外的解方程脚本，这里我们暂时按下不表，先说解密

假设我们已经知道了pq，那么对于$t=flag(x+y)+z$，两边整除一个x+y，类似海洋大学的easyrsa，由于x+y远大于z，z成了小数部分了，取个整得到就是flag加密后的结果

好了，最关键的一步，解方程，现有的函数不行，因为数据太大、格式等问题
$$
x+y=(p+q)^3-(p+q)^2+(p+q)+4n=(t-z)\div c\notag
$$
右边我们已经得到了，设a=p+q，则$f(a)=a^3-a^2+a+4n-(t-z)\div c$

求一次导可知$f^{‘}(a)=3a^2-2a+1$，$\Delta=4-12<0$，$f^{‘}(a)>0$

所以f(a)是单调递增的，与x轴只有一个交点，而且它的根p+q的范围在$(2^{511}, 2^{513})$

说到解这个方程，枚举当然简单暴力，但无奈数字实在太大，时间复杂度为O(n)，那么很快就可以想到降低复杂度的二分法，用二分法逼近本身就是解方程的算法之一；这样时间复杂度就是O(logn)，也就是500多

加上之前的枚举z写了以下脚本，因为对近似不是很懂，所以先还是框定在熟悉的整数范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from sympy import poly, symbols, solve
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import invert
n = 89376247830772550635393374593591171289469473653660506041384870807672514851291613034103293150272794811662040962795338417767924390664160855795592847165664672215596625265833096358547808457216406919256623973605519954393257168668848139892103199585870486478679862843688695515256562706151337833114331221189851505307
m = bytes_to_long(b'0')
xy48z = 573183539558274845040105647253832611006389515982240063596818567154070335454441330456418916326928035506269242019877858095541028214384303624168930086298598137836679435122632007591230447675399859253040527098932082536817835600632684346743007442271210095370147310122023527616598189055800206892622591152310306250178532132575799836929460532267589534884854821163062186146162009389124822796655667824602408842104081327204184627274796695507250901179031687241027321102940261994875706732189407136668725738443141883613083605571514576490785426071453368710281928806135571137549546326030047579322709176195586142692435882988042924394657669689613769885662846359646103364540846219586145970778569409592707222106372820845133370558195785112000772658458805185628127184922396498760974419572604362
flag = 481729115764190744536910657085560158889970175686907401215490337526880230376819524492470636911767799236673524142385694360618832004117695823025161532124563697622558707411901261718979417287250753659221620598917189492752483245076665914783267295393931619281742213297076869813336749887922096598517333008819428035961760565398531704160502999798281136827037178130719826007120327143140435965940414720309889209176695802426545166579994960663962651160284302004216242606526094359968261816259941079928016610890122763028512785756541595874084647315002410857503747496456626710003349795505137331698911171491656135642059625243605709398076541265707971793648280382336060691064915972346110379252467007887636411312702061909523885468047172320514051839865352276472579281312844240544893396792447946
e = 0x10001
c = int(pow(m, e, n))
z0 = xy48z % c
x = symbols('x')
p = symbols('p')
q = symbols('q')
for k in range(2**16+1, 2**18):
    z = z0 + c * k
    t = (xy48z - z) // c
    _poly = poly(x ** 3 - x ** 2 + x + 4 * n - t)
    xy = poly(x ** 3 - x ** 2 + x + 4 * n)
    l = 2 ** 511
    r = 2 ** 513
    while l < r:
        mid = (l + r) // 2
        if _poly(mid) == 0:
            sol = solve([p * q - n, p + q - mid], [p, q])
            p = int(sol[0][0])
            q = int(sol[0][1])
            print(long_to_bytes(pow(flag // xy(p + q), invert(e, int((p - 1) * (q - 1))), n)))
            break
        elif _poly(mid) < 0:
            l = mid + 1
        else:
            r = mid - 1

结果还是跑了很久

研究一下其他师傅的做法

他们的思路是直接用得到的z0求出一个x+y的近似值，将其带入f(a)，得到是正数，说明这个数在真正的x+y的右边，根据单调性

image-20210825170440092

这个近似的x+y的位数是1538，所以只要在$[2^{511}, 2^{1538}]$之间二分就好了，最后会二分到两个相邻的整数之间，因为方程的右边是我们得到的近似值，所以妄想得到一个整数解是不太可能的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sympy import poly, symbols, solve
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import invert
n = 89376247830772550635393374593591171289469473653660506041384870807672514851291613034103293150272794811662040962795338417767924390664160855795592847165664672215596625265833096358547808457216406919256623973605519954393257168668848139892103199585870486478679862843688695515256562706151337833114331221189851505307
m = bytes_to_long(b'0')
xy48z = 573183539558274845040105647253832611006389515982240063596818567154070335454441330456418916326928035506269242019877858095541028214384303624168930086298598137836679435122632007591230447675399859253040527098932082536817835600632684346743007442271210095370147310122023527616598189055800206892622591152310306250178532132575799836929460532267589534884854821163062186146162009389124822796655667824602408842104081327204184627274796695507250901179031687241027321102940261994875706732189407136668725738443141883613083605571514576490785426071453368710281928806135571137549546326030047579322709176195586142692435882988042924394657669689613769885662846359646103364540846219586145970778569409592707222106372820845133370558195785112000772658458805185628127184922396498760974419572604362
flag = 481729115764190744536910657085560158889970175686907401215490337526880230376819524492470636911767799236673524142385694360618832004117695823025161532124563697622558707411901261718979417287250753659221620598917189492752483245076665914783267295393931619281742213297076869813336749887922096598517333008819428035961760565398531704160502999798281136827037178130719826007120327143140435965940414720309889209176695802426545166579994960663962651160284302004216242606526094359968261816259941079928016610890122763028512785756541595874084647315002410857503747496456626710003349795505137331698911171491656135642059625243605709398076541265707971793648280382336060691064915972346110379252467007887636411312702061909523885468047172320514051839865352276472579281312844240544893396792447946
e = 0x10001
c = int(pow(m, e, n))
z0 = xy48z % c
x = symbols('x')
p = symbols('p')
q = symbols('q')
t = (xy48z - z0) // c
_poly = poly(x ** 3 - x ** 2 + x + 4 * n - t)
xy = poly(x ** 3 - x ** 2 + x + 4 * n)
l = 2 ** 511
r = 2 ** 1538
while l < r:
    mid = (l + r) // 2
    if _poly(mid) < 0:
        l = mid
    else:
        r = mid
    # 相邻两个整数之间
    if r == l+1:
        a = l if l % 2 == 0 else r
        sol = solve([p * q - n, p + q - mid], [p, q])
        p, q = sol[0][0], sol[0][1]
        print(long_to_bytes(pow(flag//xy(p+q), invert(e, int((p - 1) * (q - 1))), n)))
        break

Random_RSA

之前也有类似的题目，通过相同的种子生成相同的随机数序列。这道题考点dp泄漏，对dp进行了异或操作；异或回来就好了

这里需要注意，出题人应该是用python2跑的，因为python3跑出来的随机数和题目中不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import *
import gmpy2
import libnum
import random
import binascii
import os

flag=r'flag{}'

p=getPrime(512)
q=getPrime(512)
e=0x10001
n=p*q
ct=pow(flag,e,n)
print("n="+ n)
print("ct="+ ct)

dp=r''
seeds = []
for i in range(0,len(dp)):
    seeds.append(random.randint(0,10000))

res = []
for i in range(0, len(dp)):
    random.seed(seeds[i])
    rands = []
    for j in range(0,4):
        rands.append(random.randint(0,255))

    res.append(ord(dp[i]) ^ rands[i%4])
    del rands[i%4]
    print(str(rands))

print(res)
print(seeds)

# n=81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
# ct=61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151

# [58, 53, 122] [145, 124, 244] [5, 19, 192] [255, 23, 64] [57, 113, 194] [246, 205, 162] [112, 87, 95] [215, 147, 105] [16, 131, 38] [234, 36, 46] [68, 61, 146] [148, 61, 9] [139, 77, 32] [96, 56, 160] [121, 76, 17] [114, 246, 92] [178, 206, 60] [168, 147, 26] [168, 41, 68] [24, 93, 84] [175, 43, 88] [147, 97, 153] [42, 94, 45] [150, 103, 127] [68, 163, 62] [165, 37, 89] [219, 248, 59] [241, 182, 8] [140, 211, 146] [88, 226, 2] [48, 150, 56] [87, 109, 255] [227, 216, 65] [23, 190, 10] [5, 25, 64] [6, 12, 124] [53, 113, 124] [255, 192, 158] [61, 239, 5] [62, 108, 86] [123, 44, 64] [195, 192, 30] [30, 82, 95] [56, 178, 165] [68, 77, 239] [106, 247, 226] [17, 46, 114] [91, 71, 156] [157, 43, 182] [146, 6, 42] [148, 143, 161] [108, 33, 139] [139, 169, 157] [71, 140, 25] [28, 153, 26] [241, 221, 235] [28, 131, 141] [159, 111, 184] [47, 206, 11] [220, 152, 157] [41, 213, 97] [4, 220, 10] [77, 13, 248] [94, 140, 110] [25, 250, 226] [218, 102, 109] [189, 238, 66] [91, 18, 131] [23, 239, 190] [159, 33, 72] [183, 78, 208] [209, 213, 101] [111, 50, 220] [166, 104, 233] [170, 144, 10] [187, 87, 175] [195, 59, 104] [165, 179, 179] [99, 247, 153] [195, 61, 100] [223, 159, 165] [230, 93, 184] [87, 28, 35] [35, 122, 38] [158, 188, 163] [229, 192, 222] [12, 12, 192] [207, 95, 224] [127, 113, 137] [22, 114, 143] [13, 45, 144] [70, 140, 211] [57, 101, 42] [132, 62, 129] [40, 128, 124] [1, 132, 161] [164, 33, 133] [252, 201, 32] [8, 18, 247] [1, 88, 55] [201, 135, 186] [101, 254, 125] [236, 196, 39] [148, 24, 103] [101, 29, 253] [97, 156, 64] [90, 103, 91] [50, 48, 80] [206, 22, 93] [11, 114, 174] [61, 132, 247] [215, 32, 232] [95, 128, 90] [57, 35, 228] [163, 143, 107] [178, 250, 28] [64, 107, 225] [106, 115, 207] [85, 134, 21] [118, 201, 76] [234, 34, 22] [241, 236, 122] [111, 185, 127] [1, 26, 164] [254, 57, 117] [243, 27, 32] [161, 88, 80] [50, 165, 93] [87, 182, 216] [184, 159, 63] [167, 166, 123] [37, 78, 33] [186, 81, 58] [48, 3, 239] [70, 186, 13] [56, 108, 178] [54, 55, 235] [105, 180, 105] [16, 194, 98] [136, 11, 41] [18, 203, 79] [185, 114, 170] [148, 181, 223] [118, 57, 160] [23, 250, 181] [235, 219, 228] [44, 151, 38] [185, 224, 134] [42, 162, 122] [3, 9, 158] [129, 245, 2] [66, 241, 92] [80, 124, 36]
# [55, 5, 183, 192, 103, 32, 211, 116, 102, 120, 118, 54, 120, 145, 185, 254, 77, 144, 70, 54, 193, 73, 64, 0, 79, 244, 190, 23, 215, 187, 53, 176, 27, 138, 42, 89, 158, 254, 159, 133, 78, 11, 155, 163, 145, 248, 14, 179, 23, 226, 220, 201, 5, 71, 241, 195, 75, 191, 237, 108, 141, 141, 185, 76, 7, 113, 191, 48, 135, 139, 100, 83, 212, 242, 21, 143, 255, 164, 146, 119, 173, 255, 140, 193, 173, 2, 224, 205, 68, 10, 77, 180, 24, 23, 196, 205, 108, 28, 243, 80, 140, 4, 98, 76, 217, 70, 208, 202, 78, 177, 124, 10, 168, 165, 223, 105, 157, 152, 48, 152, 51, 133, 190, 202, 136, 204, 44, 33, 58, 4, 196, 219, 71, 150, 68, 162, 175, 218, 173, 19, 201, 100, 100, 85, 201, 24, 59, 186, 46, 130, 147, 219, 22, 81]
# [4827, 9522, 552, 880, 7467, 7742, 9425, 4803, 6146, 4366, 1126, 4707, 1138, 2367, 1081, 5577, 4592, 5897, 4565, 2012, 2700, 1331, 9638, 7741, 50, 824, 8321, 7411, 6145, 1271, 7637, 5481, 8474, 2085, 2421, 590, 7733, 9427, 3278, 5361, 1284, 2280, 7001, 8573, 5494, 7431, 2765, 827, 102, 1419, 6528, 735, 5653, 109, 4158, 5877, 5975, 1527, 3027, 9776, 5263, 5211, 1293, 5976, 7759, 3268, 1893, 6546, 4684, 419, 8334, 7621, 1649, 6840, 2975, 8605, 5714, 2709, 1109, 358, 2858, 6868, 2442, 8431, 8316, 5446, 9356, 2817, 2941, 3177, 7388, 4149, 4634, 4316, 5377, 4327, 1774, 6613, 5728, 1751, 8478, 3132, 4680, 3308, 9769, 8341, 1627, 3501, 1046, 2609, 7190, 5706, 3627, 8867, 2458, 607, 642, 5436, 6355, 6326, 1481, 9887, 205, 5511, 537, 8576, 6376, 3619, 6609, 8473, 2139, 3889, 1309, 9878, 2182, 8572, 9275, 5235, 6989, 6592, 4618, 7883, 5702, 3999, 925, 2419, 7838, 3073, 488, 21, 3280, 9915, 3672, 579]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
import random

n = 81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
ct = 61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151
e = 65537

res = [55, 5, 183, 192, 103, 32, 211, 116, 102, 120, 118, 54, 120, 145, 185, 254, 77, 144, 70, 54, 193, 73, 64, 0, 79,
       244, 190, 23, 215, 187, 53, 176, 27, 138, 42, 89, 158, 254, 159, 133, 78, 11, 155, 163, 145, 248, 14, 179, 23,
       226, 220, 201, 5, 71, 241, 195, 75, 191, 237, 108, 141, 141, 185, 76, 7, 113, 191, 48, 135, 139, 100, 83, 212,
       242, 21, 143, 255, 164, 146, 119, 173, 255, 140, 193, 173, 2, 224, 205, 68, 10, 77, 180, 24, 23, 196, 205, 108,
       28, 243, 80, 140, 4, 98, 76, 217, 70, 208, 202, 78, 177, 124, 10, 168, 165, 223, 105, 157, 152, 48, 152, 51, 133,
       190, 202, 136, 204, 44, 33, 58, 4, 196, 219, 71, 150, 68, 162, 175, 218, 173, 19, 201, 100, 100, 85, 201, 24, 59,
       186, 46, 130, 147, 219, 22, 81]
seeds = [4827, 9522, 552, 880, 7467, 7742, 9425, 4803, 6146, 4366, 1126, 4707, 1138, 2367, 1081, 5577, 4592, 5897, 4565,
         2012, 2700, 1331, 9638, 7741, 50, 824, 8321, 7411, 6145, 1271, 7637, 5481, 8474, 2085, 2421, 590, 7733, 9427,
         3278, 5361, 1284, 2280, 7001, 8573, 5494, 7431, 2765, 827, 102, 1419, 6528, 735, 5653, 109, 4158, 5877, 5975,
         1527, 3027, 9776, 5263, 5211, 1293, 5976, 7759, 3268, 1893, 6546, 4684, 419, 8334, 7621, 1649, 6840, 2975,
         8605, 5714, 2709, 1109, 358, 2858, 6868, 2442, 8431, 8316, 5446, 9356, 2817, 2941, 3177, 7388, 4149, 4634,
         4316, 5377, 4327, 1774, 6613, 5728, 1751, 8478, 3132, 4680, 3308, 9769, 8341, 1627, 3501, 1046, 2609, 7190,
         5706, 3627, 8867, 2458, 607, 642, 5436, 6355, 6326, 1481, 9887, 205, 5511, 537, 8576, 6376, 3619, 6609, 8473,
         2139, 3889, 1309, 9878, 2182, 8572, 9275, 5235, 6989, 6592, 4618, 7883, 5702, 3999, 925, 2419, 7838, 3073, 488,
         21, 3280, 9915, 3672, 579]
dp = r''
rands = [[58, 53, 122], [145, 124, 244], [5, 19, 192], [255, 23, 64], [57, 113, 194], [246, 205, 162], [112, 87, 95],
         [215, 147, 105], [16, 131, 38], [234, 36, 46], [68, 61, 146], [148, 61, 9], [139, 77, 32], [96, 56, 160],
         [121, 76, 17], [114, 246, 92], [178, 206, 60], [168, 147, 26], [168, 41, 68], [24, 93, 84], [175, 43, 88],
         [147, 97, 153], [42, 94, 45], [150, 103, 127], [68, 163, 62], [165, 37, 89], [219, 248, 59], [241, 182, 8],
         [140, 211, 146], [88, 226, 2], [48, 150, 56], [87, 109, 255], [227, 216, 65], [23, 190, 10], [5, 25, 64],
         [6, 12, 124], [53, 113, 124], [255, 192, 158], [61, 239, 5], [62, 108, 86], [123, 44, 64], [195, 192, 30],
         [30, 82, 95], [56, 178, 165], [68, 77, 239], [106, 247, 226], [17, 46, 114], [91, 71, 156], [157, 43, 182],
         [146, 6, 42], [148, 143, 161], [108, 33, 139], [139, 169, 157], [71, 140, 25], [28, 153, 26], [241, 221, 235],
         [28, 131, 141], [159, 111, 184], [47, 206, 11], [220, 152, 157], [41, 213, 97], [4, 220, 10], [77, 13, 248],
         [94, 140, 110], [25, 250, 226], [218, 102, 109], [189, 238, 66], [91, 18, 131], [23, 239, 190], [159, 33, 72],
         [183, 78, 208], [209, 213, 101], [111, 50, 220], [166, 104, 233], [170, 144, 10], [187, 87, 175],
         [195, 59, 104], [165, 179, 179], [99, 247, 153], [195, 61, 100], [223, 159, 165], [230, 93, 184], [87, 28, 35],
         [35, 122, 38], [158, 188, 163], [229, 192, 222], [12, 12, 192], [207, 95, 224], [127, 113, 137],
         [22, 114, 143], [13, 45, 144], [70, 140, 211], [57, 101, 42], [132, 62, 129], [40, 128, 124], [1, 132, 161],
         [164, 33, 133], [252, 201, 32], [8, 18, 247], [1, 88, 55], [201, 135, 186], [101, 254, 125], [236, 196, 39],
         [148, 24, 103], [101, 29, 253], [97, 156, 64], [90, 103, 91], [50, 48, 80], [206, 22, 93], [11, 114, 174],
         [61, 132, 247], [215, 32, 232], [95, 128, 90], [57, 35, 228], [163, 143, 107], [178, 250, 28], [64, 107, 225],
         [106, 115, 207], [85, 134, 21], [118, 201, 76], [234, 34, 22], [241, 236, 122], [111, 185, 127], [1, 26, 164],
         [254, 57, 117], [243, 27, 32], [161, 88, 80], [50, 165, 93], [87, 182, 216], [184, 159, 63], [167, 166, 123],
         [37, 78, 33], [186, 81, 58], [48, 3, 239], [70, 186, 13], [56, 108, 178], [54, 55, 235], [105, 180, 105],
         [16, 194, 98], [136, 11, 41], [18, 203, 79], [185, 114, 170], [148, 181, 223], [118, 57, 160], [23, 250, 181],
         [235, 219, 228], [44, 151, 38], [185, 224, 134], [42, 162, 122], [3, 9, 158], [129, 245, 2], [66, 241, 92],
         [80, 124, 36]]


def leak_dp(n, p, e, c):
    q = n // p
    phi = (p - 1) * (q - 1)
    try:
        d = invert(e, phi)
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        return flag
    except:
        return


for i in range(0, len(seeds)):
    random.seed(seeds[i])
    rands = []
    for j in range(0, 4):
        rands.append(random.randint(0, 255))
        print(rands)
    dp += chr(res[i] ^ rands[i % 4])
dp = int(dp)
for X in range(1, e):
    # e * dp == (p-1) * X + 1
    if 0 == (e*dp-1) % X:
        p = (e*dp-1) // X + 1
        if 0 == n % p:
            flag = leak_dp(n, p, e, ct)
            print(flag)
            break

secret_share（not solve）