2022HFCTF的RRSSAA笔记

解方程、解方程和解方程，反正我当时是没找到论文然后就一直在推解密方法，感觉有非预期- -

题目链接：https://paste.ubuntu.com/p/RGgs3dCFmC/

前言·

首先go里的密钥生成是典型的Wiener攻击的密钥生成方法，所以当时很自然地就往Wiener方面想了，然后就可以分解hint的$n$，但是分解不了flag的，就又很自然地往Coppersmith想（而且hint也提示了Coppersmith），最后跑了很久都没跑出来（感觉参数被卡了）。

后来赛后看其他队大佬的wp才知道$q$与$p+2^{1024\beta}$接近，可以解方程加枚举直接分解- -（虽然我也看漏了next_prime里面的1 << int(nbits * beta)是个定值）。反正如果next_prime的偏移是知道的话，肯定是不需要Coppersmith的，甚至beta还可以更大（所以感觉是非预期了）。

然后，比赛时没有找到相关论文（这关键词搜啥啊，），就硬推解密函数（+解方程），感觉这个解方程的方法还是挺有用的，所以就水篇博客。赛后跟@晓鹿交流才发现有这个论文，加密方法都一样的，对着抄就好了- -

最后，这篇博客大概以记录为主吧，记一下分解n时分别想到的几个（格）方法和推解密函数的过程。

分解模数·

Wiener变种·

首先看q = next_prime(p + (1 << int(nbits * beta)))这句，就可以得出$q-p < N^{\beta+\epsilon}$（$\epsilon$表示一个可忽略的数。另，事实上这是不够紧致的，一会再说），作平方：

$$(q-p)^2=p^2+q^2-2pq=p^2+q^2-2N < N^{2\beta+2\epsilon}$$

由于$\varphi=(p^2-1)(q^2-1)=p^2q^2+1-(p^2+q^2)$，令$s=p^2+q^2-2N$，$N'=N^2-2N+1$，则有$s < N^{2\beta+2\epsilon}$，且：

$$N'-s = N^2 - 2N + 1 - (p^2 + q^2 - 2N) = N^2 + 1 - (p^2 + q^2) = \varphi$$

根据$ed-k\varphi=1$，有：

$$ed - k(N'-s) = 1 \\ ed - kN' = 1-ks$$

然后到这里就是之前讲Wiener与格的套路，可以选择用$\frac{e}{N'}$逼近得到$\frac{k}{d}$，或者构造格（个人偏好）：

$$(k, d)*\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix} \\ = (kN^{2\beta}, 1-ks)$$

大概估算一下，$k \approx N^\delta$，$s \approx N^{2\beta}$，$e \approx N^2$，则：

$$\sigma(\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix}) \approx N^{\frac{2+2\beta}{2}} = N^{1+\beta} \\ \|(kN^{2\beta}, 1-ks)\| \approx N^{\delta+2\beta}$$

计算得，若：

$$\delta+2\beta < 1+\beta \\ \beta + \delta < 1$$

