矩阵 m * M = c

题1

(2023江苏领航杯-prng)
题目来源：https://dexterjie.github.io/2023/09/12/%E8%B5%9B%E9%A2%98%E5%A4%8D%E7%8E%B0/2023%E9%A2%86%E8%88%AA%E6%9D%AF/
题目描述：
(没有原数据，自己生成的数据)

from Crypto.Util.number import *              
from secret import flag              
import random              
              
def base(n, l):              
    bb = []              
    while n > 0:              
        n, r = divmod(n, l)              
        bb.append(r)              
    return ''.join(str(d) for d in bb[::-1])              
              
def prng(secret):                
    seed = base(secret, 5)              
    seed = [int(i) for i in list(seed)]              
    length = len(seed)              
    R = [[ random.randint(0,4) for _ in range(length)] for _ in range(length*2)]              
    S = []              
    for r in R:              
        s = 0              
        for index in range(length):              
            s += (r[index] * seed[index]) % 5              
        s %= 5              
        S.append(s)              
    return R, S              
        
m = bytes_to_long(flag)              
R, S = prng(m)              

with open('output.txt', 'w') as f:              
    f.write(f'R = {R}\nS = {S}')
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

题目分析：
$$\left(\begin{array}{cccc}{R}_{1,1}& R_{1,2}& \cdots & R_{1,n}\\ R_{2,1}& R_{2,2}& \cdots & R_{2,n}\\ ⋮& ⋮& \ddots & ⋮\\ R_{2n,1}& R_{2n,2}& \cdots & R_{2n,n}\end{array}\right)\ast \left(\begin{array}{c}see{d}_1\\ see{d}_2\\ ⋮\\ see{d}_n\end{array}\right)=\left(\begin{array}{c}{S}_1\\ S_2\\ ⋮\\ S_{2n}\end{array}\right)$$
5进制，R * seed = S，已知R,S求seed

from Crypto.Util.number import *              
from gmpy2 import *
with open('output1.txt') as f:
    exec(f.read())
p = 5
R = matrix(GF(5),R).transpose()
S = matrix(GF(5),S)
m = R.solve_left(S).list()
print(long_to_bytes(int(''.join(str(i) for i in m),5)))

# CnHongKe{a8cc755d375811f55cec82153388c}
1
2
3
4
5
6
7
8
9
10
11

题2

题目来源：https://blog.csdn.net/weixin_52640415/article/details/132925227?spm=1001.2014.3001.5502
题目描述：
(没有原数据，自己生成的数据)

import os
import secret
import hashlib
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
 
LEN = 32
 
def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])
 
def challenge(m: bytes, pbits: int, level: int=0):
    p = getPrime(pbits)
    M = random_matrix(GF(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M
 
    return {"p": p, "M": M.list(), "c": c.list()}
 
args = {
    "chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00
    },
    "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01
    },
    "chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10
    }
}
 
out = dict()
enc = pad(secret.flag, LEN)
for i in range(3):
    out[f"chall{i+1}"] = challenge(**args[f"chall{i+1}"])
    enc = xor(enc, hashlib.sha512(args[f"chall{i+1}"]["m"]).digest())
out["enc"] = enc.hex()
with open('output.txt', 'w') as f:
    f.write(f"{out = }")
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

题目分析：
$$\begin{gathered} m\ast M=c，已知M,c求m \\ 共有三组数据，求解三组矩阵 \\ 第一组：m_{1\ast 32}\ast M_{32\ast 32}=c_{1\ast 32} \\ 第二组：m_{1\ast 32}\ast M_{32\ast 31}=c_{1\ast 31} \\ 第三组：m_{1\ast 32}\ast M_{32\ast 16}=c_{1\ast 16} \end{gathered}$$
第一组为方阵，用solve_left()直接解

with open('output.txt') as f:
    exec(f.read())
len = 32
   
p1,M1,c1 = out['chall1']['p'],out['chall1']['M'],out['chall1']['c']
M1 = Matrix(GF(p1),len,len,M1)
c1 = vector(GF(p1),c1)
m1 = M1.solve_left(c1)
print(m1)
bytes([i for i in m1])

# b'\xcd\xf4\xd6\xa5#\xa2\x04~q\xf6\x90\xb6@\xf9Z\xbd\x1fw\xfe\\w\xc3\xad\xabQZBQk\xa0L\xc5'
1
2
3
4
5
6
7
8
9
10
11
12

话说非方阵是有无数组解的，solve_left()也可解非方阵，比如题1，所以来到第二组
看大佬博客是这样解的：

p2,M2,c2 = out['chall2']['p'],out['chall2']['M'],out['chall2']['c']
M2 = Matrix(GF(p2),len,len-1,M2)
c2 = Matrix(GF(p2),1,31,c2)
m2 = M2.solve_left(c2).list()
print(m2)

