LitCTF2025 • Misay's blog

偷偷摸一下

basic#

签到

from Crypto.Util.number import *

from enc import flag

  

m = bytes_to_long(flag)

n = getPrime(1024)

e = 65537

c = pow(m,e,n)

print(f"n = {n}")

print(f"e = {e}")

print(f"c = {c}")

  

'''

n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893

e = 65537

c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

'''

python

这里直接用的素数 $n$ ,直接计算它的欧拉函数解密就可以了 exp

from Crypto.Util.number import inverse, long_to_bytes  

n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893

e = 65537

c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

phi = n-1

print(gcd(phi,e))

print(long_to_bytes(pow(c, inverse(e, phi), n)))
# LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

python

LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

ez_math#

from sage.all import *

from Crypto.Util.number import *

from uuid import uuid4

  

flag = b'LitCTF{'+ str(uuid4()).encode() + b'}'

flag = bytes_to_long(flag)

len_flag = flag.bit_length()

e = 65537

p = getPrime(512)

P = GF(p)

A = [[flag,                 getPrime(len_flag)],

     [getPrime(len_flag),   getPrime(len_flag)]]

A = matrix(P, A)

B = A ** e

  

print(f"e = {e}")

print(f"p = {p}")

print(f"B = {list(B)}".replace('(', '[').replace(')', ']'))

  

# e = 65537

# p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869

# B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

python

基于矩阵的RSA，同样的方式求解即可

exp

from Crypto.Util.number import inverse, long_to_bytes

e = 65537

p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869

B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

  

phi = p-1

d=inverse(e, phi)

M = Matrix(Zmod(p), B)

M = M**d

# print(M)

res = M[0]

print(long_to_bytes(int(res[0])).decode())
# LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}

python

LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}

math#

from Crypto.Util.number import *

from enc import flag

  

m = bytes_to_long(flag)

e = 65537

p,q = getPrime(1024),getPrime(1024)

n = p*q

noise = getPrime(40)

tmp1 = noise*p+noise*q

tmp2 = noise*noise

hint = p*q+tmp1+tmp2

c = pow(m,e,n)

print(f"n = {n}")

print(f"e = {e}")

print(f"c = {c}")

print(f"hint = {hint}")

'''

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141

e = 65537

c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196

hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

'''

python

题目给了一个 $noise$ ，记为 $h$ 满足

hint-n=h(p+q)+h

，我们直接计算 $hint-n$ 之后，显然这个 $h$ 是小因子，直接丢factordb 可以算出来，然后就是常规的 $p,q$ 解方程了，exp

from Crypto.Util.number import inverse, long_to_bytes

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141

e = 65537

c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196

hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

  

hh = hint-n

print(hh)

  

t = 942430120937

print(f2.bit_length())

pq = hh//t - t

var('x')

S = pq

solutions = solve(x^2 - S*x +n == 0, x)

p = solutions[0].rhs()

q = solutions[1].rhs()

print("p =", p)

print("q =", q)

phi = (p-1)*(q-1)

d = inverse_mod(e, phi)

print("d =", d)

m = pow(c, d, n)

print(long_to_bytes(m))
# LitCTF{db6f52b9265971910b306754b9df8b76}

python

LitCTF{db6f52b9265971910b306754b9df8b76}

baby#

格子题

import gmpy2

from Crypto.Util.number import *

from enc import flag

  
  

m = bytes_to_long(flag)

g = getPrime(512)

t = getPrime(150)

data = (t * gmpy2.invert(m, g)) % g

print(f'g = {g}')

print(f'data = {data}')

'''

g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547

data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498

'''

python

已知

t\equiv\;md\;mod\;g

这里 $m$ 位数是比较大的，我们考虑打格子

(m,k)\begin{pmatrix}1&d*s\\0&g*s\end{pmatrix}=(m,t*s)

再用Hermite定理算一下两边的大小， $s$ 取 $2^{200}$ 即可规约出来

from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long

import string

g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547

data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498

print(data.bit_length())

k = 2^200

M = matrix(ZZ,2,2)

M[0,0] = 1

M[0,1] = data*k

M[1,0] = 0

M[1,1] = g*k

# print(M)

print(M.LLL())

v=M.LLL()[0]

print(v)

m = abs(v[0])

t = abs(v[1])//k

print(m.bit_length())

print(t.bit_length())

print(long_to_bytes(m))

# LitCTF{56008a819331c9f3608a718327b7e6ce}

python

LitCTF{56008a819331c9f3608a718327b7e6ce}

* leak#

不太常规的RSA $d_{p}$ 泄露

from Crypto.Util.number import *

from enc import flag

  

m = bytes_to_long(flag)

p,q,e = getPrime(1024),getPrime(1024),getPrime(101)

n = p*q

temp = gmpy2.invert(e,p-1)

c = pow(m,e,n)

hint = temp>>180

print(f"e = {e}")

print(f"n = {n}")

