wiener attack 笔记

发表于 更新于 本文字数： 18k 阅读时长 ≈ 16 分钟
wiener attack 相关的笔记

维纳攻击 (wiener attack)

普通维纳攻击

连分数

一个简单的表达式 \(x=a_0\)，对其进行连分数展开应该是这样的： \[ x=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}} \] 其中 \(a_i\) 我们称作商(quotient)。

一般我们将连分数简记为 \[ x=[a_0,a_1,a_2,\cdots,a_n] \] 而一个有理数（无理数）具有有限（无限）的连分数展开式。

一些简单的例子是： \[ \begin{align} \frac{73}{95}&=0+\frac{1}{1+\frac{1}{3+\frac{1}{3+\frac{1}{7+}}}}=[0,1,3,3,7]\\ \pi&=[3,7,15,1,292,1,1,1,2,\cdots] \end{align} \] 获取连分数的 Python 脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def continuedFractions(x: int, y: int):
    """
    使用辗转相处将分数 x/y 转为连分数的形式
    >>> list(continuedFractions(73, 95))
    [0, 1, 3, 3, 7]

    `Parameters`:
        x - 分子\\
        y - 分母
    
    `Returns`:
        连分数
    """
    while y:
        yield x // y
        x, y = y, x % y

或者我们也可以使用 Sagemath 的函数获取连分数：

1
2
3
a = continued_fraction(73/95)
print(a.quotient(3))
print(a.quotients())

有理近似（收敛分数）

虽然 \(\pi\) 是一个无理数，但我们可以使用连分数展开式获取到一个简洁的有理近似： \[ \begin{align} &c_0=\frac{3}{1}=3.0\\ &c_1=3+\frac{1}{7}=3.142857\\ &c_2=3+\frac{1}{7+\frac{1}{15}}=3.141509\\ &\cdots \end{align} \] 这些有理数 (\(c_i\)) 我们称作连分数的收敛，当 \(i\) 增大时，\(c_i\) 将会无限接近于 \(\pi\)

我们把这样的 \(c_i\) 所组成的数列称作对某个数 \(e\) 的一个收敛分数，表示形式为： \[ e=[c_0,c_1,\cdots,c_n] \] 而同时需要知道任何一个有理数与其连分数形式是一一对应的。

故实际上对于任何一个有理数我们都可以将其展开成一个对应的收敛分数形式。

获取收敛分数的 Python 脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def convergents(x: int, y: int):
    """
        使用辗转相处将分数 x/y 转为渐进分数的形式
        >>> list(ContinuedFraction.convergents(73, 95))
        [(0, 1), (1, 1), (3, 4), (10, 13), (73, 95)]

        `Parameters`:
            x - 分子\\
            y - 分母

        `Returns`:
            连分数
        """
    numerators, denominators = [], []
    for idx, val in enumerate(ContinuedFraction.fractions(x, y)):
        if idx == 0:
            ni, di = val, 1
            elif idx == 1:
                ni, di = val * numerators[-1] + 1, val
                else:
                    ni, di = val * numerators[-1] + numerators[-2], val * denominators[-1] + denominators[-2]
                    numerators.append(ni)
                    denominators.append(di)
                    yield ni, di

或者我们也可以使用 Sagemath 的函数获取渐进分数：

1
2
3
a = continued_fraction(73/95)
print(a.convergent(3))
print(a.convergents())

Legendre's theorem (连分数定理)

如果存在 \(\alpha \in Q\)，\(c,d\in Z\) 满足 \[ \left|\alpha-\frac{c}{d}\right|<\frac{1}{2d^2} \] 那么 \(\displaystyle\frac{c}{d}\) 就是 \(\alpha\) 的一个有理近似。

原理

首先我们考虑，如果已知 \(N=pq\) 和 \(\varphi(N)=(p-1)(q-1)\)，那么 \[ \begin{align} \varphi(N)&=(p-1)(q-1)\\ &=N-p-q+1\\ &=N-p-\frac{N}{p}+1 \end{align} \] 因此我们可以得到方程： \[ p^2+p(\varphi(N)-N-1)+N=0 \] 所以当已知 \(N\) 和 \(\varphi(N)\) 时，\(N\) 是极易分解的。

其次我们知道 \(ed=1\pmod{\varphi(N)}\)，即存在一个 \(k\) 使得： \[ ed=1+k\varphi(N) \] 对其变形可得 \[ \left|\frac{e}{\varphi(N)}-\frac{k}{d}\right|=\frac{1}{d\varphi(N)} \] 由 Legendre's theorem 可得，\(\displaystyle\frac{k}{d}\) 是 \(\displaystyle\frac{e}{\varphi(N)}\) 的一个有理近似，如果我们获得了 \(\displaystyle\frac{e}{\varphi(N)}\)，那么我们就可以从其的有理近似中获取 \(\displaystyle\frac{k}{d}\)。（\(d\) 泄露攻击）

