糖醋小鸡块的blog
0%

2025-9-wp-crypto

发表于 分类于 Valine：

神奇的题目ヾ(´∀ ˋ)ﾉ

CrewCTF

Inverse With Errors

题目

题目描述：

1
This chall is equal to mystiz's chall, or is it?

题目：

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
import secrets
import hashlib

from Crypto.Cipher import AES
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad


flag = b'crew{*** REDACTED ***}'

N_size = 1024

N = secrets.randbits(N_size) | (1 << N_size)
d = N

while d >= N:
    d = getPrime(N_size)

values = []
R = []

for _ in range(30):
    r = secrets.randbits(100)
    R.append(r)
    values.append(pow(d, -1, N + r))

key = hashlib.sha256(str(d).encode()).digest()
flag = pad(flag, 16)

cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv.hex()
enc = cipher.encrypt(flag).hex()

print(f'{R = }')
print(f'{values = }')
print(f'{iv = }')
print(f'{enc = }')

题目有30组如下形式的等式：

其中$N, d$均为1024bit，$r_i$为100bit的小量，给出$e_i,r_i$，要求解$d$。

思路

概览

在赛中的时候我对这个题没有一点有效思路，但很好奇他的解法，就在赛后在discord上看了出题人@KLPP的解释，第一眼也没太看懂，仔细琢磨了很久他的exp，最终才明白这个题有多巧妙。

首先由于我们并没有$N$，因此写不出来一个模大数下的方程组，所以只能把上面的式子都展开到$\mathbb{Z}$下，也就是：

这个时候整个系统变成了一个32个变量、30个方程的方程组，直接求解这个方程组有几个问题：

  • 变量数大于方程数，显然是欠定的
  • 有二次项$k_iN$，整个方程并不线性，求解难度比较高

能利用的地方在于：

  • 方程结构很统一，并且并不复杂
  • 所有未知量都有界，都在$2^{1024}$这个量级
变量代换(部分$k_i \rightarrow t_i$)

解法的思路是很难直接想到的，所以我就直接阐述解法的步骤了。首先我们可以固定几个等式（出题人的exp中固定了4个），然后对剩下的第5到第30个等式，分别找到一组小系数$v_{i1},v_{i2},v_{i3},v_{i4}$，使其满足：

把这些小系数分别乘到对应等式上并求和，就可以消去d，得到新的等式：

这个等式也可以写为：

一共会有30-4=26组这样的等式。

而对于这样的等式，我们需要注意一下各项的数量级关系。笼统的说，由于$v_{ij}$是小系数且$r_i$也在100bit内，所以整个式子是$k_i$和$N$两个1024bit数量级的在占主导作用，因此上述等式的这两项的数量级差不多：

这告诉了我们重要的一个事实：$\sum_{j=1}^{4}v_{ij}k_j + k_i$的值是比较小的，实际测试一下大约是440bit左右，我们不妨把这个量记做$t_i$，也就是$t_i = \sum_{j=1}^{4}v_{ij}k_j + k_i$，此时$k_i$就可以表示成$k_i = t_i - \sum_{j=1}^{4}v_{ij}k_j$。

那么把这种表示代回刚才的式子，我们的方程组发生了一点变化：

  • 前四个式子不变，依然是$e_id = 1 + k_i(N+r_i) \quad i \in \{1,2,3,4\}$
  • 第5-30个式子代入$t_i$的表示后，变成了$e_id = 1 + (t_i - \sum_{j=1}^{4}v_{ij}k_j)(N+r_i) \quad i \in \{5,6,\cdots,30\}$

做这样的等式变换的好处和坏处都很明显：

  • 好处在于有26个变量从1024bit变成了440bit的小量
  • 坏处在于有26个式子的结构变复杂了，多了几个二次项

所以这有一种tradeoff的思想在里面。

coppersmith

而神奇的地方才刚刚开始，出题人接下来的想法是对上述式子做copper，这很容易让人感到疑惑：

  • copper的作用一般来说可以表述成这样：给定一组模意义下有小根的方程，通过格的手段约简多项式的系数，从而使整个方程组从模数下脱离出来，变成$\mathbb{Z}$下的方程，此时可以对方程求根得到这些小根

那这题目的方程组怎么会用到copper？这些方程本身就是$\mathbb{Z}$下的，无法求根的原因在于方程数不够且方程为二次方程。

精妙的地方就在这里，我们先忽略copper的目的，直接去应用他，也就是把30个等式按照单项依次写成行向量从而得到一个矩阵，这个矩阵是30x62的：

  • 行数是30很好理解，30个方程分别对应一个行向量

  • 列数是62是因为这30个方程一共有62个不同的单项，分别是：

由copper我们可以知道，既然这格的行向量都是以$d,k_i,t_i,N$这些为根的多项式，因此对他做约简之后，得到的每一行行向量其实都对应一个同样以$d,k_i,t_i,N$这些为根、且系数更小的多项式。

