挨打日记

发表于 更新于 阅读次数： Waline： 本文字数： 3.9k 阅读时长 ≈ 14 分钟

记录部分题目

强网拟态决赛——BadRSA

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
from Crypto.Util.number import *

f = open('flag.txt','rb')
m = bytes_to_long(f.readline().strip())

p = getPrime(512)
q = getPrime(512)
e = getPrime(8)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
leak = d & ((1<<265) - 1)

print(f'e = {e}')
print(f'leak = {leak}')
print(f'n = {n}')
c = pow(m,e,n)
print(f'c = {c}')

'''
e = 149
leak = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299
'''

由$ed \equiv 1 \mod \phi(n)$

即$ed = k(p-1)(q-1) + 1$

两边同时模$2^{265}$，得$ed_0 \equiv k(p-1)(q-1) + 1 \mod 2^{265}$，这里$d_0 = leak$

$\therefore ed_0 \equiv k(pq - p - q + 1) + 1 \mod 2^{265}$

再同乘$p$，得到$ed_0p \equiv knp - kp^2 - kn + kp + p \mod 2^{265}$

因为$d \approx 1023bit$

所以$k < e$

爆破$k$，解方程得到$p$的低位，然后用copper恢复$p$

exp:

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
from Crypto.Util.number import *
import gmpy2

e = 149
d0 = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299

for k in range(1,e):
    var("p")
    temp = e*d0*p
    f = (k*n*p - k*p^2 - k*n + k*p + p) - temp  == 0

    roots = solve_mod([f],2^265)
    if roots != []:
        for root in roots:
            plow = int(root[0])
#             print(plow)
# 55136429770900518182274612434328885021714880080534773062619965935822096183916139
            R.<x> = PolynomialRing(Zmod(n))
            
            f1 = x*2^265 + plow
            f1 = f1.monic()
            res = f1.small_roots(X=2^247,beta=0.5,epsilon = 0.01)
            if res != []:
                print(res)
                # [188210689227294472160085325314952069542671020803828390144430392548173787275]
                p = int(res[0])*2^265 + plow
                print("p =",p)
                # p = 11158174168280917736979570452068827611755694573672250873587467083259280584739528118050085070475912733864211083865201596017044398008278425498714490994488939
                q = n // p
                d = gmpy2.invert(e,(p-1)*(q-1))
                m = pow(c,d,n)
                print(long_to_bytes(int(m)))
                # flag{827ccb0eea8a706c4c34a16891f84e7b}
                break

这里beta = 0.5是因为，对于度（即最大次方）为$d$的多项式，要求根小于$n^{\frac{\beta^2}{d} - \epsilon}$，而且要求因子$p > n^{\beta}$

此题$d = 1$，经过计算我们要求的根的上界为$2^{247}$，$\frac{247}{1024} = 0.2412$，所以取beta = 0.5可以恢复p

未知来源 ——多次共模

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
import gmpy2
from Crypto.Util.number import *
import random

from secret import flag

p = getPrime(1024)
q = getPrime(1024)
phi = (p-1)*(q-1)
n = p*q

g = random.randint(2, n-1)

round = 10
E = 1
print(f'n = {n}')
print('give you hand!')
for i in range(round):
    while True:
        e = random.randint(3, 2**128)
        if gmpy2.gcd(e, phi) == 1:
            break
    d = gmpy2.invert(e, phi)
    print(e, pow(g,d,n))
    E *= e
print('give me fight!')
C = int(input('> ').strip())
if pow(C, E, n) == g:
    print('Pa!!!!')
    print(flag)
else:
    print('Wrong!')

已知$e_1 … e_{10}$，$g^{d_1} … g^{d_{10}}$

$\because g^{d_1}\equiv (g^{d_1d_2})^{e_2}\mod n$，$g^{d_2} \equiv (g^{d_1d_2})^{e_1} \mod n$，（这里是硬凑的）

由扩展欧几里得算法得到$x,y$，使得$e_1x + e_2y = 1$

于是$(g^{d_2})^{x}\times (g^{d_1})^y \equiv (g^{d_1d_2})^{e_1x}\times (g^{d_1d_2})^{e_2y} \equiv (g^{d_1d_2})^{e_1x+e_2y} \equiv g^{d_1d_2}\mod n$

同理，继续凑一个$g^{d_1d_2} \equiv (g^{d_1d_2d_3})^{e_3} \mod n$

由扩展欧几里得算法得到$s,t$，使得$s(e_1e_2) + te_3 = 1$

于是$(g^{d_1d_2})^{t} \times (g^{d_3})^s \equiv (g^{d_1d_2d_3})^{e_3t} \times (g^{d_1d_2d_3})^{e_1e_2s} \equiv (g^{d_1d_2d_3})^{e_1e_2s + e_3t} \equiv g^{d_1d_2d_3} \mod n$

由此类推，直到我们求得$g^{d_1…d_{10}}$，令它为$C$

然后有$C^{e_1…e_{10}} \equiv (g^{d_1…d_{10}})^{e_1…e_{10}} \equiv g \mod n$

由此便完成攻击

需要注意的是，这个攻击需要e两两互素，所以不是百分百成功的，因为是交换题，可以一直刷，直到刷出正确的

