格(Lattice )
前置知识
线性代数 ：向量、矩阵、线性方程、线性空间、线性相关、基
什么是格
格与格基
令\(\mathbf{b_0},\mathbf{b_1}, \cdots
,\mathbf{b_{n-1}}\) 为空间\(\mathbb{R}^m\) 上一组线性无关的向量(\(m \ge n\) )，则集合 \[
\mathcal{L}(\mathbf{b_0},\mathbf{b_1}, \cdots ,\mathbf{b_{n-1}}) :=
\{\sum_{i = 0}^{n-1}x_i\mathbf{b_i}:x \in \mathbb{Z}\}
\] 被称作一个格
其中矩阵\(\mathbf{B} :=
[\mathbf{b_0},\mathbf{b_1}, \cdots
,\mathbf{b_{n-1}}]\) 称为该格的格基 ，所以格又可以表示为：
\[
\mathcal{L}(\mathbf{B}) := \{\mathbf{Bx} : \mathbf{x} \in \mathbb{Z}^n\}
\]
基本域
设\(B = [\mathbf{b_0},\mathbf{b_1}, \cdots
,\mathbf{b_{n-1}}]\) 为一组格基，则该组格基的基本域为： \[
\mathcal{F}(\mathbf{b_0},\mathbf{b_1}, \cdots ,\mathbf{b_{n-1}}) :=
\{\sum_{i=0}^{n-1}t_i\mathbf{b_i}:0 \le t_i < 1\}
\]
高斯启发式（The Gaussian
Heuristic）
\(L\) 是\(n\) 维格，高斯所期望的最短长度为 \[
\sigma(L) = \sqrt{\frac{n}{2 \pi e}} (\det{L})^{\frac{1}{n}}
\]
高斯启发式表示，在一个“随机选择的 格”中的最短非零向量满足
\[
||v_{shortest}|| \approx \sigma(L)
\] 更精确地，如果确定了\(\epsilon >
0\) ，则当\(n\) 足够大时这个随机的 \(n\) 维格将满足 \[
(1 - \epsilon )\sigma(L) \le || v_{shortest} || \le (1 + \epsilon )
\sigma(L)
\] P.S：看不懂一点，直接从An Introduction to
Mathematical Cryptography 抄来的（逃
最短向量问题(SVP,The
Short Vector Problem)
在格\(\mathcal{L}\) 中找到最短的非零向量
对于高维格很难解决，但是可以利用\(LLL\) 算法在多项式时间内求解近似最短近似非零向量，如在SageMath中：
1 2 3 4 5 B = matrix(ZZ,[[3 ,9 ],[1 ,1 ]]) L = B.LLL() L = B.BKZ(block_size=2 ) shortestV = L[0 ]
一般用BKZ效果会比LLL好，其中的block_size设置越大效果越好，但算得越慢，最大是格的维度
格攻击简单实例
例1：ez_NTRU
例题代码
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 from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytesimport randomimport mathFLAG = b'crypto{?????????????????????}' def gen_key (): q = getPrime(512 ) upper_bound = int (math.sqrt(q // 2 )) lower_bound = int (math.sqrt(q // 4 )) f = random.randint(2 , upper_bound) while True : g = random.randint(lower_bound, upper_bound) if math.gcd(f, g) == 1 : break h = (inverse(f, q)*g) % q return (q, h), (f, g) def encrypt (q, h, m ): assert m < int (math.sqrt(q // 2 )) r = random.randint(2 , int (math.sqrt(q // 2 ))) e = (r*h + m) % q return e def decrypt (q, h, f, g, e ): a = (f*e) % q m = (a*inverse(f, g)) % g return m public, private = gen_key() q, h = public f, g = private m = bytes_to_long(FLAG) e = encrypt(q, h, m) print (f'Public key: {(q,h)} ' )print (f'Encrypted Flag: {e} ' )''' Public key: (7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800) Encrypted Flag: 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523 '''
加解密原理：
密钥选取： \[
p \space \text{is a prime} \\
\text{random: }2 < f < \sqrt{\frac{q}{2}}\space \\
\text{random: }\sqrt{\frac{q}{4}} < g < \sqrt{\frac{q}{2}}\\
\gcd(f,g) = 1\\
h = f_q^{-1}g \mod{q}\\
\text{public key: }(q,h)\\
\text{private key: }(f,g)\\
\] 加密： \[
\text{plaintext: }m < \sqrt{\frac{q}{2}}\\
\text{random: }2 < r < \sqrt{\frac{q}{2}}\\
e = (rh + m) \mod{q} \\
\text{ciphertext: } e
\] 解密： \[
a = fe \mod{q}\\
m = af_g^{-1} \mod{g}
\] 解密原理： \[
\begin{align}
a
&= fe \mod{q}\\
&= frh + fm \mod{q}\\
&= frf_q^{-1}g + fm \mod{q}\\
&= rg + fm \mod q\\
&= rg +fm \\
\\
m
&= af_g^{-1} \mod{g}\\
&= (rg + fm)f_g^{-1} \mod{g}\\
&= m
\end{align}
\] 解题：
关键需要知道私钥\((f,g)\)
找关系 \[
h = f_q^{-1}g \mod{q}\\
fh \equiv g \pmod{q}\\
fh = g + kq\\
fh - kq = g
\] 两个未知量，一个已知方程，再构造一个方程 \[
f - 0k = f
\] 即 \[
h \cdot f - q \cdot k = g \\
1 \cdot f - 0 \cdot k = f\\
\] 目的是将线性方程分离为已知的矩阵和未知的向量 \[
\begin{pmatrix}
f & -k
\end{pmatrix}
\begin{pmatrix}
h & 1\\
q & 0
\end{pmatrix}
=
\begin{pmatrix}
g & f
\end{pmatrix}
\]
\[
\mathbf{v} \mathbf{B} = \mathbf{w}
\]
所求\(\mathbf{w}\) ，已知\(\mathbf{B}\) ，在满足The
Gaussian
Heuristic (目前还没学明白)
对\(\mathrm{B}\) 进行LLL格基规约，得到的最短向量即为\(\mathbf{w}\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 q = 7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257 h = 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800 B = matrix(ZZ, [ [h,1 ], [q,0 ] ]) L = B.LLL() g,f = L[0 ] g,f = abs (g), abs (f) R = GF(q) assert R(h) == R(f) ^ (-1 ) * R(g)print ("f =" , f)print ("g =" , g)m = decrypt(q,h,f,g,e) print (long_to_bytes(m))
例2：超递增序列背包加密
例题代码
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 import randomfrom collections import namedtupleimport gmpy2from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytesFLAG = b'crypto{??????????????????????????}' PrivateKey = namedtuple("PrivateKey" , ['b' , 'r' , 'q' ]) def gen_private_key (size ): s = 10000 b = [] for _ in range (size): ai = random.randint(s + 1 , 2 * s) assert ai > sum (b) b.append(ai) s += ai while True : q = random.randint(2 * s, 32 * s) if isPrime(q): break r = random.randint(s, q) assert q > sum (b) assert gmpy2.gcd(q,r) == 1 return PrivateKey(b, r, q) def gen_public_key (private_key: PrivateKey ): a = [] for x in private_key.b: a.append((private_key.r * x) % private_key.q) return a def encrypt (msg, public_key ): assert len (msg) * 8 <= len (public_key) ct = 0 msg = bytes_to_long(msg) for bi in public_key: ct += (msg & 1 ) * bi msg >>= 1 return ct def decrypt (ct, private_key: PrivateKey ): ct = inverse(private_key.r, private_key.q) * ct % private_key.q msg = 0 for i in range (len (private_key.b) - 1 , -1 , -1 ): if ct >= private_key.b[i]: msg |= 1 << i ct -= private_key.b[i] return long_to_bytes(msg) private_key = gen_private_key(len (FLAG) * 8 ) public_key = gen_public_key(private_key) encrypted = encrypt(FLAG, public_key) decrypted = decrypt(encrypted, private_key) assert decrypted == FLAGprint (f'Public key: {public_key} ' )print (f'Encrypted Flag: {encrypted} ' )
加解密原理 ：
密钥选取：
构造超递增序列，记为向量\(\mathbf{b}\) ，
选取足够大的\(q,r\) 满足\(q>r > \sum{b_i}\) ，且\(\gcd(r,q) = 1\)
生成公钥$ = r ( a_i = r b_i ) $
生成私钥\(w = r^{-1}
\pmod{q}\) 并保存超递增序列\(\mathbf{b}\)
加密：
将明文信息\(m\) 转为二进制序列\(x_0,x_1,x_2,\cdots \in \{0,1\}\) ，记为\(\mathbf{x} \in \{0,1\}^n\)
计算密文\(c = \mathbf{x} \cdot
\mathbf{a}\)
解密：
计算\(S = wc\)
根据超递增序列\(\mathbf{b}\) 容易分离\(S\) 为\(\mathbf{x}\)
根据\(\mathbf{x}\) 解码得到明文\(m\)
解密原理： \[
\begin{align}
S
&= wc\\
&= w \mathbf{x} \cdot \mathbf{a}\\
&= w \mathbf{x} \cdot r\mathbf{b}\\
&= (wr)\mathbf{x} \cdot \mathbf{b}\\
&= \mathbf{x} \cdot \mathbf{b}
\end{align}
\] 利用超递增序列特性： \[
\forall i \in \{1,\cdots,n-1\}, b_i > \sum_{j=0}^{i-1}{b_j}
\] 可解\(\mathbf{x}\)
解题：
构造格 \[
\begin{pmatrix}
2 & 0 & \cdots & 0 & a_0\\
0 & 2 & \cdots & 0 & a_1\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 2 & a_{n-1}\\
1 & 1 & 1 & 1 & c
\end{pmatrix}_{(n+1) \times (n+1)}
\] 和线性方程 \[
\begin{pmatrix}
x_0 & x_1 & \cdots & x_{n-1} & -1
\end{pmatrix}
\begin{pmatrix}
2 & 0 & \cdots & 0 & a_0\\
0 & 2 & \cdots & 0 & a_1\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 2 & a_{n-1}\\
1 & 1 & 1 & 1 & c
\end{pmatrix}
=
\begin{pmatrix}
2x_0-1 & 2x_1-1 & \cdots & 2x_{n-1}-1 & 0
\end{pmatrix}
\] 由于\(x_i \in
\{0,1\}\) ，可得\(2x_i-1 \in
\{1,-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 pubkey = [] enc = nbits = len (pubkey) B = Matrix(ZZ, nbits+1 , nbits+1 ) for i in range (nbits): B[i,i] = 2 B[i,nbits] = pubkey[i] B[-1 ,:] = 1 B[nbits,nbits] = enc L = B.LLL() for r in L: tmp = True for c in r: if c != 1 and c != -1 and c != 0 : tmp = False break if not tmp: continue x = r[:-1 ][::-1 ] for i in range (len (x)): x[i] = (1 - x[i]) // 2 flag = int ('' .join(str (xi) for xi in x),2 ) print ("flag =" ,hex (flag)) print (long_to_bytes(flag))
基于格规约的题目分类集合
RLWE
[DUTCTF2024] Rolling Lava
Waves Erupt
临时把难度降了很多，真是简简又单单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 from sage.all import *from Crypto.Util.number import *from secret import flagq = getPrime(128 ) P = PolynomialRing(Zmod(q), "x" ) x = P.gen() n = 32 f = x ^ n - 1 A = [randint(0 , q) for i in range (n)] e = [randint(-4 , 4 ) for i in range (n)] s = [ord (flag[i]) for i in range (len (flag))] b = (P(A)*P(s)+P(e)) % f b = b.list () print (q)print (A)print (b)
高中好友给发来他们的校赛题目，算是我自主解决的第一道格题目
题目玩了个藏头，暗(明)
定义环 \[
\frac{\mathbb{Z}_{q}[x]}{x^{32}-1}
\] 把flags并生成随机多项式\(A\) 和小噪声多项式\(e\) ，计算出 \[
b = As + e
\] 已知\(b,A\) 求\(s\)
最初拿到这个题目，先弄清楚了所谓"多项式环"的数学含义，用简单的语言表示，就是把高次多项式模 了一下，类似通常数论那样的模
例如对于模\(q = 7\) ： \[
x^2 -4x + 4 \equiv x^2 + 3x + 4 \\
x^8 -3x^3 + 9x^2 - x - 7 \equiv x^8 + 4x^3 + 2x^2 + 6x
\] 又对于模\(x^4 - 1\) ： \[
\begin{align}
&\space x^5 + 2x^4 +3x^3 + 4x^2 + 5x + 6\\
&\equiv (x^5 - x(x^4 -1)) + (2x^4 - 2(x^4-1)) +3x^3 + 4x^2 + 5x +
6\\
&\equiv 5x + 2 +3x^3 + 4x^2 + 5x + 6\\
&\equiv 3x^3 + 4x^2 + 10x + 8
\end{align}
\] 上述两种计算规则合在一起，就是多项式环\(\frac{\mathbb{Z}_{7}[x]}{x^{4}-1}\) 的计算方式（应该没错吧
再看题目脚本是如何利用数组生成多项式的，通过sage实践发现，定义环P后，P(arr)可以将数组转为多项式，其中arr[i]映射到多项式P(arr)的\(x^i\) 项系数；
.list()可将多项式的系数转为数组，和P()互为逆运算，即我们可以得到P(arr).list() == arr # arr空位由0补全。一个小细节：.list()会把系数为\(0\) 的也都扔进数组。
解决语法问题，可以来看纯数学问题：
\(As\) 是两个多项式相乘：A[0](对应\(x^0\) 项)在模\(q\) 下乘以 s[0](对应\(x^0\) 项)的积对应\(x^0\) 项，A[31](对应\(x^{31}\) 项)在模\(q\) 下乘以 s[31](对应\(x^{31}\) 项)的积对应\(x^{62}\) 项，类比卷积乘法可以列出下面的竖式：
\[
\begin{matrix}
A_{0} s_{0} & A_{1} s_{0} & A_{2} s_{0} & \cdots &
\cdots & A_{30} s_{0} & A_{31} s_{0}\\
& A_{0} s_{1} & A_{1} s_{1} & A_{2} s_{1} & \cdots &
\cdots & A_{30} s_{1} & A_{31} s_{1}\\
& & \ddots & \ddots & \ddots & \ddots &
\ddots & \ddots & \ddots \\
&&&&& A_{0} s_{30} & A_{1} s_{30} & A_{2}
s_{30} & \cdots & \cdots & A_{30} s_{30} & A_{31}
s_{30}\\
&&&&&& A_{0} s_{31} & A_{1} s_{31} &
A_{2} s_{31} & \cdots & \cdots & A_{30} s_{31} & A_{31}
s_{31}\\
\end{matrix}
\] 将此竖式纵向相加后，可以得到每一项的系数表达式，\(x_k\) 项对应的系数是 \(\sum_{i+j = k}A_i s_j\)
由于模
\(x^{32}-1\) 的存在，对次数过高的项进行处理，在视觉上就是把右面的竖式三角平移到左侧：
\[
\begin{matrix}
A_{0} s_{0} & A_{1} s_{0} & \cdots & A_{30} s_{0} &
A_{31} s_{0}\\
A_{31} s_{1} & A_{0} s_{1}& \cdots & A_{29} s_{1} &
A_{30} s_{1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
A_{2} s_{30} & A_{3} s_{30} & \cdots & A_{0} s_{30} &
A_{1} s_{30}\\
A_{1} s_{31} & A_{2} s_{31} & \cdots & A_{31} s_{31} &
A_{0} s_{31}\\
\end{matrix}
\] 抽象成矩阵：
\[
\begin{bmatrix}
s_0 & s_1 & \cdots & s_{30} & s_{31}
\end{bmatrix}
\begin{bmatrix}
A_{0} & A_{1} & \cdots & A_{30} & A_{31}\\
A_{31}& A_{0} & \cdots & A_{29} & A_{30}\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
A_{2} & A_{3}& \cdots & A_{0} & A_{1} \\
A_{1} & A_{2}& \cdots & A_{31} & A_{0}
\end{bmatrix}
\] 也就是可以得到这样的线性方程： $$
\[\begin{bmatrix}
s_0 & s_1 & \cdots & s_{30} & s_{31}
\end{bmatrix}\]
\[\begin{bmatrix}
A_{0} & A_{1} & \cdots & A_{30} & A_{31}\\
A_{31}& A_{0} & \cdots & A_{29} & A_{30}\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
A_{2} & A_{3}& \cdots & A_{0} & A_{1} \\
A_{1} & A_{2}& \cdots & A_{31} & A_{0}
\end{bmatrix}\]
\[\begin{bmatrix}
e_0 & e_1 & \cdots & e_{30} & e_{31}
\end{bmatrix}
\equiv
\begin{bmatrix}
b_0 & b_1 & \cdots & b_{30} & b_{31}
\end{bmatrix}
\pmod{q}\]
$$
\[
\mathbf{s} \mathbf{M} + \mathbf{e} = \mathbf{b} + q\mathbf{k}
\] 各个参数取值如下： \[
\mathbf{s} = [s_0,s_1,s_2,\cdots,s_{31}] \in \{0,1,\cdots,127\}^{32}\\
\mathbf{e} = [e_0,e_1,e_2,\cdots,e_{31}] \in \{-4,-3,\cdots,4\}^{32}\\
\mathbf{b} = [b_0,b_1,b_2,\cdots,b_{31}]\\
\mathbf{k} = [k_0,k_1,k_2,\cdots,k_{31}] \in \mathbb{Z}^{32} \\
\] 最初的想法是根据上述线性方程构造一个格出来，
下面是最初很天真的想法，毕竟刚学格，不要笑话我QAQ\[
\mathbf{s} \mathbf{M}+ \mathbf{e} = \mathbf{b} +q\mathbf{k}\\
\mathbf{e} = (\mathbf{b} + q\mathbf{k})\mathbf{M}^{-1}\mathbf{M} -
\mathbf{s}\mathbf{M}\\
\mathbf{e} = ((\mathbf{b} + q\mathbf{k})\mathbf{M}^{-1} -
\mathbf{s})\mathbf{M}\\
\det{\mathbf{M}} \gg \sqrt{4^{n}} > ||\mathbf{e}||\\
\] 据此构造格：
1 2 3 4 5 6 M = matrix(n) for i in range (n): for j in range (n): B[i,j] = A[(j-i)%n] L = B.LLL() print (L[0 ])
然后发现根本规约不出来，究其原因，推测是该格规律性过强，不满足使用LLL时“格足够随机”的条件（参见本页面"高斯启发式"部分）
经过资料查找，构造出这样的格：
\[
\mathbf{N} =
\begin{bmatrix}
\mathbf{M} & & \\
q\mathbf{I} & \mathbf{I} & \\
\mathbf{b} & & \beta
\end{bmatrix}_{(2n+1) \times (2n+1)}
\] 对应的方程： $$
\[\begin{bmatrix}
-\mathbf{s}, \mathbf{k}, 1
\end{bmatrix}\]
\[\begin{bmatrix}
\mathbf{M} & & \\
q\mathbf{I} & \mathbf{I} & \\
\mathbf{b} & & \beta
\end{bmatrix}\]
=
\[\begin{bmatrix}
\mathbf{e},\mathbf{k},\beta
\end{bmatrix}\]
$$ 据此写脚本如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 n = 32 q = 238355018964699036477605770797311983483 A = b = beta = 2 N = matrix(2 *n +1 ) for i in range (n): N[i+n,i] = q N[-1 ,i] = b[i] N[i+n,i+n] = 1 N[-1 ,-1 ] = beta for j in range (n): N[i,j] = A[(j-i)%n] L = N.LLL() res = L[0 ] * N^(-1 ) for i in res[0 :n]: print (chr (abs (i)),end = '' ) print ()
反思
毕竟算是入门的一道题，而且有一次试错的经历，简单记录一下
我先前的构造格的方法过于东拼西凑，本身就是一个NP困难问题，而我在看似巧妙的东拼西凑中无形丢失了很多信息，最后反映出来的是格过于随机，无法规约出预期答案，构造的格应当尽量包含已知信息，然后再交给LLL碰碰运气，从NP的狭缝中找到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 25 from Crypto.Util.number import *from random import *from secret import flagp = getPrime(128 ) n = 64 assert len (flag) < nPRp.<x> = PolynomialRing(Zmod(p)) f = x^n+2024 PR = PRp.quo(f) assert f.is_irreducible()A = [randint(0 , p) for i in range (n)] E = [randint(-4 , 4 ) for i in range (n)] S = [ord (flag[i]) for i in range (len (flag))] B = PR(A)*PR(S)+PR(E) print (A)print (B.list ())print (p)
学长给发的题(接下来两道都是)，很有趣
本题RLWE问题，换了一个新的环： \[
\frac{\mathbb{Z}_{p}[x]}{x^{64}+2024}
\] 把flags并生成随机多项式\(A\) 和小噪声多项式\(e\) （\(s\) 和\(e\) 是小的我就要小写!）\[
B = As + e\\
\]
和上一题一样，列竖式，化矩阵，构造格，不同的是矩阵部分三角要乘以\((-2024)\)
理好逻辑后直接可以写脚本：
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 n = 64 p = A = B = beta = 2 N = matrix(2 *n +1 ) for i in range (n): N[i+n,i] = p N[-1 ,i] = B[i] N[i+n,i+n] = 1 N[-1 ,-1 ] = beta for j in range (n): N[i,j] = A[(j-i)%n] if i > j: N[i,j] = N[i,j] * (-2024 ) % p L = N.LLL() res = L[0 ] * N^(-1 ) for i in res[0 :n]: print (chr (abs (i)),end = '' ) print ()
新年用个新新环！
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 from Crypto.Util.number import *from random import *from secret import flagp = getPrime(128 ) n = 64 assert len (flag) < nPRp.<x> = PolynomialRing(Zmod(p)) f = x^n+2 *x^3 +0 *x^2 +2 *x+4 PR = PRp.quo(f) assert f.is_irreducible()A = [randint(0 , p) for i in range (n)] E = [randint(-4 , 4 ) for i in range (n)] S = [ord (flag[i]) for i in range (len (flag))] B = PR(A)*PR(S)+PR(E) print (A)print (B.list ())print (p)
本题RLWE问题，换了一个新新的环： \[
\frac{\mathbb{Z}_{p}[x]}{x^{64} + 2x^3 + 0x^2 + 2x + 4}
\]
如果弄明白了RLWE的原理，做这个题只要构造出来那个很有规律的矩阵\(\mathbf{M}\) 即可
不过像我这么懒的CTFer肯定不会自己去推
于是我先去做了下一道题的通解脚本，具体推导也在下一题，这里直接放解题脚本：
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 n = 64 p = A = B = beta = 2 PRp.<x> = PolynomialRing(Zmod(p)) f = x^n+2 *x^3 +0 *x^2 +2 *x+4 PR = PRp.quo(f) assert f.is_irreducible()M = [] for i in range (n): M.append((PR(A) * x**i).list ()) M = matrix(M) N = matrix(2 *n+1 ) N[-1 ,-1 ] = beta for i in range (n): N[i,i+n] = 1 N[i+n,i] = p N[-1 ,i] = B[i] for j in range (n): N[i,j] = M[i,j] L = N.LLL() res = L[0 ] * N^(-1 ) for i in res[:n]: print (chr (abs (i)),end='' ) print ()
新年用个新新新新环！
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 from Crypto.Util.number import *from random import *from secret import flagp = getPrime(128 ) n = 64 assert len (flag) < nPRp.<x> = PolynomialRing(Zmod(p)) newyear = [2 ,0 ,2 ,4 ] f = x^n for i in range (n): f += newyear[i%4 ]*x^(n-1 -i) PR = PRp.quo(f) assert f.is_irreducible()A = [randint(0 , p) for i in range (n)] E = [randint(-4 , 4 ) for i in range (n)] S = [ord (flag[i]) for i in range (len (flag))] B = PR(A)*PR(S)+PR(E) print (A)print (B.list ())print (p)
本题RLWE问题，换了一个新新新新的环： \[
\frac{\mathbb{Z}_p[x]}{x^{64}+2x^{63}+2x^{61}+4x^{60}+...++2x^3+2x+4}
\] 如此逆天复杂的环我更不可能去手推关系了
于是我们可以模拟上述过程，构造的矩阵方程要把A和s多项式的乘法分离开来，也就是让\(s_ix^i\) 分别乘以对应的\(A\) 多项式，sage能帮我们直接在环上计算出来，最后只需.list()一下就能得到对应的矩阵的一行，把每一行算一遍就能直接得到想要的\(\mathbf{M}\) 矩阵，就像这样：
1 2 3 4 M = [] for i in range (n): M.append((PR(A) * x**i).list ()) M = matrix(M)
PR是原题的环，我们直接拿过来用
最后整体的攻击脚本如下：
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 n = 64 p = A = B = beta = 2 PRp.<x> = PolynomialRing(Zmod(p)) newyear = [2 ,0 ,2 ,4 ] f = x^n for i in range (n): f += newyear[i%4 ]*x^(n-1 -i) PR = PRp.quo(f) assert f.is_irreducible()M = [] for i in range (n): M.append((PR(A) * x**i).list ()) M = matrix(M) N = matrix(2 *n+1 ) N[-1 ,-1 ] = beta for i in range (n): N[i,i+n] = 1 N[i+n,i] = p N[-1 ,i] = B[i] for j in range (n): N[i,j] = M[i,j] L = N.LLL() res = L[0 ] * N^(-1 ) for i in res[:n]: print (chr (abs (i)),end='' ) print ()
Mateusz carried a huge jar of small papers with public keys written
on them, but he tripped and accidentally dropped them into the scanner
and made a txt file out of them! D: Note: This challenge is just an
introduction to RLWE, the flag is (in standard format) encoded inside
the private key. 得到的flag请使用NSSCTF{}格式提交.
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 from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler as d_gaussflag = bytearray (raw_input()) flag = list (flag) n = len (flag) q = 40961 F = GF(q) R.<y> = PolynomialRing(F) S.<x> = R.quotient(y^n + 1 ) def gen_small_poly (): sigma = 2 /sqrt(2 *pi) d = d_gauss(S, n, sigma) return d() def gen_large_poly (): return S.random_element() a = gen_large_poly() s = S(flag) file_out = open ("downloads/public_keys.txt" , "w" ) file_out.write("a: " + str (a) + "\n" ) for i in range (100 ): e = gen_small_poly() b = a*s + e file_out.write("b: " + str (b) + "\n" ) file_out.close()
附件给了一大堆数据，最高次为\(103\) ，易得n = 104
错误向量使用高斯随机产生了一百份，使用统计学原理拟合出\(\mu\) 值
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 import reimport numpy as npfrom scipy import statswith open (R"E:\Desktop\public_keys.txt" ,'r' ) as f: lines = f.readlines() a = eval ('[' + re.sub(R"(\*x)(\^\d{0,3})? \+ " ,',' ,lines[0 ][2 :-1 ]) + ']' ) b_with_error = [] for line in lines[1 :]: b_i = eval ('[' + re.sub(R"(\*x)(\^\d{0,3})? \+ " ,',' ,line[2 :-1 ]) + ']' ) b_with_error.append(b_i) sigma = 2 / np.sqrt(2 * np.pi) ASinv = [] n = len (b_with_error[0 ]) for i in range (n): c = [b_with_error[j][i] for j in range (len (b_with_error))] mean_estimate = np.mean(c) z_score = stats.norm.ppf(0.975 ) margin_of_error = z_score * (sigma / np.sqrt(n)) confidence_interval = (mean_estimate - margin_of_error, mean_estimate + margin_of_error) print (f"{round (mean_estimate)} -> {confidence_interval} " ) ASinv.append(round (mean_estimate)) print (ASinv[::-1 ])
检查置信区间没有特别离谱的数据
如此就可以拟合出实际的\(\mathbf{b} =
\mathbf{a}*\mathbf{s}\) 多项式系数
于是构造格 $$
\[\begin{bmatrix}
-\mathbf{s}, \mathbf{k}, 1
\end{bmatrix}\]
\[\begin{bmatrix}
\mathbf{M} & \mathbf{I} & \\
q\mathbf{I} & & \\
\mathbf{b} & & \beta
\end{bmatrix}\]
=
\[\begin{bmatrix}
\mathbf{0},\mathbf{s},\beta
\end{bmatrix}\]
$$ 发现无法规约出合适的\(\mathbf{w}\) ，以为是需要配平，也无法得到正常的解，试图配平也无效
找到官解发现
\(\mathbf{b}\) 和\(\mathbf{a}\) 都已知了，直接除过去不就行了……
emmm……
1 2 3 4 5 6 7 8 9 10 11 12 AS = n = 104 q = 40961 F = GF(q) R.<y> = PolynomialRing(F) S.<x> = R.quotient(y^n + 1 ) a_s = S(AS) a = s = a_s / a print ('' .join(map (chr ,s.list ())))
[L3hctf2024] badrlwe
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 from Crypto.Util.number import *from random import *import randomimport numpy as npfrom secret import flag, skassert len (flag[7 :-1 ]) <= 64 data = [ord (i) for i in list (flag[7 :-1 ])] for i in range (len (sk)): assert data[i] == sk[i] q = 1219077173 R.<x> = PolynomialRing(Zmod(q), 'x' ) N = 1024 f = x^N - 1 a = [0 ] * N for i in range (N): a[i] = randint(0 , q) s = sk e = [0 ] * N for i in range (N): val = np.random.normal(loc=0.0 , scale=2.1 , size=None ) e[i] = int (val) a = R(a) s = R(s) e = R(e) b = (a*s + e)%f print (a)print (b)print (q)
乍一看这个
N=1024也太大了整个，这解一下先不说能不能，LLL的时间都够我吃一顿的了。
再仔细看的话，有一句
assert len(flag[7:-1]) <= 64，也就是多项式
s其实很小，如果还是按照先前通解的思维，可以把多项式
s看成高位系数都是
0的
1023阶多项式，构造
2*1024+1阶矩阵，应该不行。根据先前[DUTCTF2024]
Rolling Lava Waves
Erupt的反思，列线性方程尽量体现所有的关系，给规约充分的机会，还是列竖式：
\[
\begin{matrix}
A_{0} s_{0} & A_{1} s_{0} & A_{2} s_{0} & \cdots &
\cdots & A_{1022} s_{0} & A_{1023} s_{0}\\
& A_{0} s_{1} & A_{1} s_{1} & A_{2} s_{1} & \cdots &
\cdots & A_{1022} s_{1} & A_{1023} s_{1}\\
& & \ddots & \ddots & \ddots & \ddots &
\ddots & \ddots & \ddots \\
&&&&& A_{0} s_{1022} & A_{1} s_{1022} &
A_{2} s_{1022} & \cdots & \cdots & A_{1022} s_{1022} &
A_{1023} s_{1022}\\
&&&&&& A_{0} s_{1023} & A_{1} s_{1023} &
A_{2} s_{1023} & \cdots & \cdots & A_{1022} s_{1023} &
A_{1023} s_{1023}\\
\end{matrix}
\] 由于
s是小多项式，从
\(s_{64}\) 到
\(s_{1023}\) 确定都是
\(0\) ，因此该竖式可以简化到只有前
\(64\) 行，取多项式模后得到一个
\(64 \times 1024\) 的矩阵
\(M\) ，任取其中连续的
\(64 \times 64\) 的子矩阵都可以体现
\(s_0\) ~
\(s_{63}\) 的全部信息，于是理同前： $$
\[\begin{bmatrix}
\mathbf{s}, \mathbf{k},-1
\end{bmatrix}\]
\[\begin{bmatrix}
\mathbf{M} & \mathbf{I} & \\
q\mathbf{I} & & \\
\mathbf{b} & & \beta
\end{bmatrix}\]
=
\[\begin{bmatrix}
\mathbf{e},\mathbf{s},\beta
\end{bmatrix}\]
$$
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 q = 1219077173 n = 64 N = 1024 beta = 2 R.<x> = PolynomialRing(Zmod(q), 'x' ) f = x^N - 1 a = b = A = a.list () B = b.list () M = [] for i in range (n): M.append((a * x**i % f).list ()) M = matrix(M) N = matrix(2 *n+1 ) N[-1 ,-1 ] = beta for i in range (n): N[i,i+n] = 1 N[i+n,i] = q N[-1 ,i] = B[i] for j in range (n): N[i,j] = M[i,j] L = N.LLL() print ('' .join(map (chr ,map (abs ,L[0 ][n:2 *n]))))
把flag多余部分剃掉就行了，或者。。都是明文？
参考学习
成功领我入门的文章（本文一开始就是照着这位大佬的写的）
超赞超详细的一本书(就是太贵了)
An Introduction to Mathematical Cryptography (2014) - Hoffstein,
Pipher, Silverman
很基础很详细的教学（虽然有点不适合我）
超棒的Manim动画演示LLL算法（有做汉化搬运的打算）：
NSSCTF的那三道RLWE题目！让我对RLWE攻击原理有了新的认知：
__END__