因为就相当于是把一些根相同的多项式做了一个系数的线性组合

此时重要的一步来了，我们从copper的视角跳脱出来，单纯审视这个格以及他的规约过程，我们可以做到这样一件事情：给含$d$以及$k_i$的列配上一个大系数再去规约，那么我们能得到一些较短的行向量，他们对应的多项式会是仅含如下单项的多项式：

而我们知道格的规约有一个特性：规约后的向量各分量是趋于平衡的，那么对于这个格来说，他规约出来的东西是新的多项式的系数，而观察原来含这些单项的多项式里（也就是$e_id = 1 + k_i(N+r_i) \quad i \in \{1,2,3,4\}$和$e_id = 1 + (t_i - \sum_{j=1}^{4}v_{ij}k_j)(N+r_i) \quad i \in \{5,6,\cdots,30\}$）这些量的系数会发现分别是：

  • $1$的系数就是$1$
  • $t_i$的系数是$r_i$
  • $t_iN$的系数是$1$

因此规约出来的系数数量级差的也不过是$r_i$的数量级，也就是100bit，形象一点理解的话，我们记格规约出来的这些单项系数为：

那么这条行向量对应多项式就是:

且$a, x_i, y_i$数量级差距不大。

意义

理解到上面这一步后，问题马上就来了：这样做的意义在哪里？

这个意义非常精妙，虽然系数向量$(a, x_5,\cdots, x_{30}, y_5,\cdots, y_{30})$的各分量数量级差距不大（并且由于是规约出来的，这些都比较小），但是我们可以注意到单项$(1, t_5,\cdots, t_{30}, t_1N,\cdots,t_{30}N)$之间的数量级差异是巨大的，由于$t_i$仅有440bit左右而$N$有1024bit，因此两部分可以分离出来，也就是我们能分别得到：

而第二条其实也就是：

这非常的有用——这些等式是崭新的等式，并且是线性的，所以把这些等式和前面30个等式一起做groebner就可以得到包括$N,d$在内的所有未知量了。

exp

1
2
3
4
R = []
values = []
iv = 
enc = 
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
m = 30
n = 4
e = values

PR = PolynomialRing(ZZ, 'x', m+2)
k, t, N, d = list(PR.gens()[:n]), list(PR.gens()[n:m]), PR.gens()[-2], PR.gens()[-1]

sub_poly = []
for i in range(n, m):
    L = block_matrix(ZZ, [
        [1, (Matrix(ZZ, [e[:n] + [-e[i]]])).T]
    ])
    L[n, n] = 2^500
    L[:, -1:] *= 2^500
    L = L.LLL()
    vec = L[-1][:-2].list() + [1]
    #print(len(bin(vector(ZZ, vec) * vector(ZZ, K[:n] + [-K[i]]))))
    sub_poly.append(vector(PR, vec)*vector(PR, k+[-t[i-n]]))

poly = []
monomials=set()
bounds = [2^2000 for _ in range(n)] + [1 for _ in range(m-n)] + [1] + [2^2000]
for i in range(n, m):
    f = e[i]*d - 1 - sub_poly[i-n]*(N+R[i])
    poly.append(f)
    for mono in f.monomials():
        monomials.add(mono)

L = Matrix(ZZ,len(poly),len(monomials))
monomials = sorted(monomials)
for row,shift in enumerate(poly):
    for col,monomial in enumerate(monomials):
        L[row,col] = shift.monomial_coefficient(monomial)*monomial(*(bounds))
L = L.LLL()
vec = L
F = []
for _ in vec:
    f = 0
    for idx,monomial in enumerate(monomials):
        f += (_[idx] // monomial(*(bounds))) * monomial
    f = f.change_ring(QQ)
    F.append(f)
1
2
3
4
5
6
7
8
Final_poly = []
for _ in F[:15]:
    temp = 0
    for i in _:
        if(i[1].degree() == 2):
            assert i[1] % N == 0
            temp += i[0]*PR(i[1] / N)
    Final_poly.append(temp)
1
2
3
4
5
6
7
8
for i in range(n):
    Final_poly.append(e[i]*d - 1 - k[i]*(N+R[i]))
for i in range(n, m):
    Final_poly.append(e[i]*d - 1 - sub_poly[i-n]*(N+R[i]))
    
gb = Ideal(Final_poly).groebner_basis()
d = gb[-1]
print(d)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
d = 105161125166605172985549230601848031277103055304769022514486694213250702858759115384924357531761239330626948615552847720925761215583349311437556873968774464033940956188047781659237669672632756699201613300897438047922454957029036703887892843872083276722895063014080938151603150387874025791522311723981427501717

import hashlib
from Crypto.Cipher import AES

iv = bytes.fromhex(iv)
key = hashlib.sha256(str(d).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv = iv)
flag = cipher.decrypt(bytes.fromhex(enc))

print(flag)


#crew{Invert1ng_W17h_3rr0rs_0a431f38e2f2c57771e5db059e77179a}