An_Interesting_CTF_Challenge_0x1

Posted on Edited on In Word count in article: 4.7k Reading time ≈ 4 mins.

题目：

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 getPrime, bytes_to_long

DEBUG = True 
p,q,r = [getPrime(1024) for _ in "pqr"] 
n = p*q*r 
l = getPrime(500)
phi = (p - 1) * (q - 1) * (r - 1)
d = phi - l  # make sure it is big enough that wiener's attack doesn't work
e = int(pow(d, -1, phi)) 

flag = b'flag{AL3XEI_FAKE_FLAG}'
m = bytes_to_long(flag)
c = pow(m, e, n)

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

if DEBUG:
    print("down: ", int((1/3)*(n**(1/6))).bit_length())  
    print("up: ", int(pow(n, 0.292)).bit_length())
    print("k:", int((e*l+1)//phi).bit_length()) 
    print("s:", int(-(- p*q-p*r-q*r+p+q+r-1)).bit_length(), (e*l+1)%phi)

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    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 []
n = 2101801799035539860375848243653132801054451921134462019374373866110453680669679728116228096526954941143040970020283393399828114443925875824588183932379885273834192731910484954788411144709921948751015541441558343176656764092738793809275299681061630506993547573421015201775110038059594540171337252827132460705417284969486435451969259818780600325555398534670916491733094260294132707875939072187173491391707313449649277098183192891613314813118642124520757752948421053236492804740143889060999569184019710912906837972887523345540489029615432519613972987805137282734764356482946944323219042189365666968054819229251479949616453742986872169406103751196586389468221506912756551140604687574649388772031807763831711543726652957664024141407257183538199978978848258101283656928012470410512808624580158297930798776593865722493803062975413045734255485096243843423675930653417911167656684607126854507821092863166533069065982066690780877092837
e = 1798551239687961610375532886075647971210906172471599139778601168998711530927486658498053767493423718276657217266761435082717065833097196130981414125278463820675511308905553451073323493745727147521630798247901750908406613577319633378540107681566782775411389038728134779741230020847443310286579013847611297623513449204451226706006318149853037042670745213288008577830422291303153690302418307348017369027087418193190693479011396409321105600327103428229426192937738575206040551035862643348615945660891234711066433979161345537023491432850903299815236095148538917751548593042292950167735341463826254089241928951912226570764380282803915883261921506519437465819474490899018672103642732865197971534067337368677992479542784111332799839136330359269285926662549496466472686638838355419165387603683703759364724015550915821877932720150577196762338463276006449931618697578092587107145371624494777982003059645909448378276501644311349766263683
c = 318595448056007859430835566255384983617318465697473420120023140644241640673424638880378719270919131051435366491098283243331756321424210761291651005448055032913869873417941899383462962263699414160722369958513754956439437564094435449868960929070309136660552598303976758242082622917297304961061549230059909982074781675568919485977715427836288527066909241230518568446305565422186644005553892676489513675616672080475488131926908143651060561572124094053476646541594768622077583421369554985209745886499396947780451818319463972761638114682208459869871250586148072142935807225182473517031666210709280160950407320951581744004413932879814696179499278772424116787322543453163269465104427439191557714025478218645714244092768933595702566430503696125616609660180860128722460508317279004332017487256930660353137256237013921375133192873041082478079088597402248704024263941172441036229514724068140431650364271016960355705503391470301812702379


P = Zmod(ZZ(e))["k,s"]
k, s = P.gens()
f = 1 + k * (n - s)
rs = small_roots(f, (2**500, 2**2049), m=4, d=5 )
print(rs)
k, s = map(int, rs[0])
phi = n - s
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

再想想有没有可能加点线性的东西。