bi0sCTF 2024#

Tuần trước, mình có chơi bi0sCTF với team G.0.4.7 và làm được 5/6 bài crypto. Sau đây là chi tiết write-up cho những bài mình làm được (và có thể update luôn bài cuối nếu làm ra 😥)

lalala - 80 solves#

• chall.sage

from random import randint
from re import search

flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}"

p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

output = []
for _ in range(100):
    aa = [randint(0, 2**1024) for _ in range(1000)]
    bb = [randint(0, 9) for _ in range(1000)]
    cc = [randint(0, 9) for _ in range(1000)]
    output.append(aa)
    output.append(bb)
    output.append(cc)
    output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)
# with open("out1.py",'w') as out:
#     out.write(f"{p = }\n")
#     out.write(f"{output = }")
print(f"{p = }")
print(f"{output = }")

• out.py
• Đây là một bài đơn giản về giải hệ phương trình. Ở đây đề bài tạo ra một mảng unknows chưa biết, sau đó thực hiện các phép tính gì đó trên unknows. Nhận thấy rằng nếu có được unknows thì ta dễ dàng tìm được flag bằng cách chia lấy dư mỗi phần tử cho 1000 nhờ vào dòng này.

unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

• Mục tiêu chính của ta là phải tìm bằng được unknows. Chương trình sẽ tạo ra các mảng aa, bb, cc, sau đó thực hiện phép tính sau:

sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p

Vì aa đã biết => tổng các a cũng đã có, coi unknows[b]^2*unknowns[c]^3 := u_{10b+c}, ta có thể dễ dàng lập được 1 phương trình 100 ẩn từ u0 đến u99. Để ý rằng chương trình tạo ra 100 lần lặp như vậy, do đó ta cũng thu được 100 phương trình tương ứng. Vấn đề còn lại bây giờ chỉ là giải hệ phương trình, còn việc giải như thế nào chắc mọi người đều biết rồi ha :)).

• Full script giải:

from random import randint
from re import search
from sage.all import * 

with open("out.py",'r') as out:
	exec(out.readline())
	exec(out.readline())
aa = []
bb = []
cc = []
res = []
for i in range(len(output)):
	if i % 4 == 0:
		aa.append(sum(output[i]))
	elif i % 4==1:
		bb.append(output[i])
	elif i % 4==2:
		cc.append(output[i])
	else:
		res.append(output[i])
assert len(aa)==len(bb)==len(cc)==len(res)==100
mat = []

for i in range(100):
	row = [0]*100
	for j in range(1000):
		row[bb[i][j]*10 + cc[i][j]] += 1
	mat.append(row)
mat = matrix(GF(p), mat)
res = [res[i] - aa[i] for i in range(len(res))]
res = vector(GF(p), res)
x = (~mat)*res
x = list(int(i) for i in x)
unknowns = [int(pow(x[i],1/5))%1000 for i in range(0,100,11)]
print(unknowns)
print(''.join(chr(c) for c in unknowns))

challengename - 54 solves#

• server.py

from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json

flag = open("flag", "rb").read()[:-1]

magic = os.urandom(16)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ###REDACTED###
b = ###REDACTED###
G = ###REDACTED###

q = G.order()

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

def bytes_to_long(s):
    return int.from_bytes(s, 'big')

def genkeys():
    d = random.randint(1,q-1)
    pubkey = Public_key(G, d*G)
    return pubkey, Private_key(pubkey, d)

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--', x, y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

nonces = set()

for _ in '01':
    try:
        msg = bytes.fromhex(input("Message: "))
        nonce = bytes.fromhex(input("Nonce: "))
        if nonce in nonces:
            print("Nonce already used")
            continue
        nonces.add(nonce)
        print(sign(msg,nonce,privkey))
    except ValueError:
        print("No hex?")
        exit()

• Đây là một bài về nonce reuse attack trong ECDSA. Ban đầu server cung cấp cho ta 2 điểm (1 public key và encrypted flag) nằm trên một hidden curve. Để xử lý được phần attack sau thì mình cần recover curve parameters từ 2 điểm đã cho.

Find curve parameters#

Ta có phương trình curve là: $y^2 = x^3 + ax + b$, thay tọa độ của 2 điểm đã cho và giải hpt để tìm a,b:

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)

