H&NCTF-2025

(Updated: )

数据处理

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 bytes_to_long
import random
flag = b"H&NCTF{}"

btl = str(bytes_to_long(flag))
lowercase = '0123456789' 
uppercase = '7***4****5' 

table = ''.maketrans(lowercase, uppercase) 

new_flag = btl.translate(table)
n = 2 ** 512

m = random.randint(2, n - 1) | 1


c = pow(m, int(new_flag), n)
print('m = ' + str(m))
print('c = ' + str(c))
# m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
# c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399

求解离散对数问题

然后给出了一个已知部分的解密数据，排列组合的方式爆破寻找到正确的e的组合

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399
n = 2**512
G=Zmod(n)
m1=G(m)
c1=G(c)
print(ZZ(discrete_log(c1,m1)))
#3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701
1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import long_to_bytes
import itertools
flag = "3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701"
for i in itertools.permutations('0123689'):  
    tmp = ''.join(i)
    target = '7' + tmp[:3] + '4' + tmp[3:] + '5'
    table = ''.maketrans(target, "0123456789")
    res = flag.translate(table)
    new_flag = long_to_bytes(int(res))
    if b'H&NCTF{' in new_flag:
        print(new_flag)
#b'H&NCTF{cut_cut_rrioajtfijrwegeriogjiireigji}'
#b'H&NCTF{e\xab\xaf\x98\x1dofP\x86=\x15\x82\xc9V\r\x8f\x8by\xd5]\xed\xe5\x93\x01\xf9O\xcc\x18X$/1\x83\xbd\xc4\x81}'

为什么出题人的rsa总是ez

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
#part 1

def pad(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)
n = p * q
e = 0x10001
flag = b''
m = pad(flag)
assert m < n

c = pow(m, e, n)

print(f"c={c}")
print(f"n={n}")
print(f"h1={p + b * q}")
print(f"h2={a * p + q}")
# c=13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043
# n=13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549
# h1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
# h2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939

#part 2

from Crypto.Util.number import *
from gmpy2 import *
a = random_prime()
b = random_prime()
g = random_prime()
h = 2*g*a*b+a+b
while not is_prime(h):
    a = random_prime()
    b = random_prime()
    g = random_prime()
    h = 2*g*a*b+a+b
N = 2*h*g+1
e from part1's flag
flag=b''
c=pow(bytes_to_long(flag),e,N)
print(N)
print(g)
print(c)
#N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
#g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
#c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097

part1

关键代码

1
2
print(f"h1={p + b * q}")
print(f"h2={a * p + q}")

审计代码，p，q，a，b都是1024位左右的数据，明显没有可能爆破构造寻找到正确的式子

后续寻找到相似的例题DownUnderCTF2023的ap+bq-ii，大致思路是一样的，通过构造等式化去未知数p和q最后用LLL算法求最小向量

后续找到原题的论文，用论文的exp得到了结果，但是原论文的exp打了sagemath会挂掉，貌似是exp中的界给高了然后会炸内存（大概吧

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
x = 16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939
y = 6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
n = 13718277507497477508850292481640653320398820265455820215511251843542886373380880887850571647060788265498378060163112689840208264538965960596605641194331300743676780910818492860412739541418029075802834265712602393103809065720527365081016381358333378953245379751008531500896923727040455566953960991908174586311899809864209624888469263612475732913062035036254077225370843701146080145441104733074178115602425412116325647598625157922655504918118208783230138448694045386019901732846478340735331718476554208157393418221315041837392020742062275999319586357229583509788489495876723122993592623230858393165458733055504467513549
c = 13148687178480196374316468746303529314940770955906554155276099558796308164996908275540972246587924459788286109602343699872884525600948529446071271042497049233796074202353913271513295267105242313572798635502497823862563815696165512523074252855130556615141836416629657088666030382516860597286299687178449351241568084947058615139183249169425517358363928345728230233160550711153414555500038906881581637368920188681358625561539325485686180307359210958952213244628802673969397681634295345372096628997329630862000359069425551673474533426265702926675667531063902318865506356674927615264099404032793467912541801255735763704043
e = 65537

R = Integers(n)
P.<a, b, p, q> = PolynomialRing(Integers(n))
f1 = a*p + q
f2 = p + b*q
f3 = p*q
I = Ideal([f1 - x, f2 - y, f3 - n])
B = I.groebner_basis()

g = B[-1]

