Contents

d3ctf2021

Contents

咕咕咕了太久了,上个有就该做的

d^3ctf2021

  • babyLattice done
    • LLL分解n的应用
  • simpleGroup done
    • babyLattice LLL分解n + 中国剩余定理特殊应用 + n次剩余判断
  • AliceWantFlag todo
  • EasyCurve todo

simpleGroup

得矩阵 A 分解 n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196

M = Matrix(ZZ, [
    [1, 0, b ^ 2],
    [0, 1, b],
    [0, 0, n]
    ])
M = M.LLL()
#
tmp1 = abs(M[0][0])
tmp2 = abs(M[0][2])

print(factor(tmp1))
print(factor(tmp2))

a12 = 1018979931854255696816714991181
a22 = 1151291153120610849180830073509
a11 = 1017199123798810531137951821909
a21 = 207806651167586080788016046729

crt

 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
from icecream import *

from Crypto.Util.number import *

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629
e = 1928983487
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120,
     27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]
# 36493 * 52859
e1 = 36493
e2 = 52859
ic(len(C))
'''
p-1 e2互质
q-1 e1互质
'''

def check(d, p, n):
    if((p - 1) % n == 0):
        return pow(d, (p - 1) // n, p) == 1
    else:
        k = gcd(n, p - 1)
        return pow(d, (p - 1) // k, p) == 1

def getM(c, e, p):
    for i in range(2, e):
        inv = int(pow(y, i, p))
        tmpc = (c * inverse(inv, p)) % p
        if check(tmpc, p, e):
            return i
    exit(0)
def func(c):
    cq = c % q
    cp = c % p

    m1 = getM(cp, e1, p)
    m2 = getM(cq, e2, q)
    ic(m1,m2)
    ans = crt([m1,m2],[e1,e2])
    ic(hex(ans))
    return ans
ans=[]
for c in C:
    ans.append(func(c))
tot =0
ans=ans[::-1]
for i in ans:
    tot*=e
    tot+=i
print(tot)
print(long_to_bytes(tot))