r = remote("13.201.224.182",30773)
# r = process(["python3", "server.py"])
pubkey = eval(r.recvlineS().strip().split(':')[1])
enc = eval(r.recvlineS().strip().split(':')[1])
coeff = matrix(K, [[pubkey[0], 1], [enc[0], 1]])
hstd = vector(K, [pubkey[1]**2 - pubkey[0]**3, enc[1]**2 - enc[0]**3])
res = coeff.inverse() * hstd 
a,b = res 
print(res)

Nonce reuse attack#

• Server cho ta 2 lần ký, mỗi lần ta sẽ phải cung cấp msg và nonce. Đọc trong hàm sign() ta thấy server ký msg với giá trị nunce=md5(bigsur(nonce,magic)).digest(). Ta phải tìm cách cung cấp 2 giá trị nonce sao cho thu được 2 nunce giống nhau. Sau một hồi phân tích hàm bigsur() thì mình nhận ra source code dài ngoằng của nó chỉ có tác dụng tương đương với hàm sau:

def _bigsur(a,b):
    if len(a) < len(b):
        a,b = b,a 
    return bytes([i ^ j for i,j in zip(a, b'\x00'*(len(a) - len(b)) + b)]) 

Đại khái là gán a là chuỗi bytes dài hơn, b là chuỗi bytes ngắn hơn trong 2 chuỗi a,b. Sau đó thêm null bytes vào trước chuỗi b sao cho dài bằng chuỗi a rồi xor 2 chuỗi lại.

• Nắm được điều đó, nếu gởi 2 nonce là b'\0' và b'\0\0' thì chắc chắn rằng 2 nunce thu được giống nhau mặc dù không biết giá trị của magic => nonce reuse attack.
• solve.py

from pwn import * 
from sage.all import *
from hashlib import md5
import json
from Crypto.Util.number import long_to_bytes, bytes_to_long
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
def hash(m):
    return bytes_to_long(md5(m).digest())

r = remote("13.201.224.182",30773)
# r = process(["python3", "server.py"])
# recover curve parameters
pubkey = eval(r.recvlineS().strip().split(':')[1])
enc = eval(r.recvlineS().strip().split(':')[1])
coeff = matrix(K, [[pubkey[0], 1], [enc[0], 1]])
hstd = vector(K, [pubkey[1]**2 - pubkey[0]**3, enc[1]**2 - enc[0]**3])
res = coeff.inverse() * hstd 
a,b = res 
print(res)
# get data from server
E = EllipticCurve(K, (a, b))
n = E.order()
m1 = b'1234'
m2 = b'abcd'
r.sendlineafter(b'Message: ', m1.hex().encode())
r.sendlineafter(b'Nonce: ',b'0000')
sig1 = json.loads(r.recvlineS().strip())
r1 = int(sig1['r'][2:], 16)
s1 = int(sig1['s'][2:], 16)

r.sendlineafter(b'Message: ', m2.hex().encode())
r.sendlineafter(b'Nonce: ',b'000000')

sig2 = json.loads(r.recvlineS().strip())
r2 = int(sig2['r'][2:], 16)
s2 = int(sig2['s'][2:], 16)
# ECDSA nonce reuse attack
k = (hash(m2) - hash(m1))*pow((s2 - s1),-1,n) % n 
d = (k*s1 - hash(m1))* pow(r1,-1,n) % n 
# Once we have the secret, find the flag
flag = E(enc) * int(pow(d,-1,n))
print(flag)
print(bytes.fromhex(hex(flag.xy()[0])[2:]))

rr - 24 solves#

• chall.py

Tìm ks#

• Để tìm được ks, ta cần giải quyết bài toán logarit rời rạc: $69^x = ks_i\text{ (mod } rr^i)$. Đây là các trường đặc biệt hay nói cách khác là bài toán logarithm rời rạc trên các số p-adic: Tham khảo.

def dlp_p_adic(p, e, y,g):
    # declaration of p-adic integers ring with precision e 
    Z = Zp(p, prec=e)
    # calculating the logarithm
    x_Z = Z(y).log() / Z(g).log()
    # lifting the solution to ordinary integers
    x = x_Z.lift()
    return int(x)

Tìm flag#

• Nhìn vào cách c1 và c2 được tính, ta thấy flag là nghiệm của 2 đa thức trên Zmod(n) sau:

