NepCTF2025

[LitCTF 2023]Where is P?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
m=bytes_to_long(b'XXXX')
e=65537
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print(p)
c=pow(m,e,n)
P=p>>340
print(P)
a=pow(P,3,n)
print("n=",n)
print("c=",c)
print("a=",a)
#n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
#c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
#a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

这里给出来了a 由于这里是 $$P^3$$我们可以直接尝试爆破来求得P的数值

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

e=65537
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
for i in range(e):
    a1 = a+i*n
    P,f = iroot(a1, 3)
    if(f):
        print(i) 
        break
print(P)
# 66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946

这里我们得到了P的数值题目中给出来了P=p>>340这里属于是P的高位泄露我们可以通过coppersmith的方法来进行p的求解

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
P = 66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946
n = 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721

p_fake = P << 340
pbits = p_fake.nbits()
pbar = p_fake & (2^pbits-2^kbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^340, beta=0.4)[0]  
p = x0 + pbar
print(p)
#148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459

得到p之后就是简单的RSA

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
e=65537
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
p = 148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
q = n // p
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

b’LitCTF{Y0U_hAV3_g0T_Th3_r1ghT_AnsW3r}’

[BaseCTF 2024]铜匠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import getPrime, bytes_to_long
#from secret import flag
flag=b'XXXX'

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 721
hint2 = q % (2 ** 266)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
'''
hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
'''

这里可以看到p是一个高位q是低位通过计算我们可以得到有455位数的未知数

运用coppersmith来进行求解

$$
n \equiv pq \equiv (p_low)(q_low) \mod 2^{266}
$$
$$
x_0*hint2 \equiv n \mod 2^{266}
$$
$$
p = (hint1<<721)+x^{266}+X_0
$$
$$
f(x)=p+2^{266}*x \quad (p_0=(hint1<<721)+x_0)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#sage
hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
e = 65537
 
p_high = hint1<<721
q_low = hint2
mod = 1<<266
p_low = n*inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
 
f = p_high + x*mod + p_low
pp = f.monic().small_roots(X=2^455,beta=0.4)
if pp:
    p=(pp[0]*mod)+p_high+p_low
    
print(p)

得到p的数值然后就是RSA

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

p = 159283759372043950279417056412033091802265743745598264436861098130148724970544195213191649176146680513963936883226073882981043500266750021458811522117917329282086352568217051323687992730755300271109836959298927976601834111434688928933727743853427947839181032241795612450167686056781516529650558649534989394677
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
e = 65537
ct =15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289

q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = long_to_bytes(pow(ct, d, n))
print(m)

b’BaseCTF{7074ddc3e006810688241196414e49e2}’

[红明谷CTF 2022]easy_ya

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

from flag import flag
def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return 
p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)
'''
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
'''

已知：

$$
\begin{aligned}
m &= k \cdot i + r \
c &\equiv m^e \pmod{n} \
c &\equiv (k \cdot i + r)^e \pmod{n}
\end{aligned}
$$

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

r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
PR.<k> = PolynomialRing(Zmod(n))
f = (M + k*r)^e - c
f=f.monic()
x0 = f.small_roots(k=2^100, beta=1)[0]
print (x0)
m = x0*r+M
print (m)
#6485097232194198437755667993910287898649267551843383452848230535806020694959067046832721252854563061586676627325202840257402325662599788040642551541918619720183975021007170350613

在sage里面好像还不出来后面去python里面去转换得到flag

flag{53a2e494-964d-4506-a2c4-c34b9475dedd}

[HNCTF 2022 WEEK3]partialP

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

p = getPrime(512)
q = getPrime(512)
n = p*q
e=65537
flag = "flag{"+str(uuid.uuid4())[:20]+"}"
m = bytes_to_long(flag.encode())
assert(m<n)
c=pow(m,e,n)

