R3CTF 2025

split3pig

Source code của bài

from Crypto.Util.number import isPrime
from hashlib import sha256
from secret import P,Q,flag
 
r = 2 
N = P * Q ** r
E1 = 17599828213549223253832044274649684283770977196846184512551517947600728059 
E2 = 13524024408490227176018717697716068955892095093578246398907145843636542721
assert isPrime(P)
assert isPrime(Q)
assert (P - 1) % E1 == 0
assert (Q - 1) % E2 == 0
 
H = sha256()
H.update(str(Q).encode())
assert flag == "r3ctf{" + H.hexdigest() + "}"
 
print(N)
"""
39857078746406469131129281921490520306196739933449401384580614683236877901453146754149222509812535866333862501431453065249306959004319408436548574942416212329735258587670686655658056553446879680643872518009328886406310298097685861873954727153720761248262606469217940464611561028443119183464419610396387619860313813067179519809796028310723320608528262638653826016645983671026819244220510314301178181698134390850683834304169240632402535087021483298892547974104858755498823118164815682452718215716370727477136888839954993949013970026988378086175471190518276414200966496353144747778470590767485019943178534397845127421058830430797806265311195099187747227867325234593386438995618936934586514932401108874934000734850169069717060963988677462779177959990601405850727404268354600078746523164279
"""

Phân tích:
Đầu tiên ở bài này thì ta có modulo $N = P Q^{2}$ và ta được cho biết 2 giá trị $E_{1}, E_{2}$ . Hai giá trị này đóng vai trò là modulo cho các đồng dư thức

P \equiv 1 (mod E_{1}) Q \equiv 1 (mod E_{2})

Ta cần dựa vào các thông tin này để factor lại $N$ , tìm $Q$ và có được flag = r3ctf{sha256(Q)}.
Minh thử tìm đọc một số tài liệu coi sao:

Dựa vào 2 điều kiện trên là ta biết được $r$ và biết một xấp xỉ $p \sim$ của p thì ta có thể tìm một nghiệm nhỏ của đa thức $F (x) = (p \sim + x)^{r} \equiv 0 mod p^{r}$ . Thực ra cách này cũng không ổn lắm vì ở bài này mình cũng chả biết $p, q$ có bit length là bao nhiêu hết?? Nhưng có thể thử ước lượng.
Đầu tiên là từ $N = P Q^{2}$

>>> N = 39857078746406469131129281921490520306196739933449401384580614683236877901453146754149222509812535866333862501431453065249306959004319408436548574942416212329735258587670686655658056553446879680643872518009328886406310298097685861873954727153720761248262606469217940464611561028443119183464419610396387619860313813067179519809796028310723320608528262638653826016645983671026819244220510314301178181698134390850683834304169240632402535087021483298892547974104858755498823118164815682452718215716370727477136888839954993949013970026988378086175471190518276414200966496353144747778470590767485019943178534397845127421058830430797806265311195099187747227867325234593386438995618936934586514932401108874934000734850169069717060963988677462779177959990601405850727404268354600078746523164279
>>> print(N.bit_length())
2607
>>> E1 = 17599828213549223253832044274649684283770977196846184512551517947600728059
8490227176018717697716068955892095093578246398907145843636542721>>> E2 = 13524024408490227176018717697716068955892095093578246398907145843636542721
>>> print(E1.bit_length())
244
>>> print(E2.bit_length())
243
>>>

Nếu ước lượng thì số bit của $Q$ sẽ rơi vào khoảng $2607/3 = 869$ .
Sau đó ta có thể recover lại một phần giá trị của $Q$ bằng cách lấy CRT hai phương trình sau

q \equiv 1 mod e_{2} q^{2} \equiv n mod e_{1}

Giả sử ta tìm được một nghiệm là $r_{q}$ thỏa mãn $r_{q} \equiv q mod e_{1} e_{2}$ thì ta có thể viết lại $q = k e_{1} e_{2} + r_{q}$ với $k$ bị chặn trên bởi $K = 2^{q bi t - 487} = 2^{382}$ .

Coppersmith methods (nhắc lại):
Ta muốn xây dựng từ $g (x)$ một đa thức $f (x)$ sao cho với mỗi nghiệm modulo $N$ là $x_{0}$ của $f$ thì nó cũng là nghiệm của $g$ . Cụ thể với mỗi $x_{0}$ thỏa

f (x_{0}) = 0 mod N, ∣ x_{0} ∣ < X