$f1(x) = \left(\sum_{i=0}^{19}ks_i.x^{i}\right)^{127}- c1$

$f2(x) = x^{65537}-c2$

• Do f1 và f2 có nghiệm chung => chứa nhân tử chung. Để tìm nhân tử chung thì ta tìm GCD của 2 đa thức bằng thuật toán Euclid.

def gcd_zmod(f, g):
    while g:
        f, g = g, f % g
    return f
P = PolynomialRing(Zmod(int(n)), name='x')
x = P.gen()
f1 = sum(ks[i]*x**i for i in range(20))**((1<<7)-1) - c1
f2 = x**((1<<16)+1) - c2
r = gcd_zmod(f1,f2)

• Sau khi in ra thì mình thấy r bậc nhất, do đó dễ dàng tìm nghiệm của r (cũng là nghiệm chung của f1 và f2, và cũng là flag ¯\(ツ)/¯)

coeff = r.coefficients()
root = (-coeff[0])/coeff[1]
print(long_to_bytes(int(root)))

• Full script here

Flag: bi0sctf{https://www.youtube.com/watch?v=soDR-BctVeE___1e9c4e8dba79812bd81ec4c2}

daisy_bell - 18 solves#

• chall.py

from Crypto.Util.number import *
from FLAG import flag

p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)

print(f"{n = }")
print(f"{c = }")
print(f"{p>>545 = }")
print(f"{pow(q, -1, p) % 2**955 = }")


"""
n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
p>>545 = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
pow(q, -1, p) % 2**955 = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858
"""

• Đây là một bài về parital key leak trong RSA, cụ thể bài này sẽ phải sử dụng coppersmith method. Điều quan trọng trong dạng bài này chính là build đa thức sao cho hợp lý và sử dụng coppersmith (coppersmith 2 biến mình hay tham khảo của defund).
• Bài này cho ta MSB của p và LSB của q_p (pow(q,-1,p)), ta thực hiện một vài biến đổi sau:

$q_p = q^{-1} \text{ (mod p)}$

$\Rightarrow q_p.q = 1 + kp$

$\Rightarrow q_p.n = p + k.p^2c$

$\Rightarrow q_p.n \equiv p \text{ (mod }p^2)$

$\Rightarrow n(2^{955}*x + q_{p_{lsb}}) - (2^{545}.p_{msb} + y) \equiv 0 \text{ (mod }p^2)$

Vậy ta sẽ build đa thức 2 biến $f(x,y) = n(2^{955}*x + q_{p_{lsb}}) - (2^{545}.p_{msb} + y)$ trên Zmod(n**2)

• Dùng Coppersmith của defund để tìm x,y. Tuy nhiên ta cần chọn 2 tham số m,d phù hợp thì mới ra được kết quả mong muốn. Sau một hồi bruteforce thì mình tìm được m=2 và d=7. Có được x,y, ta dễ dàng tính được p và decrypt flag.
• solve.sage

from sage.all import *  

n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
p_msb = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
qp_lsb = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858

import itertools

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.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.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 []
P.<x, y> = PolynomialRing(Zmod(n**2))
f = n*(2**955 *x + qp_lsb) - (2**545 * p_msb + y)
# for m in range(10):
# 	for d in range(10): 
# 		print(f'{m = }')
# 		print(f'{d = }')
# 		r = small_roots(f, (2**(1024-955), 2**545),m=m, d=d)
# 		print(r)

root = small_roots(f, (2**(1024-955), 2**545),m=2, d=7)
x,y = root[0]
p = 2**545*p_msb + y 
assert is_prime(p) and n%p == 0
q = int(n)//int(p)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(int(pow(c,pow(65537,-1,(p-1)*(q-1)),n)))) 