但在维纳攻击中，我们只有 \(e\) 和 \(N\)，那是否会在特定条件中 \(\displaystyle\frac{k}{d}\) 是 \(\displaystyle\frac{e}{N}\) 的一个有理近似？

如果说 \(N=pq\) 且 \(q<p<2q\)，那么 \[ \varphi(N)=(p-1)(q-1) \] 可以计算误差限 \[ N-\varphi(N)=p+q-1< 3\sqrt{N} \] 如果此时把 \(N\) 替换为 \(\varphi(N)\) 到上述变形式，有 \[ \begin{align} \left|\frac{e}{N}-\frac{k}{d}\right|&=\frac{ed-kN}{Nd}\\ &=\left|\frac{1-k[N-\varphi(N)]}{Nd}\right|\\ \end{align} \] 此时误差限 \[ \begin{align} \left|\frac{e}{N}-\frac{k}{d}\right|&<\left|\frac{k[N-\varphi(N)]}{Nd}\right|\\ &<\left|\frac{3k\sqrt{N}}{Nd}\right|\\ &=\frac{3k}{d\sqrt{N}}\\ &\leq \frac{3k}{d\sqrt{N}}\\ &<\frac{3}{\sqrt{N}} \end{align} \]

由 \(k\varphi(N)<ed<\varphi(N)d\)，得 \(k<d\)

由于连分数定理，必须要有 \[ \frac{3}{\sqrt{N}}<\frac{1}{2d^2} \] 得 \[ d<\frac{1}{\sqrt{6}}N^{\frac{1}{4}} \] 只有满足此式时，\(\displaystyle\frac{k}{d}\) 才是 \(\displaystyle\frac{e}{N}\) 的一个有理近似。

实际证明中应该是 \(d<\displaystyle\frac{1}{3}N^{\frac{1}{4}}\)，因为这里在数值的界定上不一定完备，仅作思路引导。

步骤

  1. 估测是否满足 \(d<\displaystyle\frac{1}{3}N^{\frac{1}{4}}\)
  2. 求 \(\displaystyle\frac{e}{N}\) 的连分数展开
  3. 迭代连分数 \(\displaystyle\frac{k_i}{d_i}\)：
    • 使用 \(k_i\) 和 \(d_i\) 计算出 \(\varphi_i(N)\)
    • 使用 \(\varphi_i(N)\) 计算出 \(N\)，然后通过因式分解进行验证是否正确（我们也可以直接进行解密验证）

脚本

以下仅给出 Sagemath 脚本：

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
def wienerAttack(N, e):
    """
    维纳攻击

    `Parameters`:
        N - p * q\\
        e - public key
    
    `Returns`:
        p, q, d
    """
    cf = continued_fraction(e / N)
    convers = cf.convergents()
    for pkd in convers:
        # possible k, d
        pk, pd = pkd.as_integer_ratio()
        if pk == 0:
            continue
        
        # verify
        if (e * pd - 1) % pk != 0:
            continue
        
        # possible phi
        pphi = (e * pd - 1) // pk
        p = var('p', domain=ZZ)
        roots = solve(p ** 2 + (pphi - N - 1) * p + N, p)
        if len(roots) == 2:
            # possible p, q
            pp, pq = roots
            if pp * pq == N:
                return pp, pq, pd
    raise ValueError('Could not factor N!')

N = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
p, q, d = wienerAttack(N, e)
m = pow(c, d, N)

技巧

有时会注意到因为某些关系使得 \(d\) 过大，导致 \(\frac{1}{d\varphi(N)}\) 不满足连分数定理，比如说最简单的情况是使其扩大一个倍数 \(d=td_0\)，其中 \(d_0\) 满足条件。

如果说此时 \(t\) 知道，我们仅需使得 \(e=te_0\) 即可，其中 \(e_0d=1\pmod{\varphi(N)}\)。

这样就会使得 \[ \frac{t}{d\varphi(N)}=\frac{1}{d_0\varphi(N)} \] 此时再次满足条件。

由于只需满足条件就会使得 \(N\) 可以替换 \(\varphi(N)\)，故这里不作严格数值分析。

扩展维纳攻击

Wiener 's Approach

