NSSCTF-工坊-格密码

约 1182 字大约 4 分钟

2025-06-09

P1

from Crypto.Util.number import *

p = getPrime(1024)

f = getPrime(400)
g = getPrime(512)
r = getPrime(400)

h = inverse(f, p) * g % p

m = b'******'
m = bytes_to_long(m)

c = (r*h + m) % p

print(f'p = {p}')
print(f'h = {h}')
print(f'c = {c}')

'''
p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *

p = 170990541130074930801165526479429022133700799973347532191727614846803741888876816210632483231997413973919037199883422312436314365293577997262903161076615619596783971730864586404602951191341733308807254112018161897113881363794353050758324742415299277578203838160939521046655099610387485947145087271531951477031
h = 19027613518333504891337723135627869008620752060390603647368919831595397216728378486716291001290575802095059192000315493444659485043387076261350378464749849058547797538347059869865169867814094180939070464336693973680444770599657132264558273692580535803622882040948521678860110391309880528478220088107038861065
c = 75639016590286995205676932417759002029770539425113355588948888258962338419567264292295302442895077764630601149285564849867773180066274580635377957966186472159256462169691456995594496690536094824570820527164224000505303071962872595619159691416247971024761571538057932032549611221598273371855762399417419551483

M = matrix([[1,h],
            [0,-p]])

f,g = M.LLL()[1]

m = (f*c) % p % g *inverse(f,g) % g

print(long_to_bytes(m))
# NSSCTF{94068324-38bb-410b-b464-e1b8baf6b358}

P2

from Crypto.Util.number import *
import random
from gmpy2 import *

flag = bytes_to_long(b'******')
flag = bin(flag)[2:]
n = len(flag)

a = [random.randint(1, 4**n)]
s = a[0]
for i in range(1, n):
    a.append(random.randint(s+1, 4**(n+i)))
    s += a[i]

m = random.randint(a[-1] + 1, 2*a[-1])
w = random.randint(1, m)

assert gcd(w, m) == 1
b = [w*i % m for i in a]

c = 0
for i in range(len(b)):
    c = (c + b[i]*int(flag[i]))
with open('output', 'w+') as f:
    print(f'b = {b}', file=f)
    print(f'c = {c}', file=f)

Exp:

# sagemath 10.6
from Crypto.Util.number import *

with open('output','r') as f:
    output = f.readlines()

b =  eval(output[0].split('=')[1])
c =  eval(output[1].split('=')[1])

n = len(b)

L = matrix(ZZ,n+1,n+1)

for i in range(n):
    L[i,i] = 1
    L[i,-1]=b[i]

L[-1,-1] = -c

res = L.LLL()

row = []
for i in range(n+1):
    row = res.row(i).list()
    key = True
    for i in row:
        if i!= 0 and i!= 1:
            key = False
            break
    if key:
        break

flag = long_to_bytes(int(''.join(map(str,row[:-1])),2))
print(flag)
# NSSCTF{4f7695b9-e026-4e9e-b456-bcf5}

P3

from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

c = pow(m, 65537, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')

'''
c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *
from tqdm import trange

c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609

M = matrix([[1,a],
            [0,b]])

res = M.LLL()

pp,qq=abs(res[0,0]),abs(res[0,1])

for r in trange(2**14,2**15):
    for h in range(50):
        p = pp + r
        q = qq + h
        phi = (p-1)*(q-1)
        if GCD(65537,phi) != 1:
            continue
        d = inverse(65537,phi)
        m = pow(c,d,p*q)

        flag = long_to_bytes(m)
        if b'NSSCTF' in flag:
            print(flag)
            exit()

# NSSCTF{0fc9dee6-ebfb-40bd-b800-b3ebe440be70}

P4

from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
flag = bytes_to_long(flag)

p = getPrime(1024)
r = getPrime(175)
a = inverse(r, p)
a = (a*flag) % p

print(f'a = {a}')
print(f'p = {p}')
'''
a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *

a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

b = 2 ^ 0
L = matrix([[1,a*b],
            [0,-p*b]])

res = L.LLL()

if res:
    for r in res:
        f = r[1]
        m = long_to_bytes(f)
        if b'NSSCTF{' in m:
            print(m)
            exit()
# NSSCTF{e572546b-abb5-4358-8970-471abc12b7ef}

P5

from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 351
p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)

a = (b*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *

a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783
k = 2^400

L = matrix([[k,0,a],
            [0,1,-b],
            [0,0,p]])

res = L.LLL()

if res:
    for r in res:
        m = long_to_bytes(abs(r[1]))
        if b'NSSCTF{' in m:
            print(m)
# NSSCTF{ee5cb1a5-257a-48b0-9d62-9ef56ff0651a}

P6


from Crypto.Util.number import *

flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)

for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = inverse(d, (p-1)*(q-1))
    c = pow(flag, e, n)
    print(f'e{i} =', e)
    print(f'n{i} =', n)
    print(f'c{i} =', c)

'''
e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *

e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465

M = isqrt(n0)
L = Matrix(ZZ,[
            [M,e0,e1,e2,e3],
            [0,-n0,0,0,0],
            [0,0,-n1,0,0],
            [0,0,0,-n2,0],
            [0,0,0,0,-n3]])
res = L.LLL()

if res:
    for r in res:
        d = (r[0])//M
        m = long_to_bytes(pow(c0,d,n0))
        if b'NSSCTF{' in m:
            print(m)

# NSSCTF{12514adb-2c14-4777-96ff-90e95bc2b5cb}