thì ta cũng sẽ có $g (x_{0}) = 0$ trên $Z$ .
Ở đây mình không nhắc lại cơ sở lí thuyết của thuật toán này (khá dài dòng). Mọi người có thể xem ở đây main-akl.

Một số định lí quan trọng:
Định lí 1. Cho $N$ là một số nguyên dương mà ta chưa rõ phân tích nguyên tố của nó. Cho $f (x)$ là một đa thức đơn biến với bậc là $δ$ . Thì khi đó ta có thể tìm được tất cả các nghiệm của phương trình

f (x_{0}) = 0 mod N, ∣ x_{0} ∣ < N^{1/ δ}

trong thời gian $O (lo g^{6 + ϵ} N)$ với mỗi $ϵ > 0$ .

Mở rộng cho thừa số.

Để tìm nghiệm cho một thừa số của $N$ (thừa số đó ta chưa biết rõ), cụ thể ta muốn tìm nghiệm của phương trình $f (x) = 0 mod b$ trong đó $b ∣ N$ và $b > N^{β}$ .

Định lí 2. Cho $N$ là một số nguyên dương mà ta chưa rõ phân tích nguyên tố của nó và có một thừa số $b \geq N^{β}, 0 < β \leq 1$ . Với $c \geq 1$ và $f (x)$ là một đa thức có bậc $δ$ , ta có thể tìm tất cả các nghiệm $x_{0}$ của phương trình

f (x) = 0 mod b, ∣ x_{0} ∣ < c N^{\frac{β ^{2}}{δ}}

trong thời gian $O (c lo g^{6 + ϵ} N)$ với mỗi $ϵ > 0$ .

Quay lại bài của ta. Trước tiên ta cần kiểm tra lại coppersmith bound cho $q$ . Ở đây $q \geq N^{2/3}$ , hệ số $β = 2/3$ . Tiếp theo là xây dựng đa thức.
Bước 1: Ta cần tìm lại $r_{q}$ .

from sage.all import *
from Crypto.Util.number import *
N = 39857078746406469131129281921490520306196739933449401384580614683236877901453146754149222509812535866333862501431453065249306959004319408436548574942416212329735258587670686655658056553446879680643872518009328886406310298097685861873954727153720761248262606469217940464611561028443119183464419610396387619860313813067179519809796028310723320608528262638653826016645983671026819244220510314301178181698134390850683834304169240632402535087021483298892547974104858755498823118164815682452718215716370727477136888839954993949013970026988378086175471190518276414200966496353144747778470590767485019943178534397845127421058830430797806265311195099187747227867325234593386438995618936934586514932401108874934000734850169069717060963988677462779177959990601405850727404268354600078746523164279
E1 = 17599828213549223253832044274649684283770977196846184512551517947600728059 
E2 = 13524024408490227176018717697716068955892095093578246398907145843636542721
qbit = N.bit_length()//3+1
e1_bit = E1.bit_length()
e2_bit = E2.bit_length()
# recover r_q
# n^2 % E1 = q^2
q_sqr = N % E1 
rq_sqrt = Zmod(E1)(q_sqr).nth_root(2, all = True)
print(f"{rq_sqrt = }")
'''
rq_sqrt = [14346144313156529128994653626365645384420894433238022881266385922892647527, 7181680325360253763581541163469962019574740615889276990812569916876713632, 14144975622940480768250834355181506362884814738282949210271592305550065370, 6980511635144205402837721892285822998038660920934203319817776299534131475, 4031690472403705718361474807012316229254472916959907066486492952455745733, 14467054698156653606780406618766317148179296296457345688584194894040539897, 3830521782187657357617655535828177207718393222004833395491699335113163576, 14265886007940605246036587347582178126643216601502272017589401276697957740, 7251923262835500513530704655170489519761013706199330546167742568691136826, 87459275039225148117592192274806154914859888850584655713926562675202931, 7050754572619452152786885383986350498224934011244256875172948951348554669, 17486118798372400041205817195740351417149757390741695497270650892933348833, 14537297635631900356729570110466844648365569386767399243939367545854963091, 7372833647835624991316457647571161283519415569418653353485551539839029196, 14336128945415851995985750839282705626829489691812325572944573928512380934, 7171664957619576630572638376387022261983335874463579682490757922496447039, 10428163255929646623259405898262662021787641322382604830060760025104281020, 3263699268133371257846293435366978656941487505033858939606944019088347125, 10226994565713598262515586627078523000251561627427531159065966407761698863, 3062530577917322897102474164182839635405407810078785268612150401745764968, 113709415176823212626227078909332866621219806104489015280867054667379226, 10549073640929771101045158890663333785546043185601927637378568996252173390, 17512368938509998105714452082374878128856117307995599856837591384925525128, 10347904950713722740301339619479194764009963490646853966383775378909591233, 3333942205608618007795456927067506157127760595343912494962116670902770319, 13769306431361565896214388738821507076052583974841351117059818612487564483, 3132773515392569647051637655883367135591680900388838823967323053560188162, 13568137741145517535470569467637368054516504279886277446065024995144982326, 10619316578405017850994322382363861285732316275911981192733741648066596584, 3454852590608742485581209919468177920886162458563235302279925642050662689, 10418147888188969490250503111179722264196236580956907521738948030724014427, 3253683900392694124837390648284038899350082763608161631285132024708080532]
'''