我们已知 \[ ed=k\varphi(N)+1 \] 不妨令 \(s=1-p-q\)，那么 \[ ed-kN=ks+1\tag{W} \]

Guo 's Approach With Two Exponents

如果对于同一个 \(N\) 存在 \((e_1,e_2)\) 都有相对应较小的 \((d_1,d_2)\)，那么我们可以得到： \[ \begin{cases} e_1d_1-k_1\varphi(N)=1\\ e_2d_2-k_2\varphi(N)=1\\ \end{cases} \] 对其进行化简得到： \[ e_1d_1k_2-e_2d_2k_1=k_2-k_1\tag{G(1,2)} \] 可以推导出 \[ \left|\frac{e_1}{e_2}-\frac{d_2k_1}{d_1k_2}\right|=\frac{|k_2-k_1|}{e_2d_1k_1} \] 那么如果 \(2(k_2-k_1)d_1k_2<e_2\)，根据 Legendre's theorem 我们得知 \(\displaystyle\frac{d_2k_1}{d_1k_2}\) 是 \(\displaystyle\frac{e_1}{e_2}\) 的一个有理近似。

但通过 \(\displaystyle\frac{d_2k_1}{d_1k_2}\) 确定 \((d_1,d_2)\) 不是很现实。

两个小解密指数的原理

结合维纳攻击和 Guo's Approach，我们可以通过多个等式构造格后，利用 LLL 格规约算法化简求解该问题。

首先假设 \(d_i<N^\alpha\)，联立四个式子：

  1. \[ k_1k_2=k_1k_2 \]

  2. \(W_1\cdot k_2\) \[ e_1d_1k_2-k_1Nk_2=k_2(k_1s+1) \]

  3. \(G(1,2)\) \[ e_2d_2k_1-e_1d_1k_2=k_1-k_2\tag{G(1,2)} \]

  4. \(W_1\cdot W_2\) \[ (e_1d_1-k_1N)(e_2d_2-k_2N)=(k_2s+1)(k_2s+1)\\ \Downarrow\\ d_1d_2e_1e_2-d_1k_2e_1N-d_2k_1e_2N+k_1k_2N^2=(k_2s+1)(k_2s+1) \]

从而构造矩阵 \(A,L,B\) \[ A= \begin{pmatrix} k_1k_2,d_1k_2,d_2k_1,d_1d_2 \end{pmatrix}\\ L= \begin{pmatrix} 1 & -N & 0 & N^2 \\ 0 & e_1 & -e_1 & -e_1N \\ 0 & 0 & e_2 & -e_2N \\ 0 & 0 & 0 & e_1e_2 \end{pmatrix}\\ B=\begin{pmatrix}k_1k_2,k_2(k_1s+1),k_1-k_2,(k_2s+1)(k_2s+1)\end{pmatrix} \] 满足 \[ A\cdot L=B \] 而根据假设可知 \[ e_i\approx N\\ d_i\approx N^\alpha\\ k_i\approx d_i \approx N^\alpha\\ g\approx 1\\ s=1-p-q\approx N^{0.5} \] 根据 Minkowoski′s first theorem 可知，只有满足 \[ \lambda_1(L)\leq\sqrt{n}\det(L)^{\frac{1}{n}} \] 才能算是最短向量，但明显右边计算结果为 \(N\)，明显 \(||B||>N\)，所以需要考虑使得等式两边的大小尽量接近，而等式右边向量的大小为 \((N^{2\alpha},N^{0.5+2\alpha},N^{\alpha},N^{1+2\alpha})\)，故我们最终构造的矩阵应该为： \[ L= \begin{pmatrix} 1 & -N & 0 & N^2 \\ 0 & e_1 & -e_1 & -e_1N \\ 0 & 0 & e_2 & -e_2N \\ 0 & 0 & 0 & e_1e_2 \end{pmatrix} \cdot \begin{pmatrix} N & & & \\ & N^0.5 & & \\ & & N^{1+\alpha} & \\ & & & 1 \end{pmatrix} \] 这样便使得向量 \(B\) 满足 \[ ||BL||<2N^{1+2\alpha} \] 将问题转化为类 SVP 问题后，使用格规约算法 LLL 既可以得到基向量 \(B\)，随后 \[ \frac{B_2}{B_1}=\frac{d_1}{k_1}\\ \varphi(N)=\frac{ed}{k} \] 在这里根据部分证明可知，对于两个小解密指数的情况，当 \(c\) 较小时，如果有 \[ \alpha<\frac{5}{14}-\varepsilon \] 就可以通过格基规约找到向量 \(B\)。

三个小解密指数的情况

