LatticeNotes8

huangx607087构造格LLL的笔记 8

0.Introduction

最近看到几个题目构造矩阵然后LLL的，发现自己以前的一些做法存在一些问题，因此在这边记录一下新学到的一些内容。

和前面的笔记不一样，这篇笔记中，很多题目都是以前出现过的，因此在这里对部分题目再进行一个复盘。

最近发现很多师傅都看过我博客？并且这里有些师傅还是在我退役后入坑的。（其实，我自己都不知道，自己在2021年写了写啥了）

1. 回顾以前的知识

1x01 几个定理

高斯启发式：在笔记2中，我们提到了高斯启发式，也就是对于一个格矩阵 $L$ ，若想在原点构造一个半径为 $r$ 的（高维）球，使得这个球中至少有一个格点向量 $\vec v$，那么对应的半径的最小值 $r$ 为
$$
r≈\sqrt{\dfrac{n}{2\pi e}}·\sqrt[n]{\det L}=\sigma (L)
$$

Hermite定理： 维数 $n$ 的每一个格矩阵 $L$ 中，其最短向量长度 $|\vec v_1|$ 满足
$$
|\vec v_1|\le\sqrt n· \sqrt[n]{\det L}
$$
Minkowski定理： 设 $L$ 是 $\mathbb R^n$ 中的一个格，$S$ 是 $\mathbb R^n$ 中的一个对称凸集，那么 $S$ 的体积 $\text{Vol }S> 2^n \det L$ 时，$S$ 中就包含一个非零格向量。

这边重点是第二个的Hermite定理，因为这个定理，明确了最短向量的大小。如果忽略掉 $\sqrt n$ 这一系数，我们可以大概得出结论：

如果待求的目标向量 $\vec v$ 的长度小于 $\sqrt[n]{\det L}$，则在解题中，构造矩阵LLL后，大概率最短向量就是所求的解。

1x02 格的构造方法回顾

Example 1 单个线性关系式

构造格主要是当确定部分未知量相对于模数 $n$ 很小，并且有较为明显线性关系时，通过矩阵的方法连接已知量和未知量，然后构造。比如在下面的例子：

1
2
3
4
5
6
7
8
9
10
11
#T1
from Crypto.Util.number import *
from random import *
x=[(1<<95)|getrandbits(96) for i in range(3)]
a=[getrandbits(1024) for i in range(3)]
p=getPrime(1024)
veca=vector(GF(p),a)
vecx=vector(GF(p),x)
y=veca*vecx
print(y)
print(veca)

可以看出，这里每个 $x$ 的值为 $96$ 位，然后 $a,y,p$ 均为 $1024$ 位，且这个线性关系给得非常明显：
$$
a_1x_1+a_2x_2+a_3x_3\equiv y \pmod p
$$
去同余，可以有
$$
a_1x_1+a_2x_2+a_3x_3-y-kp=0
$$
因为我们要求的内容是 $x$，因此我们可以暂时把 $x$ 放在前 $3$ 个。因为上面的线性关系一共是五项，因此可以有 $1\times -y$ 和 $-k\times p$ 项。因此，矩阵的最后一列可以放入 $(a_1,a_2,a_3,-y,p)$。而第四列的 $1$，是为了第五列第四行的 $y$ 匹配。这个 $1$ 也可以作为一个标志使用。因为我们结出来的向量 可能不是 最短向量，这个 $1$ 和最后的 $0$ 可以当成一个哨兵，如果我们最后LLL的后矩阵中，我们只需要筛选出倒数第二个分量为 $1$，最后一个分量为 $0$ 的向量，那么这个向量的前三个分量就 可能是 $x_1,x_2,x_3$。

1

然后我们可以写个代码测试一下：

2

可以看出，最后求出的第一个向量，恰好就是三个未知的 $x$ 值。

Example 2 多个线性关系式

当然，其实也不一定要构造对角线全 $1$，因为这样的话，会严重拉低矩阵的行列式的值，这样就会导致求出来的向量不在最短的 $n$ 个向量中。如果有未知量和未知量之间的关系，也可以从未知量到未知量构造线性关系，比如下面这个题：

1
2
3
4
5
6
7
8
9
10
11
12
13
#T2
from Crypto.Util.number import *
from random import *
p=getPrime(1024)
x=[getPrime(160) for i in range(3)]
y=[getPrime(160) for i in range(3)]
a=[getrandbits(1024) for i in range(3)]
b=[getrandbits(1024) for i in range(3)]
z=[(a[i]*x[i]+b[i]*y[i])%p for i in range(3)]
print(a)
print(b)
print(z)
print(p)

这个题的方法是 $a_ix_i+b_iy_i\equiv z_i \pmod p$ ，有两个未知量 $x,y$，并且数字都很小。如果像刚才那样构造矩阵，会导致矩阵中对角线上的 $1$ 过多，扩大了矩阵的维数，导致矩阵中的最短向量变得很短（甚至LLL后得到的是一个单位矩阵的行置换）。

由于 $x$ 和 $y$ 都很小，因此我们可以考虑从 $x$ 到 $y$ 的一个表达式，由于
$$
a_ix_i+b_iy_i\equiv z_i\pmod p
$$
因此：
$$
y_i\equiv \frac{z_i-a_ix_i}{b_i}\pmod p
$$
也就是：
$$
y_i\equiv Z_i-A_ix_i\pmod p
$$
其中：
$$
Z_i\equiv \frac{z_i}{b_i}\pmod p,A_i\equiv \frac{a_i}{b_i} \pmod p
$$
对上面的式子去同余，可以得到：
$$
y_i=Z_i-A_ix_i-k_ip
$$

因此，可以构造下面的线性关系：

3

