二元Coppersmith问题归纳总结

这部分内容其实我很早就想系统学习一下了。说实话，比赛中遇到的二元 Coppersmith 题目并不算多，但归纳之后才发现，这类题目其实并不少。对于一些 d 比较小的题目，往往可以用二元 Coppersmith 的方法来解决。

不得不说，把一类问题归纳起来进行系统学习，确实是一个很不错的方法。

板子

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 []

说明一

可能报如下错误

注释掉

f /= f.coefficients().pop(0)

即可

说明二

参数问题

small_roots(f, bounds, m=1, d=None):

f是多项式

bounds是界

m和d越大越慢，越容易出，只能说多尝试吧

题目一：[LitCTF 2025]leak

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

m = bytes_to_long(flag)
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
c = pow(m,e,n)
hint = temp>>180
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {hint}")
e*dp=1+k*(p-1)
'''
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
'''

思路及解码代码

\begin{array}{l} e\cdot dp=1+k(p-1) \\ 由于\ dp<p-1,\ 那么\ k<e,\ 也就是说\ k\ 的位数只有101位 \\ e\cdot (hint\ll 180+dplow)=1+k(p-1) \\ 移项可得,\ f=e(hint+x)-1+k \pmod p=0 \\ 对于未知量,\ dplow\ 是180位,\ k\ 是100位,\ 对比\ n\ 的2048位足够小 \\ 完全可以在 \bmod n\ 的条件下进行二元\ Coppersmith \\ 由于我们是在 \bmod n\ 下进行\ smallroots,\ 那么求到的根满足\ f=0 \pmod p \\ 故,\ 构造方程\ f=e(hint+x)-1+k \pmod n \end{array}

import itertools
from Crypto.Util.number import *
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 []

e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
P.<x,y> = PolynomialRing(Zmod(n))
hint=hint<<180
f=e*hint+e*x+y-1
res=small_roots(f,(2**180, 2**101), m=2, d=3)[0]
print(res)
dp_low,k=res
print(gcd(n,e*hint+e*dp_low+k-1))
p=gcd(n,e*hint+e*dp_low+k-1)
print(is_prime(p))
q=int(n)//int(p)
d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(int(m)))

因此，这道题目的特征应该是dp部分泄露

题目二：[央企杯 2025]big_e_rsa

from sage.all import *
from Crypto.Util.number import getStrongPrime, inverse
from hashlib import *
while True:
    p = getStrongPrime(512)
    q = getStrongPrime(512)
    if p%4==3 and q%4==3:
        print(p,q)
        break
N = p * q
phi_N = (p**2 + p + 1) * (q**2 + q + 1)
d = Integer(N)**RR(0.31)
e = inverse(Integer(d), phi_N)
flag='flag{'+md5(str(p+q).encode()).hexdigest()+'}'
print(f"e = {e}")
print(f"N = {N}")
"""
e = 1551272466605872863416403977607292631633701035332147619334397735304780667522023412306036671510826302844606446851894336124057998125262840234194050349637823374524170830050888493129093785047790768479824853974485992897094462464812937258543116078662875776075027424552496083294550754325632098348117392765307939361584083284301895309303537418746278506279259977605077340832463160592170634327044102649366071222424124607846377204960029629274181604893740461442615864409257969910222040007572920062878004810852999179043297689530784435487435361166796498735890127211075763324999654593958063926772895325778380833510441152388535129397
N = 114844384426038454254660651833814261274384746047765676028021231000119586728613054758356259645955152450739070905660390543576514347506026385857367390443306247721678976046962085618294460484178352540250850748434273095861501307425230078443520622440057792872004498471410258909184474490354627866870431592356692438209
"""

思路及解码代码

\begin{array}{l} e*d=1+k*\phi \\ e<\phi,\ k<d,\ \text{故 } d \text{ 是320位} \\ \text{展开得， } e*d=1+k*(n^2+n*s+s^2-n+s+1),\ \text{其中 } s=p+q \\ f=1+k*(n^2+n*s+s^2-n+s+1)\pmod e=0 \\ e \text{ 的位数是2048，} s \text{ 的位数是513，} k \text{ 的位数是320， 可以尝试二元 Coppersmith} \end{array}

import itertools
from hashlib import *
from Crypto.Util.number import *
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 []

