Challenge


from Crypto.Util.number import bytes_to_long, getPrime
from SECRET import FLAG

e = getPrime(128)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(bytes_to_long(FLAG), e, n)

d = pow(e, -1, (p - 1) * (q - 1))
dp = d % (p - 1)
dp_high = dp >> 205

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

"""
n = 12567364021021536069276139071081301321773783503415410122482063162815802632532262852631733566943908930876147793969043836275748336698486250666608690152319164539308799173942970880405365621942480869038031173565836135609803219607046250197218934622063531043191571238635559343630285434743137661162918049427668167596108116123813247574023489647941191092646108484359798178312183857161198552950237016232564837163103701319852345468700518013420435831423503394375188294692875472478236076844354332788143724582596188171429101120375457060113120938123836683660988201443089327738905824392062439034247838606482384586412614406834714072187
e = 302855054306017053454220113135236383717
c = 4891864668386517178603039798367030027018213726546115291869063934737584262406041165900191539273508747711632172112784295237035437771196319634059866827443546543304905951054697225192869131382430968922874630769470296997764149219967748222295126835357440172029624432839432442542014919311928847815297342723030801298870843985791566021870092065045427815279776382037308098892891521540483210118257005467504087917529931331454698510489305696908930175868148922286615019210097019743367080206300230172144203634385318929457785251214794930401419137018353777022634635240368493042317181737723067635048719777029127030494920756862174788399
dp_high = 1528682061327606941204027235121547734644486174542891631806426376137001818312801429494781262718713071077103179054205712581085921624900599327139049785998451580793229375262096344994664540984947702348067124539258177759586538935334513702134177319291812
"""


Inspiration for writing


Theorem 62 (page 120) from this paper.


Solution


\[dp \equiv d \ (\text{mod } p-1)\] \[dp \cdot e \equiv d \cdot e \ (\text{mod } p-1)\] \[dp \cdot e \equiv 1 \ (\text{mod } p-1)\] \[dp \cdot e = 1 + k (p-1)\] \[k \cdot p = dp \cdot e + k - 1\] \[k \cdot p \approx dp \cdot e + x\]

Now we can use univariate coppersmith to solve kp, then p = gcd(n, kp).

from Crypto.Util.number import long_to_bytes, isPrime
from tqdm import tqdm

n = 12567364021021536069276139071081301321773783503415410122482063162815802632532262852631733566943908930876147793969043836275748336698486250666608690152319164539308799173942970880405365621942480869038031173565836135609803219607046250197218934622063531043191571238635559343630285434743137661162918049427668167596108116123813247574023489647941191092646108484359798178312183857161198552950237016232564837163103701319852345468700518013420435831423503394375188294692875472478236076844354332788143724582596188171429101120375457060113120938123836683660988201443089327738905824392062439034247838606482384586412614406834714072187
e = 302855054306017053454220113135236383717
c = 4891864668386517178603039798367030027018213726546115291869063934737584262406041165900191539273508747711632172112784295237035437771196319634059866827443546543304905951054697225192869131382430968922874630769470296997764149219967748222295126835357440172029624432839432442542014919311928847815297342723030801298870843985791566021870092065045427815279776382037308098892891521540483210118257005467504087917529931331454698510489305696908930175868148922286615019210097019743367080206300230172144203634385318929457785251214794930401419137018353777022634635240368493042317181737723067635048719777029127030494920756862174788399
dp_high = 1528682061327606941204027235121547734644486174542891631806426376137001818312801429494781262718713071077103179054205712581085921624900599327139049785998451580793229375262096344994664540984947702348067124539258177759586538935334513702134177319291812


beta = 0.4
z_search = 20

def recover():
    upper_bound = int(2*n**(beta**2))
    for z in tqdm(range(z_search)):
        for xi in range(-upper_bound + upper_bound//8, upper_bound, upper_bound//4):
            P.<x> = PolynomialRing(Zmod(n))
            f = (dp_high << (205-z)) * e + x - xi
            x = f.small_roots(X=upper_bound, beta=beta)
            if x == []:
                continue
            kp = int(f(x[0]))
            p = gcd(n, kp)
            if 1 < p < n and isPrime(p):
                return p

p = recover()
q = n // p
d = pow(e, -1, (p-1)*(q-1))
flag = pow(c, d, n)
print(long_to_bytes(int(flag)))


Alternative


\[dp \equiv d \ (\text{mod } p-1)\] \[dp \cdot e \equiv d \cdot e \ (\text{mod } p-1)\] \[dp \cdot e \equiv 1 \ (\text{mod } p-1)\] \[dp \cdot e = 1 + k (p-1)\] \[0 = 1 + k \cdot p- k - dp \cdot e\] \[0 \equiv 1 - k - dp \cdot e \ (\text{mod } p)\]

Now for bivariate coppersmith we can use Defund’s implementation https://github.com/defund/coppersmith/blob/master/coppersmith.sage

It has to be modified a bit to work, credit to Mistsu for the great work!

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()
    
    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k/g)

    f *= 1/k
    f = f.change_ring(ZZ)

    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m-k+1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f**k * prod(subvars) * N**(max(d-k, 0))
                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, Integer(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 = 12567364021021536069276139071081301321773783503415410122482063162815802632532262852631733566943908930876147793969043836275748336698486250666608690152319164539308799173942970880405365621942480869038031173565836135609803219607046250197218934622063531043191571238635559343630285434743137661162918049427668167596108116123813247574023489647941191092646108484359798178312183857161198552950237016232564837163103701319852345468700518013420435831423503394375188294692875472478236076844354332788143724582596188171429101120375457060113120938123836683660988201443089327738905824392062439034247838606482384586412614406834714072187
e = 302855054306017053454220113135236383717
c = 4891864668386517178603039798367030027018213726546115291869063934737584262406041165900191539273508747711632172112784295237035437771196319634059866827443546543304905951054697225192869131382430968922874630769470296997764149219967748222295126835357440172029624432839432442542014919311928847815297342723030801298870843985791566021870092065045427815279776382037308098892891521540483210118257005467504087917529931331454698510489305696908930175868148922286615019210097019743367080206300230172144203634385318929457785251214794930401419137018353777022634635240368493042317181737723067635048719777029127030494920756862174788399
dp_high = 1528682061327606941204027235121547734644486174542891631806426376137001818312801429494781262718713071077103179054205712581085921624900599327139049785998451580793229375262096344994664540984947702348067124539258177759586538935334513702134177319291812

PR.<x,k> = PolynomialRing(Zmod(n), 2)
f = 1 - k - ((dp_high << 205) + x) * e

x, k = small_roots(f, [2**205, 2**128], m=4, d=1)[0]

p = gcd(int(f(x, k)), n)
q = int(n) // int(p)
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, int(d), n)
print(long_to_bytes(int(m)))