print(f"h = {((p>>128)<<128)}")
print(f"e = 65537")
print(f"c = {c}")
print(f"n = {n}")
"""
h = 9605964225476901441398365225327926616880072280289780777971846998748464126891804587377933727304510424852546683782576240573278202121547956666293242671661056
e = 65537
c = 2226099021169425534206121605501718994593261953280046899345810118356590881389142531649792348146129153474985003929407172972982275439970723778495455838452638879586163957468972518078320159354264971816842073874550773309020013613432004074760802192607651584906352686468143648939740004838208640531785439362344039075       
n = 96928253979490973984593903132811649229014718994486532280648145898877952846656019305217095845257550421730063527538581223570539203247068060192535543753763017716750817560470547219370972835770943358384150269303529653434434525449357699107332781898776312692702549420939758722366794431784782973884379040574148608179      


"""

这里可以看到p>>128

这里运用coppersmith来恢复p的数值

1
2
3
4
5
6
7
8
9
10
11
12
13
h=9605964225476901441398365225327926616880072280289780777971846998748464126891804587377933727304510424852546683782576240573278202121547956666293242671661056
n=96928253979490973984593903132811649229014718994486532280648145898877952846656019305217095845257550421730063527538581223570539203247068060192535543753763017716750817560470547219370972835770943358384150269303529653434434525449357699107332781898776312692702549420939758722366794431784782973884379040574148608179

PR.<x> = PolynomialRing(Zmod(n))

f=h+x

x0=f.small_roots(X=2^128,beta=0.4)[0]

print(x0)
print(h+x0)

#9605964225476901441398365225327926616880072280289780777971846998748464126891804587377933727304510424852546683782576502313782852920367078761087206532330667

然后就是RSA解出来flag

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

p = 9605964225476901441398365225327926616880072280289780777971846998748464126891804587377933727304510424852546683782576502313782852920367078761087206532330667
h = 9605964225476901441398365225327926616880072280289780777971846998748464126891804587377933727304510424852546683782576240573278202121547956666293242671661056
e = 65537
c = 2226099021169425534206121605501718994593261953280046899345810118356590881389142531649792348146129153474985003929407172972982275439970723778495455838452638879586163957468972518078320159354264971816842073874550773309020013613432004074760802192607651584906352686468143648939740004838208640531785439362344039075
n = 96928253979490973984593903132811649229014718994486532280648145898877952846656019305217095845257550421730063527538581223570539203247068060192535543753763017716750817560470547219370972835770943358384150269303529653434434525449357699107332781898776312692702549420939758722366794431784782973884379040574148608179
q = n//p
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c,d,n)
print(long_to_bytes(m))

b’flag{c014bbe0-d90b-4249-b}’

LCG

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 *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数
    def generate(self):
        self.seed = self.a * (self.seed - self.b) % self.m
        return self.seed