e = 1551272466605872863416403977607292631633701035332147619334397735304780667522023412306036671510826302844606446851894336124057998125262840234194050349637823374524170830050888493129093785047790768479824853974485992897094462464812937258543116078662875776075027424552496083294550754325632098348117392765307939361584083284301895309303537418746278506279259977605077340832463160592170634327044102649366071222424124607846377204960029629274181604893740461442615864409257969910222040007572920062878004810852999179043297689530784435487435361166796498735890127211075763324999654593958063926772895325778380833510441152388535129397
n = 114844384426038454254660651833814261274384746047765676028021231000119586728613054758356259645955152450739070905660390543576514347506026385857367390443306247721678976046962085618294460484178352540250850748434273095861501307425230078443520622440057792872004498471410258909184474490354627866870431592356692438209
P.<x,y> = PolynomialRing(Zmod(e))
f=1+x*(n^2+n*y+y^2-n+y+1)
res=small_roots(f,(2**320, 2**513), m=2, d=3)[0]
print(res)
paddq=int(res[1])
flag='flag{'+md5(str(paddq).encode()).hexdigest()+'}'
print(flag)

拿到p+q进行md5之后就是flag

题目三：[西湖论剑 2022]MyErrorLearn

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(246)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(3):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

思路及解码代码

\begin{array}{l} d_1=(secret+r_1)^{-1} \pmod p + k_1 \\ \text{移项可得，}(d_1-k_1)(secret+r_1)=1 \pmod p \qquad (1) \\ \text{同理有，}(d_2-k_2)(secret+r_2)=1 \pmod p \qquad (2) \\ \text{我们需要想办法消掉 } secret,\ \text{因为 } secret \text{ 太大，直接求是不明智的} \\ \text{将式子 }(1)\text{ 两边同乘 }(d_2-k_2),\ \text{式子 }(2)\text{ 两边同乘 }(d_1-k_1) \\ (d_1-k_1)(d_2-k_2)(secret+r_1)=(d_2-k_2) \pmod p \qquad (3) \\ (d_1-k_1)(d_2-k_2)(secret+r_2)=(d_1-k_1) \pmod p \qquad (4) \\ \text{两式相减得} \\ (d_1-k_1)(d_2-k_2)(r_1-r_2)=(d_2-k_2)-(d_1-k_1) \pmod p \\ \text{此时未知量有 } k_1,k_2,\ \text{而且位数只有246} \\ \text{构造式子，进行二元 Coppersmith 即可} \\ f=(d_1-k_1)(d_2-k_2)(r_1-r_2)-(d_2-k_2)+(d_1-k_1) \pmod p \end{array}

求到k1,k2，后面求secret就是简简单单的计算了

from pwn import *
from Crypto.Util.number import *
import itertools

host = "node4.anna.nssctf.cn"
port = 22459

io = remote(host, port)

mod = None
vals = []

while True:
    line = io.recvline().decode(errors="ignore").strip()
    print(line)
    if line.startswith("> mod ="):
        mod = int(line.split("=", 1)[1].strip())
        break

for k in range(2):
    io.sendline(b"1")

    r = None
    d = None

    while r is None or d is None:
        line = io.recvline().decode(errors="ignore").strip()
        print("recv:", repr(line))

        if line.startswith("> r ="):
            r = int(line.split("=", 1)[1].strip())
        elif line.startswith("> d ="):
            d = int(line.split("=", 1)[1].strip())
        elif "Error. try again." in line:
            raise Exception("服务端报错了")
        else:
            pass

    vals.append((r, d))

(r1, d1), (r2, d2) = vals
p = mod

print("\n==== result ====")
print("mod =", mod)
print("r1 =", r1)
print("d1 =", d1)
print("r2 =", r2)
print("d2 =", d2)

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

    R = f.base_ring()
    N = R.cardinality()

    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(root[var] for var in f.variables())
                roots.append(root)
            return roots
    return []

PR.<x,y> = PolynomialRing(Zmod(p))
f = (r2-r1)*(d1+x)*(d2+y) - (d1+x) + (d2+y)

res = small_roots(f, (2^246, 2^246), m=2, d=3)
print("roots =", res)

k1, k2 = res[0]
k1 = int(k1)
k2 = int(k2)

secret1 = (pow(d1 + k1, -1, p) - r1) % p
secret2 = (pow(d2 + k2, -1, p) - r2) % p

print("secret1 =", secret1)
print("secret2 =", secret2)
print("same =", secret1 == secret2)