Bước 2. Tính small roots

Cần dựng đa thức để tìm $k$ . Cụ thể $f = (x \times e_{1} e_{2} + r_{q})^{2}$ . Bound cho $x$ sẽ là $∣ x ∣ < N^{β^{2} / δ}$ . Ở đây $N^{\frac{( 2/3 ) ^{2}}{2}} \sim 2^{579}$ trong khi đó $k$ mà ta tính ở trên rơi vào khoảng $2^{382}$ nên ổn

from sage.all import *
from Crypto.Util.number import *
from hashlib import sha256
 
from sage.modules.free_module_integer import IntegerLattice
N = 39857078746406469131129281921490520306196739933449401384580614683236877901453146754149222509812535866333862501431453065249306959004319408436548574942416212329735258587670686655658056553446879680643872518009328886406310298097685861873954727153720761248262606469217940464611561028443119183464419610396387619860313813067179519809796028310723320608528262638653826016645983671026819244220510314301178181698134390850683834304169240632402535087021483298892547974104858755498823118164815682452718215716370727477136888839954993949013970026988378086175471190518276414200966496353144747778470590767485019943178534397845127421058830430797806265311195099187747227867325234593386438995618936934586514932401108874934000734850169069717060963988677462779177959990601405850727404268354600078746523164279
E1 = 17599828213549223253832044274649684283770977196846184512551517947600728059 
E2 = 13524024408490227176018717697716068955892095093578246398907145843636542721
qbit = N.bit_length()//3+1
e1_bit = E1.bit_length()
e2_bit = E2.bit_length()
# recover r_q
# n^2 % E1 = q^2
q_sqr = N % E1 
rq_sqrt = Zmod(E1)(q_sqr).nth_root(2, all = True)
print(f"{rq_sqrt = }")
def flatter(M):
    import re
    from subprocess import check_output
    # compile <https://github.com/keeganryan/flatter> and put it in $PATH
    z = "[[" + "]\\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\\\\d+", ret))))
def Babai_CVP(mat,target):
    M = flatter(mat)
    G = M.gram_schmidt()[0]
    diff = target 
    for i in reversed(range(G.nrows())):
        diff -= M[i] * ((diff*G[i]) / (G[i]*G[i])).round()
    return target - diff 
def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR
 
    N = self.parent().characteristic()
 
    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")
 
    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")
 
    f = self.change_ring(ZZ)
 
    P, (x,) = f.parent().objgens()
 
    delta = f.degree()
 
    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)
 
    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)
 
    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)
 
    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)
 
    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h
 
    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j
 
    B = flatter(B)
 
    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()
 
    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]
K = 2**(qbit - e1_bit - e2_bit)
for roots in rq_sqrt:
    rq = crt([int(roots),1],[E1,E2])
    P = PolynomialRing(Zmod(N),'x')
    x = P.gen()
    f = (x*E1*E2+ZZ(rq))**2
    f = f.monic()
    rs = small_roots(f, X=K, beta = 2/3-0.1, epsilon = 0.05)
    if len(rs) >=1:
        print(f"{rs = }")
        q = int(rs[0])*E1*E2+int(rq)
        H = sha256()
        H.update(str(q).encode())
        print("r3ctf{" + H.hexdigest() + "}")

TODO: https://github.com/kionactf/coppersmith

Crypto and Math

Trong bài này

R3CTF 2025

split3pig

Biểu Đồ