对于三个指数的情况我们额外选取 \(G(1,3),W_1G(2,3),W_2G(1,3)\) 的等式，这样我们的向量 \(B\) 为： \[ B = \begin{pmatrix} k_1k_2k_3&d_1gk_2k_3&k_1d_2gk_3&d_1d_2g^2k_3&k_1k_2d_3g&k_1d_3g&k_2d_3g&d_1d_2d_3g^3 \end{pmatrix} \] 然后我们便可以构造格： \[ L = \begin{pmatrix} 1 & -N & 0 & N^{2} & 0 & 0 & 0 & -N^{3} \\ 0 & e_{1} & -e_{1} & -N e_{1} & -e_{1} & 0 & N e_{1} & N^{2} e_{1} \\ 0 & 0 & e_{2} & -N e_{2} & 0 & N e_{2} & 0 & N^{2} e_{2} \\ 0 & 0 & 0 & e_{1} e_{2} & 0 & -e_{1} e_{2} & -e_{1} e_{2} & -N e_{1} e_{2} \\ 0 & 0 & 0 & 0 & e_{3} & -N e_{3} & -N e_{3} & N^{2} e_{3} \\ 0 & 0 & 0 & 0 & 0 & e_{1} e_{3} & 0 & -N e_{1} e_{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & e_{2} e_{3} & -N e_{2} e_{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & e_{1} e_{2} e_{3} \end{pmatrix} \] 其中 \[ D = diag\begin{pmatrix} N^{\frac{3}{2}}&N&N^{a + \frac{3}{2}}&\sqrt{N}&N^{a + \frac{3}{2}}&N^{a + 1}&N^{a + 1}&1\end{pmatrix} \] 同样我们可以得知 \[ ||BL||<\sqrt{8}N^{1.5+2\alpha} \] 证明可得，当 \[ \alpha<\frac{2}{5}-\varepsilon \] 时，可以通过格基规约求出向量 \(B\)。

选择关系

论文末位给出的 \(n\leq 5\) 的选择关系表：

选择关系表

脚本

这里仅给出 Sagemath 的脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def wienerAttack2(N, e1, e2):
    a = 5/14
    D = diagonal_matrix(ZZ, [N, int(N^(1/2)), int(N^(1+a)), 1])
    M = matrix(ZZ, [[1, -N, 0, N^2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]])*D
    L = M.LLL()
    B = vector(ZZ, L[0])
    A = B * M^(-1)
    phi = int(A[1]/A[0]*e1)
    d1 = inverse_mod(e1, phi)
    d2 = inverse_mod(e2, phi)
    p = var('p', domain=ZZ)
    roots = solve(p ** 2 + (pphi - N - 1) * p + N, p)
    if len(roots) == 2:
        # possible p, q
        p, q = roots
        if p * q == N:
            return p, q, d1, d2
    raise ValueError('Could not factor N!')

e1 = 114552459553730357961013268333698879659007919035942930313432809776799669181481660306531243618160127922304264986001501784564575128319884991774542682853466808329973362019677284072646678280051091964555611220961719302320547405880386113519147076299481594997799884384012548506240748042365643212774215730304047871679706035596550898944580314923260982768858133395187777029914150064371998328788068888440803565964567662563652062845388379897799506439389461619422933318625765603423604615137217375612091221578339493263160670355032898186792479034771118678394464854413824347305505135625135428816394053078365603937337271798774138959
e2 = 27188825731727584656624712988703151030126350536157477591935558508817722580343689565924329442151239649607993377452763119541243174650065563589438911911135278704499670302489754540301886312489410648471922645773506837251600244109619850141762795901696503387880058658061490595034281884089265487336373011424883404499124002441860870291233875045675212355287622948427109362925199018383535259913549859747158348931847041907910313465531703810313472674435425886505383646969400166213185676876969805238803587967334447878968225219769481841748776108219650785975942208190380614555719233460250841332020054797811415069533137170950762289
N = 14922959775784066499316528935316325825140011208871830627653191549546959775167708525042423039865322548420928571524120743831693550123563493981797950912895893476200447083386549353336086899064921878582074346791320104106139965010480614879592357793053342577850761108944086318475849882440272688246818022209356852924215237481460229377544297224983887026669222885987323082324044645883070916243439521809702674295469253723616677245762242494478587807402688474176102093482019417118703747411862420536240611089529331148684440513934609412884941091651594861530606086982174862461739604705354416587503836130151492937714365614194583664241
p, q, d1, d2 = wienerAttack2(N, e1, e2)

针对于三个小解密指数，假设生成代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getStrongPrime(1024)
q=getStrongPrime(1024)
phi=(p-1)*(q-1)
e1=inverse(getPrime(768),phi)
e2=inverse(getPrime(768),phi)
e3=inverse(getPrime(768),phi)
n=p*q
c=pow(m,0x10001,n)
print(f'e1={e1}')
print(f'e2={e2}')
print(f'e3={e3}')
print(f'c={c}')
print(f'n={n}')

解密代码为

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
e1 = 5077048237811969427473111225370876122528967447056551899123613461792688002896788394304192917610564149766252232281576990293485239684145310876930997918960070816968829150376875953405420809586267153171717496198336861089523701832098322284501931142889817575816761705044951705530849327928849848158643030693363143757063220584714925893965587967042137557807261154117916358519477964645293471975063362050690306353627492980861008439765365837622657977958069853288056307253167509883258122949882277021665317807253308906355670472172346171177267688064959397186926103987259551586627965406979118193485527520976748490728460167949055289539
e2 = 12526848298349005390520276923929132463459152574998625757208259297891115133654117648215782945332529081365273860316201130793306570777735076534772168999705895641207535303839455074003057687810381110978320988976011326106919940799160974228311824760046370273505511065619268557697182586259234379239410482784449815732335294395676302226416863709340032987612715151916084291821095462625821023133560415325824885347221391496937213246361736361270846741128557595603052713612528453709948403100711277679641218520429878897565655482086410576379971404789212297697553748292438183065500993375040031733825496692797699362421010271599510269401
e3 = 12985940757578530810519370332063658344046688856605967474941014436872720360444040464644790980976991393970947023398357422203873284294843401144065013911463670501559888601145108651961098348250824166697665528417668374408814572959722789020110396245076275553505878565603509466220710219260037783849276475397283421068716088638186994778153542817681963059581651103563578804145156157584336712678882995685632615686853980176047683326974283896343322981521150211317597571554542488921290158122634140571148036732893808064119048328855134054709120877895941670166421664806186710346824494054783025733475898081247824887967550418509038276279
c = 1414176060152301842110497098024597189246259172019335414900127452098233943041825926028517437075316294943355323947458928010556912909139739282924255506647305696872907898950473108556417350199783145349691087255926287363286922011841143339530863300198239231490707393383076174791818994158815857391930802936280447588808440607415377391336604533440099793849237857247557582307391329320515996021820000355560514217505643587026994918588311127143566858036653315985177551963836429728515745646807123637193259859856630452155138986610272067480257330592146135108190083578873094133114440050860844192259441093236787002715737932342847147399
n = 17853303733838066173110417890593704464146824886316456780873352559969742615755294466664439529352718434399552818635352768033531948009737170697566286848710832800426311328560924133698481653594007727877031506265706341560810588064209681809146597572126173303463125668183837840427667101827234752823747483792944536893070188010357644478512143332014786539698535220139784440314481371464053954769822738407808161946943216714729685820896972467020893493349051243983390018762076812868678098172416465691550285372846402991995794349015838868221686216396597327273110165922789814315858462049706255254066724012925815100434953821856854529753

L = matrix(ZZ, [
    [1, -n, 0, n**2, 0, 0, 0, -n**3],
    [0, e1, -e1, -n * e1, -e1, 0, n * e1, n**2 * e1],
    [0, 0, e2, -n * e2, 0, n * e2, 0, n**2 * e2],
    [0, 0, 0, e1 * e2, 0, -e1 * e2, -e1 * e2, -n * e1 * e2],
    [0, 0, 0, 0, e3, -n * e3, -n * e3, n**2 * e3],
    [0, 0, 0, 0, 0, e1 * e3, 0, -n * e1 * e3],
    [0, 0, 0, 0, 0, 0, e2 * e3, -n * e2 * e3],
    [0, 0, 0, 0, 0, 0, 0, e1 * e2 * e3]
])
# alpha = 768 / 2048
alpha = 2 / 5
D = diagonal_matrix(ZZ, [floor(pow(n, 3 / 2)), n, floor(pow(n, alpha + 3/2)), floor(pow(n, 1/2)), floor(pow(n, alpha + 3/2)), floor(pow(n, alpha + 1)), floor(pow(n, alpha + 1)), 1])
M = L * D
B = M.LLL()
b = vector(ZZ, B[0])
A = b * M^(-1)
phi = floor(A[1] / A[0] * e1)

d = inverse_mod(0x10001, phi)
m = pow(c, d, n)
flag = long_to_bytes(int(m))
print(flag)

参考论文

《A New Attack on RSA with Two or Three》