assert (d1 + k1) % p == pow((secret1 + r1) % p, -1, p)
assert (d2 + k2) % p == pow((secret1 + r2) % p, -1, p)

io.sendline(b"2")
io.sendline(str(secret1).encode())

while True:
    try:
        line = io.recvline(timeout=2)
        if not line:
            break
        print(line.decode(errors="ignore").strip())
    except EOFError:
        break

io.close()

题目四：Cop! Run!!

这个题目是来自ctfshow平台的

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

n = 1 << 8
p = getPrime(n)
print(p)

P.<t> = PolynomialRing(Zmod(p))
f = t * t + randrange(p)
print(f)

x = [randrange(p)]
x += [f(x[0])]
print([x_ >> (n - ceil(5 * n / 7)) for x_ in x])

flag = bytes_to_long(flag)
y = f(x[-1])
for i in range(7):
    y = f(y)
    flag ^^= int(y)
print(flag)

'''
92946459607669937513774102250057295249718593723232674702212854287358873135783
t^2 + 43844336985235863734419631630425915388298791521868754583032904718644333115590
[3248642833056635029095920782095626337949113592116495266, 4883935221919623989344404485025479346028101682781790392]
193207529097125793778662519051231322609402866155819915933598367395102313904490702547833
'''

思路及解码代码

\begin{array}{l} \text{存在关系 } x_{i+1}=x_i^2+b \pmod p \\ x_1=x_0^2+b \pmod p \\ p \text{ 是256位},\ x_0,\ x_1 \text{ 分别泄露183位} \\ \text{带入得，} \\ (x_{1high}\ll 73+x_{1low})=(x_{0high}\ll 73+x_{0low})^2+b \pmod p \\ \text{未知量 } x_{1low} \text{ 和 } x_{0low} \text{ 是73位，} p \text{ 是256位，使用二元 Coppersmith} \\ \text{构造式子，} f=(x_{0high}\ll 73+x_{0low})^2+b-(x_{1high}\ll 73+x_{1low}) \pmod p \end{array}

得到x0和x1之后继续迭代，异或即可拿到flag

import itertools
from Crypto.Util.number import *
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 []

p=92946459607669937513774102250057295249718593723232674702212854287358873135783
b=43844336985235863734419631630425915388298791521868754583032904718644333115590
x0,x1=[3248642833056635029095920782095626337949113592116495266, 4883935221919623989344404485025479346028101682781790392]
c=193207529097125793778662519051231322609402866155819915933598367395102313904490702547833
PR.<x,y> = PolynomialRing(Zmod(p))
f=(x0*(2**73)+x)**2+b-(x1*(2**73)+y)
res=small_roots(f,(2**73, 2**73), m=2, d=3)[0]
print(res)
x0=int(x0*(2**73))+int(res[0])
x1=int(x1*(2**73))+int(res[1])
P.<t> = PolynomialRing(Zmod(p))
f = t * t + b

y = f(x1)          # 先到 x2
for i in range(7):
    y = f(y)       # 再到 x3 ~ x9
    c ^^= int(y)

print(long_to_bytes(c))

题目五：factor1

这道题目来自qsn平台

import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(256)
e = gmpy2.invert(d, (p**2 - 1) * (q**2 - 1))
flag = "qsnctf{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
# 78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053

思路及解码代码

做法类似题目二，直接写代码了

import itertools
import hashlib
from Crypto.Util.number import *
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 []


e=4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
n=78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053
P.<x,y> = PolynomialRing(Zmod(e))
f=1+x*(n**2-(y)**2+2*n+1)
res=small_roots(f,(2**256, 2**513), m=6, d=8)[0]
print(res)
paddq=res[1]
flag = "qsnctf{" + hashlib.md5(str(paddq).encode()).hexdigest() + "}"
print(flag)

这个题目完全可以用维纳攻击来做，而且m和d的参数很大了，跑的太慢，放到这儿勉勉强强吧

题目六：高位攻击

from Crypto.Util.number import *
from secret import flag
# 生成1024位的大素数p和q
p = getPrime(1024)
q = getPrime(1024)

# 计算RSA模数n
n = p * q

d=getPrime(521)
e = inverse(d,(p-1)*(q-1))
flag_int = bytes_to_long(flag())
c = pow(flag_int, e, n)
# 生成提示信息1：p的高位部分（右移224位）
hint1 = p >> (1024-224)

# 生成提示信息2：q的高位部分（右移224位）
hint2 = q >> (1024-224)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")



