Nanxer's blog

外观

LitCTF 2025

约 737 字大约 2 分钟

crypto

2025-06-08

basic


from Crypto.Util.number import *
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

print(long_to_bytes(pow(c,inverse(e,n-1),n)))
# b'LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}'

baby

简单的NTRU，需要配平

from Crypto.Util.number import *

g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
c = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
b = 2 ** 128

mat =  [[1,b*c],[0,b*g]]
M = matrix(ZZ,mat)
m = M.LLL()[0][0]

print(long_to_bytes(int(m)))
# b'LitCTF{56008a819331c9f3608a718327b7e6ce}'

ez_math

用e在p上的逆元对矩阵进行运算

from Crypto.Util.number import *

e = 65537
p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

P = GF(p)
M = matrix(P, B)

m = (M ** inverse(e,p-1))[0][0]

print(long_to_bytes(int(m)))
# b'LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}'

leak

dp高位泄露+二元coppersmith

from Crypto.Util.number import *
import itertools

e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930

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

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)

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

    B = B.dense_matrix().LLL()

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

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

    return []

R.<x,y> = PolynomialRing(Zmod(n),implementation='generic')
leak = hint << 180

f = e*(leak + x) + (y - 1)

res = small_roots(f,(2^180,2^101),m=2,d=4)
print(res)

dp = leak + res[0][0]
tmp = pow(2,e*dp,n)-2
p = GCD(tmp,n)
q = n//p
print(long_to_bytes(pow(c,inverse(e, (p-1)*(q-1)), n)))
# LitCTF{03ecda15d1a89b06454c6050c1bd489f}

math

from Crypto.Util.number import *

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

# print(hint-n)
# hint-n = noise*(p+q+noise) = 19*942430120937*13942360585323048470909846656964572704513299405546046811010328770033198426421576349568926279384369628072261252513038693891801832793244205614823946991510903118232135334563566099595180800155562142673080500174590397281272043792295225345391996291640336108556360227747859478557651612788250116887738800942290148741

noise = 942430120937
paq = (hint - n) // noise -noise
phi = n - paq + 1
print(long_to_bytes(pow(c,inverse(e,phi),n)))
# LitCTF{db6f52b9265971910b306754b9df8b76}

new_bag

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

def get_flag(length):
    characters = string.ascii_letters + string.digits + '_'
    flag = 'LitCTF{' + ''.join(random.choice(characters) for _ in range(length)) + '}'
    return flag.encode()

flag = get_flag(8)
print(flag)
flag = bin(bytes_to_long(flag))[2:]

p = getPrime(128)
pubkey = [getPrime(128) for i in range(len(flag))]
enc = 0
for i in range(len(flag)):
    enc += pubkey[i] * int(flag[i])
    enc %= p

f = open("output.txt","w")
f.write(f"p = {p}\n")
f.write(f"pubkey = {pubkey}\n")
f.write(f"enc = {enc}\n")
f.close()

背包密码，部分明文已知，同时p的大小和pub相当，可知k小于sum(flagi)<64 (i=56−119)sum(flag_i)<64 \ (i=56-119),能够直接爆破。

enc−know=∑i=56119pubi∗int(flagi)mod  penc-know = \sum^{119}_{i=56}pub_i*int(flag_i) \mod p

(f1f2⋅⋅⋅f641)(20⋅⋅⋅0pub102⋅⋅⋅0pub2⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅00⋅⋅⋅2pub64−1−1⋅⋅⋅−1−(enc−know+k∗p))=\begin{pmatrix}f_1 & f_2 & ··· & f_{64} & 1\end{pmatrix}\begin{pmatrix} 2 & 0 & ··· & 0 & pub_1 \\ 0 & 2 & ··· & 0 &pub_2 \\ ··· & ··· & ··· & ··· & ··· \\ 0 & 0 & ··· & 2 & pub_{64} \\ -1 & -1 & ··· & -1 & -(enc-know+k*p)\end{pmatrix}=

(2∗f1−12∗f2−1⋅⋅⋅2∗f64−10)\begin{pmatrix}2*f_1-1 & 2*f_2-1 & ··· & 2*f_{64}-1 & 0\end{pmatrix}

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

p = 173537234562263850990112795836487093439
pubkey = [···]
enc = 82516114905258351634653446232397085739

flag_know = b'LitCTF{'+b'\x00'*8+b'}'
know = [int(i) for i in bin(bytes_to_long(flag_know))[2:]]
new_pub = pubkey[-72:-8]
for i in range(len(know)):
    enc = (enc - know[i]*pubkey[i]) % p

n = len(new_pub)
M = matrix(ZZ,n+1,n+1)
b = 2^256 # 配平

for i in range(n):
    M[i,i]=2
    M[-1,i]=-1
    M[i,-1]=new_pub[i]*b

for k in trange(64):
    c = enc + k*p
    M[-1,-1] = -b*c

    res = M.LLL()
    for i in range(n+1):
        rows = res.row(i).list()
        key=True
        for i in rows[:-1]:
            if i!=-1 and i!=1:
                key=False
                break
        if key:
            print(rows)
            flag = ''.join(['0' if i==-1 else '1' for i in rows[:-1]])
            print(b'LitCTF{'+long_to_bytes(int(flag,2))+b'}')
            exit()