P7

from Crypto.Util.number import *

flag = b'******'
flag = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p * q
c = pow(flag, 65537, n)
print(f'n =', n)
print(f'c =', c)
for i in range(2):
    d = getPrime(350)
    e = inverse(d, (p-1)*(q-1))
    print(f'e{i} =', e)

'''
n = 110697784133988071803253124431092603234028687101567047811203431433689306543322837414808117411806181193598553341878079973980865551938790090419082150555675782822484149943421418447579383449269148197087985041351210982545320569973241390962326458234562044133505940521052500278777242988196544039226173227204865907343
c = 3281096209929505523196793672137624804022934270452947405454462490250571524417033484978613243658208567511735641542935158434165363547355697159503378251318054879687577130170122911449101189974762808655638497967674004219512386442280269940950792767174561412932638740423542930763914255112354969122157915514816022159
e0 = 28562806554366667733480283991307446762365777397933141571728113235368201162305126722188842319240464207580134816039095093401651171977877327756351539588974913736802534970867173212883308325913939353140276201705478124488858328502643345172188729914731042179091733244225184522680724392375975935305371163502863968963
e1 = 28572469216883232254074869113744730984165641173439644880182528671699871929340616919028955398474678696802739685594548793470261306125219888911330937557582939811068530294470712859439149735950996866732508004061234613146407591546995439312326450834903885979660916965052092661398640105827442036234500556755520316031
'''

Exp:

拓展维纳攻击

# sagemath 10.6
from Crypto.Util.number import *

n = 110697784133988071803253124431092603234028687101567047811203431433689306543322837414808117411806181193598553341878079973980865551938790090419082150555675782822484149943421418447579383449269148197087985041351210982545320569973241390962326458234562044133505940521052500278777242988196544039226173227204865907343
c = 3281096209929505523196793672137624804022934270452947405454462490250571524417033484978613243658208567511735641542935158434165363547355697159503378251318054879687577130170122911449101189974762808655638497967674004219512386442280269940950792767174561412932638740423542930763914255112354969122157915514816022159
e0 = 28562806554366667733480283991307446762365777397933141571728113235368201162305126722188842319240464207580134816039095093401651171977877327756351539588974913736802534970867173212883308325913939353140276201705478124488858328502643345172188729914731042179091733244225184522680724392375975935305371163502863968963
e1 = 28572469216883232254074869113744730984165641173439644880182528671699871929340616919028955398474678696802739685594548793470261306125219888911330937557582939811068530294470712859439149735950996866732508004061234613146407591546995439312326450834903885979660916965052092661398640105827442036234500556755520316031

a = 5/14
D = diagonal_matrix(ZZ,[n, int(n^(1/2)),int(n^(1+a)),1])
M = matrix(ZZ,[
            [1,-n,0,n^2],
            [0,e0,-e0,-e0*n],
            [0,0,e1,-e1*n],
            [0,0,0,e0*e1]])*D

L = M.LLL()
t = vector(ZZ,L[0])
x = t * M^(-1)

phi = int(x[1]/x[0]*e0)

d = inverse(65537,phi)

print(long_to_bytes(pow(c,d,n)))
# NSSCTF{00121664-7e76-4f6f-a2f7-4813e21ff4aa}

P8

from Crypto.Util.number import *

flag = b'******'
m = bytes_to_long(flag)

p = getPrime(512)
s = [getPrime(32) for i in range(3)]
a = [getPrime(512) for i in range(3)]

c = (a[0]*s[0]**2*s[1]**2 + a[1]*s[0]*s[2]**2 + a[2]*s[1]*s[2]) % p

flag = m*s[0]*s[1]*s[2]
print(f'c = {c}')
print(f'flag = {flag}')
print(f'a = {a}')
print(f'p = {p}')

'''
c = 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028
flag = 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927
a = [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]
p = 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573
'''

Exp:

# sagemath 10.6
from Crypto.Util.number import *

c = 740925064346371394698186587854547113606276228956443989781507592148712696471120454242180757282913190509143771235457885619359315384722931529795071829165028
f = 68803130911709451943985629442913968356735244797651554293510331427148284907075221530061581131130283569506280604032687824733336171953927
a = [8205051800134728054685810600921116779466017139080528864745521629232854690213051609775306424843961090482436503418278207286549634492623172279113808752825877, 7656695314164580223033364292542508972053206838456547579023164583502640699225283686572923544677077467571265812610524520719197913305928971777756847148151453, 12016313094941119621096276870216129960285946825332008187797823075795491053640261786033376211694851951499688886358239835607622191418940486434225440651886891]
p = 9725369974716521164256395525866212215114818770667579116304398350357785690930260317036889742178436308598088096925530431498664796728861093872628194022265573

d = 2^32
aa = inverse(a[2],p)
D = diagonal_matrix(ZZ,[1,d,d^4,d^2])

M = matrix(ZZ,[[1,0,0,a[0]*aa%p],
                [0,1,0,a[1]*aa%p],
                [0,0,1,-c*aa %p],
                [0,0,0,p]])*D
res = M.LLL()

for r in res:
    s0s1 = isqrt(abs(r[0]))
    s1s2 = abs(r[3]) >> 64
    s1 = GCD(s0s1, s1s2)
    s0 = s0s1 // s1
    s2 = s1s2 // s1
    flag = long_to_bytes(f//(s0*s1*s2))
    if b'NSSCTF' in flag:
        print(flag)
# NSSCTF{30636075-1942-49e7-acf2-721e3b587188}