这里提供一组可完成攻击的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
g =22136395143609454976723797324915375892465458460162538554758975512290330310462935478471377746705872023037585651562303930686697149598735182001433843661344683937481278553476043895994376093762632880498775801894554447925738051558752427375827779134424039708578534124740362818189228748172799480866657274093243750771952204622917969533264152347676918369536414076429004883207983132609122743468459666055848861325082710322928215402870897872649346566174889842248181216751672299720007671451631574647591976991860572724840491278478322071515991215048070720284195832197577116430301150596643004499815389085904519819007714828581479303762
n =24334747292037404112865160517613815174503142521512467118781752462256524846660202651608105021152838841464800848411610339632008109314593498904841254783833095524245344334259753072119599288639319161965306150794960077341342130818296593504205403952151140530444973126394974186321440434928979038126725143690709502951482793525467893618437766411113731723300068702568750603041490326932139922109533386219357059788591995997295396333041651361437650085297021821007580489992720617859571151109342601319066685152239942772654643207499625384861340006100368171656427450077500694366735001157949305918599711152983331850547469488734957458701
e1=80109013470482584561429027170542647747
c1=17168838142406187666524644206915238240655249084892146529640783916666817121252338756542365773327385343675883475098308052605873233419163716243066487421108047596747104087882739479394182239031885611433783658365703761198661047088062013808496947345568845961932656982694170194080768318217805419617274421904930725670867551418570910817667398771570753980178393517954774013086838338307224543084777676142092225425574461044218610874306794346811602272227397122041969569374373024610101412352688215798172394634186041548667561512725835488688765493033218342468771812426530140814011169524736787875606180643654013106714941704646695865267
e2=6454219972827877111299703069663455059
c2=4394728068138388191897233254377576335466841612404892531679430639425231443058954352547684920989986599764457777616351914322079018364993892208634840565133433778361087357582083971203031684547313840385442681979472687426962383338094489740283948582201939388826611714838525895085112767708957991801623254755689601559044068639057546786248305391647122828855703308724378316287116248717848191815234380775995125634672445917694161908682644731268760838340661971574337583899232922709148886721962000491282947717575405776220204601083793079271584801088036374457286264006724521055473173655030443235008631258153139057454073919436064930232
e3=42101634222112713431671486941143372695
c3=4581004962059487033646207072972232585581465907180041024995502630264714862124342908249609466308012912855337417246373564916886688534494470732816278292099393355439701667101542074061019097522359469681494066123839321496334208859352082991876715028774373112584617688494216833346737803643125920532390825083374666545637949013383149054303117717390897979627515422848359971030433749382516467905451243682855900490799457148607931591098922878250000881310432828411254912355976585465636698243503283516816872888621024487698618942116646165187237291876829531716820328304768617230478548735427682562365339631160604801074134824027538504696
e4=173516685810195045136493242835446951469
c4=11644264833270973839308128201657255350764050294685530813380782987348781486574306773781384343871251215891783008643037734176174823675357897792876437742225111922246161264330435089318255560613316983176069438234787527786197812321695163345079271939354875097485059357339488790354314183560473238024133260267071868481019692754325921722354302042429747413576748551405265051736982586658401354887951085292042361337206758799264446591035974747965267376821575289753470640680046800432006925714444296613334204798958609361474557437674849829070095037481793125538604657056702662343181209616756363394462003669236178478023523898847973222238
e5=55252937385114340149656092895036524601
c5=19545785560131771169215408497065064428487975386219125280585149330316146475572873815413048086109570770140286034862143515770659674691082419492185898037830991173371012420922107837433620341796455083068615051151312202166591933409649241633000993070344626732751482225339936777531680455018815749482439366758577676814349956346152615771478747064262502667455902438333397392526640068170634510686822274178145269030768640122161106113569189797889716774044369376371071674627827547143401279517830482139145611402904587811864648760994354631307155175708484705528824370123297443929157314513651509107121758787650126708587252799542805953517
e6=24681780289072133326361209064008770497
c6=19313732900765244706325537999685806961052588793055791540628791026317466045027812676672261976728944038676283147934103924089887921822421205351461613459447616068138047074160535704063274406055508592187188439964491717713317610423331916382728862333410002559176269287689154741776126939834091349952640019014453898754342523462948925369626815791755981927764986894869698369181316256023728505055253010615915068027977926899857033824040232676998986598403637223861179580424977901873755415196166123591651141288643100076144450344061973493937779805599431680896658131033898783887229941787805818606000016669139330136638363096657783669437
e7=143881904432810539900694531170626853231
c7=12989523566931771697065502053809115138368517944711308593911711797280537931346437104633108807244585472352456178649606227161847301136385778284185857955593272300302161954771356258288938783740117961004493011771345301718052053727786267865943180185344428775442225330281459026483256088461963839243836208786194554503674970567676505624910254875082989642769698027931886311440181894175424316600671359700701247231749470141444332260741695211889197959814024943977619246760245750408410104731881141625325242876165262628073956291185104065702222915740842846275162771866720279516598794230014751732627841485893747199995222964280852666131
e8=109733158267107101016123718788342740447
c8=9465499331274758285939016692045721466888773448825250640155454213342178338427519444285915305966908096737095708523804531647901026364431580466301218108203466993618175377568378100635420676364721184144506667771494193422972690027004985865829223712009495004657660578395990663297600489764478570015555943968850361399140980856827998016451024351077832123887331643440231016771034089324006496755117155414426787149067492688307535878264643029842331091939615723536721722598412663903809586327940027913734621409605073845430215398856640310860822592781083509687838572305234862394151484174700293395758419821311420347160593907010920605807
e9=286075265548878817466531187400022969759
c9=3120304551099235200989594437901010720215230743684261555102887535078408698616021481015593297678558818438368625863394473257358676058388212961787882238318715236884791751750761351215518801295828459825563949094641567872915749463138171809953494070609209024250803969419197219968855804280241213542721231391402250315315082082526745683381594343596001500846074031523765785412816201158490902180638309085745151114254704341313387625189803467814398479586744587060327983619788735211869824010183041871558873698968801155022839605505005098388291012051287918260130900733968252709776912887553009358004213033733282342448513824012676433523
e10=40371334924742398172003637747729169541
c10=6203858446495752360229983135729667621857796512578952860418207378981978529910273999396267892337184921112578272611072658955400497469061478376072623094557979238580016557032485749011634883744896291952836115827252436244245307671713411566356489517624806554188345503509465391657356602076526970334532155881940056562709382116010527584299750713687749163688425773926677703331219259296217589937465377914000516692144373926133083446344339154808035543565996596738049775391305512666480346390988136076685652331328465582817549441044590584822566008819215427071768153065719371081289221859894135336588760044436597897921936787253696177094

exp:

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
import gmpy2

f = open("output.txt",'r')

m = eval(f.readline().split("=")[-1])
n = eval(f.readline().split("=")[-1])

c = []
e = []
for i in range(10):
    ee = eval(f.readline().split("=")[-1])
    cc = eval(f.readline().split("=")[-1])
    c.append(cc)
    e.append(ee)
    
def decode(e1,e2,c1,c2):
    s,x,y = gmpy2.gcdext(e1,e2)
    c = pow(c2,x,n) * pow(c1,y,n) % n
    return c

cd1d2 = decode(e[0],e[1],c[0],c[1])
cd1d2d3 = decode(e[0]*e[1],e[2],cd1d2,c[2])
cd1d2d3d4 = decode(e[0]*e[1]*e[2],e[3],cd1d2d3,c[3])
cd1d2d3d4d5 = decode(e[0]*e[1]*e[2]*e[3],e[4],cd1d2d3d4,c[4])
cd1d2d3d4d5d6 = decode(e[0]*e[1]*e[2]*e[3]*e[4],e[5],cd1d2d3d4d5,c[5])
cd1d2d3d4d5d6d7 = decode(e[0]*e[1]*e[2]*e[3]*e[4]*e[5],e[6],cd1d2d3d4d5d6,c[6])
cd1d2d3d4d5d6d7d8 = decode(e[0]*e[1]*e[2]*e[3]*e[4]*e[5]*e[6],e[7],cd1d2d3d4d5d6d7,c[7])
cd1d2d3d4d5d6d7d8d9 = decode(e[0]*e[1]*e[2]*e[3]*e[4]*e[5]*e[6]*e[7],e[8],cd1d2d3d4d5d6d7d8,c[8])