lcg = LCG(bytes_to_long(flag), getPrime(256), getPrime(256), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
57648351648792284446777383544515312078150027665462203747924668509833442797796
90378879763416486117626477831653213918315023665514305359005153448529276829825
21826576702665114807208181233864324586557058567478767825970403161758214940301
47594460970742467761038407996122637655856234121180714918606854365482948918701
11871076497267630136796123094001159466754095580273018347962555675375123133730
'''

这里的LCG给出来的公式并不是普通的LCG的公式
公式写的很抽象还没有改就将就看一下（）

这里我们要将其转换成普通的 LCG 的公式：

$$
\begin{aligned}
X_n &\equiv a(X_{n-1}-b) \pmod{n} \
X_n &\equiv aX_{n-1} - ab \pmod{n} \
\text{令 } -ab &\equiv b \pmod{n} \quad \text{(新 b)} \
X_n &\equiv aX_{n-1} + b \pmod{n}
\end{aligned}
$$

在此之前我还在用原来的公式将 $a,b$ 的推导公式都推出来了，但是发现一算逆元的时候就不互素 :moai:
但是那样好像会比较麻烦，就转换公式，但是计算到 $b$ 的时候就算不出来，也不知道是为什么。这里我把 $a,b$ 的推导写出来，求大家看看是不是对的。

原公式推导：

$$
\begin{aligned}
\text{1式: } X_n &\equiv a (X_{n-1} - b) \pmod{n} \
\text{2式: } X_{n+1} &\equiv a (X_n - b) \pmod{n}
\end{aligned}
$$

用 1式 - 2式：

$$
\begin{aligned}
X_n - X_{n+1} &\equiv aX_{n-1} - \cancel{ab} - aX_n + \cancel{ab} \pmod{n} \
X_n - X_{n+1} &\equiv aX_{n-1} - aX_n \pmod{n} \
a(X_{n-1} - X_n) &\equiv X_n - X_{n+1} \pmod{n} \
a &\equiv (X_n - X_{n+1}) \cdot (X_{n-1} - X_n)^{-1} \pmod{n}
\end{aligned}
$$

b 的推导：

$$
\begin{aligned}
X_n &\equiv a (X_{n-1} - b) \pmod{n} \
a (X_{n-1} - b) &\equiv X_n \pmod{n} \
aX_{n-1} - ab &\equiv X_n \pmod{n} \
-ab &\equiv X_n - aX_{n-1} \pmod{n} \
ab &\equiv aX_{n-1} - X_n \pmod{n} \
b &\equiv (aX_{n-1} - X_n) \cdot a^{-1} \pmod{n} \
b &\equiv X_{n-1} - X_n \cdot a^{-1} \pmod{n}
\end{aligned}
$$

这边就是解出来的推导公式。

这里我们通过递减的方式来求出 $n$ 的数值：

$$
\begin{aligned}
X_n &\equiv aX_{n-1} + b \pmod{n} \
X_{n+1} &\equiv aX_n + b \pmod{n}
\end{aligned}
$$

然后做差：

$$
\begin{aligned}

X_{n+1} - X_n &= a(X_n - X_{n-1}) + kn \
X_{n+1} - X_n - a(X_n - X_{n-1}) &= kn \
X_{n+2} - X_{n+1} - a(X_{n+1} - X_n) &= kn
\end{aligned}
$$

再通过 GCD 求公约数来得到 $n$。

另外，由转换后的公式也可以求 $a,b$：

$$
\begin{aligned}
X_n &\equiv aX_{n-1} + b \pmod{n} \
aX_{n-1} + b &\equiv X_n \pmod{n} \
aX_{n-1} &\equiv X_n - b \pmod{n} \
a &\equiv (X_n - b) \cdot (X_{n-1})^{-1} \pmod{n} \
b &= X_{n-1} - aX_n \pmod{n}
\end{aligned}
$$
求出来a,b,n的数值了我们现在对seed进行回推在加上前缀就可以得到flag

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
from Crypto.Util.number import long_to_bytes, isPrime
from gmpy2 import gcd
import gmpy2

outputs = [
    57648351648792284446777383544515312078150027665462203747924668509833442797796,
    90378879763416486117626477831653213918315023665514305359005153448529276829825,
    21826576702665114807208181233864324586557058567478767825970403161758214940301,
    47594460970742467761038407996122637655856234121180714918606854365482948918701,
    11871076497267630136796123094001159466754095580273018347962555675375123133730
]
d0 = outputs[1] - outputs[0]
d1 = outputs[2] - outputs[1]
d2 = outputs[3] - outputs[2]
d3 = outputs[4] - outputs[3]

T1 = d1 ** 2 - d0 * d2
T2 = d2 ** 2 - d1 * d3

n = gcd(T1, T2)
print(n)
for i in range(1,100):
    if isPrime(n//i):
        print(i)
        n//=i
        break
p1=outputs[3]-outputs[2]
p2=outputs[2]-outputs[1]
a = (p1)*gmpy2.invert(p2,n) % n
print(a)
b = (outputs[2]-a*outputs[1]) % n
print(b)

a_1=gmpy2.invert(a,n)
print(a_1)
for i in range(2**16):
    outputs[1] = a_1 * (outputs[1]-b) % n
    flag = long_to_bytes(outputs[1])

    if b'NSSCTF{' in flag:
        print(flag)
        break

b’NSSCTF{another_lcg}’

EZRSA

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 secrets import flag, get_random_emojiiiiii
from Crypto.Util.number import *


def genarate_emojiiiiii_prime(nbits, base=0):
    while True:
        p = getPrime(base // 32 * 32) if base >= 3 else 0
        for i in range(nbits // 8 // 4 - base // 32):
            p = (p << 32) + get_random_emojiiiiii() # 猜一猜
        if isPrime(p):
            return p


m = bytes_to_long(flag.encode()+ "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)

n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)

print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)
# p0 = 😘😾😂😋😶😾😳😷
# n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
# c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401

这里给出来的emoji 的表情p0 从 long_to_bytes(p % 2 ** 256).decode()可以看出来所给的p并不完整我们需要通过coppersmith的方法来求得p的数值

这里p的生成方法，先生成224位的素数，然后填充了九个32bits的emoji

这里我们对未知的表情进行爆破但是爆破 2^{31} -2^{32}太大了所以我们可以找一些表情进行爆破

这里我们可以得到未知数为512-256-32=224

低位plow=256

高位eomji = 32

构造多项式f(x)

来求224位的未知数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import*
from gmpy2 import*
e=4036989615
plow = 108837065531980906150333850570890620719343963272506332719822248235755953428663
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
emoji = '🌚 🌚 🌚 🌚 😆 🌚 🤣 🌚 🙂'
def recover_p(n, p_low, k_bits):
    P.<x> = PolynomialRing(Zmod(n))
    f = x * 2**k_bits + p_low
    roots = f.monic().small_roots(X=2^(n.nbits()//2 - k_bits), beta=0.4)
    if roots:
        return roots[0] * 2**k_bits + p_low
    
for i in emoji:
    pp=bytes_to_long(i.encode())*2**256+plow
    p=recover_p(n,pp,288)
    if p:
        print(p)
        break

这里我们得到了p的数值但是后面进行计算的时候发现还有一个不互素的问题

这里的最大公约数为15

有限域开方

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
import gmpy2
from Crypto.Util.number import *
import libnum
e=4036989615
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
p = 12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
q = 12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579

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

assert p*q == n
d = inverse(e//15,phi)
m = pow(c,d,n)


R.< x > = Zmod(p)[]
f = x ^ 15 - m
f = f.monic()
res1 = f.roots()
R.< x > = Zmod(q)[]
f = x ^ 15 - m
f = f.monic()
res2 = f.roots()

for rp, _ in res1:
    for rq, _ in res2:
        mm = crt([int(rp), int(rq)], [p, q])
        try:
            res = long_to_bytes(mm)
            if b'TGCTF' in res:
                print(res.decode())
        except:
            pass

TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢

但是这道题其实并没有完全搞明白

语法题

img

1
2
3
4
5
6
7
8
9
n=int(input())
if n<=2:
    print(-1)
else:
    ans='1 '
    for i in range(n,1,-1):
        ans+=str(i)+' '
        
    print(ans)

img

1
2
3
4
5
6
7
8
9
10
11
12
def calculate_materials(n):
    torch_common = 2 * (n // 5)
    torch_red = 0
    if n >= 5:
        torch_red = (n - 5) // 10 + 1
    rail_normal = 3 * (n // 20)
    rail_powered = 2 * (n - (n // 20))

    return torch_common, torch_red, rail_normal, rail_powered
n = int(input().strip())
result = calculate_materials(n)
print(result)

在 PJSK (Project Sekai) 等二次元音游里，一个必不可少的环节就是组建你的小队。在挑出了组队的角色之后，玩家还需要从中选出一个角色当队长。

​ 你选择了 5 个角色组成小队，TA们的战力按照降序排列分别是 a1,a2,a3,a4,a5。而你的好友也用 5 个角色组了一个小队，TA们的战力按照降序排列分别是 b1,b2,b3,b4,b5。一个小队的总实力，等于队长战力的两倍，加上其余四个队员的战力之和。 你的好友是个萌新，TA打算从五个角色中随机取出一个当队长。你想知道，你是否存在一种选队长的方案，使得你的小队总实力有可能严格大于你的好友。

​ 第一行，输入五个整数 a1,a2,a3,a4,a5 (100000≥a1≥a2≥a3≥a4≥a5≥1)，代表你选出的五个角色的战力。

​ 第二行，输入五个整数 b1,b2,b3,b4,b5 (100000≥b1≥b2≥b3≥b4≥b5≥1)，代表你的好友选出的五个角色的战力。

​ 如果存在一种选队长的方案，使得你的小队总实力有可能严格大于你的队友，那么输出 YES，否则输出 NO。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    while True:
        try:
            a = list(map(int, input().split()))
            b = list(map(int, input().split()))
            if len(a) != 5 or len(b) != 5:
                continue
            a_decreasing = all(a[i] > a[i + 1] for i in range(4))
            b_decreasing = all(b[i] > b[i + 1] for i in range(4))
            if a_decreasing and b_decreasing:
                u = a[0] * 2 + sum(a[1:])
                s = b[4] * 2 + sum(b[:4])
                print("NO" if u <= s else "YES")
            else:
                pass
        except EOFError:
            break
        except (ValueError, IndexError):
            continue
if __name__ == "__main__":
    main()

已知变量主流有两种命名方式：“驼峰命名法”和“下划线命名法”。小红更喜欢用“下划线命名法”。这个命名法的规则是：

∙变量名仅由小写字母和下划线组成，用下划线来连接每个单词（单词不能为空），每个单词均由小写字母组成，每两个单词之间有一个下划线（

）。例如，xiong_ming, zhu_ge

均为下划线命名法。

现在小红希望你写出一个长度为 n 的、使用了下划线命名法命名的变量。为了显出特征，请保证该变量至少由两个单词组成。

输入一个正整数 n(3≦n≦100)，代表需要构造的变量长度。

输出一个长度为 n 的字符串，代表你所构造的使用了下划线命名法命名的变量。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
m = int(input())
a="a"
b="_"
s="w"
d="c"
p="y"
for i in range(m-1):
    if(i%2==0):
        s+=a
        if i in range(m-1):
            s+=s
            if i in range(m-1):
                s+=d
                if i in range(m-1):
                    s+=p
    else:
        s+=b
s+=a
s+=p
s+=d
print(s)

Bingbong 给定一个字符串 s。她认为一个长度为 5 的字符串 ttt 是「完美对称字符串」，当且仅当 t0=t2=t4t_0=t_2=t_4t0=t2=t4 且 t1=t3t_1=t_3t1=t3，同时 t0≠t1t_0\neq t_1t0=t1（下标从 0 开始）。 现在请你统计 sss 中有多少个子串是「完美对称字符串」。 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入一个长度为 5≦length(s)≦2×1055 ，由小写字母构成的字符串 s。

一个整数，表示 s 中有多少个子串是「完美对称字符串」。

1
2
3
4
5
6
7
s = list(input())
n = 0
for i in range(len(s)-5):
    if s[i] != s[i+1]:
        if s[i] == s[i+2] and s[i] == s[i+4] and s[i+1] == s[i+3]:
            n = n + 1
print(n)

Bingbong 对于本题有时间复杂度 O(2n)和 O(n3) 的做法。现在给定整数 n，请你判断哪种时间复杂度是更优解。 更优解的意思是，通过代入整数 nnn 得出的计算次数更少的时间复杂度方案。

一个整数 n(1≦n≦20)表示数据范围。

一个字符，表示方案。若 O(2n) 更优，直接输出字符 A，否则（若 O(n3) 更优）输出字符 B。我们可以证明，不存在两个复杂度计算次数相等的情况，即题目保证有唯一解。

1
2
3
4
5
6
7
n = int(input())
A = 2 ** n
B = n ** 3
if (A > B):
    print ("B")
else:
    print ("A")

给定一个 n 行 m 列的网格，我们使用 (i,j) 表示网格中从上往下数第 iii 行和从左往右数第 jjj 列的格子。小红现在位于 (1,1)，准备前往 (n,m)。

\hspace{15pt}然而，不是所有的格子都是可以通行的，有且恰有一个格子是陷阱格，一旦小红踏入陷阱格，就会直接去逝。保证这个陷阱格不会出现在 (1,1) 和 (n,m)。

小红每一步只能向右或者向下前进。请你帮小红规划一条行动路线，使得她可以顺利到达 (n,m)(n,m)(n,m)。

行动路线为一个仅由字符 ‘D’\texttt{D'}‘D’、‘S’\texttt{S’}‘S’ 构成的字符串 sss，第 iii 个字符代表小红第 iii 次行动的方向。记第 iii 次行动前小红位于 (x,y)(x,y)(x,y)，则：

$$
\bullet,若 si=‘D’s_i = \texttt{`D’}si=‘D’，则小红向右移动一格即抵达 (x,y+1)； \

\bullet,若 si=‘S’s_i = \texttt{`S’}si=‘S’，则小红向下移动一格即抵达 (x+1,y)。
$$

第一行输入两个正整数 n,m(2≦n,m≦103)n,m ，代表网格的行数和列数。

接下来的 n 行，第 i 行输入一个长度为 m 的、仅由 ‘.’\texttt{.'}‘.’ 和 ‘#’\texttt{#‘}‘#’ 构成的字符串 ai,1ai,2⋯ai,ma_{i,1}a_{i,2}\cdots a_{i,m}ai,1ai,2⋯ai,m。其中 ai,j=‘.’a_{i,j} = \texttt{.'}ai,j=‘.’ 表示格子 (i,j)(i,j)(i,j) 可以通行，ai,j=‘#’a_{i,j} = \texttt{#‘}ai,j=‘#’ 表示格子 (i,j)(i,j)(i,j) 是陷阱格。

除此之外，保证有且只有一个陷阱格，且不位于 (1,1)和 (n,m)。

输出一个字符串，代表小红的行动路线。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

1
2
3
4
5
6
7
8
9
10
n,m=map(int,input().split())
for i in range(1,n+1):
    a=input()
    if '#' in a:
        x=i
        y=a.find('#')+1
if x==1 or y==m:
    print('S'*(n-1)+'D'*(m-1))
else:
    print('D'*(m-1)+'S'*(n-1))

wjh 参加了一场简单的游戏。游戏规则如下：一场游戏有三个人，第 iii 个人会抽到一个数字 aia_iai，保证数字两两不同。现在已知每个人的数字，wjh 的编号为 xxx，请你判断 wjh 是否会赢。如果 wjh 没有赢（即数字不是最大）就输出 No，否则输出 Yes。

在一行上输入四个正整数 a1,a2,a3,x(0≤ai<231; 1≤x≤3)a_1, a_2, a_3, x ，代表第一、二、三人的数字和 wjh 的编号。保证 a1,a2,a3a_1, a_2, a_3 两两不同。

如果 wjh 数字最大，请输出 Yes，否则输出 No。

1
2
3
4
5
6
7
8
9
a1, a2, a3, x = map(int, input().split())
if x == 1 and a1 > a2 and a1 > a3:
    print("Yes")
elif x == 2 and a2 > a1 and a2 > a3:
    print("Yes")
elif x == 3 and a3 > a1 and a3 > a2:
    print("Yes")
else:
    print("No")

学习中碰到的疑问

Nepsign

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
from gmssl import sm3
from random import SystemRandom
from ast import literal_eval
import os
flag = os.environ["FLAG"]
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)
    return h
def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]


class Nepsign():
    def __init__(self):
        self.n = 256
        self.hex_symbols = '0123456789abcdef'
        self.keygen()

    def keygen(self):
        rng = SystemRandom()
        self.sk = [rng.randbytes(32) for _ in range(48)]
        self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)]
        return self.sk, self.pk

    def sign(self, msg, sk=None):
        sk = sk if sk else self.sk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        qq = [0] * 48
        for i in range(32):
            step[i] = a[i]
            qq[i] = SM3_n(sk[i], step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            qq[i + 32] = SM3_n(sk[i + 32], step[i + 32])
        return [i for i in qq]

    def verify(self, msg, qq, pk=None):
        qq = [bytes.fromhex(i) for i in qq]
        pk = pk if pk else self.pk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        pk_ = [0] * 48
        for i in range(32):
            step[i] = a[i]
            pk_[i] = SM3_n(qq[i], 255 - step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            pk_[i + 32] = SM3_n(qq[i + 32], 255 - step[i + 32])
        return True if pk_ == pk else False


print('initializing...')
Sign = Nepsign()
while 1:
    match int(input('> ')):
        case 1:
            msg = bytes.fromhex(input('msg: '))
            if msg != b'happy for NepCTF 2025':
                print(Sign.sign(msg))
            else:
                print("You can't do that")
        case 2:
            qq = literal_eval(input('give me a qq: '))
            if Sign.verify(b'happy for NepCTF 2025', qq):
                print(flag)

这里给出来了伪造消息 b’happy for NepCTF 2025’ 的有效签名，我们需要从服务器获取flag。

SM3_n(data, n, bits)：迭代计算n次SM3哈希，返回指定位数结果

初始化：计算目标消息的step_target（48元素数组）

交互循环：

生成随机消息

计算其step_i

寻找未完成且满足step_i[i] <= step_target[i]的位置

发送消息获取服务器签名（48元素列表）

对有效位置计算：qq_target[i] = SM3_n(服务器签名[i], delta)

（其中delta = step_target[i] - step_i[i]）

结果提交：用完整qq_target列表获取flag

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
from gmssl import sm3
import os
from pwn import *
import ast

# 实现与服务器一致的SM3和SM3_n
def SM3(data):
    d = list(data)
    return sm3.sm3_hash(d)


def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        d = list(data)
        h = sm3.sm3_hash(d)
        data = bytes.fromhex(h)
    return data.hex()[:bits // 4]


# 计算step数组
def calc_step(msg):
    m = SM3(msg)
    m_bin = bin(int(m, 16))[2:].zfill(256)
    a = [int(m_bin[i * 8:i * 8 + 8], 2) for i in range(32)]
    hex_symbols = '0123456789abcdef'
    sum_arr = [0] * 16
    for i in range(16):
        for j in range(1, 65):
            if m[j - 1] == hex_symbols[i]:
                sum_arr[i] += j
        sum_arr[i] %= 255
    return a + sum_arr


# 设置目标消息
target_msg = b'happy for NepCTF 2025'
step_target = calc_step(target_msg)

# 连接服务器（替换实际地址和端口）
host = "nepctf30-cbwv-uyxi-bmk7-vlok77utp923.nepctf.com"
port = 443

# 使用pwntools原生SSL支持
conn = remote(host, port, ssl=True, sni=host)
conn.recvuntil(b'> ')

# 初始化存储
qq_target = [None] * 48
done_mask = [False] * 48
count_done = 0

# 主攻击循环
while count_done < 48:
    random_msg = os.urandom(32)  # 生成32字节随机消息
    step_i = calc_step(random_msg)
    useful_indices = []

    # 检查是否有未完成的位置满足条件
    for i in range(48):
        if not done_mask[i] and step_i[i] <= step_target[i]:
            useful_indices.append(i)
    if not useful_indices:
        continue

    # 发送选项1获取签名
    conn.sendline(b'1')
    conn.recvuntil(b'msg: ')
    conn.sendline(random_msg.hex().encode())
    sig_line = conn.recvline().decode().strip()

    # 处理错误响应
    if sig_line == "You can't do that":
        continue
    try:
        qq_list = ast.literal_eval(sig_line)
    except:
        continue

    # 计算目标签名片段
    for i in useful_indices:
        if done_mask[i]:
            continue
        delta = step_target[i] - step_i[i]
        qq_i_bytes = bytes.fromhex(qq_list[i])
        qq_target[i] = SM3_n(qq_i_bytes, delta, 256)
        done_mask[i] = True
        count_done += 1
        print(f"Position {i} done: {count_done}/48")

# 提交伪造签名获取flag
conn.sendline(b'2')
conn.recvuntil(b'give me a qq: ')
conn.sendline(str(qq_target).encode())
flag = conn.recvline().decode()
print("FLAG:", flag)
conn.close()

NepCTF{c7b2a558-2ac5-2bb2-cc00-767c18282528}

在LCG的那个题还有另一个方法但是没有成功不清楚行不行反之当时我没有搞出来

情感思考总结

打完NepCTF感觉水平好高 要学的东西还有好多 感觉自己效率好低进度好慢也不知道为什么可能是学习方法还有问题吧