'''
n = 28384198625234311024055591508760545859772557962616705058087134570313766078246339432810722251075770426155260882976548948745855775802466082136886198916308950895091350291804323083377746723426585662829956721593008069417593656058519847917141571157423337000995823498275338699783892359735051369928648561714630161425631668045643208548745557419257154201912621422125784538013535319473974771074731705230991582524865280419594116357454200441743555890216903447536600103202560201259871803992219002685757605178878578265090068993111854329728311196716695934142083541791762952464173221834117578210442075243829228771641151482461878395681
e = 24233198590433138929759046268361507704173924810200652679220620112938468106193887274039561623781677698718659545011949842007599587857513820908529013019054134965026341908641820214813864848590705039503962393544485942577593170832200318338048424938687583902593193451991009036073079376645787351773806712023712043915544661222738699918976674231029998684765476662313863475966304161444465282825845046504385175046765187829943107254178661647191288636247051016225997643316505985860750972663378492448313338846037936997542245777268091759458108263910160659565995588095034641162401363842335174968680271594738396192872825937509377247217
c = 940844774044002760041224401562703091111426466612866082339966140841639939444648025078973826624076043358296937037021610358779157680065548800768654725751103021962957103161713314365598234258437018412919647354775780700585758075623352776449216395723630660676425946215835561424716152933938854890964273887565373627808873987131623770696128641766795559659984456300489545944324461938795805156161909329750290251725440271617055330398638953715159135274381585663770711778978803710571670536163056904818086237979881559953073139720433782186818163069926281641109314202702006420384137994982480163260679548223758917067813649186512456317
hint1 = 24918310222298699952176984963600731297429200840056013317855084116853  # p高位
hint2 = 25619165931627397281111327022328112349852649641215268689996006001965  # q高位
'''

思路及解码代码

其实可以用Boneh--Durfee 攻击，但是也可以用二元Coppersmith

做法类似题目二，直接写代码了

import itertools
import hashlib
from Crypto.Util.number import *
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 = 28384198625234311024055591508760545859772557962616705058087134570313766078246339432810722251075770426155260882976548948745855775802466082136886198916308950895091350291804323083377746723426585662829956721593008069417593656058519847917141571157423337000995823498275338699783892359735051369928648561714630161425631668045643208548745557419257154201912621422125784538013535319473974771074731705230991582524865280419594116357454200441743555890216903447536600103202560201259871803992219002685757605178878578265090068993111854329728311196716695934142083541791762952464173221834117578210442075243829228771641151482461878395681
e = 24233198590433138929759046268361507704173924810200652679220620112938468106193887274039561623781677698718659545011949842007599587857513820908529013019054134965026341908641820214813864848590705039503962393544485942577593170832200318338048424938687583902593193451991009036073079376645787351773806712023712043915544661222738699918976674231029998684765476662313863475966304161444465282825845046504385175046765187829943107254178661647191288636247051016225997643316505985860750972663378492448313338846037936997542245777268091759458108263910160659565995588095034641162401363842335174968680271594738396192872825937509377247217
c = 940844774044002760041224401562703091111426466612866082339966140841639939444648025078973826624076043358296937037021610358779157680065548800768654725751103021962957103161713314365598234258437018412919647354775780700585758075623352776449216395723630660676425946215835561424716152933938854890964273887565373627808873987131623770696128641766795559659984456300489545944324461938795805156161909329750290251725440271617055330398638953715159135274381585663770711778978803710571670536163056904818086237979881559953073139720433782186818163069926281641109314202702006420384137994982480163260679548223758917067813649186512456317
hint1 = 24918310222298699952176984963600731297429200840056013317855084116853  # p高位
hint2 = 25619165931627397281111327022328112349852649641215268689996006001965  # q高位

P.<x,y> = PolynomialRing(Zmod(e))
f=1+x*(n-(hint1*(2**800)+hint2*(2**800)+y)+1)
res=small_roots(f,(2**521, 2**801), m=3, d=4)[0]
print(res)
paddq=(hint1*(2**800)+hint2*(2**800)+res[1])
x, y = var('x y')

# 定义方程组
equations = [x * y == n, x + y == int(paddq)]

# 求解方程组
solutions = solve(equations, [x, y])

# 输出解
print(solutions)
p=solutions[0][1].rhs()
print(p)
q=int(n)//int(p)
d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(int(m)))