C = decode(e[0]*e[1]*e[2]*e[3]*e[4]*e[5]*e[6]*e[7]*e[8],e[9],cd1d2d3d4d5d6d7d8d9,c[9])

E = 1
for i in range(len(e)):
    E *= e[i]
    
g = pow(C,E,n)
print(g == m)

2023山东省省赛

EasyRSA

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
from Crypto.Util.number import getPrime,bytes_to_long
from random import randint
from gmpy2 import *

m = bytes_to_long(b'flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}')

p=getPrime(1024)
q=getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
p_2=((p>>128)<<128)
Result = []
Divisor = []
for i in range(12):
    Divisor.append(getPrime(128))
for i in range(12):
    Result.append(p_2%Divisor[i])



print(c,n,Divisor,Result)
'''
output:
16054555662735670936425135698617301522625617352711974775378018085049483927967003651984471094732778961987450487617897728621852600854484345808663403696158512839904349191158022682563472901550087364635161575687912122526167493016086640630984613666435283288866353681947903590213628040144325577647998437848946344633931992937352271399463078785332327186730871953277243410407484552901470691555490488556712819559438892801124838585002715833795502134862884856111394708824371654105577036165303992624642434847390330091288622115829512503199938437184013818346991753782044986977442761410847328002370819763626424000475687615269970113178 
23074300182218382842779838577755109134388231150042184365611196591882774842971145020868462509225850035185591216330538437377664511529214453059884932721754946462163672971091954096063580346591058058915705177143170741930264725419790244574761160599364476900422586525460981150535489695841064696962982002670256800489965431894477338710190086446895596651842542202922745215496409772520899845435760416159521297579623368414347408762466625792978844177386450506030983725234361868749543549687052221290158286459657697717436496769811720945731143244062649181615815707417418929020541958587698982776940334577355474770096580775243142909913
[205329935991133380974880368934928321273, 274334866497850560640212079966358515253, 264739757264805981824344553014559883169, 314495359937742744429284762852853819407, 197513216256198287285250395397676269263, 194633662721082002304170457215979299327, 320085578355926571635267449373645191637, 310701821184698431287158634968374845899, 198238777199475748910296932106553167589, 292201037703513010563101692415826269513, 332238634715339876614712914152080415649, 334257376383174624240445796871873866383]
[108968951841202413783269876008807200083, 29053101048844108651205043858001307413, 243503157837867321277650314313173163504, 160933173053376016589301282259056101279, 53063624128824890885455759542416407733, 34980025050049118752362228613379556692, 132553045879744579114934351230906284133, 160998336275894702559853722723725889989, 87211131829406574118795685545402094661, 36445723649693757315689763759472880579, 11133325919940126818459098315213891415, 1404668567372986395904813351317555162]
'''

CRT得到p的高位，再CopperSmith

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import *
from functools import reduce

c=
n=
Divisor=
Result=

result = crt(Result,Divisor)
print(result)
p_high = result

R.<x> = PolynomialRing(Zmod(n))
f = p_high + x
roots = f.small_roots(X = 2^128,beta=0.4)
if roots:
    p = p_high + int(roots[0])
    q = n // p
    d = gmpy2.invert(mpz(65537),mpz((p-1)*(q-1)))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))
    # flag{2233747d3bf06f070048e80300dac75f}

未知来源——多次共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
n= 11672019302452791847976885139444631215461587185717078202624003924652951501798384922503898316362903060176081013552938226213011583751926194924396393418200651
e1= 37225285522048136640234665763046515323975509553621367657869064354936271714829346249434627374319
c1= 6561722503245252326473053673931040930595312994943980248495845399811061479424894049448701395583033072492090543775264658233447269792082269923634944044048256
e2= 70315276642197782765663176680921382778458161267671069199886568041544910757703388867999283216163
c2= 9066268516840187719542778544704780714171982540841490634414621855403984061059739999874863413132321650373233970883703949578287256313808334696472977486324913
e3= 58837722071754802848691484671357909781375192830519619984728820904241517467527927917135829010379
c3= 730854709209141236091580301314373586143021167616383007322134713546247591542340712258626648615405228669556469908924732371622895444546773648310427525959172
e4= 39962739918421564384514799600347097815718411244203624166594989321985600148885015490096249377807
c4= 8108849016571769502794280186251611513990470823260478636285626060116720170476186696634283894490546942075655268700445495749546968653904937741195898959273980
e5= 13674264940531101583993023214988209465694922107852800127773093452790552973417619144140118040733
c5= 10872298284524544458837665238479335285081693337094151700583969438305415460105492220388361549493071304913191336037120105186380797009744966714309842659475365
e6= 59147351162492841726778830667407599619308114751273828762593642198074445917721385886537215917201
c6= 11296598073089872245831685958996723544918273046720124943231496825155755869691947790362561866005131404407380922096357780152157765492707383368897855598481051

根据常规共模攻击的思路，$e_1$与$e_2$互素，利用扩展欧几里得求$x,y$

使得$e_1x+ e_2y = 1$

于是$c_1^x\times c_2^y = m^{e_1x + e_2y} \equiv m \mod n$

本题有6组$e$，经过检验，gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(e1,e2),e3),e4),e5),e6) = 1

所以多次共模攻击即可求解

exp:

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
from Crypto.Util.number import *
import gmpy2

n = 11672019302452791847976885139444631215461587185717078202624003924652951501798384922503898316362903060176081013552938226213011583751926194924396393418200651
e1 = 37225285522048136640234665763046515323975509553621367657869064354936271714829346249434627374319
c1 = 6561722503245252326473053673931040930595312994943980248495845399811061479424894049448701395583033072492090543775264658233447269792082269923634944044048256
e2 = 70315276642197782765663176680921382778458161267671069199886568041544910757703388867999283216163
c2 = 9066268516840187719542778544704780714171982540841490634414621855403984061059739999874863413132321650373233970883703949578287256313808334696472977486324913
e3 = 58837722071754802848691484671357909781375192830519619984728820904241517467527927917135829010379
c3 = 730854709209141236091580301314373586143021167616383007322134713546247591542340712258626648615405228669556469908924732371622895444546773648310427525959172
e4 = 39962739918421564384514799600347097815718411244203624166594989321985600148885015490096249377807
c4 = 8108849016571769502794280186251611513990470823260478636285626060116720170476186696634283894490546942075655268700445495749546968653904937741195898959273980
e5 = 13674264940531101583993023214988209465694922107852800127773093452790552973417619144140118040733
c5 = 10872298284524544458837665238479335285081693337094151700583969438305415460105492220388361549493071304913191336037120105186380797009744966714309842659475365
e6 = 59147351162492841726778830667407599619308114751273828762593642198074445917721385886537215917201
c6 = 11296598073089872245831685958996723544918273046720124943231496825155755869691947790362561866005131404407380922096357780152157765492707383368897855598481051
# print(gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(gmpy2.gcd(e1,e2),e3),e4),e5),e6)) = 1