print(f"c = {c}")

print(f"hint = {hint}")

'''

c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399

e = 1915595112993511209389477484497

n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951

hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930

'''

python

参考这篇博客RSA dp泄漏攻击 - vconlln - 博客园 (cnblogs.com) ↗ 因为

d_{p}\equiv\;1\;mod\;p-1

所以

d_{p}-1=k(p-1)

也就是

d_{p}+k-1=kp

即

d_{p}+k-1\equiv\;0\;mod\;p

从而

d_{p}+k-1\equiv\;0\;mod\;n

又知道 $d_{p}$ 高位，所以

(hint<<180+x)+k-1\equiv\;0\;mod\;n

这里和上述过程相比，因为 $e$ 太大，无法按照遍历 $k$ 的思路来求解这个方程，在此感谢Ramoor师傅 ↗的思路，把 $k$ 当为一个未知变量来解，使用二元coppersmith的思路，恰好这里 $x,k$ 的大小都小于 $n^{\frac{1}{4}}$ , 解出了 $d_{p}$ 之后，我们不难得到

a^{ed_{p}}\equiv\;a^{1+k(p-1)}\;\equiv\;a*(a^{p-1})^k\;\equiv\;a\;mod\;p

也就是

a^{ed_{p}}-a\;\equiv0\;mod\;p

又考虑到 $p\;|\;n$ 那么很容易得到

p=gcd(n,a^{ed_{p}}-a)

exp如下

#sage

  

import itertools

from Crypto.Util.number import *

def small_roots(f, bounds, m=1, d=None):

    if not d:

        d = f.degree()

  

    if isinstance(f, Polynomial):

        x, = polygens(f.base_ring(), f.variable_name(), 1)

        f = f(x)

  

    R = f.base_ring()

    N = R.cardinality()

    f = f.change_ring(ZZ)

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

  
  

    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.coefficient_matrix()

    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 []

n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951

c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399

e = 1915595112993511209389477484497

hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930

leak = hint << 180

  

R.<x,y> = PolynomialRing(Zmod(n))

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

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

for root in res:

    dp_low = root[0]

    dp = leak + dp_low

    tmp = pow(2,e*dp,n) - 2

    p = gcd(tmp,n)

    q = n // p

    d = inverse(e,(p-1)*(q-1))

    m = pow(c,d,n)

    print(long_to_bytes(m))

python

* 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:]

print(flag)

print(len(flag))

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()

python

随机生成八个字符，套上LitCTF{...}的壳子，转二进制，做一个子集和问题这里你直接造127位的格子打不了的，我们可以计算背包的密度，如下公式

\rho\;=\;\frac{len(bag)}{log_{2}(max(bag))}

稍微计算就能知道127位的背包，它的密度是 0.992194太大了，算不了一点但我们实际只用求中间的八个字符，也就是说前面的56个，和最后的8个我们都不用管，我们计算一下目标背包的密度

secret = pubkey[56:len(pubkey) - 8]

print(len(secret))

result = len(secret) / max(secret).log(2)

print(round(result, 6))

# 0.492259

python

这个密度就比较小，我们能成功构造格子来打了，参考博客其他加密算法 | Lazzaro (lazzzaro.github.io) ↗ exp如下

from Crypto.Util.number import *

  

p = 173537234562263850990112795836487093439

pubkey = ...

c = 82516114905258351634653446232397085739

  

#处理前缀

prefix = b'LitCTF{'

prefix_bits = bin(bytes_to_long(prefix))[2:]

for i, b in enumerate(prefix_bits):

    c = (c - int(b) * pubkey[i]) %p

  

#处理后缀

suffix = b'}'

suffix_bits = bin(bytes_to_long(suffix))[2:].zfill(8)

secret = pubkey[56:len(pubkey) - 8]

print(len(secret))

result = len(secret) / max(secret).log(2)

print(round(result, 6))

  
  

n= len(pubkey)

for i, b in enumerate(suffix_bits):

    c = (c - int(b) * pubkey[n - 8 + i]) %p

  

start = len(prefix_bits)

elements = pubkey[start:-8]

m = len(elements)

#print(m)

  

#造格

L = Matrix(ZZ, m+2, m+2)

for i in range(m):

    L[i, i] = 1

    L[i, m+1] = elements[i]

L[m, m] = 1

L[m, m+1] = c

L[m+1, m+1] = p

  

L = L.BKZ(block_size=20)

for row in L:

    if row[-1] == 0:

        bits = ''.join(['1' if x==1 else '0' for x in row[:m]])

        ans = long_to_bytes(int(bits, 2)).decode('utf-8', errors='ignore')

        if len(ans) == 8 and ans.isalnum() and ans.isascii():

            print(f'LitCTF{{{ans}}}')

            break

# LitCTF{Am3xItsT}

python

LitCTF{Am3xItsT} 很不错的一次参赛体验

感谢各位师傅，一次宝贵的练手机会！