当然，这么看着好像有点不太顺眼，实际上，这么解出来也得不到任何有价值的信息，因为这个矩阵形状有点怪异：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#exp2-1
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [-diagonal_matrix(A)],
        [matrix(Z)],
        [p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
print(M3L)
"""
Output:
[ 0  0  0]
[ 0  0  0]
[ 0  0  0]
[ 0  0  0]
[-1  0  0]
[ 0  1  0]
[ 0  0  1]
"""

不过，我们可以在这个矩阵的左上角塞一个单位矩阵，这样就是 $7\times6$，效果好多了：

4

然后运行一下这个代码看看：

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
#exp2-2
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [identity_matrix(3),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix(Z)],
        [zero_matrix(3),p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
Output:
0 0 0 0 0 0 
160 160 160 160 160 160 
377 376 376 376 376 376 
373 376 376 373 377 376 
377 377 374 375 373 373 
375 374 377 378 377 375 
375 375 375 374 377 378 
"""

然后我们看一下第一行内容，经过测试没有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
#exptest2
print(f'{x=}')
print(f'x1={M3L[1][:3]}')
print(f'{y=}')
print(f'y1={M3L[1][3:]}')
print(vector(x)==M3L[1][:3] or -vector(x)==M3L[1][:3])
print(vector(y)==M3L[1][3:] or -vector(y)==M3L[1][3:])
#x=[1059875609154052394049446554149851904167774738381, 898532734274997387994126363047576903953022594169, 1461113197585095174694740018880741222582006584223]
#x1=(1059875609154052394049446554149851904167774738381, 898532734274997387994126363047576903953022594169, 1461113197585095174694740018880741222582006584223)
#y=[1325343819676712371092085429082944496756103571807, 745378211847616885781181840559736682949015771531, 800128726102435929010952852039360480436507220627]
#y1=(1325343819676712371092085429082944496756103571807, 745378211847616885781181840559736682949015771531, 800128726102435929010952852039360480436507220627)
#True
#True

当然，如果你有强迫症，想要构造方阵，让最短向量成为答案，当然没有问题，可以构造矩阵

6

这边只输出了每个分量的比特数，经过测试，可以发现，第一个分量就是 $(x_1,x_2,x_3,1,y_1,y_2,y_3)$，符合条件！

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
#exp2-3
M=block_matrix(ZZ,
    [
        [identity_matrix(3),zero_matrix(3,1),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix([1]),matrix(Z)],
        [zero_matrix(3),zero_matrix(3,1),p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
print(vector(x)==M3L[0][:3] or -vector(x)==M3L[0][:3])
print(vector(y)==M3L[0][-3:] or -vector(y)==M3L[0][-3:])
"""
160 160 160 1 160 160 160 
484 484 483 482 481 484 478 
481 483 484 483 484 484 483 
484 483 483 485 484 483 481 
485 484 484 485 480 481 484 
484 484 484 484 483 484 485 
485 483 485 484 484 485 485 
True
True
"""

Example 3 第一题的加强版

如果我们改一下Example 1，啥也没有改，就把第一行的 $x$ 每个分量从 $96$ 比特改成 $240$ 比特：

1
2
3
4
5
6
7
8
9
10
11
#T3
from Crypto.Util.number import *
from random import *
x=[getPrime(240) for i in range(3)]
a=[getrandbits(1024) for i in range(3)]
p=getPrime(1024)
veca=vector(GF(p),a)
vecx=vector(GF(p),x)
y=veca*vecx
print(y)
print(veca)

现在如果我们构造那个代码，会怎样呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#exp1
M=[
    [1,0,0,0,a[0]],
    [0,1,0,0,a[1]],
    [0,0,1,0,a[2]],
    [0,0,0,1,-y],
    [0,0,0,0,p]
]
M=Matrix(ZZ,M)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
204 204 202 204 203 
204 202 204 204 203 
205 203 205 203 198 
203 206 202 204 201 
204 201 203 204 205 
"""

好像解不出啥东西来了！我们期待的 $(x_1,x_2,x_3,1,0)$ 对应的比特数分别为 $(240,240,240,1,0)$，这里得到的向量的比特数都是 $204$ 左右。如果我们回顾定理，可以发现 $\log_2 \det M=\log_2 p=1024$，矩阵阶数为 $5$，因此矩阵中最短向量长度是 $1024/5=205$ 比特，最后事实也确实如此。我们期待的向量并不是最短的 $5$ 个向量。

因为这个矩阵是三角矩阵，因此以前我的操作就是在最后一列乘上一个很大的数字（可以用定理算出来，但我几乎是乱乘的），然后我们期待的向量就又在其中了，因为这个时候矩阵行列式的值达到了 $2^{10000}$ 以上，最短向量大小范围被扩大，因此我们期待的向量也就出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#exp3
M=[
    [1,0,0,0,a[0]],
    [0,1,0,0,a[1]],
    [0,0,1,0,a[2]],
    [0,0,0,1,-y],
    [0,0,0,0,p]
]
C=2**9999
M=Matrix(ZZ,M)*diagonal_matrix(ZZ,[1,1,1,1,C])
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
240 240 240 1 0 
258 260 260 260 0 
261 261 261 259 0 
260 259 261 262 0 
260 259 259 260 10000 
"""

Example 4 第二题的加强版

同理，我们改一下Example 2，$x$ 和 $y$ 大小从 $2^{160}$ 变成 $2^{450}$

1
2
3
4
5
6
7
8
9
10
11
12
13
#T4
from Crypto.Util.number import *
from random import *
p=getPrime(1024)
x=[getPrime(450) for i in range(3)]
y=[getPrime(450) for i in range(3)]
a=[getrandbits(1024) for i in range(3)]
b=[getrandbits(1024) for i in range(3)]
z=[(a[i]*x[i]+b[i]*y[i])%p for i in range(3)]
print(a)
print(b)
print(z)
print(p)

然后我们再看看会怎样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#exp2-3
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [identity_matrix(3),zero_matrix(3,1),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix([1]),matrix(Z)],
        [zero_matrix(3),zero_matrix(3,1),p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
439 438 436 438 436 434 438 
439 438 437 438 436 437 438 
438 438 438 438 438 434 435 
438 434 439 435 436 439 437 
436 438 437 436 438 436 439 
433 438 439 439 439 437 436 
438 437 439 439 434 438 438 
"""

可以看到，因为矩阵大小为 $7\times7$，行列式值为 $p^3$，因此最短向量长度为 $p^{3/7}$，对应长度也就是 $438$ 比特左右，可以看出，最后得到的$7$ 个向量长度都是 $438$ 比特左右。

然后以前我做到这边，直接大力出奇迹，还真别说，最后解出来，最后一个向量还真是答案。。。

7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#exp4
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [identity_matrix(3),zero_matrix(3,1),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix([1<<20000]),matrix(Z)],
        [zero_matrix(3),zero_matrix(3,1),p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
0 0 511 0 0 0 510 
508 0 0 0 512 0 0 
0 512 0 0 0 512 0 
0 512 0 0 0 512 0 
513 0 0 0 509 0 0 
0 0 512 0 0 0 513 
450 450 450 20001 450 450 450 
"""

然后，好像就没啥然后了，似乎这么做还挺对的，直到我遇到。。。

Example 5 出现问题

1
2
3
4
5
6
7
8
9
10
11
12
13
#T5
from Crypto.Util.number import *
from random import *
p=getPrime(1024)
x=[getPrime(333) for i in range(3)]
y=[getPrime(633) for i in range(3)]
a=[getrandbits(1024) for i in range(3)]
b=[getrandbits(1024) for i in range(3)]
z=[(a[i]*x[i]+b[i]*y[i])%p for i in range(3)]
print(a)
print(b)
print(z)
print(p)

然后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#exp4
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [identity_matrix(3),zero_matrix(3,1),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix([1<<20000]),matrix(Z)],
        [zero_matrix(3),zero_matrix(3,1),p*identity_matrix(3)]
    ]
)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
0 0 511 0 0 0 509 
510 0 0 0 512 0 0 
0 511 0 0 0 511 0 
0 512 0 0 0 512 0 
512 0 0 0 512 0 0 
0 0 512 0 0 0 514 
509 512 511 20001 506 510 512 
"""

怎么回事呢？

2.观察解出的向量特点

观察一下前面LLL生成的每个向量各个分量的比特长度，我们可以发现，Example1,2两个例子中，解出来的向量每个分量的比特数都比较近似。这甚至也包括了Example 3,4中解出来的部分向量的特性。

而之所以我们可以在Example 3,4中，通过加入一个远大于模数的数字，最后依然能够得到答案，是因为那个矩阵中所有行向量中，只有那唯一一个行向量对应的分量为非 $0$。比如Example 4中构造的矩阵，7​ 个行向量中，只有第 ​4​ 个行向量的第 4 分量为非 0，这是一个bug级别的设置，因为当那个分量值为 $2^{20000}$ 后，LLL后，矩阵中第 4 个分量必须是 $2^{20000}$ 的倍数，且至少有一个向量的第 4 分量不为 0。因此，格中满足第 4 分量非 0 的最短向量的第 4 分量只能为 $2^{20000}$，至于其他的分量，那也只能让其尽量短了。因此最后LLL之后，$2^{20000}$ 就保存下来了。

并且我们也能发现，加入 $2^{20000}$ 后，包含 $2^{20000}$ 项的那个向量的其他几个分量长度也比较接近。并且抛开对应矩阵的第四分量不看，其他向量的比特数也比较接近。而之所以会出现这种情况，可以这么想：

已知两个向量 $\log_2\vec v_1=(500,600,700)$ 和 $\log_2 \vec v_2=(600,600,600)$，很显然，$\vec v_1$ 的长度远远长于 $\vec v_2$，因为向量长度是所有分量的平方和开根号。越大的数字平方后，会变得更大，而此时小数字相对于大数字就可以被忽略了！

请注意，这两个向量前面加了 $\log_2$ 符号，$(500,600,700)$ 和 $(600,600,600)$ 都是取对数后的结果，这里 $700$ 代表的数字比 $600$ 代表的数字大 $2^{100}$ 倍！那么最后算长度，$\vec v_1$ 的长度就是 $700$ 位，而 $\vec v_2$ 的长度大概是 $601$ 位，这样明确的感觉就来了！换句话说，LLL格基归约时，如果遇到某个分量较大时，会通过线性计算，扩大较小的分量，来降低较大的分量的大小，因为LLL是要求最短向量，也就是每个向量的平方和尽量短，因此，最后得到的向量，每个分量的结果就会趋近于平均。

而Example 5中出现的问题，就是 $x$ 为 $333$ 位，$y$ 为 $633$ 位。 两个数字之间不平衡所导致的，因此我们可以通过乘入一个系数的方法，将该向量中的每一个分量凑平衡。

由于我们的目标向量为 $(x_1,x_2,x_3,1,y_1,y_2,y_3)$，每个数字比特数分别为 $(333,333,333,1,633,633,633)$，因此可以对构造的原矩阵的前 $3$ 列乘入一个 $2^{300}$，第四列乘一个 $2^{633}$，最后得到的目标向量就变成了：
$$
(2^{300}x_1,2^{300}x_2,2^{300}x_3,2^{633},y_1,y_2,y_3)
$$
这个向量每个分量均为 $633$ 位，原矩阵为 $7$ 阶方阵，此时乘入这个平衡系数后，矩阵的行列式满足：
$$
\log_2 \det M=300\times3+633+1024\times3=4605
$$
因此，最短向量的长度大概为：
$$
\log_2 |\vec v_1|<\frac{4605}{7}=657.85
$$
而我们所求的向量，每个分量均为 $633$ 位，因此其长度大概为 $2^{633}\sqrt7$，对应位数为 $635$ 位不到，比 $657.85$ 小，因此可能为最短向量。

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
#exp5
A=[a[i]*inverse(b[i],p)%p for i in range(3)]
Z=[z[i]*inverse(b[i],p)%p for i in range(3)]
M=block_matrix(ZZ,
    [
        [identity_matrix(3),zero_matrix(3,1),-diagonal_matrix(A)],
        [zero_matrix(1,3),matrix([1]),matrix(Z)],
        [zero_matrix(3),zero_matrix(3,1),p*identity_matrix(3)]
    ]
)
M=M*diagonal_matrix(ZZ,[1<<300]*3+[1<<633]+[1]*3)
M3L=M.LLL()
for i in range(M3L.nrows()):
    for j in range(M3L.ncols()):
        print(abs(M3L[i][j]).nbits(),end=' ')
    print()
"""
633 633 633 634 633 633 633 
657 661 657 658 657 660 658 
660 659 658 659 661 658 659 
658 658 662 658 658 657 660 
656 661 659 661 660 660 662 
659 660 660 662 661 662 661 
662 659 658 659 662 658 659 
"""

第一行很明显是答案（呃，因为 $2^{633}$ 比特数为 $634$），当然我们可以验证一下。

1
2
3
4
5
6
7
8
9
vans=list(M3L[0])
assert abs(vans[3])==(1<<633)
xguess=vans[:3]
yguess=vans[4:]
for i in range(3):
    xguess[i]=abs(xguess[i])>>300
    yguess[i]=abs(yguess[i])
print(xguess==x,yguess==y)
#True True

3. [网鼎杯2024半决赛] RSA加密分析

之所以写这篇博客，是因为当时wdb半决赛的时候，自己没考虑平衡常数，结果构造的矩阵左上角为 $1$，怎么解也解不出东西来。。。

还好，这个题只有 $1$ 解，本质还是一个套娃题。但CTF只有4h，最后做起来还挺繁琐的。

3x01 题目大意

先看看题

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
# sagemath
import random
from Crypto.Util.number import *

flag = b''

k = 3
d = k/(2*(k+1))
ns = []
pqs = []
es = []

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    if p < q:
        tmp = p
        p = q
        q = tmp
    n = p*q
    ns.append(n)
    pqs.append((p,q))

n = min(ns)
x = random.randint(0,int(n^(d/2)))
x = next_prime(x)

for i in range(3):
    p,q = pqs[i][0],pqs[i][1]
    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
    z = random.randint(bound1,bound2)
    f = (p-1)*(q-1)
    e = inverse(x^2,f) * z % f
    es.append(e)

e = 8462913
c = pow(bytes_to_long(flag),e,ns[0])

print(f'ns={ns}')
print(f'es={es}')
print(f'c={c}')

'''
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
'''

根据题目数据的规模，大致可以得到： $x$ 是 $192$ 位，因此 $x^2$ 是 $384$ 位。bound1 是 $192+256=448$ 位， bound2 是$384+512=640$ 位，因此 bound1 相对于 bound2 可以忽略不计。那么，随机数 $z$ 就是 $896$ 位。因此第一步就是求 $x$。

3x02 求解 $x$

题目给出的关系式为：
$$
e_i\equiv \frac{z_i}{x^2} \pmod {f_i}
$$
其中，$f_i=(p_i-1)(q_i-1)$。

因此，对上面式子，去同余化简，得
$$
e_ix^2-z_i-kf_i=0
$$
由于 $f_i$ 与 $n_i$ 之间的关系为 $f_i=n_i-(p_i+q_i)+1$，设 $y_i=p_i+q_i$，那么 $y_i$ 的比特数为 $513$。上面的式子可以化成
$$
e_ix^2-z_i-kn_i+ky_i-1=0
$$
由于 $e_ix^2-z_i=kf_i$ ，$e_i,x^2$ 分别为 $1024$ 和 $384$ 位，因此 $e_ix^2$ 的值（不取模）是 $1408$ 位，$z_i$ 是 $635$ 位，相对于 $1408$ 位可以忽略不计。因此，$kf_i$ 也应当是 $1408$ 位，由于 $f$ 是 $1408$ 位，因此 $k$ 和 $x^2$ 同阶，也是 $384$ 位。且 $k$ 在知道 $x$ 后是可求的，其值为：
$$
k_i=\frac{e_ix^2-z_i}{f_i}=1+ \left \lfloor\frac{e_ix^2}{n_i} \right\rfloor
$$
同时，我们知道了 $y_i$ 是 $513$ 位，因此 $ky_i$ 为 $513+384=899$ 位。相对于格中 $1024$ 的量，还是比较小的。所以最终的等式为：
$$
e_ix^2-k(n_i+1)=z_i-k_iy_i
$$
$z_i-ky_i$ 的位数为 $899$ 位，符合预期。所以：

8

然后就GG了，卡了我4h。

正确做法：因为 $x$ 是 $384$ 位，带 $z_i-ky_i$ 的量是 $899$ 位，中间差了 $515$ 位，因此得带个平衡系数 $2^{515}$。

9

然后就出了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#sage
M=[
    [2**515,es[0],es[1],es[2]],
    [0,ns[0],0,0],
    [0,0,ns[1],0],
    [0,0,0,ns[2]]
]
M=Matrix(ZZ,M)
M3L=M.LLL()
x2=(abs(M3L[0][0])>>(515))
assert x2.is_square()
x=x2.nth_root(2)
assert isPrime(x)
print(x)
#1696237025993008832375257492068228509280454088630659960513

3x03 求 $y$ 的值

有了 $x$ 之后，就可以把三个 $k$ 也给求出来，但我们实际上只需要第一组数据就行。

目前我们已知的内容为 $x,k_1,z_1-k_1y_1$，目标是求 $y_1$。

根据前面已知的等式：
$$
e_1x^2-z_1-k_1n_1+k_1y_1-1=0
$$
变形一下，可以有
$$
e_1x^2-k_1(n_1+1)-z_1-k_1y_1=0
$$
这个式子中，只有 $y_1,z_1$ 为未知量，其中 $z_1$ 为 $640$ 位， $y_1$ 为 $513$ 位，差值为 $127$。并且还要考虑 已知项 $e_1x^2-k_1(n_1+1)$，对应向量分类中的常数项 $1$。

因此继续构造：

11

简单瞄一下：对角线元素约为 $127+640=767$ ，这个不是方阵。感觉有点不太够的样子。

在这里，哨兵元素为 $2^{640}$ 和 $0$，因此我们LLL之后，找第三分量为 $2^{640}$，第四分量为 $0$ 的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
k=1+(((es[0])*x)//ns[0])
zky=M3L[0][1]
G=[
    [1<<127,0,0,-k],
    [0,1,0,-1],
    [0,0,1<<640,es[0]*x**2-k*(ns[0]+1)]
]
G=matrix(ZZ,G)
G=G#*diagonal_matrix(ZZ,[1,1,1,2**2000])
G3L=G.LLL()
vans=None
for v in G3L:
    if(v[2]==2**640 and v[3]==0):
        vans=v
        break
print(vans)

结果没找到，然后输出 G3L 的结果看一眼，发现一个向量满足第三分量是 $2^{640}$，另一个向量满足第四分量是 $0$。

看来是界不太够了，那就再来一波大力出奇迹。

12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
k=1+(((es[0])*x*x)//ns[0])
zky=M3L[0][1]
G=[
    [1<<127,20,0,-k],
    [0,1,0,-1],
    [0,0,1<<640,es[0]*(x**2)-k*(ns[0]+1)]
]
G=matrix(ZZ,G)
G=G*diagonal_matrix(ZZ,[1,1,1,2**20000])
#print(G)
G3L=G.LLL()
vans=None
for v in G3L:
    if(v[2]==2**640 and v[3]==0):
        vans=v
        break
print(vans)
y=abs(vans[0])>>127
z=vans[1]
print(y.nbits(),z.nbits())
#(-2601742433829735205717510958984597054031885650700522469656590841975973352498358057919092577419846355269586088827959437508632269659680389249804349835135992919707882192966293703794747575323590656, -191810479825992932776976119516271570787555880246177445289447710773949638278444955289971892948555085597643726446747043, 4562440617622195218641171605700291324893228507248559930579192517899275167208677386505912811317371399778642309573594407310688704721375437998252661319722214188251994674360264950082874192246603776, 0)
#513 387

$y$ 对应的值是 $513$ 位，貌似是正确的，但 $z$ 不对。但我们并不需要那个 $z$。但输出 $y$ 看一下，发现 $y$ 是个奇数。。。

1
2
print(y)
#15291667666307414493036951046107275741397940767822287922559621898054774057554431022160493431539991508171319851807097492122079767748903000613100351624105777

说明 $y$ 可能是 $p_1+q_1$ 的高位。由于后面只涉及第一组数据了，因此，下标 $1,2,3$ 将再下一小节被省略。

3x04 求 $p$ 值

用题目代码生成其他几组数据测一下，$y$ 确实为 $p+q$ 高位，最低 $254$ 位有偏差，也就是我们知道了 $p+q$ 位数的一半。那么构建方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n=58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167
y=15291667666307414493036951046107275741397940767822287922559621898054774057554431022160493431539991508171319851807097492122079767748903000613100351624105777
R.<x> = PolynomialRing(RealField(2048))
f = x * ((y) - x) - n
res = f.roots()
def longdouble2int(x):
    x=str(x)
    x=x.split('.')
    x[1]=x[1].split('e')
    return Integer(x[0]+x[1][0][:int(x[1][1])])
for i in res:
    print(longdouble2int(i[0]))
#7595466686419558151205913432118661460574378336265188601308332178368424478703277500529523587366925897212947299535668041397861697290034233117986300118079322
#7696200979887856341831037613988614280823562431557099321251289719686349578851153521630969844173065610958372552271429450724218070458868767495114051506026454

得到了 $p$ 的高位和 $q$ 的高位，这个值大概有一半是精确的。尝试爆破 $12$ 位，应该能出解，大概耗时为一小时左右（刚好前几天搞了个58一年的2h2g的服务器）。

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
ph=7696200979887856341831037613988614280823562431557099321251289719686349578851153521630969844173065610958372552271429450724218070458868767495114051506026454
n=58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167
from multiprocessing import *
from tqdm import *
def solve(p4):
    pbits = 512
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2**kbits, beta=0.42,epsilon=0.012)
    if roots:        
        p = p4 + int(roots[0])
        q = n//p
        with open('result','w') as f:
            f.write(f'p: {p}\n')
            f.write(f'q: {q}\n')
        return True
    return False
ph=ph>>256
def solve1():
    for i in tqdm(range(2**11)):
        if(solve((ph<<12)|i)):
            return
def solve2():
    for i in tqdm(range(2**11,2**12)):
        if(solve((ph<<12)|i)):
            return
from multiprocessing import Process, current_process
PROC=[]
PROC.append(Process(target=solve1))
PROC.append(Process(target=solve2))
for i in range(2):
    PROC[i].start()
for i in range(2):
    PROC[i].join()

然后跑了20分钟后，发现服务器负载突然降到了50%，看来是一个进程出了结果，打开result.txt查看结果：

1
2
p: 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q: 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023

3x05 求最终flag

发现 $e=8462913$，不是默认的 $65537$ 或 getPrime 得到的数字，看来大事不妙，果然，有 $e=3 \times 2820971$。然后发现：$p-1,q-1$ 都是 $3$ 的倍数，还得把 AMM算法调出来。

得到：

1
2
cbrtcp={5457734212209914607812625325490750749661326921613441346478932389873269831927640313433909213645212354490723810811111424420872595194416663018676652425769843, 2078396872589066084890946019870420517722364119774927920595224513472857788525543374144267568390931958280362619350258000147602830214465571608914879090611743, 160069895088875649127466268627443013439871390168730054177132816340221958397973907734914351297231942466861162448734436372267775149700993955551576608933943}
cbrtcq={2673359237708120727862398760587900169638391052868557052175750873601678618266229531730282702839716628363656139382035102683850049531165943543150164597396242, 4480948863344673380560358841432740594822756100315860318495558241131293070924509985646332250166426369654468055542550092440114644741178753450051611037785301, 441158585366764042783155830098020696113231183080771230637023063635452789512533962790534500306763480779397135319061362824997213764244461898482925626873480}

结果发现，$p-1$ 竟然也是 $2820971$ 的倍数

因为512比特对应64字节，因此可以尝试盲猜flag没有64字节。。。然后就出了 。。。

1
2
3
4
5
6
7
from Crypto.Util.number import *
phi=(p-1)*(q-1)
n=p*q
e=2820971
for i in cbrtcq:
    print(long_to_bytes(pow(i,inverse(e,q-1),q)))
#flag{N3w_Attacks_4_key_equat1ons}

那如果flag超过了64字节呢？

用AMM算法，对 $p$ 再开根 $2820971$ 次根，得到一个特解 $x^*$。然后再求 $x^{2820971}\equiv 1\pmod p$ 的 $2820971$ 次根，能得到 $2820971$ 个满足条件的数据（这个很简单，用群论的知识就可以解决）。然后再CRT。耗时约为 $3^2\times2820971$，也就是 $2538$ 万次CRT。。。

4. 关于small_roots 的调参

自己测试了一下，实验环境为 Sagemath 10.4。

f.small_roots 有三个参数： X,beta,epsilon，分别代表结果的上界、模数因子的下界和求解步长。其中， $X$ 越大、 $\beta$ 越大、$\epsilon$ 越小，得到结果的概率越高，但耗时也越长。。。

在2h2g的云服务器上跑的。得到的结果如下：

4x01 beta=0.4的实验结果

unknownbit 240 241 242 243 244 245 246 247 248 249 250
$\beta$ 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
$1000\epsilon$ 22 20 18 17 16 14 12 11 10 8 7
timecost(s) 0.09 0.15 0.19 0.23 0.34 0.53 1.08 1.53 2.81 9.6 13.6

4x02 beta=0.495 的实验结果

unknownbit 248 249 250 251 252 253
$\beta$ 0.495 0.495 0.495 0.495 0.495 0.495
$1000\epsilon$ 13 12 10 $9\sim8$ $7.5\sim6$ $5.5\sim5$
timecost(s) 3.71 6.42 16.9 $32\sim60$ $76\sim308$ $544\sim1400$

4x03 beta=0.498+ 的实验结果

unknownbit 252 253 254 255
$\beta$ 0.498 0.498 0.499 0.499
$1000\epsilon$ $7.5\sim6.5$ $5.5\sim4.5$ $3.5\sim3$ 不可做
timecost(s) $92\sim238$ $600\sim2200$ $26877\sim63702$ 不可做

254在服务器上跑了一天，只跑出来了两组数据，一组 $3.5$ 的 $26877$ 秒，一个 $3$ 的 $63702$ 秒。直接把我服务器CPU红温了一整天。

前三个的测试代码（只修改for ub，for betak 和for epsk 中的内容）：

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
from Crypto.Util.number import *
def Sample(ubits):
    p=getPrime(512)
    q=getPrime(512)
    n=p*q
    return n,p>>ubits
from datetime import *
def solve(p4,n):
    pbits = 512
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    for betak in [0.499]:
        for epsk in[0.0045,0.004,0.0035,0.003,0.0025,0.002,0.0015]:
            print(epsk)
            stime=datetime.now()
            roots = f.small_roots(X=2**kbits, beta=betak,epsilon=epsk)
            if roots:        
                p = p4 + int(roots[0])
                q = n//p
                assert p!=n and q!=n and p!=1 and q!=1
                ttime=datetime.now()
                with open('result0499-254255','a') as f:
                    f.write(f'{kbits},'+'{:.4f}'.format(betak)+','+'{:.4f}'.format(epsk)+','+str((ttime-stime).total_seconds())+'\n')
                return True
    return False

for ub in [254,255]:
    print(datetime.now())
    for _ in range(5):
        n,ph=Sample(ub)
        n,ph=Integer(n),Integer(ph)
        print(datetime.now())
        print(solve(ph,n))

4x04 flatter

根据striving ✌的提示，可以安装flatter后求解似乎更快。

unknownbit 253 254 255
$\beta$ 0.499 0.499 0.499
$1000\epsilon$ 5 $3.5\sim3$ （不保证） 不可做
timecost(s) $75\sim120$ $400\sim820$ 不可做 
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
65
66
67
68
69
from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

def matrix_overview(BB):  # see the shape of matrix
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def Small_Roots_Univariate(f, X=None, beta=1.0, epsilon=None):  # 多项式f,X,beta,epsilon

    delta = f.degree()  # 度delta
    N = f.parent().characteristic()  # 模数N
    PR = PolynomialRing(ZZ, 'x')
    x = PR.gen()

    Zm = f.base_ring()  # Zmod(N)
    f = f.change_ring(ZZ)  # ZZ下f(x)
    if not f.is_monic():  # 首一
        f = f.monic()  # f = f * f[delta].inverse_mod(N)

    m = ceil(max(beta * beta / (delta * epsilon), 7 * beta / delta))  # m
    t = floor(delta * m * (1 / beta - 1))  # t
    print('m={}, t={}'.format(m, t))

    f_ij = []
    for i in range(m):
        for j in range(delta):
            f_ij.append(x ** j * N ** (m - i) * f ** i)  # shift g_ij(x)
    for i in range(t):
        f_ij.append(x ** i * f ** m)  # shift h_i(x)

    monomials = []
    for g in f_ij:
        monomials += g.monomials()  # 统计所有出现的单项 x^i
    monomials = sorted(set(monomials))  # 去重并排序

    M = Matrix(ZZ, len(f_ij), len(monomials))  # 行数为多项式个数，列数为所有单项可能个数
    for i in range(M.nrows()):
        for j, monomial in enumerate(monomials):
            M[i, j] = f_ij[i].monomial_coefficient(monomial) * monomial.subs(x=X)  # g_ij(xX)和h_i(xX)
    matrix_overview(M)  # see
    assert M.nrows() == M.ncols()  # 方阵 nrows()=ncols()
    B = flatter(M)  # flater加速
    print('end LLL')
    for j in range(M.nrows()):  # 得到f(xX)，构建f(x)，求根检验
        Cx = sum(ZZ(B[j, i] // monomials[i](X)) * monomials[i] for i in range(M.ncols()))  # construct polynomial,
        R = Cx.roots()  # get roots
        roots = [Zm(r[0]) for r in R if abs(r[0]) <= X]  # check x0<=X
        roots = [r for r in roots if gcd(N, ZZ(f(r))) >= ZZ(floor(N ** beta))]  # check gcd(f(x_0),N)>N^beta
        if roots:
            return roots  # 返回root

N = 135500646574582511239845764710311769260801998982429500680171919823431178899526463566215834234383331374445093363969218810906991784569340270510936759183504496584225937614940086329775325893307453919055830270986601152002191368431527285285313669979358099782497422114870417519470053198217401297960844455029559146309
h = 918578024558168836638919636090777586135497638818209533615420650282292168631485
PR = PolynomialRing(Zmod(N), 'x')
x = PR.gen()
f = (h << 253) + x
roots = Small_Roots_Univariate(f, 2 ** 253, 0.499, 0.005)
print(roots)

总之，$254$ 基本不可做，$255$ 完全不可做，不如用flatter爆破几位，用 $253$ 做效率高

5.[强网杯2024决赛] Signin:减掉MSB平衡法[Update 12.8]

12 月 6 日拿到了强网杯决赛的题目，看到一个Signin感觉有点意思，打算看看。

搞到题之后， 15 分钟出思路，调平衡参数又用了一天。。。

5x01 题目大意

先看看题目（因为本地复现，故略有修改，不改变原题题意，只是为了方便debug）：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
from hashlib import sha256
from Crypto.Util.number import inverse, bytes_to_long
from random import randint
from os import urandom
#from secret import flag
from datetime import *
import signal

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

zero = (0, 0)
G = (gx, gy)


def add(p1, p2):
    if p1 == zero:
        return p2
    if p2 == zero:
        return p1
    (p1x, p1y), (p2x, p2y) = p1, p2
    if p1x == p2x and (p1y != p2y or p1y == 0):
        return zero
    if p1x == p2x:
        tmp = (3 * p1x * p1x + a) * inverse(2 * p1y, p) % p
    else:
        tmp = (p2y - p1y) * inverse(p2x - p1x, p) % p
    x = (tmp * tmp - p1x - p2x) % p
    y = (tmp * (p1x - x) - p1y) % p
    return (int(x), int(y))


def mul(n, p):
    r = zero
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r


def sign(msg, q, d, G):
    z = int(sha256(msg).hexdigest(), 16)
    while True:
        k = randint(1, q - 1)
        P = mul(k, G)
        r = P[0]
        s = inverse(k, q) * (z + r * d) % q
        if r != 0 and s != 0:
            return r, s, k.bit_length()


def verify(sig, msg, q, G, Q):
    r, s = sig
    print(r, s)
    if r == 0 or s == 0:
        return False
    z = int(sha256(msg).hexdigest(), 16)
    u1 = z * inverse(s, q) % q
    u2 = r * inverse(s, q) % q
    P = add(mul(u1, G), mul(u2, Q))
    return P[0] == r


signal.alarm(240)
menu = '''
1.sign
2.verify
3.exit
'''
uur=urandom(27)
secret_key = bytes_to_long( uur+ b"qwbs8")
with open('dbg','w') as f: # only for debug check.
	f.write(uur.hex())
Q = mul(secret_key, G)

count = 678 #1300 #1300 for debug and test, original changces is 678
for i in range(count):
    print(menu)
    op = int(input(">").strip())
    if op == 1:
        msg = input("msg: ").strip().encode()
        if msg == b"qwbs8_send_flag_to_me":
            print("another msg plz.")
        else:
            r, s, kbits = sign(msg, order, secret_key, G)
            print(r, s, kbits)
    elif op == 2:
        msg = input("msg: ").strip().encode()
        ur = int(input("r: ").strip())
        us = int(input("s: ").strip())
        sig = (ur, us)
        if verify(sig, msg, order, G, Q):
            if msg == b"qwbs8_send_flag_to_me":
                flag='flag{success-at-'+str(datetime.now()).replace(' ','-')+'}'
                print(flag)
            else:
                print(True)
        else:
            print("malformed signature.")
    else:
        exit(0)

题目给出了一个ECDSA，其中私钥低 40 位泄露，也没有什么其他可做的东西。因此只能从私钥泄露去思考。并且，题目给出了每次签名随机数 $k$ 的比特数，这应该也属于一个突破口。

5x02 初步思路

15分钟时间，我就有了思路：每次用同一条消息 $m$，对 $m$ 签名 $677$ 次，这样 $z$ 就相同。

很快找到线性关系式：
$$
\frac{z+dr_i}{s_i}\equiv k_i \pmod q
$$
也就是：
$$
\frac{z}{s_i}+\frac{d_Lr_i}{s_i}+\frac{2^{40}r_i}{s_i}d_H-u_iq=k_i
$$
设 $C_i=\dfrac{z}{s_i}+\dfrac{d_Lr_i}{s_i}$，$B_i=\dfrac{2^{40}r_i}{s_i}$那么可以构造线性关系式（仍然以三组数据为例）：

13

然后算一下界：$q$ 是 $256$ 位，$d_H$ 是 $216$ 位，那么确定一下 $k$ 的比特数。

因为要留最后一次机会伪造签名，因此签名次数为 $677$ 次。为了保证 $k$ 比较小，可以选取 $k$ 不超过 $253$ 位的数据做。那么获取 $k$ 不超过 $253$ 位的组数期望为 $84$ 次左右，最后向量的全部分量可以全平衡到 $253$ 位，也就是 $\log_2 |\vec v|=253(n+2)$ ，而$\log_2 \det M=256n$，零前者小于后者，得 $n>73$，貌似可行。

然后先用 1200次机会测一把：

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
from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
#context.log_level='debug'
sh=process(['python3','taskdbg.py'])
q=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
z = int(sha256(b'1').hexdigest(), 16)
D=[]
def cmp(xtuple):
	return xtuple[2]
for i in tqdm(range(1200)):
	sh.recvuntil(b'>')
	sh.sendline(b'1')
	sh.recvuntil(b'msg: ')
	sh.sendline(b'1')
	rline=sh.recvline(keepends=False)
	r,s,lgk=[int(i) for i in rline.split()]
	if(lgk<=253):
		D.append((r,s,lgk))
D=sorted(D,key=cmp)
dl=bytes_to_long(b"qwbs8")
n=len(D)
C,B=[],[]
for i in range(n):
	ri,si,lgk=D[i]
	C.append((z+dl*ri)*inverse(si,q)%q)
	B.append((ri*2**40)*inverse(si,q)%q)
M=block_matrix(ZZ,
	[
		[identity_matrix(2),matrix(ZZ,[B,C])],
		[zero_matrix(n,2),q*identity_matrix(n)],
	])
scale=[216,0]+[(D[i][2]) for i in range(n)]
H=diagonal_matrix([1<<(253-i) for i in scale])
M3L=(M*H).LLL()
count=0
for v in M3L:
    if(abs(v[1])==2**253 and v[0]%2**37==0):
        print('{:054x}'.format(abs(v[0]>>37)))
#00035200d2eb85df354d512e1ed7507fafa5f65421af758c6b69da
#0001e3bb8bf2700f617a094f0a9bbeb9a4846a50e9fa6fe58ae15f
#00052585d2d84afe1946e4c677b624fd13d46406c738b1dd456dbd
#1565175e195b3e11fcab83369564a74051eaddd58da439d1d43b4f
#156c8b3f909c72c31b7bd954c030a0e1c69d8c538ad3c375ff8eba
#143967156dabd7d3acfc42a814a16017166cd69fd9f1e3d61c293d
#1733855122e779bb0825373d45e906062963d8889d9291cea0d1a7
#17259640adc01e43c2b4e11150063b9703fe06734a2762f931a4bb
#16059790aec15b5f13ad8b9bd0616741b9a46b9af96c75fac7f97f
#033c737ebad6cb1e7e0c1f4edfe1f2d76f35b56026475a81df7ee0
#140f3ee633e6aaba4634aaa658010c524923b369035728c95fa649
#12d7a77743dd51f6368865420fb199ca13cb389972e2a6279214d7
#017c96aee9f5b7c4daf633f3e3d384a508545c73fec68f4bf02ce8
#... ... 反正没一个对的
#ans: d2dffadd7e9a6d4e839c17b2c5907a51c130cf352c9eb356c0a0e4

然后测了好几次，也没一个对的。（按道理说不应该啊，瞄了眼所有向量：我期待的是第二分量为 $2^{253}$，然后其他所有分量均为 $253$ 比特）。结果输出一看：每个向量都混杂着 248,249,250 比特的数字，或者一个值为256比特（等于 $q$），然后其余全 $0$。

5x03 新的平衡系数方法？

然后向鸡块师傅问了一下 ，顺便要到了测试程序

糖醋小鸡块 2024/12/7 19:10:55
主要思路是balance掉d高位和k

huangx607087 2024/12/7 19:11:05
所有的k都balance吗？

糖醋小鸡块 2024/12/7 19:14:02
噢，balance我这里说的不是系数配平

糖醋小鸡块 2024/12/7 19:14:08
是你减去msb

糖醋小鸡块 2024/12/7 19:14:20
比如k现在范围是$(0，2^{253})$

糖醋小鸡块 2024/12/7 19:14:32
你可以减去msb变成 $(-2^{252},2^{252})$

糖醋小鸡块 2024/12/7 19:28:41
d也可以balance

糖醋小鸡块 2024/12/7 19:28:43
一个道理

huangx607087 2024/12/7 19:28:58
dH是216位

huangx607087 2024/12/7 19:29:08
乘个$2^{37}$是253位？

huangx607087 2024/12/7 19:29:24
还是减个多少？

糖醋小鸡块 2024/12/7 19:29:33
dh也可以减个$2^{215}$之类的

糖醋小鸡块 2024/12/7 19:29:35
照你这个

糖醋小鸡块 2024/12/7 19:29:58
总之就是把 $(0,a)$ 变成 $(-a/2,a/2)$

啊？还能这么操作的吗？奇怪的知识又增加了！也就是所有的值，全部减去最高位，最后再加回来。

那么前面的式子就变成了（其中 $\beta_i=\mathrm{kbits-1}$）：
$$
\frac{z}{s_i}+\frac{d_Lr_i}{s_i}+\frac{2^{40}r_i}{s_i}(d_H-2^{215}+2^{215})-u_iq=k_i+2^{\beta_i}-2^{\beta_i}
$$
然后重新整理：
$$
\frac{z}{s_i}+\frac{d_Lr_i}{s_i}+\frac{2^{255}r_i}{s_i}-2^{\beta_i}+\frac{2^{40}r_i}{s_i}(d_H-2^{215})-u_iq=k_i-2^{\beta_i}
$$
设 $C_i=\dfrac{z}{s_i}+\dfrac{d_Lr_i}{s_i}+\dfrac{2^{255}r_i}{s_i}-2^{\beta}$，$B_i=\dfrac{2^{40}r_i}{s_i}$那么可以构造线性关系式（仍然以三组数据为例）：

14

然后对上面的矩阵进行平衡就好，平衡到 $253$ 位就可以。

由于最后解出来可能会有符号差，也就是不知道是 $d_H-2^{215}$ 还是 $2^{215}-d_H$，因此可以都试一下。经过测试，一般第一行就是答案

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
from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
#context.log_level='debug'
sh=process(['python3','taskdbg.py'])
q=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
z = int(sha256(b'1').hexdigest(), 16)
D=[]
def cmp(xtuple):
	return xtuple[2]
for i in tqdm(range(1200)):
	sh.recvuntil(b'>')
	sh.sendline(b'1')
	sh.recvuntil(b'msg: ')
	sh.sendline(b'1')
	rline=sh.recvline(keepends=False)
	r,s,lgk=[int(i) for i in rline.split()]
	if(lgk<=253):
		D.append((r,s,lgk))
#D=sorted(D,key=cmp)
dl=bytes_to_long(b"qwbs8")
n=len(D)
C,B=[],[]
for i in range(n):
	ri,si,lgk=D[i]
	C.append((-2**(D[i][2]-1) +(z+ri*dl+ri*2**255)*inverse(si,q))%q)
	B.append((ri*2**40)*inverse(si,q)%q)
M=block_matrix(ZZ,
	[
		[identity_matrix(2),matrix(ZZ,[B,C])],
		[zero_matrix(n,2),q*identity_matrix(n)],
	])
# scale=[2**215,1]+[2**(D[i][2]-1) for i in range(n)]
H=diagonal_matrix([1<<38,1<<253]+[1<<(253-D[i][2]) for i in range(n)])
M3L=(M*H).LLL()
count=0
for v in M3L:
    if(abs(v[1])==2**253 and v[0]%2**(38)==0):
        print('{:054x}'.format(2**215+(v[0]>>38)),'{:054x}'.format(2**215-(v[0]>>38)))
#76999ca36b634ef46930567a8115ac40f3cb3c9f89e6432fd9dcc8 8966635c949cb10b96cfa9857eea53bf0c34c3607619bcd0262338
#...
#ans:8966635c949cb10b96cfa9857eea53bf0c34c3607619bcd0262338

5x04 exp(1200次机会):

既然能求出 $d$ ，那最后的签名就好伪造了，随机数 $k$ 可以选 $1$。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
#context.log_level='debug'
sh=process(['python3','taskdbg.py'])
q=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
z = int(sha256(b'1').hexdigest(), 16)
D=[]
def cmp(xtuple):
	return xtuple[2]
for i in tqdm(range(1200)):
	sh.recvuntil(b'>')
	sh.sendline(b'1')
	sh.recvuntil(b'msg: ')
	sh.sendline(b'1')
	rline=sh.recvline(keepends=False)
	r,s,lgk=[int(i) for i in rline.split()]
	if(lgk<=253):
		D.append((r,s,lgk))
#D=sorted(D,key=cmp)
dl=bytes_to_long(b"qwbs8")
n=len(D)
C,B=[],[]
for i in range(n):
	ri,si,lgk=D[i]
	C.append((-2**(D[i][2]-1) +(z+ri*dl+ri*2**255)*inverse(si,q))%q)
	B.append((ri*2**40)*inverse(si,q)%q)
M=block_matrix(ZZ,
	[
		[identity_matrix(2),matrix(ZZ,[B,C])],
		[zero_matrix(n,2),q*identity_matrix(n)],
	])
# scale=[2**215,1]+[2**(D[i][2]-1) for i in range(n)]
H=diagonal_matrix([1<<38,1<<253]+[1<<(253-D[i][2]) for i in range(n)])
M3L=(M*H).LLL()
count=0
dh1,dh2,k0p,k0n=None,None,None,None
for v in M3L:
    if(abs(v[1])==2**253 and v[0]%2**(38)==0):
        vlow=v[0]>>38
        dh1,dh2=2**215+vlow,2**215-vlow
        k0p=2**(D[0][2]-1)+(v[2]>>(253-D[0][2]))
        k0n=2**(D[0][2]-1)-(v[2]>>(253-D[0][2]))
        break
print(hex(dh1),hex(dh2))
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
E=EllipticCurve(GF(p),[0,7])
gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G=E(gx,gy)
d=None
for k in [k0p,k0n]:
    for dh in [dh1,dh2]:
        testd=(dh<<40)|dl
        P=k*G
        r0=P[0]

        s0=(z+int(r0)*testd)*inverse(int(k),int(q))%q
        if(s0==D[0][1]):
            print((k),(dh))
            d=testd
            break
    if(d):
        break
FLAGMSG=b"qwbs8_send_flag_to_me"
print(d)
if(d):
	zf=int(sha256(FLAGMSG).hexdigest(), 16)
	ansK=1
	P=G
	ansR=P[0]
	ansS=(zf+int(ansR)*d)%q
	sh.recvuntil(b'>')
	sh.sendline(b'2')
	sh.recvuntil(b'msg: ')
	sh.sendline(FLAGMSG)
	sh.recvuntil(b'r: ')
	sh.sendline(str(ansR).encode())
	sh.recvuntil(b's: ')
	sh.sendline(str(ansS).encode())
	sh.interactive()

运行结果：

15

那如果把次数调回 677 呢？貌似概率还能接受，40几次能出一次，不过还真的得看运气，因为有的时候 79 组就能出，有的 95 组也出不了。

16

9. 总结

回顾了一下自己以前的构造LLL存在的问题，因为之前确实没考虑过LLL求解向量的原理，加上自己这次网鼎杯被卡住了，写篇博客，回顾一下自己没注意到的一些部分，比如平衡参数的构造。

不过网鼎杯那个题确实挺难的，套了这么多层:(

12月12日的复现，结果还知道了可以把msb减掉去平衡参数，新的知识又增加了。。。。

期待着，自己在线下赛做出来的第 1 题。

CTFSeason4
#Notes
LatticeNotes8
http://example.com/2024/12/05/LatticeNotes8/
作者
huangx607087
发布于
2024年12月5日
许可协议