def decode(e1,e2,c1,c2):
    s,x,y = gmpy2.gcdext(e1,e2)
    res = pow(c1,x,n) * pow(c2,y,n) % n
    return res

res1 = decode(e1,e2,c1,c2)
res2 = decode(e3,gmpy2.gcd(e1,e2),c3,res1)
res3 = decode(e4,gmpy2.gcd(e3,gmpy2.gcd(e1,e2)),c4,res2)
res4 = decode(e5,gmpy2.gcd(e4,gmpy2.gcd(e3,gmpy2.gcd(e1,e2))),c5,res3)
res5 = decode(e6,gmpy2.gcd(e5,gmpy2.gcd(e4,gmpy2.gcd(e3,gmpy2.gcd(e1,e2)))),c6,res4)
flag = long_to_bytes(res5)
print(flag)

2023长城杯——p+q高位泄露

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

BITS = 233

def broken(x, bits):
    return x>>bits

def gen():
    p,q = getPrime(512),getPrime(512)
    n = p*q
    e = 65537
    return n, broken(p+q, BITS)

n, hint = gen()
e = 0x10001
m = bytes_to_long(flag)
assert m < n
c = pow(m, e, n)

print(n)
print(hint)
print(c)

'''
107847645025513535850791225440130707186374273414737521825714442885442542984529827092766916748308266623066053421754530398675086374798530909982183476265477598220972320436343536618913608933549054793948336438240303192183575843300257235195070331758555882832698815894168120103459360566404203412796086643598204242029
1505246122706281178983443268987790509406564031452059494152554645294649335244676839890
16589212605025468264862689939961340646400626438824064459026078002373801735937861932598660491280834517490394340315480853421268981930217857435669572426110105938015092688880859031418213297139875807487434491329423279700179082306961439610731922669459168752958192842026918421354512654494583087220572962719510130677
'''

爆破。好久好久

exp:

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
#sage
N = 107847645025513535850791225440130707186374273414737521825714442885442542984529827092766916748308266623066053421754530398675086374798530909982183476265477598220972320436343536618913608933549054793948336438240303192183575843300257235195070331758555882832698815894168120103459360566404203412796086643598204242029
gift = 1505246122706281178983443268987790509406564031452059494152554645294649335244676839890
gift = gift<<233
 
PR.<x> = PolynomialRing(Zmod(N))
ok = False
test=1
def pq_add(tp,tq,tgift,idx):
    global ok 
    global test
    if ok:
        return 
    if tp*tq>N:
        #print('>')
        return 
    
    if (tp+(2<<idx))*(tq+(2<<idx))<N:
        #print('<', hex((tp+(1<<(idx+2))))[:20], hex(tq+(2<<idx))[:20], hex(N)[:20])
        return 
        
    if idx<=233:
        try:
            test += 1
            print(test)
            for i in range(1024):
                tpp = tp+(i<<223)
                f = tpp + x 
                test += 1
                rr = f.monic().small_roots(X=2^223, beta=0.4)
                if rr != []:
                    print(rr)
                    print(tpp)
                    print('p = ',f(rr[0]))
                    ok = True
                    return
        except:
            pass
        
        return
    
    idx -=1
    b = tgift >>idx 
    one = 1<<idx
    
    #print(hex(tp)[:20],hex(tq)[:20],hex(tgift)[:20],idx,b)
    
    if b==0 or b==1:
        pq_add(tp,tq,tgift,idx)    
    if b==1 or b==2:
        pq_add(tp+one,tq,tgift-one,idx)
        pq_add(tp,tq+one,tgift-one,idx)
    if b==2 or b==3:
        pq_add(tp+one,tq+one,tgift-(one<<1),idx)
        
        
tp = 1<<511
tq = 1<<511
tgift = gift -tp -tq 
pq_add(tp,tq,tgift,511)
print(test)
print("OK")
print("111111111111")
# p = 10671810890705142935923698352497956126372923054885272713948800012376136275817384032407712447142702386637160839942871245602734437654810217233791561733480407

求出p后，正常求解

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2

n = 
p = 10671810890705142935923698352497956126372923054885272713948800012376136275817384032407712447142702386637160839942871245602734437654810217233791561733480407
c = 

q = n // p
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#flag{ccc2e285-7bb1-484e-ad62-58cc474ef9d4}

另外一种求解：

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
from Crypto.Util.number import *
import gmpy2

N = 107847645025513535850791225440130707186374273414737521825714442885442542984529827092766916748308266623066053421754530398675086374798530909982183476265477598220972320436343536618913608933549054793948336438240303192183575843300257235195070331758555882832698815894168120103459360566404203412796086643598204242029
gift = 1505246122706281178983443268987790509406564031452059494152554645294649335244676839890
c = 16589212605025468264862689939961340646400626438824064459026078002373801735937861932598660491280834517490394340315480853421268981930217857435669572426110105938015092688880859031418213297139875807487434491329423279700179082306961439610731922669459168752958192842026918421354512654494583087220572962719510130677

RF = RealField(1024)
X = polygen(RF)
f =X*((gift << 233)-X) - N
# print(f.roots())
P = int(f.roots()[0][0])

kbits = 245

P_high = (P >> shift) << shift
PR.<x> = PolynomialRing(Zmod(N))
f1 = x + P_high
x0 =f1.small_roots(X=2^shift, beta=0.4,epsilon=0.01)[0]
p = P_high+x0
print(f"p = {p}")
q = N // int(p)
phi = (p-1)*(q-1)
d = gmpy2.invert(65537,gmpy2.mpz(phi))
m = pow(c,d,N)
print(long_to_bytes(int(m)))
#flag{ccc2e285-7bb1-484e-ad62-58cc474ef9d4}

2

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
from Crypto.Util.number import *
from random import randint
from gmpy2 import *

flag = b'xxx'