z = ZZ(g.coefficient({q: 1}))
assert g.constant_coefficient() == R(-y)

_, (z1, _), (z2, _) = list(g)
z1 = ZZ(z1)
z2 = ZZ(z2)

S = 2^1024
for p_upper_bits in range(16):
	p_upper = p_upper_bits << 1020
	for q_upper_bits in range(16):
		q_upper = q_upper_bits << 1020
		M = matrix(ZZ, [[S, -1, 0, 0], [S*z1, 0, -1, 0], [S*(z2 + p_upper + q_upper*z1), 0, 0, S], [S*n, 0, 0, 0]])
		B = M.LLL()
		for b in B:
			if b[-1] == S:
				if b[1] < 0:
					b *= -1

				p_guess = b[1] + p_upper
				q_guess = b[2] + q_upper
				if p_guess * q_guess == n:
					d = pow(e, -1, (p_guess - 1)*(q_guess - 1))
					print(int(pow(c, d, n)).to_bytes(1024//8, 'big'))
					exit()
#b'flag{e_is_xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix,bubbleBabble}\xea\xc7P|OQ\x0f\xbc\xdcL;@-\x04\x9de\xd4\x14\xa7vNN\xa1\xce$T\xfd\x12\xc4\x9b\xfe\xeew'

根据提示用工具解密得到e=81733668723981020451323

part2

Common prime 未成年版本，已经知道N,g,又N=(2ga+1)(2gb+1)，直接求a和b的近似值

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
from tqdm import trange
from Crypto.Util.number import *
N=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
e=81733668723981020451323
g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
enc=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097
h = (N-1)//(2*g)
# print(h)
from gmpy2 import iroot
ab_ = h//(2*g)
# print(ab - a*b)

# print((ab - a*b).bit_length())

# print(2**24-13699487)

for i in trange(2**24):
     ab = ab_ - i
     absum = h - 2*g*ab
     if absum**2-4*ab < 0:
         continue
     abdiff = iroot(absum**2-4*ab, 2)[0]
     a = (absum + abdiff) // 2
     b = (absum - abdiff) // 2
     if a*b == ab:
         print(a)
         print(b)
         break

a =24870971735420969866980201699353105101318234729573742624326108601424579832109415269399197614067973836280816637774236895569768620866007016994268948848166203739 
b = 19528989906570790635395875562119230831068132104662250479566778328876156336866218924360075104993591320925404144434470748817281822291441354435866249504179957130

p = 2*g*a + 1
q = 2*g*b + 1

assert p*q == N
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(enc,d,N)
print(long_to_bytes(m))
b'flag{I wish you success in your cryptography career}'

PS：出这题的哥们对24强网杯这么情有独钟吗

LCGP

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 Crypto.Util.number import *
import gmpy2
import random
n = getPrime(1024)
flag = b'H&NCTF{' + str(uuid.uuid4()).encode() + b'}'
flag=bytes_to_long(flag)
e = 2024
c=pow(e, flag, n)

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(c, getPrime(256), getPrime(256), getPrime(2048))
random = [lcg.generate() for _ in range(5)]

print(random)
print("n=",n)
#[11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]
#n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

lcg问题给了5个output输出要求恢复a，b，n（眼瞎了以为是给出output和n恢复a，b浪费了半小时）

用grobner基构造4个式子组成线性方程组求解即可（还不太懂grobner基的核心，目前当黑盒用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage
from Crypto.Util.number import *
output =  [11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]
R.<a,b> = PolynomialRing(ZZ)

f1 = output[0]*a + b - output[1]
f2 = output[1]*a + b - output[2]
f3 = output[2]*a + b - output[3]
f4 = output[3]*a + b - output[4]

F = [f1,f2,f3,f4]

ideal = Ideal(F)

I = ideal.groebner_basis()

a = ZZ(-I[0].univariate_polynomial()(0))
b = ZZ(-I[1].univariate_polynomial()(0))
n = ZZ(I[2])
m = (output[0] - b) * inverse(a,n) % n

print(m)
#98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350

然后接着求解离散对数问题即可

1
2
3
4
5
6
7
8
from Crypto.Util.number import long_to_bytes

m=98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350
n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

c=discrete_log(mod(m,n),mod(2024,n))
print(long_to_bytes(int(c))
      #H&NCTF{7ecf4c8c-e6a5-45c7-b7de-2fecc31d8511}