basis = M2.left_kernel().basis()[0]
for k in range(p2):  
    try:
        m21 = m2 + k * basis
        print(k, bytes(m21.list())) # 题目中m是byte类型，把超过256的过滤掉
    except:
        pass
1
2
3
4
5
6
7
8
9
10
11
12
13

说明一下
basis 是矩阵 M 的左核空间（left kernel space）中的一个基向量。
左核空间是指满足方程 M * v = 0 的所有向量 v 的集合。
这些向量使得将它们与矩阵 M 进行乘法运算的结果为零向量

不过我很不理解为什么出来的m2是1 * 32的（虽然最后一个元素是0），但不应该是1 * 31吗。题1也不是这样啊，题一求得的seed是1 * n的。这个疑问先留下，我们继续。

这里确实是特殊的，题目中明确了m是byte类型，范围是1~256，不过有限域的范围是p，比256大得多，故通过M2.solve_left(c2)得到的m2并不是最终解，只能说这也是一个解，不过不是我们需要的解。通过爆破将解中的元素锁定在 1 ~ 256的范围内。（通过看他写的题解，我是这样理解的）

第三部分

试了下用solve_left()解，结果可想而知，是有解，不过不是我们要的，解出的数值太太太大了，M3与方阵相差太大，造basis也没用了。
如何将解中数值的范围锁定在1 ~ 256？------ 格基规约（又学到了，记下）
佬的方法：
$$\begin{gathered} 构造如下块矩阵 \\ {\left(\begin{array}{cc}M& 1\\ p& 0\\ c& 0\end{array}\right)}_{49\ast 48} \\ 其中1是32\ast 32的单位矩阵 \\ p={\left(\begin{array}{cccc}p& & & \\ & p& & \\ & & \ddots & \\ & & & p\end{array}\right)}_{16\ast 16} \end{gathered}$$
规约后第二行是目标向量，第一行是0向量

p3,M3,c3 = out['chall3']['p'],out['chall3']['M'],out['chall3']['c']
M3 = matrix(ZZ,32,16,M3)
c3 = matrix(ZZ,1,16,c3)
A = block_matrix([[M3,1],[Integer(p3),0],[c3,0]])
m33 = A.LLL()
m3 = bytes(map(abs,m33[1][16:]))
print(m3)
# b'f\xcb\xf1L\xaf\xf2\xf3@a\\4\xb4[op\xa1`\x0c\x0b\x89\xa7\x1e?\x10x\x1e\xf68\xb8\xb9\x9d\xb9'
1
2
3
4
5
6
7
8

之后全部异或即可得到flag

from hashlib import *
m1 = sha512(b'\xcd\xf4\xd6\xa5#\xa2\x04~q\xf6\x90\xb6@\xf9Z\xbd\x1fw\xfe\\w\xc3\xad\xabQZBQk\xa0L\xc5').digest()
m2 = sha512(b'\x90\x1b\x87\x9c!\xe4\x92\xef\xd4\xe8\x94\x8f\x1c,\x02N\x80\x97\xb5ep\x90\x06\x8f ]\xba\x9f\xc1N\xb8Z').digest()
m3 = sha512(b'f\xcb\xf1L\xaf\xf2\xf3@a\\4\xb4[op\xa1`\x0c\x0b\x89\xa7\x1e?\x10x\x1e\xf68\xb8\xb9\x9d\xb9').digest()
enc = bytes.fromhex('496415ff125bacee09c8e721f8adf44158e398a854a48415110d0cf88fdc03767b93f91142e035e718d6ad6b7965d15a973cb9fb97923d1a37580cf60f48eabc')
print(len(m1),len(m2),len(m3))
flag = bytes([m1[i] ^ m2[i] ^ m3[i] ^ enc[i] for i in range(len(enc))])
print(flag)
1
2
3
4
5
6
7
8

浅记一下：

解疑：为什么是1 * 32 而不是1 * 31，我觉得应该是相差太小，而且，最后一位本来就是0，没有实际意义，它乘出来的结果和 1 * 31乘出来的结果本就相同，故这个1 * 32 的结果很大意义上是等同于1 * 31 的。

还有，不要用题2第三部分的解法去解题1，没用，解不出，如果对题1构造格，格中向量与想要得到的目标向量相差过小(都在GF(5)中)，规约不出，得不到结果。

题2真的学到了
记点:块矩阵的构造，left_kernel().basis()的应用

还有一点，题2不要构造下面这种，也得不到结果，矩阵构造不一样结果不一样很正常，反正就是那个对按哪个来。嗯，没了。
$${\left(\begin{array}{ccccccc}{M}_{1,1}& \cdots & M_{1,16}& 1& & & \\ M_{2,1}& \cdots & M_{2,16}& & 1& & \\ ⋮& \ddots & ⋮& & & \ddots & \\ M_{32,1}& \cdots & M_{32,16}& & & & 1\\ p& \cdots & p& & & & \\ c_1& \cdots & c_{16}& & & & \end{array}\right)}_{34\ast 48}$$