def get_secretkeys():
    while True:
        m = 2 ** 3
        a = getRandomNBitInteger(128)
        b = getRandomNBitInteger(128)
        if a > b :
            continue
        if b > 2 * a:7
            continue
        ra_ = randint(1000,10000)
        p_ = pow(a,m) + ra_
        p = next_prime(p_)
        ra = p - p_ + ra_
        rb_ = randint(1000, 10000)
        q_ = pow(b, m) + rb_
        q = next_prime(q_)
        rb = q - q_ + rb_
        
        if ra > 100000 or rb > 100000:
            continue
        if b > iroot(2 * pow(a, m) + ra, m)[0]:
            continue
        if ra > 2 * iroot(a,m//2)[0] or rb > 2 * iroot(b,m//2)[0]:
            continue
        break
    return p, ra, int(p).bit_length(), q, rb, int(q).bit_length()

p, ra, len_p, q, rb, len_q = get_secretkeys()

n = p * q
m = bytes_to_long(flag)
e = 0x10001
ct = pow(m,e,n)

print(f'ra = {ra}')
print(f'rb = {rb}')
print(f'len_p = {len_p}')
print(f'len_q = {len_q}')
print(f'n = {n}')
print(f'ct = {ct}')

'''
ra = 8607
rb = 7150
len_p = 1024
len_q = 1024
n = 28098722633030488893312283528887829649553659514053781575839443778746567710358683558509768930786261053897116586758341172713231425712608663734433267335002333760261583976848753337338129716792124202066388265994360580739266657504481707827816610267011366001142300093926601793983384666604377328323493638248481764153911921310476848622133065363121266256704484624454408157373499690818152144645904269865423396689289703578108901228755055729490144039004436875090060394642072739901593627031008002995026214521011417826487454434739123729500727953687489123493596702814564384266479646307886530097993679086392267067430262508230063492593
ct = 1361368491194202361715607865372797868849909740139730895054740999951755977992724940480130958163781061991384502597774968578284702191375825258332749459177999721414531960173967638050842294432428891589365478524879091438660354502169037756949918455465931069407443747905678846811248473459896942787043705093661155283970943862884656259675846526304020149516360300122739147864690004414833366319773397061007864065322841302908571648122903295064833926287970664637537668175501504866705196230324464962122113398544393881450146243000410853975781504185685414280739943390199620950135398253008721600717727922668728798959184802994979420495
'''

$\because q’ = b^8 +rb’ $

$q - q’ =q - b^8 - rb’$

$q-q_ + rb_ = q-b^8$

$\therefore rb = q - b^8$

同理

$ra = p - a^8$

$\therefore p = a^8 + ra$，$q = b^8 + rb$

$\therefore n = pq = (a^8+ra)(b^8+rb) = (ab)^8 + ra\times b^8+rb\times a^8 + ra\times rb$

因为$a^8 + ra \approx a^8$，$\therefore n \approx a^8b^8$

n开8次方得到$ab$，再结合 $n=(ab)^8 + ra\times b^8+rb\times a^8 + ra\times rb$解方程组

exp:

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
#sage
from Crypto.Util.number import *
import gmpy2

e = 65537
ra = 8607
rb = 7150
n = 
ct = 

# ab = int(gmpy2.iroot(n,8)[0])

# var("a,b")
# f1 = a*b - ab
# f2 = ab^8 + ra*b^8 + rb * a^8 + ra*rb - n
# ans = solve([f1,f2],[a,b])
# print(ans)

a = 334500267976593357847948592364017458136
b = 340164785123729724868130765428093274671
# print(isPrime(b))
# print(int(b).bit_length())
p = a^8 + ra
q = b^8 + rb

d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(ct,d,n)
print(long_to_bytes(int(m)))

注意一下a和b的大小即可

2023江苏省首届数据安全竞赛

题目：

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
from Crypto.Util.number import *

def pad(msg):
    return msg + b'\x00' * (2048 // 8 - len(msg))


def day():
    print("# == Day Time == #")
    A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']

    from notebook import pubkeys
    hint = str(A)[1:-1].replace(', ', '||').encode()
    hint = bytes_to_long(pad(hint))
    package = []
    for pubkey in pubkeys:
        e, n = pubkey
        package.append(pow(hint, e, n))
    print(f"{package = }")

    return A


def night(A):
    print("# == Night Time == #")
    from secrets import secret

    p, q = [getPrime(1024) for _ in '01']
    e, n = 0x10001, p * q
    message = bytes_to_long(pad(secret))
    ciphertext = pow(message, e, n)
    print(f"{e = }")
    print(f"{n = }")
    print(f"{ciphertext = }")

    core = getRandomRange(1 << 70, 1 << 80)
    box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
    shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n
    print(f"{shell = }")

A = day()
night(A)

附件1：

1
2
3
4
5
6
7
# == Day Time == #
package = [11348275592172789430802632398715397831929456592129727148350341695822097922745546634103895397114240780119492097879709874341733998189314701220819602086989170395665694216144611451695210776788208725517321710496401109614989729783280209806513298851774400705822274570042128297336679615535569295725037051009221966882907606741910671983811835353310553679554656322510247012465612842055583530354825164440556725066351429241835394579392892121937744444324723509039593320520073762479405487678614235658010109343868772211070874500834820005557924944766175445227592086997786601600141172729543326022039897279215360210475222205314199752358, 11817047514083750028443306573161291960303002458276716688201587284992675854178250185695613342603396451495053496021018943618684096193774851513377343785523373066637422156529843356640438514917147007662989366432951340073247573347091422478343675687872524102452812391963856179412214914106817415620613886827405526709334122157218264253412138947978859771457788135381194396144386611627935519990330309154612803264373276472523863776757124489507206744895878709136339189551422814752920383697719212261820943113370067423118794871570596583232694067119303936516491830190746798281923693136901268220982292626728815051587839682733501582997, 3131427695639074007646625687827523632044624200167725001731246731463369200890045250738898155425873822581405723445926216099453276470655307513244478613248253397941362848890729091875615893643288181126353294271063912991208029628896380928878098320509891044728414542705582996774991148116051162157848421643082210867849206627757941596203046799655123006406284498009424107637970927771132706399889289085811447333980744767367889464364519571965014435281718495338752896521777070285880327861778156398424643033288480056322928449210425585380975486759287881877636187364299666207762828705236236071045450767253946524067440138527952996304, 3345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443, 689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
# == Night Time == #
e = 65537
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665

附件2：

1
2
3
4
5
6
7
pubkeys = [
    [13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]

day主要是把填充后的hint进行5次同e，n的加密。

第一反应应该是用中国剩余定理进行求解，但是填充后的hint约2048bit，5组n是不够求解的。

分析pad，发现pad函数只是在msg后面填充上许多00

于是根据$c \equiv m^e \mod n$可以推出$c \equiv (m’ \times pad)^e \mod n$

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

def pad(msg):
    return msg + b'\x00' * (2048 // 8 - len(msg))

A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']

hint = str(A)[1:-1].replace(', ', '||').encode()
hint1 = bytes_to_long(hint) 
hint2 = bytes_to_long(pad(hint))

print(hex(hint2 // hint1))

自己测试几组数据发现填充的内容大概是

0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

实际可以把填充内容减少一些0

于是我们有$c \equiv m’^e \times pad ^e \mod n \longrightarrow m’^e \equiv c \times (pad^e)^{-1} \mod n$

m'大约560bit

到此，我们有了5组新的c，可以用中国剩余定理求解了

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
#sage
from Crypto.Util.number import *
import gmpy2

package = [, , , , ]
pubkeys = [
    [13, ],
    [13, ],
    [13, ],
    [13, ],
    [13, ]
]
N = []
for i in range(5):
    N.append(pubkeys[i][1])
c = []
e = 13
pad = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

for i in range(5):
    cc = int(package[i] * pow(pad,-13,N[i]))
    c.append(cc)
    
C = CRT_list([c[0],c[1],c[2],c[3],c[4]],[N[0],N[1],N[2],N[3],N[4]])
m = gmpy2.iroot(C,e)
print(long_to_bytes(int(m[0])))

得到hint = 646919678902||598613162045||90472013741||917100488664||838250498519\x00

我们便得到了A

想先通过方程shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n，来求解box

但是没成功

请教了一下Van1sh师傅，他说一般roots解二次方程，而且一般得模素数

换个思路，通过

1
2
3
core = getRandomRange(1 << 70, 1 << 80)
box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n

我们发现$shell \equiv A[4]\times core^4 + A[3]\times core^3 + A[2]\times core^2 + A[1]\times core + A[0] \mod p$

$core$给出范围，可以通过copper求解

求解出$core$后，$kp =shell - A[4]\times core^4 + A[3]\times core^3 + A[2]\times core^2 + A[1]\times core + A[0]$

求$kp$和$n$公因数便可得到p

exp:

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
from Crypto.Util.number import *
import gmpy2

package = [, , , , ]
pubkeys = [
    [13, ],
    [13, ],
    [13, ],
    [13, ],
    [13, ]
]
N = []
for i in range(5):
    N.append(pubkeys[i][1])
c = []
e = 13
pad = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

for i in range(5):
    cc = int(package[i] * pow(pad,-13,N[i]))
    c.append(cc)
    
C = CRT_list([c[0],c[1],c[2],c[3],c[4]],[N[0],N[1],N[2],N[3],N[4]])
hint = gmpy2.iroot(C,e)
print(long_to_bytes(int(hint[0])))

A = [,,,,]
shell = 
n = 
ciphertext = 

R.<x> = PolynomialRing(Zmod(n))
f = (A[4] * x^4 + A[3] * x^3 + A[2] * x^2 + A[1] * x + A[0]) - shell
f = f.monic()
ans = f.small_roots(X=2^80,beta=0.4,epsilon=0.02)
print(ans)

core = 
kp = shell - (A[4] * core^4 + A[3] * core^3 + A[2] * core^2 + A[1] * core + A[0])
p = gmpy2.gcd(kp,n)
q = n // p
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(ciphertext,d,n)
print(long_to_bytes(int(m)))
#b'Your flag is: flag{8d24d7d491106a7974d5afe9342b2834}

祥云杯线下（高校组）

ezmath——未解决

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
from secret import flag
from Crypto.Util.number import *
total_bit = 512
def make_para(bit_size):
    P = getStrongPrime(bit_size)
    Q = getStrongPrime(bit_size)
    N = P * Q
    magic = (N + 1) * (N + P + Q + 1) + (P - Q) ** 2 + N
    d = int(0.394 * bit_size)
    e = inverse(d, magic)
    k = d * e // magic
    return (N, e), (P, Q, k)
pubkey, sec_key = make_para(2 * total_bit)
flag = bytes_to_long(flag) * sec_key[2]
p = getStrongPrime(total_bit)
q = getStrongPrime(total_bit)
n = p * q
e = 65537
c = pow(flag, e, n)
t = ((p - getRandomNBitInteger(16)) * sec_key[0] + q) % sec_key[1]
with open('output.txt', 'w') as f:
    f.write(str(pubkey) + '\n')
    f.write(str((t, c)))
 
"""
N,e=(21136120517038375343657055317361461947217610380415290931285704769845405139443342030139838613845989765254932385503454684656325859309861269837188207923942223163348944160792729101485975484543693998035828762630825174735962679103457025646672449491007685400869138263581883506767852264244013623583813540066115060793144049256890248337903932112449333735324371400873419104520104079223733159263094092843185909770131443506433825708789563521497940390674504488024226655482568491358458107989880756229607524452273305978138461190013290440068226454238375505010225133919526068226837545142734502100757510899741312502285931571783851666429, 291542085122413541028076006933740091355832744332602513957292369860771664833892358795585946753279254101863581542678927529330607906769804928526978686071141386341893467977451552634615917127445748737712286687041822255325772392569586666055711202824870471562051621883329559663555059967665101455578668904247279540014709971958403913939101728330638301270881265277488332145439522278871554725936095617940701105161078332467466405454007283937177070102098256744642045839067405705972784471374421818844770106228499198315920181837950503279178647052157269318876892192700670366858062171759498850112906238502375693099462427930964555274451795362167393410749436026095037695100430810204847979914959732383773952788768239221142673268839750770222737928397507645337714199166919835667638401309062163501094032890215821366318775462220119081175885338966308921205861717088926659072208866126879068213582499260316364548817213314952246293713853884872460934174624844462586276340207505217646013915381902979372875919823493439285174120160656952728493383464761519634974414670811896809158801804891938928244053980210687334268664219571818927285279999791212932795196689285015367417706597781418431735001428656415752334850685705212368666855124013583549768407830008606258798409140)
t,c=(18872151984199200051633005759140295224788252451326410141022483203855894790958837408470348915966212063467995292461061069273539234939320647533902914083943444743748789975745514239518406829738286900177972974033143896932863898553599888597165054837513698667686277110587659188172271629973371164557353473146831275972, 47672712219012743425382676880904671136942826695249149129159924785186563239747047304204962529935078111450524236186612259355850306867579998685662967391936502046679744616903469002187225791339629835786750259999982506494377133775859573660632942293353420327987860136624649402598383416748766985203781387716072244402)
"""

安徽省省赛——rwx

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
from flag import flag
from Crypto.Util.number import long_to_bytes,bytes_to_long
from os import urandom
import hashlib

def know(m):
    r=[]
    w=[]
    x=[]
    e=[]
    for i in m:
        r.append(bin(ord(i))[-1])
        w.append(bin(ord(i))[-2])
        x.append(bin(ord(i))[-3])
        e.append(ord(i)>>3)
    return r,w,e,x

def inf(r,w,x,files):
    re=[]
    for i in range(len(files)):
        re.append(long_to_bytes(int(bin(bytes_to_long(files[i]))[2:]+r[i]+w[i]+x[i],2)))
    return re

r,w,e,x=know(flag)
files=[]
f=open("output","wb")
for i in range(len(flag)):
    files.append(urandom(8))
for i in files:
    f.write(i.encode("hex")+"\n")
files=inf(r,w,x,files)
for i in files:
    f.write(hashlib.sha256(i).hexdigest()+"\n")
for i in e:
    f.write(hashlib.sha256(str(i)+urandom(2)).hexdigest()+"\n")

print r
print w
print x
print e

output

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
abb490d5efe69766
a42c15dd0717102b
ee0d2fc5c7351947
4876242f69135f77
f7f7e8648cf39204
594b5fb7c4396a5d
5b254e10bc3f2e83
d27b465c51cb56aa
02fde9f77e201f13
5a5a717c5610113c
0228c96208f04be7
1f21b57c69e164c6
eb9ff8ed6de6ae5a
e9ff62161ebfd07f
fc92701a784575fb
246fb05d1f5a6f74
91a9a630e9e91e8b
c27160d38c8b8247
4b473325d4de665c
d1c1b9a58ca6d1e5
818cf44df4d7b088
569014c59066b916
408fb2edb34c77a9
d24576a95ddc151c
9284b46648b92a5c
073f776f6a36eb4a
1b9a6ff58b537364
9a327f0ff86f7687
be0fe6df6ce0726f
98734efb617a527b
3e0e772fd9669166
af8f0e61263ad605
326c9434cc213d55
5d6df6d0425fd13c
c798fca9337f4e09
b8b44901c1e2847c
39c7932c6c9565d8
0df12d3f4023f6cf
df47f8efee88f469
92bbcc351d041479
77b55a5574fa0830
24b60c00c2cda9c2
3c00ce8fad4bdb0e
3368003bfbca99e727ddfe6de1976fe7133392ddcf1e9b858af76aec41a3a0d6
e5cf55af23a0c8b42b4d9f22d1c9dfc2b04a22c0202cd35c783bbf9b82e79525
54ad655d2f450d96eb0198dd620758cbddc8987656b195df04a5e254447e9f19
d093a5e18283d59816ed32156eaaabe64fc2575bc3cee6b4fccf6325d4b669a3
8d32f93d356a459e8c2807c91ab52581c2d3ea225187b8fc2b7d6dc0dbf81500
8778e6d1901c10b1d1090c32cef6aeb36702d37dceac8c0e5a16356473f82a15
090bfe2dd0be43160b406e6b33845c6c5bde6bf47d466d26b7f69ea896eddfdd
91e3ece70e184e3f768925751fb5a0c2cf9369d6bc268464cd2737af38dea781
f16f4fae20ae181dc5a332e423a2a79fb3e2d28f072cb7ba2f8a0b29e2c1c698
b5efdd3705fcf45d3b330202e0387ab9d24c1b79af9577ba0563b669d420723d
d31afdf0eb4149e516658867b07b3032ec3d685f2eb68a565249f4f439a688fa
ac039fae367745a39019561e4f9f953068d0b4639c19a5eaf7a05abc46e734e0
f09637c3a24c14ad0d4fd442ede44009f85f898d506f9ba7a8563650cc4068e5
4bedd3d498e83bd16f363a3eaed9209d1b700f63eeb6f96f775d97ab31cac5f8
33c37802ce6c6dc22d15e60b62e68649ac2d2888ec1ea6fc8c44e01d9869dd75
b5610f79b982ce4666b0df76539cfd74255a00aca06d08acd05eaa7d60084a1c
24a8467f30d49602dc24318cd0665ea57b3333ed22aefde5f161a5f3044272bd
4b1b131e729d9bd102bd27ced202f6d5d800c2c17969c04a30bc7ad29664e59a
19429fd0d54ccf175abd9c4ecc7f24de183f5fee5193c5e895638dcda6a8bc27
6ce1410665315540b25e34c0f1e058567d88ef4fa91e710114f20d62114fd550
fec593226268610fbbc5352d0fb1f41b79a77eab3a2429f731feebaeb23841f7
33935fb947103ab453057052223fd5958a8897b665c8b3650b5cfaf1d8cccdc7
888b1eb7a6d29dc1cef64e6cc539d68b024c109736915630d5ddacc9c636851f
9970385c755daf6275142edb885d03506a738762bf5bfa957f9aadb31f31cb7a
c5ff5de1968b6458758a641d70525d098272c714840e0c2057ba8ec05d531b63
2c208eb6a63a5beca0488ee83d4e5f0eedcc29227f6f25cddd169e87bd07a320
b1d6e133e07eacfa6fbdcd9178344a861599d73c0aa1480b7b0bd7335736d665
aefbae60c94eea15bfbc7a2824f7032b2740f95e19460bde15aae20cae0722ca
6bdfea1b95fd48f168d545e409626e783c272b12b0895cbd17564dbbcf2da66f
02a1b05474d3a86672f76712f0338a00ce95af62b7c6d2aca5492d3d7a8c7305
3a011998e70fe4460f0acdec68a77933b41f6efbad345e66b18cf014cd88af88
cd0fdb32c3e60912b54a2c1f26df90c3243626f636a9c498acbebcbcc2cbebbc
87dc8336d829915f3f98709041cfa033be859e2b1ace2c9478e26c457e4aadc0
d2e84a52aa49ed36237c81ea9f2ff66ca9d48d406df092535971601e80ec31d1
042025bb6c7535549c2cb536a04125348c48454ac6a8210cfef8a71e50813aff
436308db651644f181d02c1b90368c150f5499836d71e6b7ae8e8334811a258e
5b8b9c76b17324ef5f35692b9ee069ec3c6135b1725bb82900bf3fbe953e0586
0506511cdc9561f76e5d85d147120fd746668b043f5a71760148008ebe37d9f0
6d89ad6b0a094a7f9a9bf4ee1ca2f3b0e5ec56f924b7efeb16fbdfbfd41358d3
25019aa8cec744ea6937729fd454100c6f5a589284b007c645c6d7c6ef58c8bc
39322232c9118f9541f6432913384444309fd10a0f627c9ecc2f95309701ab13
115a84ee3ac24122fd5482b0f7eb900ce99382ca41777cc2577c82cec766cab0
ed9f6161c423f30cc7ceac974ae5e432e755f08cb79b47ce3d43452dcf74c76c
a3df8f1e5dd063595188044473fa1c2bc69eec2e29bafaeeb3962c2750585fca
3f8bb91ade38f8e0b0e269a57191d70cf60ac2db4c79518e79b48c08a737f6cb
439190a055187e9c9a0120ed91b15365f716330c8df21cadcf14f6ea0f35b4b8
dd1ce000a01a41ead05d03d74e184345aa1340c14873d75bf99275b6042c66a5
5e2002006de48dc19d2116bd6de751ede5bdcfd96bfafbc41d9a227b06c8f7e6
d05a972e1fa0d36533c88c3d6f51175df426ab3ad3950cbd82fe789907de7178
e108856d6e85ea36e8b0330a5b62489ce939c11f0e3aa673327eef4c87adfdf9
0f673f6397808e53248ce5778e31d669ad9ddcdd4c732a3dcea05a3c03322972
2c6d0af5b1ea6178d647eaad2a41f76bdf0111dce813b136262ab9cbd1a042da
2c4b24bc7213bd16739ac23b0988e27ea3b52fbf87b7c3648cae97d3535449d2
accea9e2c218217fc967bd11d772c442adf4cfbaf6d81c57e13eda48c907a584
befe454b22b4eb940732ab972657e474c211d6d9dfcddd34f68d9628b32d61fe
fc1090ba15ccae04a9648183bfd9050e5513d98035af00a83e9a371bcff72512
d85b886abcdc31f028a2be8fdfa31ef3510c4b7f099baa0f15b9308493f3d2a7
2e631a9a04bf11d2354df921e482d6059684cc746ca1725b6d62952739c75ade
31dcc3a2dd334474173f6d16adcd3546736ddea1dda53d7ae7120bc5bcbc12f1
11d699bf7dcc57780f5b4217b4a6f777c0c4cdbd4269bf76b3daa5b6a6901fcb
02ae1e11650bf5ea33b0f2b9a65e830a0e4ff33b64be2f84eb0c89aeea0718fb
e3d6ba04b3583099db6095205e50eaf338260cbd97c77c3b3d9058522f108892
81f062c17993b7266ce990b4d115721973958d5f81a9f24fa5e7c718b4bfd1be
9dbb8f5215d43034aff34bcb3a2cb950b76c5dc78320bf729739f28c2316c381
b5ce8e8ca3b8e872f7640f0980af6aec31cb8549f48911081264b87c94ed9a16
70cdeb42324021d98cb408f2e0e2425a4be90d6b263a44f05e65af40c842a105
ef679767995bfa61402bf90cd697f388199ed92b24e5a1cd67485f9951b73bf0
ccfb009cacb758e3ed525b4941c61e973d7bc2bc079c3a2bd089f85fbf634a2f
f367d169e7fed794e76f711a4f75c0dbf8ac9426f1da48374bc86f179487d83a
90e786a6c635b110c1a9e8b717809b665d2ea91cf0851e8615ea276628544a6d
926cc73a86228b74a4ef8a386c2ecd56c7ed1c8979f2437dd53aa8c1a15b5513
32e8b07e1f7bb7da7012fff02cdcf84971d976fe056ddba651731657c7bce278
dbd86282a86ce7523cc2920ecd87070f46f436f4c9436667599fff95b0ebdc1b
4ab6a0ad4b50df2e2a178576f4aae0c7289ea00385b9d29be0c4e3b2921b5f2d
1b9a6ed279789ca017162f12586aef68f0d55acbbfb85f7a0ea294ff22a2eacf
07fc3be55d5d43dcb80f69121d6847aa0d093d4d4f723017ef75ab5b09ec555b
efb6468f620d1a0dd71ddfdc66b1a5145a1666c07729db8cba93ccadf66d6363
25164ae1c0e8c1f6243fb7761310c398c607b3be6ff0cdc41fa7583288cece47
01baccd7e9415275d8e9f797b90362496935e279d02bcf68e5bcd89577688934
e6bb9d20c9f7b528dcf323143fde093be6859b63583e58fbe0c319d5f6104cfd
048856baa298e3d69421db8f4777fd44756f25933484edf6574f1ad0c3a35d6a
0799af8cad7311dd6c27f07a1b13e57eb81d9ff79520b05428d6599105d41c37
f34f86804facfee48869f64b42b2f507fab255425001d368078bae02ae660f21
dc658b6bef96c02fd9ddcf1aaa442a5994c4789cc6ab76b2e592a36e0f61e205
8852c503f1fe03706f3a6afffed6f5ad6a9f375f7ef430fc29ecbefc7696d28c
62a37ed7404473449d756a1750ff5d65de9b3e27e10367e63a25e38681a144d3

分析代码知道r,w,x，e分别存放flag每个字符转ASCII码的倒数第一位，倒数第二位，倒数第三位，前x-3位

分析inf(r,w,x,files)函数

根据re.append(long_to_bytes(int(bin(bytes_to_long(files[i]))[2:]+r[i]+w[i]+x[i],2)))

发现需要通过加密后的files和加密前的files来恢复r,w,x

题目已经给出加密前的files，只需要爆破3位就可以知道r,w,x

得到r,w,x以后

根据f.write(hashlib.sha256(str(i)+urandom(2)).hexdigest()+"\n")

来爆破e，因为e是flag每个字符转ASCII码右移3位后的值，所以$1 \le e \le 16$

又因为urandom(2)的值在$2^8 —2^{16}$之间（这个下限一开始找错了，从$2^{15}$一直试到$2^8$），这样以来，我们便确定了爆破范围

然后把e,r,w,x拼接转回字符就行

exp:

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
from Crypto.Util.number import *
from itertools import product
import hashlib
from tqdm import *

f = open("0.txt",'r')

files = []
for i in range(129):
    files.append(f.readline().strip())

files1 = files[:43]
files2 = files[43:43*2]
files3 = files[43*2:]


r = []
w = []
x = []
byte = []
for i in range(len(files1)):
    byte_f = bytes.fromhex(files1[i])
    num_f = bytes_to_long(byte_f)
    bin_f = bin(num_f)[2:]
    for j in product(['1','0'],repeat=3):
        may_f = bin_f + "".join(j)
        hash_f = hashlib.sha256(long_to_bytes(int(may_f,2))).hexdigest()
        if hash_f == files2[i]:
            r.append("".join(j)[-3])
            w.append("".join(j)[-2])
            x.append("".join(j)[-1])
            byte.append(byte_f)

e = []
for k in trange(43):
    for i in range(17):
        may_e = str(i).encode()
        for j in range(2**16,2**8,-1):
            may = may_e + long_to_bytes(j)
            hash_may = hashlib.sha256(may).hexdigest()
            if hash_may == files3[k]:
                e.append(may_e)

m = []
for i in range(43):
    bin_m = bin(int(e[i].decode()))[2:] + x[i] + w[i] + r[i]
    mm = int(bin_m,2)
    m.append(chr(mm))

flag = "".join(m)
print("flag=",flag)
#flag{8uuuuu_dd_3yyyui_like_the_internet_g0}
-------------已经到底啦！-------------