Flag: bi0sctf{https://www.youtube.com/watch?v=uerNtYhgzSw___f4e2788de0dbce918e411f35}

Katyusha’s Campervan - 16 solves#

• chall.py

from Crypto.Util.number import *
from random import randint
from FLAG import flag

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(132)
n = p*q
hint = pow(e, -1, (p-1)*(q-1))
hint %= p-1
hint %= 2**892
c = pow(3, int.from_bytes(flag), n**5) * pow(randint(0, n**5), n**4, n**5) % n**5

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print(f"{hint = }")

"""
n = 9722343735487336242847355367175705096672092545117029199851527087227001665095112331406581010290318957921703096325328326862768861459201224096506317060919486835667369908780262880850949861734346363939614200227301344831209845565227637590016962469165064818450385339408084789219460490771570003649248250098125549751883777385917121014908647963900636814694225913533250242569263841750262192296795919177720443516042006972193940464844059718044438878017817432336475087436031866077325402373438547950481634275773767410248698596974769981162966656910136575149455523084473445761780201089182021418781347413453726696240548842411960178397
e = 5323153428600607366474827268153522064873
c = 9128106076400211790302891811252824557365859263295914819806672313027356017879597156259276057232557597614548050742418485365280305524694004426832069896531486671692562462063184624416012268348059935087037828161901243824582067161433586878141008884976330185561348052441637304755454643398179479215116505856245944555306345757777557395022121796068140566220391012921030768420736902592726104037200041403396506760483386523374366225161516294778224985920562226457769686733422726488624795847474711454397538514349555958637417188665977095558680525349235100286527905789576869572972662715040982208185436819557790062517857608731996417066519220133987864808243896151962316613504271341630230274953625158957103434031391582637694278277176886221304131078005240692954168656292222792833722555464070627220306776632641544334188357810067577550784029449834217848676080193960627138929032912578951880151284003878323853182114030012207949896373695734783631698004600675811512726913649141626146115066425891236975554237158682938964099745220780884079884347052906073216530490633243676915134831324804418410566989306886192743687590855529757605789691981493863292029273401139254934543448966341439303948513266699261650278938684067402860913507689842621595391519090227639907684629841162983852454124546030986411283762938101536264676221777904450717178547838152674410566294280937400196290368544481636850750666313771438253636667634601122561235018292316232335633111595474772273810349284893171480302604833719250453453781210093266339454843926482821341993360016434693250661347303203216948599305102121353574445652764255573536572077762409837628479280331295047290459975370026620838169978316921035609492162085052786943829915442906137063599836720584533200385074702683101049336194258783047318183521466098437420153628598968954236332678203275614402446435216223033804260963642393142002417568855964535316709986640977596845897721671783670070696907220894520837335160816494605130683705587464386202643385688263935088026204614056121745160246499509455752793089324629215884008499726564579763845757062068182946721730306128755414268910929410742220199282343421146810430121947827801171056425435942640932150535954546458772114121498557119913825127286832860975814307160175273154886250581960709573672488119996389986116735407178214281982766051391618187878672106737928646489671994503814871652107136752677107398141842179907758909246276653861569864776043204134345135427118784118473462309509988521112691717301811627018054555866015966545532047340607162395739241626423495285835953128906640802690450118128515355353064004001500408400502946613169130088974076348640048144323898309719773358195921400217897006053213222160549929081452233342133235896129215938411225808985658983546168950790935530147276940650250749733176085747359261765601961315474656996860052862883712183817510581189564814317141703276878435707070103680294131643312657511316154324112431403040644741385541670392956841467233434250239028068493523495064777560338358557481051862932373791428839612299758545173203569689546354726917373906408317003812591905738578665930636367780742749804408217333909091324486584514813293
hint = 27203100406560381632094006926903753857553395157680133688133088561775139188704414077278965969307544535945156850786509365882724900390893075998971604081115196824585813017775953048912421386424701714952968924065123981186929525951094688699758239739587719869990140385720389865
"""

• Tiếp tục là một bài về partial key leak. Bài này cho ta LSB của dp (pow(e,-1,p-1)). Bài này mình build đa thức như sau:

$dp = e^{-1} \text{ (mod p-1)}$

$\Rightarrow dp*e = 1 \text{ (mod p-1)}$

$\Rightarrow e*(2^{892}*x + hint) = 1 + k(p-1)$

$\Rightarrow e*(2^{892}*x + hint) - 1 +k \equiv 0 \text{ (mod p)}$

Vậy đa thức ta build được là $f(x,k) = e*(2^{892}*x + hint) - 1 +k$ trên Zmod(n).

Defund’s Coppersmith#

• Cũng tương tự challenge trước, trong giải mình dùng Coppersmith của defund, không hẳn là của defund vì đã nó đã có 1 vài sửa đổi nhỏ, mình tham khảo tại đây (tại chạy code gốc ếu ra :)).