则则$(kN^{2\beta}, 1-ks)$大概率是$L(\begin{bmatrix} N^{2\beta} & -N' \\ 0 & e \\ \end{bmatrix})$的最短向量，LLL解之，然后可解$(k, d)$。

$\beta=0.33$、$\delta=0.63$时是符合条件的，$\beta=0.44$、$\delta=0.63$不符合，所以只能解hint那部分。

# sage 
# for hint

n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259

size=1024
beta = 0.33
n2 = (n-1)^2
R = int(n^(2*beta))
m = matrix(ZZ, [
  [R, -n2],
  [0, e]
])

L = m.LLL()
w = L[0]

v = m.solve_left(w)
print('v = %s' % v)

k, d = v
print(len(bin(d)))
print((e*d-1) % k)
phi = (e*d-1)//k

pq_p = Integer(sqrt(n^2+2*n+1-phi))
pq_m = Integer(sqrt(n^2-2*n+1-phi))
p = (pq_p+pq_m)//2
q = pq_p-p
if p*q == n:
  print('p = %d' % p)
  print('q = %d' % q)

d = e.inverse_mod(phi)
print('d = %d' % d)  

'''
p = 11080378090495548888711346538044743233499815208179802720810821877018321760024765272011515142380916992839687768295921206534475286830411300347575580967025893
q = 11080378090495548888711346538044743233499815208179802440842729104792795440344480200955980377175229838508495905797283586060491389310293127737888922016136003
d = 121139118831078102076565175484037979390315779651424626323741939233877664377574934056315052293655422386668889543147047138108873461630703630129146688760636392702002802083436463455161665094535393763
'''

Boneh-Durfee变种·

利用上面推出的关系$ed - kN' = 1-ks$，转化一下可得：

$$k(N'-s)+1 \equiv 0 \pmod e$$

然后就推出了跟Boneh-Durfee差不多的关系，Coppersmith解之。

不过，令$x=k$、$y=s$的话，即取$X=2^{1024\delta}$、$Y=2^{2048\beta}$，根据之前讲Coppersmith时推出的关系，需要符合（下图的$x$和$y$换成大写- -）：

大概推算了一下，发现$m$要设置为$15$以上（PS：$m=16$时取$t=4$有最优），推算过程就不详说了，下面截图留了个过程。反正$m$这么大的话是要跑很久的（渣机表示一下午没出来，把方法在这里留一下，放个20年看看以后的电脑能不能算出来吧，x）

忽略的条件·

赛后再看了一下才发现，我把1 << int(nbits * beta)是已知的这个条件忽略了（即，当成随机数了- -），如果加上这个条件的话根本就不需要用到Coppersmith。

首先令$a=2^{1024\beta}$（即上面的移位的值），由于q = next_prime(p + a)，令$s=q-(p+a)$，$s$相对于$N$来说其实是一个非常小的值（两个素数的差值其实是很小的，这个不用怀疑- ），整理一下则$q-p=a+s$，同样做个平方：

$$(q-p)^2 = p^2+q^2-2N = (a+s)^2 = a^2 + 2as + s^2$$

令$t = p^2+q^2-2N - a^2 = 2as + s^2$，则$t<N^{\beta+\epsilon}$（这里的$\epsilon$是为了考虑上$s$，实际应该是可忽略的，吧，反正不能忽略也可以枚举）。

然后也一样，由于$\varphi=(p^2-1)(q^2-1)=p^2q^2+1-(p^2+q^2)$，令$u=p^2+q^2-2N-a^2$，$N'=N^2-2N+1-a^2$，则有$u < N^{\beta+\epsilon}$，且：

$$N'-s = N^2 - 2N + 1 - a^2 - (p^2 + q^2 - 2N - a^2) = \varphi$$

根据$ed-k\varphi=1$，有：

$$ed - k(N'-s) = 1 \\ ed - kN' = 1-ks$$

然后也是可以选择连分数/格，个人偏好用格解：

$$(k, d)*\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix} \\ = (kN^{\beta}, 1-ku)$$

大概估算一下，$k \approx N^\delta$，$u \approx N^{\beta}$，$e \approx N^2$，则：

$$\sigma(\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix}) \approx N^{\frac{2+\beta}{2}} \\ \|(kN^{\beta}, 1-ks)\| \approx N^{\delta+\beta}$$

计算得，若：

$$\delta+\beta < \frac{2+\beta}{2} \\ 2 \delta + \beta < 2$$

则$(kN^{\beta}, 1-ks)$大概率是$L(\begin{bmatrix} N^{\beta} & -N' \\ 0 & e \\ \end{bmatrix})$的最短向量，LLL解之，然后可解$(k, d)$。（其实基本上跟前面的是一样的- -）

如果固定$\delta=0.63$的话，可得$\beta < 2-2*0.63 = 0.74$，即hint部分的$0.33$和flag部分的$0.44$都在范围，甚至还能更大。

# sage
# for flag

n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

size=1024
beta = 0.44
a = 1 << int(size * beta)
n2 = (n-1)^2 - a^2
R = int(n^(beta))
m = matrix(ZZ, [
  [R, -n2],
  [0, e]
])

L = m.LLL()
w = L[0]

v = m.solve_left(w)
print('v = %s' % v)

k, d = v
print(len(bin(d)))
print((e*d-1) % k)
phi = (e*d-1)//k

pq_p = Integer(sqrt(n^2+2*n+1-phi))
pq_m = Integer(sqrt(n^2-2*n+1-phi))
p = (pq_p+pq_m)//2
q = pq_p-p
if p*q == n:
  print('p = %d' % p)
  print('q = %d' % q)

d = e.inverse_mod(phi)
print('d = %d' % d)  

'''
p = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
q = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
d = 91530255743213804238059422201508844509005370104602135173607248138301475575179518423751713150218534315997028245173456360624292973766196816229696622248975836077175204186997500189564114519436678423
'''

Coppersmith的界·

没推过，咕

推解密函数·

首先讲一下思路，由加密函数里的$c \equiv (1+mn)v \pmod {n^2}$，可以盲猜$m < n$，不然$mn$模$n^2$会有数据损失，整理一下提取出$mn$：

$$mn = cv^{-1}-1 \pmod {n^2}$$

注意上面是$=$而不是$\equiv$，因为$m < n$即$mn < n^2$，模运算可忽略，上面式子右边未知的只有$v \pmod {n^2}$。首先$v \mod n$其实是已知的，因为$c$模个$n$就可得到$v \equiv c \pmod n$。假设有$v \pmod n$可以解出$r \pmod n$的话，由于$r < n$，即$\pmod n$可忽略，解出的是真实的$r$，然后把$r$代进seq(r, e)就可以解$v$了。所以现在问题可以分解为：

1. 知$p$、$q$、$v \pmod n$，求$r$；
2. 知$r$、$e$求$v \pmod {n^2}$；
3. $mn = cv^{-1}-1 \pmod {n^2}$求$mn$；
4. $m=\frac{mn}{n}$求flag。

其中最难的是第一步。

1. 求r·

刚开始的时候给题目的phi = (p**2 - 1) * (q**2 - 1)误导了（大概），因为，在seq中，如果令$A=\begin{bmatrix} r & -1 \\ 1 & 0 \\ \end{bmatrix}$，$v_0=(r, 2)^T$的话，seq(r, k)就是在做$v_k=A^kv_0$的操作，然后返回$v_k$的第一个元素。由之前讲一般线性群时的推导加上一点验算可得phi就是$A$的群阶，所以就很自然地往一般线性群上面想，但这个结构好像解不出来（菜）。

既然往矩阵上想不行的话就要换一个思路了，首先$seq$的操作跟Fibonacci数列非常像（矩阵也很像），那么seq应该是可以推出通项公式的，推公式可以用解特征方程的方法（具体自行Google），偷懒的就直接在这里查到了：

代进这题的seq就是（附Wolfram代码）：

Solve[x^2 - r*x + 1 == 0, x]
x1 = (r + Sqrt[r^2 - 4])/2;
x2 = (r - Sqrt[r^2 - 4])/2;
g[i_] := Simplify[x1^i + x2^i];
g[e]

（上图左边要加个$v=$）。令$a=r+\sqrt{r^2-4}$、$b=r-\sqrt{r^2-4}$，则上式简化为：

$$2^{e}v = a^e+b^e$$

且有规律：

$$ab = r^2-(r^2+4) = 4 \\ r = \frac{a+b}{2}$$

利用第一个规律，把$2^{e}v = a^e+b^e$再整理一下：

$$2^{e}v = a^e+(4a^{-1})^e = a^e + 4^ea^{-e}$$

令$x=a^e$，上式左右乘个$x$即:

$$2^evx = x^2 + 4^e$$

是个二次方程，由于现在已知的是$v \pmod n$，如果把上面方程放在$\pmod n$下，则可解出$a^e \pmod{n}$，然后就转化为普通的RSA问题，现在知道$p$和$q$了自然可以解密出$a \pmod n$，同理可解出$b \pmod n$，代入上面规律$r=2^{-1}(a+b) \pmod {n}$。所以合理地转化为解模$n$的二次方程：

$$x^2 -2^evx + 4^e \equiv 0 \pmod n$$

然后就是很麻烦的扩域问题了（PS：这里的解并不小（甚至不是整数- -），所以不能Coppersmith解）。扩域可以类比一下初中学的整数域扩复数域，如$x^2=1$，在整数域$\mathbb{Z}$上明显是没解的，所以就要扩到复数域$\mathbb{C}$上解出$x_1=i$、$x_2=-i$。

扩域解方程·

2023.10.17注：其实域上的二次方程直接用二次剩余或者Sage的.roots()解就好了，不知道为什么当时脑抽搞了个扩域，不过感觉以后可以用到，所以就不删了

看回这个题目，首先名字都叫扩域了那就得先转成一个域，由于$n$的分解已经知道了，即$p$和$q$已经知道了，即可以先解出$r_p\ in\ \mathbb{F}_p$和$r_q\ in\ \mathbb{F}_q$然后上CRT解出$r \pmod{n}$。先拿$p$作栗子，令$f(x) = x^2 -2^evx + 4^e$，那现在就是解：

$$f(x) \equiv 0 \ in\ \mathbb{F}_p$$

然后扩域的方法之前在讲Jordan Form的时候大概提到过，先算出$f(x)$的度为$2$（最高项次数），于是就把域扩到：

$$\mathbb{F}_{p^2} = \mathbb{F}[x] / f(x)$$

至于为什么是$\mathbb{F}_{p^2}$，因为$f(x)$最高项是2次，所以应该会有2个解，而现在就恰好有两个解：

$$x = x^{p^0}, x^{p^1} \ in\ \mathbb{F}_{p^2}$$

这里补一下之前留的坑，说一下为什么这两个东西是解（大概，我也不确定）。首先$x^{p^0}=x$肯定是$f(x) \equiv 0 \ in\ \mathbb{F}_p$的解，而在$\mathbb{F}_p$上会有$x^{p^1} \equiv x^p \equiv x$（后面的等号大概是费马小定理），那么$x^{p^1}$也是$f(x) \equiv 0 \ in\ \mathbb{F}_p$的解。注意在$\mathbb{F}_p$上$x^{p^0}$和$x^{p^1}$是一样的，但是在$\mathbb{F}_{p^2}$上是不一样的（即刚才说的两个解）。

这里先令$x_0 = x^{p^0}$、$x_1 = x^{p^1}$（$in\ \mathbb{F}_{p^2}$）。由于$r_p$是个整数（或者说在$\mathbb{F}_p$上），所以最后肯定是要转回$\mathbb{F}_p$上的关系的，但$x_0$和$x_1$不能直接转回$\mathbb{F}_p$（上面说过不然就变相等了），所以还需要一点转化在$\mathbb{F}_{p^2}$上。

首先解出来的$x$应该会是之前设的$x=a^e$，那么应该会有$a \equiv x_0^d$或$a \equiv x_1^d$（注意这里的$d$是$d \equiv e^{-1} \pmod {(p-1)(q-1)}$，另外实验测试用$x_0$和用$x_1$解出来的是一样的），即现在可以知道$a \ in\ \mathbb{F}_{p^2}$。

翻一下上面说的两个规律，现在有（注意在$\mathbb{F}_{p^2}$上也是成立的）：

$$b = 4a^{-1} \\ r = \frac{a+b}{2}$$

于是就可以解出$r \ in\ \mathbb{F}_{p^2}$。由于$r$是个整数（即在$\mathbb{F}_p$上），所以解出来的也是$r_p \ in\ \mathbb{F}_p$。

同理可以解出$r_q\ in\ \mathbb{F}_q$。最后crt([int(rp), int(rq)], [p, q])就可恢复$r$。

比论文的好像复杂一点- -，但这个解方程的方法是通用的（扩域$\to$转成整数$\to$“缩域”$\to$得解），以后应该也能用到。

234. 求m·

这个有了$r$根据刚开始的思路就很容易解了（略，有问题的话可以评论-），最后附代码：

hint·

# sage

n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
e = 7105408692393780974425936359246908629062633111464343215149184058052422839553782885999575538955213539904607968494147112651103116202742324255190616790664935322773999797774246994193641076154786429287567308416036562198486649223818741008968261111017589015617705905631979526370180766874051731174064076871339400470062519500450745667838729104568633808272577378699913068193645578675484681151593983853443489561431176000585296710615726640355782811266099023653898050647891425956485791437516020367967793814415345332943552405865306305448753989707540163585481006631816856260061985275944250758886027672221219132999488907097750048011
c = 2593129589804979134490367446026701647048897831627696427897506570257238733858989741279626614121210703780002736667183915826429635213867589464112850355422817678245007337553349507744893376944140333333044928907283949731124795240808354521353751152149301719465724014407412256933045835977081658410026081895650068864922666975525001601181989114436054060461228877148361720945120260382962899756912493868467226822547185396096960560068874538680230073168773182775945272726468512949751672553541335307512429217493003429882831235199830121519272447634533018024087697385363918421438799206577619692685090186486444886371979602617584956259

p = 11080378090495548888711346538044743233499815208179802720810821877018321760024765272011515142380916992839687768295921206534475286830411300347575580967025893
q = 11080378090495548888711346538044743233499815208179802440842729104792795440344480200955980377175229838508495905797283586060491389310293127737888922016136003
phi = (p-1)*(q-1)
d1 = e.inverse_mod(phi)
v = c%n

# get rp
Fp.<ap> = GF(p)
Rp.<xp> = PolynomialRing(Fp) 
fp = xp^2 - pow(2, e, n)*v*xp + pow(4, e, n) 
Sp = Rp.quotient(fp, 'yp')
deg = fp.degree()  # 2

lambdap = []
lam = Sp(xp)
for di in range(deg+1):
  if di != 0:
    lam = power(lam, p)
    lambdap.append(lam)

# get rq
Fq.<aq> = GF(q)
Rq.<xq> = PolynomialRing(Fq) 
fq = xq^2 - pow(2, e, n)*v*xq + pow(4, e, n) 
Sq = Rq.quotient(fq, 'yq')
deg = fq.degree()  # 2

lambdaq = []
lam = Sq(xq)
for di in range(deg+1):
  if di != 0:
    lam = power(lam, q)
    lambdaq.append(lam)

x1 = lambdaq[0]^d1
x2 = lambdaq[1]^d1
rq1 = 4*x1^(-1) + x1
rq2 = 4*x2^(-1) + x2
assert rq1 == rq2
rq = rq1 / 2
print('rq = %d' % rq)


x1 = lambdap[0]^d1
x2 = lambdap[1]^d1
rp1 = 4*x1^(-1) + x1
rp2 = 4*x2^(-1) + x2
assert rp1 == rp2
rp = rp1 / 2
print('rp = %d' % rp)

r = crt([int(rp), int(rq)], [p, q])
print('r = %d' % r)
# r = 94481828629554556545829029253743639447330281687996501375557067273722993889483560013238090578754733435061039628971763184648836020175350429440493279023808177274857411552495011041326858998774439225875373629039942586972277592866979375576806144415372496959932885289333063119248077134254345866166462313245694271456

A = matrix(Zmod(n^2), [
  [r, -1], 
  [1, 0]
])
v0 = vector(Zmod(n^2), [r, 2])
ve = pow(A, e)*v0
print(ve[1] % n == v)
v2 = int(ve[1])
print('v2 = %s' % v2)

import libnum
mn = (c*libnum.invmod(v2, n^2) - 1) % n^2
#mn = (c*v2.inverse_mod(n^2) - 1) % n^2
print(mn % n == 0)
m = mn//n

hint = libnum.n2s(int(m))
print(hint)
# b'The original challenge picks beta = 0.33, which yields straightforward unintended solution. BTW do you know coppersmith?'

flag·

# sage
n = 59969098213446598961510550233718258878862148298191323654672950330070587404726715299685997489142290693126366408044603303463518341243526241117556011994804902686998166238333549719269703453450958140262475942580009981324936992976252832887660977703209225426388975233018602730303262439218292062822981478737257836581
e = 970698965238639683403205181589498135440069660016843488485401994654202837058754446853559143754852628922125327583411039117445415303888796067576548626904070971514824878024057391507617988385537930417136322298476467215300995795105008488692961624917433064070351961856959734368784774555385603000155569897078026670993484466622344106374637350023474339105113172687604783395923403613555236693496567851779400707953027457705617050061193750124237055690801725151098972239120476113241310088089420901051617493693842562637896252448161948655455277146925913049354086353328749354876619287042077221173795354616472050669799421983520421287
c = 2757297249371055260112176788534868300821961060153993508569437878576838431569949051806118959108641317578931985550844206475198216543139472405873345269094341570473142756599117266569746703013099627523306340748466413993624965897996985230542275127290795414763432332819334757831671028121489964563214463689614865416498886490980692515184662350519034273510244222407505570929178897273048405431658365659592815446583970229985655015539079874797518564867199632672678818617933927005198847206019475149998468493858071672920824599672525667187482558622701227716212254925837398813278836428805193481064316937182435285668656233017810444672

p = 7743971733771153105036156209981171560215008954284943420880584133648389139833517283670475349302080701240378945438911146974137885250527042074631329729385091
q = 7743971733771153102128801312798743998017713722732925283466018690899116898707556486947918196848489007935614742583856884731087798825462330340492923214926391
phi = (p-1)*(q-1)
d1 = e.inverse_mod(phi)
v = c%n

# get rp
Fp.<ap> = GF(p)
Rp.<xp> = PolynomialRing(Fp) 
fp = xp^2 - pow(2, e, n)*v*xp + pow(4, e, n) 
Sp = Rp.quotient(fp, 'yp')
deg = fp.degree()  # 2

lambdap = []
lam = Sp(xp)
for di in range(deg+1):
  if di != 0:
    lam = power(lam, p)
    lambdap.append(lam)

x1 = lambdap[0]^d1
x2 = lambdap[1]^d1
rp1 = 4*x1^(-1) + x1
rp2 = 4*x2^(-1) + x2
assert rp1 == rp2
rp = rp1 / 2
print('rp = %d' % rp)

# get rq
Fq.<aq> = GF(q)
Rq.<xq> = PolynomialRing(Fq) 
fq = xq^2 - pow(2, e, n)*v*xq + pow(4, e, n) 
Sq = Rq.quotient(fq, 'yq')
deg = fq.degree()  # 2

lambdaq = []
lam = Sq(xq)
for di in range(deg+1):
  if di != 0:
    lam = power(lam, q)
    lambdaq.append(lam)

x1 = lambdaq[0]^d1
x2 = lambdaq[1]^d1
rq1 = 4*x1^(-1) + x1
rq2 = 4*x2^(-1) + x2
assert rq1 == rq2
rq = rq1 / 2
print('rq = %d' % rq)


r = crt([int(rp), int(rq)], [p, q])
print('r = %d' % r)

A = matrix(Zmod(n^2), [
  [r, -1], 
  [1, 0]
])
v0 = vector(Zmod(n^2), [r, 2])
ve = pow(A, e)*v0
print(ve[1] % n == v)
v2 = int(ve[1])
print('v2 = %s' % v2)

import libnum
mn = (c*libnum.invmod(v2, n^2) - 1) % n^2
#mn = (c*v2.inverse_mod(n^2) - 1) % n^2
print(mn % n == 0)
m = mn//n

flag = libnum.n2s(int(m))
print(flag)
# b'HFCTF{5eb34942-bd0d-4efd-b0e1-a73225d92678}'

总结·

想复杂了-

PS：hint的coppersmith都不需要用到，合理推测非预期