格(Lattice ) 前置知识 线性代数 ：向量、矩阵、线性方程、线性空间、线性相关、基
什么是格 格与格基 令$\mathbf{b0},\mathbf{b_1}, \cdots ,\mathbf{b {n-1}}$为空间$\mathbb{R}^m$上一组线性无关的向量($m \ge n$)，则集合
被称作一个格
其中矩阵$\mathbf{B} := [\mathbf{b0},\mathbf{b_1}, \cdots ,\mathbf{b {n-1}}]$称为该格的格基 ，所以格又可以表示为：
基本域 设$B = [\mathbf{b0},\mathbf{b_1}, \cdots ,\mathbf{b {n-1}}]$为一组格基，则该组格基的基本域为：
高斯启发式（The Gaussian Heuristic） $L$是$n$维格，高斯所期望的最短长度为
高斯启发式表示，在一个“随机选择的 格”中的最短非零向量满足
更精确地，如果确定了$\epsilon > 0$，则当$n$足够大时这个随机的 $n$维格将满足
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 '''
加解密原理：
密钥选取：
加密：
解密：
解密原理：
解题：
关键需要知道私钥$(f,g)$
找关系
两个未知量，一个已知方程，再构造一个方程
即
目的是将线性方程分离为已知的矩阵和未知的向量
所求$\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$
生成公钥$\mathbf{a} = r\mathbf{b} \mod{q} \space\space( a_i = r b_i \mod{q}) $
生成私钥$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$
解密原理：
利用超递增序列特性：
可解$\mathbf{x}$
解题：
构造格
和线性方程
由于$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)
高中好友给发来他们的校赛题目，算是我自主解决的第一道格题目
题目玩了个藏头，暗(明)
定义环
把flags并生成随机多项式$A$和小噪声多项式$e$，计算出
已知$b,A$求$s$
最初拿到这个题目，先弄清楚了所谓”多项式环”的数学含义，用简单的语言表示，就是把高次多项式模 了一下，类似通常数论那样的模
例如对于模$q = 7$：
又对于模$x^4 - 1$：
上述两种计算规则合在一起，就是多项式环$\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}$项，类比卷积乘法可以列出下面的竖式：
将此竖式纵向相加后，可以得到每一项的系数表达式，$xk$项对应的系数是 $\sum {i+j = k}A_i s_j$
由于模$x^{32}-1$的存在，对次数过高的项进行处理，在视觉上就是把右面的竖式三角平移到左侧：
抽象成矩阵：
也就是可以得到这样的线性方程：
各个参数取值如下：
最初的想法是根据上述线性方程构造一个格出来，
下面是最初很天真的想法，毕竟刚学格，不要笑话我QAQ
据此构造格：
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时“格足够随机”的条件（参见本页面”高斯启发式”部分）
经过资料查找，构造出这样的格：
对应的方程：
据此写脚本如下：
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问题，换了一个新的环：
把flags并生成随机多项式$A$和小噪声多项式$e$ （$s$和$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问题，换了一个新新的环：
如果弄明白了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问题，换了一个新新新新的环：
如此逆天复杂的环我更不可能去手推关系了
于是我们可以模拟上述过程，构造的矩阵方程要把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:
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}$多项式系数
于是构造格
发现无法规约出合适的$\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的反思，列线性方程尽量体现所有的关系，给规约充分的机会，还是列竖式：
由于s是小多项式，从$s{64}$到$s {1023}$确定都是$0$，因此该竖式可以简化到只有前$64$行，取多项式模后得到一个$64 \times 1024$的矩阵$M$，任取其中连续的$64 \times 64$的子矩阵都可以体现$s0$~$s {63}$的全部信息，于是理同前：
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__