x,k = PolynomialRing(Zmod(n), "x,k").gens()
f = 1 - k - (hint + x*2**892) * e
## Defund's coppersmith
for d in range(10):
	for m in range(10):
		print(f"{m=}")
		print(f"{d=}")
		r = small_roots(f, [2**(1024-892), e], m=m, d=d)
		print(r)

# x,k = (1364278824202792998093019636227517188336, 2238131335516129175817357831521181270929)

Factos: mình đã treo máy đâu đó 30 phút mới ra 😥

Kiona’s Coppersmith#

• Sau giải, mình mới tìm hiểu được 1 implementation tốt hơn của Coppersmith của kiona. Theo mình tìm hiểu nó sử dụng fplll và flatter để reduce lattice, vì vậy tốc độ được cải thiện đáng kể.

import sys 
sys.path.append("../../tools/coppersmith/")
from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic 
x,k = PolynomialRing(Zmod(n), "x,k").gens()
f = 1 - k - (hint + x*2**892) * e
## kiona's coppersmith
r = coppersmith_multivariate_heuristic(f, (2**(1024-892), e), 0.499)
print(r)

Decrypt flag#

(đoạn này mình có tham khảo blog này của anh m1dm4n)

• Sau khi có giá trị x,k, dễ dàng tính được p = gcd(f(x,k), n).
• Tới đây ta thấy flag được giấu qua c như sau: $c = 3^{flag}*r^{n^4} \text{ (mod }n^5)$ với r = random.randint(0,n**5). Để bài toán trên trở về bài toán DLP thì phải làm sao để mất r. Để ý rằng $r^{\varphi(n^5)}\equiv 1 \text{ (mod }n^5)$ với $\varphi(n^5)=p^4*q^4*(p-1)*(q-1)$, khi đó $c^{(p-1)(q-1)} = 3^{flag*(p-1)*(q-1)} = 3^a \text{ (mod }n^5)$.
• Tới đây là bài toán DLP, dựa vào challenge trên thì ta dễ dàng tính dlog trên 2 trường con $p^4$ và $q^4$

x,k = (1364278824202792998093019636227517188336, 2238131335516129175817357831521181270929)
p = gcd(int(f(x, k)), n)
q = int(n) // int(p)
# print(p)
# print(q)
# p = 107137790764109294435738452887955149442794115385917421133088316383957513812938944418454606256987491520085074052815215859908950491406982768196727659910881462433670091921679086357171751905670595866834745181195419362013584004876446081357773024790677648597247435270479338298917890197185252569905294212062983995409
# q = 90746165906048159474154095991389030950712801945941795430201281468665317834501062751616036041934198161203798480412193507303323619830943569148411089764905202815514556117346348126016453518349943163524986909838095207733566566591045379396133769593776454928828989448679093566272816546270747251714472002195562821133

c = pow(c,(p-1)*(q-1), n**5)
# Solve DLP on p-adic 
Rp = Zp(p, 5)
Rq = Zp(q, 5)
ap = (Rp(c).log() / Rp(3).log()).lift()
aq = (Rq(c).log() / Rq(3).log()).lift()

• Tuy nhiên $\varphi(n^5) =p^4*q^4*(p-1)*(q-1)$, do đó việc tính dlog trên các số p-adic chỉ trả về 1 số thuộc subgroup có order $p^4$ của GF(p**5), tương tự với q. Để tìm được “chính xác” a thì ta cần tính dlog trên 2 trường con p-1 và q-1, rồi dùng CRT đề gom lại để khôi phục a. Tuy nhiên p và q không phải là 2 smooth prime, do đó việc tính toán trên 2 trường con p-1 và q-1 là gần như bất khả thi. Tới đây đoán rằng độ dài flag chắc không vượt quá $n^4$ (tâm linh vl 🤣) nên mình thử tính luôn a trên subgroup có order = $n^4$ (dùng CRT để gộp 2 subgroup mod $p^5$ và $q^5$) và cuối cùng cũng recover được flag 🤣.

a = int(crt([ap, aq], [p**4, q**4]))
assert pow(3, a, n**5) == c
print(long_to_bytes(a*pow((p-1)*(q-1),-1,n**4) % n**4))

Hmm hình như họ cố tình padding space vào đề flag dài hơn thì phải, may là không dài quá $n^4$ Flag: bi0sctf{https://www.youtube.com/watch?v=ugaq46wedOk__________09f05ff4f5d5b6c2f}