糖醋小鸡块的blog
0%

2024-网鼎杯半决赛/决赛-wp-crypto

发表于 分类于 Valine：

赛后拿到题复现，学习一下。

半决赛

RSA

题目：

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
'''

题目基于RSA，加密过程首先生成：

  • 一个大约为192bit的$x$
  • 三组RSA的密钥$p_i,q_i,n_i$

之后进行三轮加密，每轮加密生成一个620bit左右的$z_i$，并计算：

给出$e_i,n_i$，要求分解$n_1$进行RSA解密。

首先把$x$移到左边并展开成等式：

由于$e_i$和$\phi_i$数量级相近且$k_i$比较小，所以$k_i$是一个和$x^2$数量级接近的小量，因此再进一步把$\phi_i$展开的话会得到：

把未知量线性化一下就是：

与已知的系数$e_i,n_i+1$相比这几个变量都不大，所以造如下格：

这个格具有的线性关系是：

所以配平规约一下就可以求出$X,Y_i,Z_i$了，也就是我们现在拥有了：

  • $x^2$
  • $k_i$
  • $z_i - k_i(p_i+q_i)$

这个时候把已知量用上，记$C_i = e_ix^2 - k_i(n_i+1) $，重新组织一下上面的等式就是：

我们只需要分解$n_1$就可以了，所以我们利用：

来造一个格：

他的线性关系是：

同样的，前三列配平并将最后一列配上一个大系数就可以进行规约。然而规约后的第一行并不是我们的目标向量，而是如下形式：

原因很简单，因为上面的格显然存在一个向量是：

这显然比我们预期的向量短，所以LLL后的第二行实际上是与这个向量约减后的结果，换句话说我们只能从LLL后的第二行得到$p_1+q_1$的一半左右的高位而已，得不到准确结果。

而已知$p+q$高位分解$n$的问题就很常见了，首先在RealField上求解方程，可以把$p+q$高位转化到$p$的高位，经测试这样做一般会有254位是准确的，那么现在问题就变成了已知$p$的高254位求解$p$的copper问题了。

这个问题很经典，要加快这个过程可以用上以下几个小优化：

  • 首先，从RealField求解的根中选择较大的那一个来copper，因为这样可以使small_roots里的beta参数设置成0.5，从而提高上界

  • 由于$p$是素数，所以可以不爆破二进制位，而爆破$p$模一些小素因子的余数，从而减小爆破量，比如这里由于已知254位，所以选择$2310=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11$比较合适

    有关这个优化的原理可以看我之前出的一道题目：

    [tangcuxiaojkuai]easy_copper2 | NSSCTF

  • 多进程XD，这个是最粗暴但是又最有用的优化，不用的话可能得爆接近十分钟

解出$p_1,q_1$之后会发现还有$e,\phi(n_1)$不互素的问题，并且$e$和$p-1,q-1$的gcd分别是$e$和3，所以模$p$下应该解的会很慢，放到模$q$下去开三次根会好一些。

exp：

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
from Crypto.Util.number import *
from multiprocessing import Pool
from tqdm import *

k = 3
d = k/(2*(k+1))
X = int(1024*(d/2))
Z = 630

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

##################################################################### part1 get x and ki
L1 = Matrix(ZZ, 4, 4)
for i in range(1, 4):
    L1[0, i] = es[i-1]
    L1[i, i] = -ns[i-1] - 1
L1[0, 0] = 2^513
res = L1.LLL()[0]
x2, k1, k2, k3 = list(map(abs, L1.solve_left(res)))


##################################################################### part2 get ph
L2 = Matrix(ZZ, [
    [1, 0, 0, 1],
    [0, 2^(Z-513), 0, -k1],
    [0, 0, 2^Z, -(es[0]*x2 - k1*(ns[0]+1))]
])
L2[:, -1:] *= 2^1000
L2 = L2.LLL()
res = L2[1][1] // 2^(Z-513)
PR.<x> = PolynomialRing(RealField(1000))
f = x*(res-x) - ns[0]
ph = (abs(int(max(f.roots(multiplicities=False)))) >> 258 << 258) // 2310 * 2310


##################################################################### part3 get p
def attack(p_low):
    PR.<x> = PolynomialRing(Zmod(ns[0]))
    f = ph + 2310*x + p_low
    f = f.monic()
    res = f.small_roots(X=2^258//2310, beta=0.5, epsilon=0.016)

    if(res != []):
        p = 2310*int(res[0]) + p_low + ph
        q = ns[0] // p
        print(p)
        print(q)
        return True

pos = []
for i in range(1,2310):
    if(GCD(i,2310) == 1):
        pos.append(i)

with Pool(16) as pool:
    for i in tqdm(pool.imap(attack, pos), total=len(pos)):
        if(i == True):
            break

##################################################################### part4 decrypt
p = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
e = 8462913

PR.<x> = PolynomialRing(Zmod(q))
f = x^3 - pow(c, inverse(e//3, q-1), q)
for i in f.roots(multiplicities=False):
    print(long_to_bytes(int(i)))

#flag{N3w_Attacks_4_key_equat1ons}



noisy-nfsr

题目：

task.py：

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
import secrets, signal
from utils import nbit, LFSR, NFSR, NOISE


def proof_of_work():
    import random, string, hashlib

    ss = ''.join(random.choices(string.ascii_letters + string.digits, k=20))
    sh = hashlib.sha256(ss.encode()).hexdigest()
    print(f"|    sha256(XXXX + {ss[4:]}) == {sh}")
    prefix = input("|    XXXX>")
    return prefix == ss[:4]


if __name__ == "__main__":
    try:
        assert proof_of_work()
        signal.alarm(666)
        
        seed, mask = [secrets.randbits(12) | 2**(12-1) for _ in range(2)]
        lfsr = LFSR(seed, mask)
        noise = NOISE(lfsr)
        seeds = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]
        masks = [secrets.randbits(nbit) | 2**(nbit-1) for _ in range(2)]
        print(f"|  {masks = }")
        
        args = [(512, 128), (256, 256), (128, 512)]
        n, m = args[int(input('|  args>')) % len(args)]

        print("|  Good luck")
        for _ in range(n):
            print("|  Menu:\n|    [H]it\n|    [S]tand\n|    [Q]uit")
            inp = input("|  inp>").lower()
            if inp == 'h':
                lfsrs = [LFSR(seed, mask) for seed, mask in zip(seeds, masks)]
                nfsr = NFSR(*lfsrs, noise=noise)
                bits = nfsr.encrypt(b'\x00'*m)
                print(f"|  {bits.hex() = }")
            else:
                if inp == 's' and all(int(input('|  seed>')) == seed for seed in seeds):
                    print('|  🏁', open('flag', 'r').read())
                break
        print("|  Bye")
    except:
        print("|  Nah")

utils.py：

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
nbit = 128

class LFSR:
    def __init__(self, seed: int, mask: int):
        self.state = seed & (2**nbit - 1)
        self.mask = mask & (2**nbit - 1)

    def __next__(self):
        b = (self.state & self.mask).bit_count() & 1
        self.state = ((self.state << 1) | b) & (2**nbit - 1)
        return b
    
    def __call__(self, bits: int):
        out = 0
        for _ in range(bits):
            out = (out << 1) | next(self)
        return out

class NFSR:
    def __init__(self, lfsr0: LFSR, lfsr1: LFSR, noise: iter):
        self.lfsr0 = lfsr0
        self.lfsr1 = lfsr1
        self.noise = noise
    
    def __next__(self):
        b0, b1 = self.lfsr0(1), self.lfsr1(1)
        b = b0 ^ b1 ^ next(self.noise)
        return b
    
    def __call__(self, bits: int):
        out = 0
        for _ in range(bits):
            out = (out << 1) | next(self)
        return out

    def encrypt(self, msg: bytes):
        return bytes([m ^ self(8) for m in msg])

def NOISE(lfsr: LFSR, p: float=2/3, prec: int=256):
    import secrets
    
    t = 2**prec
    while True:
        if lfsr(1):
            yield int(secrets.randbelow(t) / t > p)
        else:
            yield int(secrets.randbelow(t) / t <= p)

题目基于nfsr，他有几个部件，每个部件分别的逻辑为：

  • nfsr：输出为两个lfsr的输出异或一个noise的输出

    这两个lfsr的mask和seed都是128bit的

  • noise：输出为一个lfsr的随机扰动输出，扰动的含义为该lfsr的输出有p=2/3的概率发生翻转

    这个lfsr的mask和seed都是12bit的

回到题目，连接上靶机后，靶机会先做如下初始化：

  • 初始化noise

  • 初始化nfsr会用到的两个lfsr的128bit的mask和seed，并发送给我们mask

  • 我们自行选择以下三组参数中的一组：

    其中n代表我们能交互的次数，m代表每次交互靶机返回的nfsr的字节数

之后正式进入交互，每次交互可以做：

  • 输入h，靶机会返回nfsr输出流的m个字节

    这里需要注意两个地方：

    • 每一次输入h，nfsr会重新初始化两个lfsr，也就是说每次nfsr的两个lfsr的输出都是一样的
    • 每一次输入h，nfsr不会重新初始化noise，也就是说每次的noise都是在上一次的基础上继续递推

  • 输入s，可以校验初始的128bit的两个seed是否正确，正确则得到flag。并且输入s之后不论正不正确都会退出。

任务理清楚了，那么下面就进入解题环节。

思路一

首先注意到以下几个事实：

  • noise对应的那个lfsr，其seed和mask都仅有12bit，并且由于MSB是1，所以爆破量只有11x2=22bit，也就是爆破2^22这个数量级，其中就存在正确的seed和mask

  • 如果能用某种方式爆破得到noise的初始lfsr的话，那么也就等价于我们可以知道noise的lfsr的所有输出流。而由于noise的实际输出是这个输出流2/3概率偏转后的值，而我们有多组nfsr的输出，所以可以通过概率统计来确定nfsr里两个lfsr的输出

  • 而由于nfsr对于两个lfsr来说仅仅是异或而已，在模2下是线性运算，所以如果没有noise的干扰的话，搜集足够比特就可以解线性方程得到两个lfsr的初始seed

    这里足够比特指线性无关的256bit(128x2)

因此整个思路的唯一问题就只剩下如何爆破noise的初始lfsr了。这很简单，比如对于我们前两轮交互来说，我们拿到的输出就是：

这里括号内表示输出的比特数，noise及lfsr的下标表示起始比特的位置

那么做异或就得到：

把p概率翻转的函数记为$f$，那么对于上面这个异或值的每一个比特来说，都是：

所以只需要爆破11bit的seed以及11bit的mask，并统计输出是不是对于这个lfsr符合上面的分布即可。

但是实际上会发现这个做法有个问题就是太慢太慢了，虽然说他确实可以爆破出来，但是就算加多进程也没有办法在规定的alarm(666)里跑出来，所以只能换思路。

思路二

由于noise的lfsr，他的mask只有12位，这代表着他的最大周期也就只会有$2^{12}-1$，并且有不小的概率周期不大（只有几百甚至几十）。

基于这一点，我们把目光从多组nfsr的输出转换到一组nfsr的输出，那么当noise的lfsr周期较小的时候，如果把这个周期记为T，那么对于同一组内的第i和第i+T个比特来说都有：

这里lfsr的下标t表示noise对应的lfsr的某个起始位置，不固定

把这两个比特异或起来就有：

之所以用中括号分成两部分，原因在于不同组的nfsr的输出用的是两个完全一样的lfsr。所以我们爆破T的话，当T正确的时候，这样的比特会因为异或了$[f(lfsr_t(1)) \oplus f(lfsr_t(1))]$的缘故，呈现出一个和随机分布不一样的分布，这就是检测T正确的依据。

举个例子就是，比如我们选择$n,m = (256,256)$，那么对于任意的i和正确的T来说，我们可以获得255个如下的异或比特：

$[f(lfsr_t(1)) \oplus f(lfsr_t(1))]$不是完全随机的0、1，推导一下会得到：

其中函数g表示p’概率翻转的函数，p’满足：

这个概率不是0.5，说明$[f(lfsr_t(1)) \oplus f(lfsr_t(1))]$的输出会有更大的概率是0或者1其中一个，而对于255组输出来说，他们的$[lfsr1_i(1) \oplus lfsr2_i(1) \oplus lfsr1_{i+T}(1) \oplus lfsr2_{i+T}(1)]$都一样，所以做统计发现分布不符合随机分布的话，就说明T正确了

有了正确的T之后，我们就可以确定我们获得的异或比特满足：

我们选取这些异或比特统计数据偏差较大的值（偏差大一些说明更可信），就可以确定下来一个比特等于：

搜集足够的比特来解线性方程即可。

说实话后面这部分实在感觉写不明白了，详情参考exp吧

这种方法对于解题来说做不到百分百成功率，导致失败的原因有：

  • 需要周期T较小来提供更多异或比特来进行统计，所以T较大时解不出来
  • 要搜集够256个线性无关的bit才能解出唯一seed，实际上这很难

不过解决的思路很简单粗暴，就反复重连就可以了。

exp：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
from Crypto.Util.number import *
from itertools import product
from hashlib import sha256
import string
from pwn import *

def proof_of_work():
    table = string.digits + string.ascii_letters
    sh.recvuntil(b"|    sha256(XXXX + ")
    temp = sh.recvline()
    suffix = temp[:16].decode()
    hex1 = temp[20:].strip().decode()
    for i in product(table, repeat=4):
        temp1 = "".join(i)
        if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
            sh.recvuntil(b"|    XXXX>")
            sh.sendline(temp1.encode())
            return

while(1):
    #sh = remote("node6.anna.nssctf.cn", 27126) #seems broken
    sh = process(["python3", "task.py"])
    proof_of_work()


    sh.recvuntil(b"|  masks = ")
    masks = eval(sh.recvline().strip().decode())
    sh.recvuntil(b"|  args>")
    sh.sendline(b"1") #256, 256
    n, m = 255, 256

    output = []
    for i in range(n):
        sh.recvuntil(b"|  inp>")
        sh.sendline(b"h")
        sh.recvuntil(b"|  bits.hex() =")
        output.append(bytes.fromhex(sh.recvline().strip().decode()[1:-1]))


    ################################################################## statistics
    from tqdm import *
    output_bin = [bin(bytes_to_long(i))[2:].zfill(8*m) for i in output]

    ################################## part1 confirm T
    for T in trange(10, 300):
        nums = 8*m // T
        chunks = [[] for i in range(n)]
        for i in range(n):
            for j in range(nums):
                chunks[i].append(output_bin[i][j*T:(j+1)*T])
        
        xor_chunks = [[] for i in range(n)]
        for i in range(n):
            for j in range(1, nums):
                xor_chunks[i].append(bin(int(chunks[i][0],2) ^^ int(chunks[i][j],2))[2:].zfill(T))
        
        Find = 0
        for k in range(nums-1):
            bin_chunks = []
            for j in range(T):
                temp = ""
                for i in range(n):
                    temp += xor_chunks[i][k][j]
                bin_chunks.append(temp)
            for i in range(T):
                if(bin_chunks[i].count("0") < 100 or bin_chunks[i].count("1") < 100):
                    Find += 1
                    break
        if(Find == nums-1):
            print(T)
            break
    
    ################################## part2 get nfsr output
    nums = 8*m // T
    chunks = [[] for i in range(n)]
    for i in range(n):
        for j in range(nums):
            chunks[i].append(output_bin[i][j*T:(j+1)*T])

    xor_chunks = [[] for i in range(n)]
    for i in range(n):
        for j in range(1, nums):
            xor_chunks[i].append(bin(int(chunks[i][0],2) ^^ int(chunks[i][j],2))[2:].zfill(T))

    known_bits = []
    for k in range(nums-1):
        bin_chunks = []
        for j in range(T):
            temp = ""
            for i in range(n):
                temp += xor_chunks[i][k][j]
            bin_chunks.append(temp)
        
        for j in range(T):
            if(abs(bin_chunks[j].count("0")-128) > 21):
                known_bits.append([j, k, int(bin_chunks[j].count("0") < 128)])
    print(known_bits)
    print(len(known_bits))

    nbit = 128
    L1 = Matrix(GF(2), nbit, nbit)
    L2 = Matrix(GF(2), nbit, nbit)
    for i in range(nbit-1):
        L1[i, i+1] = 1
        L2[i, i+1] = 1
    for i in range(nbit):
        L1[-1, i] = int(bin(masks[0])[2:].zfill(nbit)[i])
        L2[-1, i] = int(bin(masks[1])[2:].zfill(nbit)[i])

    L = Matrix(GF(2), 0, 256)
    R = []
    for i in known_bits:
        a, b, bit = i
        temp1 = ((L1^(a+1) + L1^((b+1)*T+(a+1)))[-1]).list()
        temp2 = ((L2^(a+1) + L2^((b+1)*T+(a+1)))[-1]).list()
        L = L.stack(vector(GF(2), temp1+temp2))
        R.append(bit)

    R = vector(GF(2), R)
    SEED = L.solve_right(R)
    print(L.rank())

    SEEDS = [int("".join(list(map(str, SEED[:128]))), 2), int("".join(list(map(str, SEED[128:]))), 2)]
    print(SEEDS)
    if(L.rank() >= 255):
        sh.recvuntil(b"|  inp>")
        sh.sendline(b"s")
        sh.recvuntil(b'|  seed>')
        sh.sendline(str(SEEDS[0]).encode())
        sh.recvuntil(b'|  seed>')
        sh.sendline(str(SEEDS[1]).encode())

        print(sh.recvline())
        break

    sh.close()



决赛

piff

题目：

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
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
import random

def pad(msg):
    return msg + bytes([16 - len(msg) % 16]) * (16 - len(msg) % 16)

def generate_irreducible_polynomial(R, n):
    while True: 
        f = R.random_element(degree=n) 
        while f.degree() != n:
            f = R.random_element(degree=n) 
        if f.is_irreducible():
            return f

def get_phi(R, t, stri):
    t_str = str(t).split("a |--> ")[1].replace(stri,"x")
    return R(t_str)

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen() 
f = generate_irreducible_polynomial(R,n).monic()
F1 = generate_irreducible_polynomial(R,n).monic()
F2 = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q^n, name = 'a', modulus = f)
k2 = GF(q^n, name = 'b', modulus = F1)
k3 = GF(q^n, name = 'c', modulus = F2)

t1 = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 
t2 = FiniteFieldHomomorphism_generic(Hom(k1, k3))
phi1 = get_phi(R, t1, "b")
phi2 = get_phi(R, t2, "c")

k = [random.choice([0,1]) for _ in range(128)]
r = [random.choice([0,1]) for _ in range(128)]
m,r = R(k),R(r)
p = 2

C = (p*phi1(x)*r(phi1(x)) + m(phi1(x))) % F1(x) 
key = int(''.join(str(i) for i in k) , 2)
aes = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
cipher = aes.encrypt(pad(flag))

print("F1 = {}".format(F1))
print("φ1 = {}".format(phi1))
print("F2 = {}".format(F2))
print("φ2 = {}".format(phi2))
print("C={}".format(C))
print("cipher={}".format(cipher))
"""
F1 = x^128 + 25*x^127 + 32*x^126 + 15*x^125 + 8*x^124 + 24*x^123 + 5*x^122 + 16*x^121 + 27*x^120 + 33*x^119 + 32*x^118 + 11*x^117 + 37*x^116 + 9*x^115 + 23*x^114 + 29*x^113 + 30*x^112 + 14*x^111 + 6*x^110 + 38*x^109 + 22*x^108 + 39*x^106 + 16*x^105 + 19*x^104 + 15*x^103 + 31*x^102 + 33*x^101 + 39*x^100 + 7*x^99 + 3*x^98 + 30*x^97 + 34*x^95 + 15*x^94 + 28*x^93 + 40*x^92 + 29*x^91 + 30*x^90 + 35*x^89 + 34*x^88 + 29*x^87 + 11*x^86 + 6*x^85 + 28*x^84 + x^83 + 12*x^82 + 2*x^81 + 7*x^80 + 12*x^79 + 5*x^78 + 35*x^77 + 6*x^76 + 23*x^75 + 21*x^74 + 6*x^73 + 32*x^72 + 23*x^71 + 11*x^70 + 8*x^69 + 18*x^68 + 38*x^67 + 13*x^66 + 38*x^64 + 19*x^63 + 36*x^62 + 21*x^61 + 12*x^60 + 28*x^59 + 22*x^58 + 19*x^57 + 8*x^56 + 7*x^55 + 34*x^54 + 9*x^53 + 15*x^52 + 37*x^51 + 6*x^50 + 22*x^49 + 19*x^48 + 33*x^47 + 2*x^46 + x^45 + 17*x^44 + 20*x^43 + 7*x^42 + 37*x^41 + 10*x^40 + 13*x^39 + 2*x^38 + 22*x^37 + 32*x^36 + 40*x^35 + 3*x^34 + 40*x^33 + 23*x^32 + 3*x^31 + 15*x^30 + 14*x^29 + 40*x^28 + 33*x^27 + 31*x^26 + 7*x^25 + 18*x^24 + 23*x^23 + 3*x^22 + 35*x^21 + 2*x^20 + 32*x^19 + 3*x^18 + 39*x^17 + 20*x^16 + 40*x^15 + 25*x^14 + 38*x^13 + 14*x^12 + 11*x^11 + 13*x^10 + 16*x^9 + 3*x^8 + 39*x^7 + 29*x^6 + 7*x^5 + 26*x^4 + 9*x^3 + 25*x^2 + 8*x + 4
φ1 = 22*x^126 + 37*x^125 + 33*x^124 + 23*x^123 + 9*x^122 + 12*x^121 + 22*x^120 + 7*x^119 + 12*x^118 + 23*x^117 + 22*x^116 + 16*x^115 + 12*x^114 + 6*x^113 + 23*x^112 + 9*x^111 + 9*x^110 + 23*x^109 + 27*x^108 + 38*x^107 + 21*x^106 + 38*x^105 + 19*x^103 + 12*x^102 + 20*x^101 + x^100 + 36*x^99 + 15*x^98 + 26*x^97 + 14*x^96 + 4*x^95 + 39*x^94 + 29*x^93 + 13*x^92 + 11*x^91 + 24*x^90 + 28*x^89 + 40*x^88 + 6*x^87 + x^86 + 30*x^85 + 33*x^84 + 21*x^83 + 38*x^82 + 24*x^81 + 3*x^80 + 29*x^79 + 32*x^78 + 14*x^77 + 28*x^76 + 19*x^75 + 21*x^74 + 16*x^73 + 32*x^72 + 4*x^71 + 24*x^70 + 30*x^69 + 18*x^68 + 19*x^67 + 16*x^66 + 12*x^65 + 24*x^64 + 26*x^63 + 10*x^62 + 25*x^61 + 15*x^60 + 22*x^59 + 35*x^58 + 27*x^57 + 35*x^56 + 25*x^55 + 3*x^54 + 4*x^53 + 27*x^52 + 12*x^51 + 20*x^50 + 29*x^49 + 29*x^48 + 11*x^47 + 34*x^46 + 13*x^45 + 5*x^44 + 5*x^43 + 26*x^42 + 29*x^41 + 15*x^40 + 21*x^39 + 24*x^38 + 26*x^37 + 2*x^36 + 22*x^35 + 40*x^34 + 14*x^33 + x^32 + 28*x^31 + 28*x^30 + 29*x^29 + 31*x^28 + 12*x^27 + 10*x^26 + 35*x^25 + 5*x^24 + 18*x^23 + 23*x^22 + 33*x^21 + 21*x^20 + 37*x^19 + 30*x^18 + 19*x^17 + 37*x^16 + 8*x^15 + 34*x^14 + 25*x^13 + 29*x^12 + 29*x^11 + 8*x^10 + 19*x^9 + 40*x^8 + 35*x^7 + 18*x^6 + 2*x^5 + 32*x^4 + 3*x^3 + 11*x^2 + 10*x + 36
F2 = x^128 + 39*x^127 + 16*x^126 + 24*x^125 + 18*x^124 + 31*x^123 + 12*x^122 + 37*x^121 + 11*x^120 + 15*x^119 + 34*x^118 + 25*x^117 + 27*x^116 + 4*x^115 + 16*x^114 + 18*x^113 + 31*x^112 + 40*x^111 + 9*x^110 + 15*x^109 + 23*x^108 + 24*x^107 + 26*x^106 + 6*x^105 + 32*x^104 + 16*x^103 + 38*x^102 + 2*x^101 + 3*x^100 + 40*x^99 + 30*x^98 + 27*x^97 + 24*x^96 + 7*x^95 + 40*x^94 + 28*x^93 + 11*x^92 + 30*x^91 + 36*x^90 + x^89 + 16*x^88 + 36*x^87 + 14*x^86 + x^84 + 33*x^83 + 5*x^82 + 15*x^81 + 33*x^80 + 28*x^79 + 39*x^78 + 16*x^77 + 29*x^76 + 34*x^75 + 38*x^74 + 34*x^73 + 25*x^72 + 9*x^71 + 5*x^70 + 19*x^69 + 39*x^68 + 23*x^67 + x^66 + 4*x^65 + 11*x^64 + 15*x^63 + 25*x^62 + 36*x^61 + 40*x^60 + 18*x^59 + 14*x^58 + 2*x^57 + 4*x^56 + 2*x^55 + 26*x^54 + 13*x^53 + 17*x^52 + 38*x^51 + 12*x^50 + 12*x^49 + 18*x^48 + 40*x^47 + 10*x^46 + 17*x^45 + 37*x^44 + 34*x^43 + 34*x^42 + 25*x^41 + 16*x^40 + 16*x^39 + 11*x^38 + 36*x^36 + 31*x^35 + 4*x^33 + 17*x^32 + 8*x^31 + 17*x^30 + 30*x^29 + 30*x^28 + 26*x^27 + 21*x^26 + 29*x^25 + 15*x^24 + 38*x^23 + 19*x^22 + 24*x^21 + 7*x^20 + 5*x^19 + 2*x^18 + 31*x^17 + 13*x^16 + 14*x^15 + 40*x^14 + 29*x^13 + 30*x^12 + 37*x^11 + 33*x^10 + 11*x^9 + 12*x^8 + 14*x^7 + 34*x^6 + 18*x^5 + 13*x^4 + 11*x^3 + 31*x^2 + 31*x + 25
φ2 = 29*x^126 + 38*x^125 + 25*x^124 + 11*x^123 + 13*x^122 + 23*x^121 + 2*x^120 + 34*x^119 + 3*x^118 + 40*x^117 + 19*x^116 + 17*x^115 + 31*x^114 + 6*x^113 + 28*x^112 + 34*x^111 + 37*x^110 + 25*x^109 + 39*x^108 + x^107 + 33*x^106 + 11*x^105 + 8*x^104 + 37*x^103 + 26*x^102 + 27*x^101 + 10*x^100 + 10*x^99 + 26*x^97 + 31*x^96 + 13*x^95 + 26*x^94 + 32*x^93 + 21*x^92 + 14*x^91 + 23*x^90 + 14*x^89 + 12*x^88 + 36*x^87 + 35*x^86 + 10*x^85 + 16*x^84 + 6*x^83 + x^82 + 13*x^81 + 23*x^80 + 27*x^79 + 23*x^78 + 31*x^77 + 2*x^76 + 7*x^75 + 39*x^74 + 17*x^73 + 23*x^72 + 3*x^71 + 37*x^70 + 17*x^69 + 17*x^68 + 29*x^67 + 4*x^66 + 30*x^65 + 11*x^64 + 21*x^63 + 11*x^62 + 8*x^61 + 32*x^60 + 26*x^59 + 7*x^58 + 37*x^57 + 4*x^55 + 26*x^54 + 37*x^53 + 27*x^52 + 40*x^51 + 6*x^50 + 9*x^49 + 14*x^48 + 23*x^47 + 9*x^46 + 18*x^45 + 21*x^44 + 37*x^43 + 13*x^42 + 24*x^41 + 11*x^40 + 40*x^39 + 5*x^38 + 32*x^37 + 7*x^36 + 31*x^35 + 4*x^34 + 12*x^33 + 24*x^32 + 40*x^31 + 16*x^30 + 23*x^29 + 29*x^28 + 12*x^27 + 32*x^26 + 25*x^25 + 12*x^24 + x^23 + 5*x^22 + 30*x^21 + 30*x^20 + 17*x^19 + 24*x^17 + 17*x^16 + 18*x^15 + 31*x^14 + 37*x^13 + 18*x^12 + 14*x^11 + 5*x^10 + 2*x^9 + 23*x^8 + 21*x^7 + 29*x^6 + 39*x^5 + 13*x^3 + 13*x^2 + 25*x + 30
C=20*x^127 + 31*x^126 + 21*x^125 + 19*x^124 + 30*x^123 + 4*x^122 + 32*x^121 + 19*x^120 + 24*x^119 + 33*x^118 + 40*x^117 + 39*x^116 + 3*x^115 + 32*x^113 + 24*x^112 + 31*x^111 + 15*x^110 + 7*x^109 + 25*x^108 + 16*x^107 + 13*x^106 + 5*x^105 + 11*x^104 + 38*x^103 + 38*x^102 + 28*x^101 + 33*x^100 + 32*x^99 + 24*x^98 + 26*x^97 + 36*x^96 + 32*x^95 + 38*x^94 + 26*x^93 + 28*x^91 + 37*x^90 + 35*x^89 + 25*x^88 + 14*x^87 + 9*x^86 + 33*x^85 + 15*x^84 + 18*x^83 + 12*x^82 + 34*x^81 + 12*x^80 + 35*x^79 + 40*x^78 + 9*x^77 + 23*x^76 + 23*x^75 + 12*x^74 + 7*x^73 + 27*x^72 + 7*x^71 + 14*x^69 + 40*x^68 + 34*x^66 + 39*x^65 + 30*x^64 + 23*x^63 + 8*x^62 + 28*x^61 + 37*x^60 + 34*x^59 + 35*x^58 + 33*x^57 + 3*x^56 + 28*x^55 + 39*x^54 + 13*x^53 + 31*x^52 + 7*x^51 + 38*x^49 + 40*x^48 + 11*x^47 + 30*x^46 + 19*x^45 + 38*x^44 + 37*x^43 + 21*x^42 + 9*x^41 + 8*x^40 + 31*x^39 + 22*x^38 + 24*x^37 + 8*x^36 + 17*x^35 + 16*x^34 + 29*x^33 + 32*x^32 + 17*x^31 + 39*x^30 + 20*x^29 + 4*x^27 + 40*x^26 + 6*x^24 + 27*x^23 + 25*x^22 + 4*x^21 + 5*x^20 + 8*x^19 + 28*x^18 + 21*x^17 + x^16 + 12*x^15 + 19*x^14 + 29*x^13 + 2*x^12 + 9*x^11 + 34*x^10 + 16*x^9 + 12*x^8 + 21*x^7 + 8*x^6 + 23*x^5 + 37*x^4 + 31*x^3 + 25*x^2 + 20*x + 21
cipher=b'\xc9\xe2\xcdzo\xa1\xcc\xe1\x0e(\x98W\xd3\xb9\x85X\xa3!P\xab\x00\x1cR r\xb4\xb8\xed\x8f\x83\x15r'
"""

这个题目和强网杯的electronic game有一定相关性：

2024-强网杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

所以接下来某些部分的推导可以看上面这篇文章。

题目在模$q=41$下先生成三个度为128的不可约多项式$f(x),F_1(x),F_2(x)$，并定义三个有限域$k_1,k_2,k_3$，分别以这三个不可约多项式作为模多项式，并定义两个同态：

之后生成两个系数均由0、1组成的多项式$m(x),r(x)$，并在模$F_1$下计算：

给出$F_1(x),\phi_1(x),F_2(x),\phi_2(x),C(x)$，要求解出$m(x)$从而解AES得到flag。

思路一

在强网杯的electronic game里推导过同态的矩阵表示，记k1表示的矩阵为$M_1$，他就满足：

1
M1 = matrix([(core**i).list() for i in range(n)])

这里的$M_1$是个n阶方阵，而实际上在强网杯那题里面用的是：

1
matrix([(core**i).list() for i in range(n+1)])

记这个矩阵为$M_1’$，他并不是一个方阵，而是129x128的矩阵。

但实际上两者没有什么区别，假设现在有多项式$a(x)\in k_1,b(x) \in k_2$满足：

那么把$a(x),b(x)$都表示为长为128的向量$a,b$，就有：

而实际上，把a表示成长为129的向量$a’$（$x^{128}$位置置0即可），那么就满足：

所以实际上没什么区别，唯一的区别在于如果把$k_1$的模多项式$f(x)$表示成向量$f$的话，由于他的度是128，所以只能表示成长129的向量，因此只能用$M_1’$来进行运算，并且满足：

这里有一个有趣的事实，那就是$f$向量就是$M_1’$的左核

有了$M_1$之后，由于在商环下进行多项式乘法也可以用矩阵表示，所以可以把乘$\phi_1(x)$对应的矩阵记为矩阵$M_2$，所以$C$的计算过程就可以从多项式完全转成矩阵方程：

由于$m,r$都是0、1组成的向量，所以在模41下会比较小，因此可以稍作优化，用如下矩阵方程去LLL一下：

如预期一样可以在LLL之后的向量找到$r,m$，之后就解AES就好了。

exp：

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
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen()

F1 = x^128 + 25*x^127 + 32*x^126 + 15*x^125 + 8*x^124 + 24*x^123 + 5*x^122 + 16*x^121 + 27*x^120 + 33*x^119 + 32*x^118 + 11*x^117 + 37*x^116 + 9*x^115 + 23*x^114 + 29*x^113 + 30*x^112 + 14*x^111 + 6*x^110 + 38*x^109 + 22*x^108 + 39*x^106 + 16*x^105 + 19*x^104 + 15*x^103 + 31*x^102 + 33*x^101 + 39*x^100 + 7*x^99 + 3*x^98 + 30*x^97 + 34*x^95 + 15*x^94 + 28*x^93 + 40*x^92 + 29*x^91 + 30*x^90 + 35*x^89 + 34*x^88 + 29*x^87 + 11*x^86 + 6*x^85 + 28*x^84 + x^83 + 12*x^82 + 2*x^81 + 7*x^80 + 12*x^79 + 5*x^78 + 35*x^77 + 6*x^76 + 23*x^75 + 21*x^74 + 6*x^73 + 32*x^72 + 23*x^71 + 11*x^70 + 8*x^69 + 18*x^68 + 38*x^67 + 13*x^66 + 38*x^64 + 19*x^63 + 36*x^62 + 21*x^61 + 12*x^60 + 28*x^59 + 22*x^58 + 19*x^57 + 8*x^56 + 7*x^55 + 34*x^54 + 9*x^53 + 15*x^52 + 37*x^51 + 6*x^50 + 22*x^49 + 19*x^48 + 33*x^47 + 2*x^46 + x^45 + 17*x^44 + 20*x^43 + 7*x^42 + 37*x^41 + 10*x^40 + 13*x^39 + 2*x^38 + 22*x^37 + 32*x^36 + 40*x^35 + 3*x^34 + 40*x^33 + 23*x^32 + 3*x^31 + 15*x^30 + 14*x^29 + 40*x^28 + 33*x^27 + 31*x^26 + 7*x^25 + 18*x^24 + 23*x^23 + 3*x^22 + 35*x^21 + 2*x^20 + 32*x^19 + 3*x^18 + 39*x^17 + 20*x^16 + 40*x^15 + 25*x^14 + 38*x^13 + 14*x^12 + 11*x^11 + 13*x^10 + 16*x^9 + 3*x^8 + 39*x^7 + 29*x^6 + 7*x^5 + 26*x^4 + 9*x^3 + 25*x^2 + 8*x + 4
φ1 = 22*x^126 + 37*x^125 + 33*x^124 + 23*x^123 + 9*x^122 + 12*x^121 + 22*x^120 + 7*x^119 + 12*x^118 + 23*x^117 + 22*x^116 + 16*x^115 + 12*x^114 + 6*x^113 + 23*x^112 + 9*x^111 + 9*x^110 + 23*x^109 + 27*x^108 + 38*x^107 + 21*x^106 + 38*x^105 + 19*x^103 + 12*x^102 + 20*x^101 + x^100 + 36*x^99 + 15*x^98 + 26*x^97 + 14*x^96 + 4*x^95 + 39*x^94 + 29*x^93 + 13*x^92 + 11*x^91 + 24*x^90 + 28*x^89 + 40*x^88 + 6*x^87 + x^86 + 30*x^85 + 33*x^84 + 21*x^83 + 38*x^82 + 24*x^81 + 3*x^80 + 29*x^79 + 32*x^78 + 14*x^77 + 28*x^76 + 19*x^75 + 21*x^74 + 16*x^73 + 32*x^72 + 4*x^71 + 24*x^70 + 30*x^69 + 18*x^68 + 19*x^67 + 16*x^66 + 12*x^65 + 24*x^64 + 26*x^63 + 10*x^62 + 25*x^61 + 15*x^60 + 22*x^59 + 35*x^58 + 27*x^57 + 35*x^56 + 25*x^55 + 3*x^54 + 4*x^53 + 27*x^52 + 12*x^51 + 20*x^50 + 29*x^49 + 29*x^48 + 11*x^47 + 34*x^46 + 13*x^45 + 5*x^44 + 5*x^43 + 26*x^42 + 29*x^41 + 15*x^40 + 21*x^39 + 24*x^38 + 26*x^37 + 2*x^36 + 22*x^35 + 40*x^34 + 14*x^33 + x^32 + 28*x^31 + 28*x^30 + 29*x^29 + 31*x^28 + 12*x^27 + 10*x^26 + 35*x^25 + 5*x^24 + 18*x^23 + 23*x^22 + 33*x^21 + 21*x^20 + 37*x^19 + 30*x^18 + 19*x^17 + 37*x^16 + 8*x^15 + 34*x^14 + 25*x^13 + 29*x^12 + 29*x^11 + 8*x^10 + 19*x^9 + 40*x^8 + 35*x^7 + 18*x^6 + 2*x^5 + 32*x^4 + 3*x^3 + 11*x^2 + 10*x + 36
C = 20*x^127 + 31*x^126 + 21*x^125 + 19*x^124 + 30*x^123 + 4*x^122 + 32*x^121 + 19*x^120 + 24*x^119 + 33*x^118 + 40*x^117 + 39*x^116 + 3*x^115 + 32*x^113 + 24*x^112 + 31*x^111 + 15*x^110 + 7*x^109 + 25*x^108 + 16*x^107 + 13*x^106 + 5*x^105 + 11*x^104 + 38*x^103 + 38*x^102 + 28*x^101 + 33*x^100 + 32*x^99 + 24*x^98 + 26*x^97 + 36*x^96 + 32*x^95 + 38*x^94 + 26*x^93 + 28*x^91 + 37*x^90 + 35*x^89 + 25*x^88 + 14*x^87 + 9*x^86 + 33*x^85 + 15*x^84 + 18*x^83 + 12*x^82 + 34*x^81 + 12*x^80 + 35*x^79 + 40*x^78 + 9*x^77 + 23*x^76 + 23*x^75 + 12*x^74 + 7*x^73 + 27*x^72 + 7*x^71 + 14*x^69 + 40*x^68 + 34*x^66 + 39*x^65 + 30*x^64 + 23*x^63 + 8*x^62 + 28*x^61 + 37*x^60 + 34*x^59 + 35*x^58 + 33*x^57 + 3*x^56 + 28*x^55 + 39*x^54 + 13*x^53 + 31*x^52 + 7*x^51 + 38*x^49 + 40*x^48 + 11*x^47 + 30*x^46 + 19*x^45 + 38*x^44 + 37*x^43 + 21*x^42 + 9*x^41 + 8*x^40 + 31*x^39 + 22*x^38 + 24*x^37 + 8*x^36 + 17*x^35 + 16*x^34 + 29*x^33 + 32*x^32 + 17*x^31 + 39*x^30 + 20*x^29 + 4*x^27 + 40*x^26 + 6*x^24 + 27*x^23 + 25*x^22 + 4*x^21 + 5*x^20 + 8*x^19 + 28*x^18 + 21*x^17 + x^16 + 12*x^15 + 19*x^14 + 29*x^13 + 2*x^12 + 9*x^11 + 34*x^10 + 16*x^9 + 12*x^8 + 21*x^7 + 8*x^6 + 23*x^5 + 37*x^4 + 31*x^3 + 25*x^2 + 20*x + 21
cipher=b'\xc9\xe2\xcdzo\xa1\xcc\xe1\x0e(\x98W\xd3\xb9\x85X\xa3!P\xab\x00\x1cR r\xb4\xb8\xed\x8f\x83\x15r'

######################################################### test
import random
k1 = GF(q^n, name = 'b', modulus = F1)
b = k1.gen()
core = 22*b^126 + 37*b^125 + 33*b^124 + 23*b^123 + 9*b^122 + 12*b^121 + 22*b^120 + 7*b^119 + 12*b^118 + 23*b^117 + 22*b^116 + 16*b^115 + 12*b^114 + 6*b^113 + 23*b^112 + 9*b^111 + 9*b^110 + 23*b^109 + 27*b^108 + 38*b^107 + 21*b^106 + 38*b^105 + 19*b^103 + 12*b^102 + 20*b^101 + b^100 + 36*b^99 + 15*b^98 + 26*b^97 + 14*b^96 + 4*b^95 + 39*b^94 + 29*b^93 + 13*b^92 + 11*b^91 + 24*b^90 + 28*b^89 + 40*b^88 + 6*b^87 + b^86 + 30*b^85 + 33*b^84 + 21*b^83 + 38*b^82 + 24*b^81 + 3*b^80 + 29*b^79 + 32*b^78 + 14*b^77 + 28*b^76 + 19*b^75 + 21*b^74 + 16*b^73 + 32*b^72 + 4*b^71 + 24*b^70 + 30*b^69 + 18*b^68 + 19*b^67 + 16*b^66 + 12*b^65 + 24*b^64 + 26*b^63 + 10*b^62 + 25*b^61 + 15*b^60 + 22*b^59 + 35*b^58 + 27*b^57 + 35*b^56 + 25*b^55 + 3*b^54 + 4*b^53 + 27*b^52 + 12*b^51 + 20*b^50 + 29*b^49 + 29*b^48 + 11*b^47 + 34*b^46 + 13*b^45 + 5*b^44 + 5*b^43 + 26*b^42 + 29*b^41 + 15*b^40 + 21*b^39 + 24*b^38 + 26*b^37 + 2*b^36 + 22*b^35 + 40*b^34 + 14*b^33 + b^32 + 28*b^31 + 28*b^30 + 29*b^29 + 31*b^28 + 12*b^27 + 10*b^26 + 35*b^25 + 5*b^24 + 18*b^23 + 23*b^22 + 33*b^21 + 21*b^20 + 37*b^19 + 30*b^18 + 19*b^17 + 37*b^16 + 8*b^15 + 34*b^14 + 25*b^13 + 29*b^12 + 29*b^11 + 8*b^10 + 19*b^9 + 40*b^8 + 35*b^7 + 18*b^6 + 2*b^5 + 32*b^4 + 3*b^3 + 11*b^2 + 10*b + 36
M1 = matrix([(core**i).list() for i in range(n)])
k = [random.choice([0,1]) for _ in range(128)]
r = [random.choice([0,1]) for _ in range(128)]
rr = vector(GF(q), r)
m,r = R(k),R(r)

assert (r(φ1) % F1).list() == (rr * M1).list()
######################################################### test

def construct_poly_mul_mat(n,v,b):
    assert v[-1] == 1 #use this after monic

    #step1 construct a matrix of d=a*b
    mat1 = Matrix(ZZ,n,2*n-1)
    for i in range(n):
        for j in range(n):
            mat1[i,j+i] = b[j] 

    #step2 construct a matrix of c=d%v
    mat2 = Matrix(ZZ,2*n-1,n)
    for i in range(n):
        mat2[i,i] = 1
    for i in range(n,2*n-1):
        for j in range(i-n,n):
            mat2[i,j] = -v[j-(i-n)]
        
        init_row = vector(ZZ,n*[0])
        for j in range(i-n):
            temp = -v[n-1-j]*vector(ZZ,mat2[i-j-1])
            init_row += temp
        for j in range(n):
            mat2[i,j] += init_row[j]   
             
    #step3 multiply them and return
    return(mat1*mat2)

PRp.<x> = PolynomialRing(Zmod(q))
f = F1
v = f.list()
M2 = construct_poly_mul_mat(n,v,φ1(x).list()+[0]*2)

assert ((φ1(x)*r(φ1(x))) % F1(x)).list() == (rr * M1 * M2).list()

# know that 2*rr*M1*M2 + mm*M1 =  CC (mod q)
# -> 2*rr*M1*M2*M1^(-1) + mm =  CC*M1^(-1) (mod q)

M = 2*M1*M2*M1^(-1)
CC = vector(GF(q), C)
L = block_matrix(ZZ,[
    [-q, 0, 0],
    [-M, 1, 0],
    [Matrix(ZZ, (CC*M1^(-1)).list()), 0, 1]
])
L = L.LLL()
for i in L:
    if(all(abs(j) <= 1 for j in i)):
        m = i[:128]
        key = int(''.join(str(jj) for jj in m) , 2)
        aes = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
        flag = aes.decrypt(cipher)
        print(flag)
        break

#flag{eZ_iSOrmOr9h1sm_Y0u_kn0w}

思路二

而做完后会发现，有几个东西似乎没有用上：

  • $F_2(x)$
  • 计算$C(x)$时乘的那个2（因为乘多少都不影响用LLL解）

所以预期应该不是这样的，0、1向量的作用不应该是短向量，而应该是要到模2下解才对。

而这很简单，回顾$C$对应的矩阵方程：

和刚才一样有：

这样求逆其实就是$\phi_1$对应的逆而已，所以此时得到的其实是：

也就是：

因为$r(x),m(x)$系数都是0或者1，所以这个多项式乘法不可能超过$q=41$，所以实际上直接模2就是向量$m$了。

exp：

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 sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen()

F1 = x^128 + 25*x^127 + 32*x^126 + 15*x^125 + 8*x^124 + 24*x^123 + 5*x^122 + 16*x^121 + 27*x^120 + 33*x^119 + 32*x^118 + 11*x^117 + 37*x^116 + 9*x^115 + 23*x^114 + 29*x^113 + 30*x^112 + 14*x^111 + 6*x^110 + 38*x^109 + 22*x^108 + 39*x^106 + 16*x^105 + 19*x^104 + 15*x^103 + 31*x^102 + 33*x^101 + 39*x^100 + 7*x^99 + 3*x^98 + 30*x^97 + 34*x^95 + 15*x^94 + 28*x^93 + 40*x^92 + 29*x^91 + 30*x^90 + 35*x^89 + 34*x^88 + 29*x^87 + 11*x^86 + 6*x^85 + 28*x^84 + x^83 + 12*x^82 + 2*x^81 + 7*x^80 + 12*x^79 + 5*x^78 + 35*x^77 + 6*x^76 + 23*x^75 + 21*x^74 + 6*x^73 + 32*x^72 + 23*x^71 + 11*x^70 + 8*x^69 + 18*x^68 + 38*x^67 + 13*x^66 + 38*x^64 + 19*x^63 + 36*x^62 + 21*x^61 + 12*x^60 + 28*x^59 + 22*x^58 + 19*x^57 + 8*x^56 + 7*x^55 + 34*x^54 + 9*x^53 + 15*x^52 + 37*x^51 + 6*x^50 + 22*x^49 + 19*x^48 + 33*x^47 + 2*x^46 + x^45 + 17*x^44 + 20*x^43 + 7*x^42 + 37*x^41 + 10*x^40 + 13*x^39 + 2*x^38 + 22*x^37 + 32*x^36 + 40*x^35 + 3*x^34 + 40*x^33 + 23*x^32 + 3*x^31 + 15*x^30 + 14*x^29 + 40*x^28 + 33*x^27 + 31*x^26 + 7*x^25 + 18*x^24 + 23*x^23 + 3*x^22 + 35*x^21 + 2*x^20 + 32*x^19 + 3*x^18 + 39*x^17 + 20*x^16 + 40*x^15 + 25*x^14 + 38*x^13 + 14*x^12 + 11*x^11 + 13*x^10 + 16*x^9 + 3*x^8 + 39*x^7 + 29*x^6 + 7*x^5 + 26*x^4 + 9*x^3 + 25*x^2 + 8*x + 4
φ1 = 22*x^126 + 37*x^125 + 33*x^124 + 23*x^123 + 9*x^122 + 12*x^121 + 22*x^120 + 7*x^119 + 12*x^118 + 23*x^117 + 22*x^116 + 16*x^115 + 12*x^114 + 6*x^113 + 23*x^112 + 9*x^111 + 9*x^110 + 23*x^109 + 27*x^108 + 38*x^107 + 21*x^106 + 38*x^105 + 19*x^103 + 12*x^102 + 20*x^101 + x^100 + 36*x^99 + 15*x^98 + 26*x^97 + 14*x^96 + 4*x^95 + 39*x^94 + 29*x^93 + 13*x^92 + 11*x^91 + 24*x^90 + 28*x^89 + 40*x^88 + 6*x^87 + x^86 + 30*x^85 + 33*x^84 + 21*x^83 + 38*x^82 + 24*x^81 + 3*x^80 + 29*x^79 + 32*x^78 + 14*x^77 + 28*x^76 + 19*x^75 + 21*x^74 + 16*x^73 + 32*x^72 + 4*x^71 + 24*x^70 + 30*x^69 + 18*x^68 + 19*x^67 + 16*x^66 + 12*x^65 + 24*x^64 + 26*x^63 + 10*x^62 + 25*x^61 + 15*x^60 + 22*x^59 + 35*x^58 + 27*x^57 + 35*x^56 + 25*x^55 + 3*x^54 + 4*x^53 + 27*x^52 + 12*x^51 + 20*x^50 + 29*x^49 + 29*x^48 + 11*x^47 + 34*x^46 + 13*x^45 + 5*x^44 + 5*x^43 + 26*x^42 + 29*x^41 + 15*x^40 + 21*x^39 + 24*x^38 + 26*x^37 + 2*x^36 + 22*x^35 + 40*x^34 + 14*x^33 + x^32 + 28*x^31 + 28*x^30 + 29*x^29 + 31*x^28 + 12*x^27 + 10*x^26 + 35*x^25 + 5*x^24 + 18*x^23 + 23*x^22 + 33*x^21 + 21*x^20 + 37*x^19 + 30*x^18 + 19*x^17 + 37*x^16 + 8*x^15 + 34*x^14 + 25*x^13 + 29*x^12 + 29*x^11 + 8*x^10 + 19*x^9 + 40*x^8 + 35*x^7 + 18*x^6 + 2*x^5 + 32*x^4 + 3*x^3 + 11*x^2 + 10*x + 36
C = 20*x^127 + 31*x^126 + 21*x^125 + 19*x^124 + 30*x^123 + 4*x^122 + 32*x^121 + 19*x^120 + 24*x^119 + 33*x^118 + 40*x^117 + 39*x^116 + 3*x^115 + 32*x^113 + 24*x^112 + 31*x^111 + 15*x^110 + 7*x^109 + 25*x^108 + 16*x^107 + 13*x^106 + 5*x^105 + 11*x^104 + 38*x^103 + 38*x^102 + 28*x^101 + 33*x^100 + 32*x^99 + 24*x^98 + 26*x^97 + 36*x^96 + 32*x^95 + 38*x^94 + 26*x^93 + 28*x^91 + 37*x^90 + 35*x^89 + 25*x^88 + 14*x^87 + 9*x^86 + 33*x^85 + 15*x^84 + 18*x^83 + 12*x^82 + 34*x^81 + 12*x^80 + 35*x^79 + 40*x^78 + 9*x^77 + 23*x^76 + 23*x^75 + 12*x^74 + 7*x^73 + 27*x^72 + 7*x^71 + 14*x^69 + 40*x^68 + 34*x^66 + 39*x^65 + 30*x^64 + 23*x^63 + 8*x^62 + 28*x^61 + 37*x^60 + 34*x^59 + 35*x^58 + 33*x^57 + 3*x^56 + 28*x^55 + 39*x^54 + 13*x^53 + 31*x^52 + 7*x^51 + 38*x^49 + 40*x^48 + 11*x^47 + 30*x^46 + 19*x^45 + 38*x^44 + 37*x^43 + 21*x^42 + 9*x^41 + 8*x^40 + 31*x^39 + 22*x^38 + 24*x^37 + 8*x^36 + 17*x^35 + 16*x^34 + 29*x^33 + 32*x^32 + 17*x^31 + 39*x^30 + 20*x^29 + 4*x^27 + 40*x^26 + 6*x^24 + 27*x^23 + 25*x^22 + 4*x^21 + 5*x^20 + 8*x^19 + 28*x^18 + 21*x^17 + x^16 + 12*x^15 + 19*x^14 + 29*x^13 + 2*x^12 + 9*x^11 + 34*x^10 + 16*x^9 + 12*x^8 + 21*x^7 + 8*x^6 + 23*x^5 + 37*x^4 + 31*x^3 + 25*x^2 + 20*x + 21
cipher=b'\xc9\xe2\xcdzo\xa1\xcc\xe1\x0e(\x98W\xd3\xb9\x85X\xa3!P\xab\x00\x1cR r\xb4\xb8\xed\x8f\x83\x15r'

k2 = GF(q^n, name = 'b', modulus = F1)
b = k2.gen()
core1 = 22*b^126 + 37*b^125 + 33*b^124 + 23*b^123 + 9*b^122 + 12*b^121 + 22*b^120 + 7*b^119 + 12*b^118 + 23*b^117 + 22*b^116 + 16*b^115 + 12*b^114 + 6*b^113 + 23*b^112 + 9*b^111 + 9*b^110 + 23*b^109 + 27*b^108 + 38*b^107 + 21*b^106 + 38*b^105 + 19*b^103 + 12*b^102 + 20*b^101 + b^100 + 36*b^99 + 15*b^98 + 26*b^97 + 14*b^96 + 4*b^95 + 39*b^94 + 29*b^93 + 13*b^92 + 11*b^91 + 24*b^90 + 28*b^89 + 40*b^88 + 6*b^87 + b^86 + 30*b^85 + 33*b^84 + 21*b^83 + 38*b^82 + 24*b^81 + 3*b^80 + 29*b^79 + 32*b^78 + 14*b^77 + 28*b^76 + 19*b^75 + 21*b^74 + 16*b^73 + 32*b^72 + 4*b^71 + 24*b^70 + 30*b^69 + 18*b^68 + 19*b^67 + 16*b^66 + 12*b^65 + 24*b^64 + 26*b^63 + 10*b^62 + 25*b^61 + 15*b^60 + 22*b^59 + 35*b^58 + 27*b^57 + 35*b^56 + 25*b^55 + 3*b^54 + 4*b^53 + 27*b^52 + 12*b^51 + 20*b^50 + 29*b^49 + 29*b^48 + 11*b^47 + 34*b^46 + 13*b^45 + 5*b^44 + 5*b^43 + 26*b^42 + 29*b^41 + 15*b^40 + 21*b^39 + 24*b^38 + 26*b^37 + 2*b^36 + 22*b^35 + 40*b^34 + 14*b^33 + b^32 + 28*b^31 + 28*b^30 + 29*b^29 + 31*b^28 + 12*b^27 + 10*b^26 + 35*b^25 + 5*b^24 + 18*b^23 + 23*b^22 + 33*b^21 + 21*b^20 + 37*b^19 + 30*b^18 + 19*b^17 + 37*b^16 + 8*b^15 + 34*b^14 + 25*b^13 + 29*b^12 + 29*b^11 + 8*b^10 + 19*b^9 + 40*b^8 + 35*b^7 + 18*b^6 + 2*b^5 + 32*b^4 + 3*b^3 + 11*b^2 + 10*b + 36
M1 = matrix([(core1**i).list() for i in range(n)])
m = (vector(GF(q), C.list())*M1^(-1)).list()
m = [int(i) % 2 for i in m]
key = int(''.join(str(i) for i in m) , 2)
aes = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
flag = aes.decrypt(cipher)
print(flag)


#flag{eZ_iSOrmOr9h1sm_Y0u_kn0w}

然而还是没有用到$F_2$，确实也没有想到要怎么才能用上。

revenge

@peigong在NSSCTF上了一个revenge：

ZMJ4396]piff_revenge | 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
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
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
import random

def pad(msg):
    return msg + bytes([16 - len(msg) % 16]) * (16 - len(msg) % 16)

def generate_irreducible_polynomial(R, n):
    while True:
        f = R.random_element(degree=n)
        while f.degree() != n:
            f = R.random_element(degree=n)
        if f.is_irreducible():
            return f

def get_phi(R, t, strj, stri):
    t_str = str(t).split(f"{strj} |--> ")[1].replace(stri,"x")
    return R(t_str)

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen()
f = generate_irreducible_polynomial(R,n).monic()
F1 = generate_irreducible_polynomial(R,n).monic()
F2 = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q^n, name = 'a', modulus = f)
k2 = GF(q^n, name = 'b', modulus = F1)
k3 = GF(q^n, name = 'c', modulus = F2)

t1 = FiniteFieldHomomorphism_generic(Hom(k1, k2))
t2 = FiniteFieldHomomorphism_generic(Hom(k2, k3))
phi1 = get_phi(R, t1, "a", "b")
phi2 = get_phi(R, t2, "b", "c")

k1 = [random.choice([0,1]) for _ in range(128)]
r1 = [random.choice([0,1]) for _ in range(128)]
m1,r1 = R(k1),R(r1)
k2 = [random.choice([0,1]) for _ in range(128)]
r2 = [random.choice([0,1]) for _ in range(128)]
m2,r2 = R(k2),R(r2)
p = 2

C1 = (p*phi1(x)*r1(phi1(x)) + m1(phi1(x))) % F1(x)
C2 = (p*phi2(x)*r2(phi2(x)) + m2(phi2(x))) % F2(x)
key1 = int(''.join(str(i) for i in k1) , 2)
aes = AES.new(long_to_bytes(key1), mode=AES.MODE_ECB)
cipher1 = aes.encrypt(pad(flag[:len(flag)//2]))

key2 = int(''.join(str(i) for i in k2) , 2)
aes = AES.new(long_to_bytes(key2), mode=AES.MODE_ECB)
cipher2 = aes.encrypt(pad(flag[len(flag)//2:]))

print("F1 = {}".format(F1))
print("φ1 = {}".format(phi1))
print("φ2 = {}".format(phi2))
print("C1={}".format(C1))
print("C2={}".format(C2))
print("cipher1={}".format(cipher1))
print("cipher2={}".format(cipher2))
"""
F1 = x^128 + 13*x^127 + 25*x^126 + 12*x^125 + 36*x^124 + x^123 + 40*x^122 + 33*x^121 + 29*x^120 + 13*x^119 + 24*x^117 + 36*x^116 + 14*x^114 + 14*x^113 + 14*x^112 + 14*x^111 + 39*x^110 + 32*x^109 + 29*x^108 + 13*x^107 + 14*x^106 + 36*x^105 + 11*x^104 + 38*x^103 + 11*x^102 + 13*x^101 + 22*x^100 + 31*x^99 + 17*x^98 + 16*x^97 + 18*x^96 + 8*x^95 + 6*x^94 + 17*x^93 + 40*x^92 + 17*x^91 + 38*x^90 + 5*x^89 + 16*x^88 + 33*x^87 + 17*x^86 + 4*x^85 + 14*x^84 + 34*x^83 + 17*x^82 + 22*x^81 + 18*x^80 + 12*x^79 + 9*x^78 + 9*x^77 + 20*x^76 + 2*x^75 + 38*x^74 + 12*x^73 + 39*x^72 + 36*x^71 + x^70 + 15*x^69 + 28*x^68 + 27*x^67 + x^66 + x^65 + 14*x^64 + 21*x^63 + 28*x^62 + 12*x^61 + 34*x^60 + 12*x^59 + 11*x^58 + 29*x^57 + 34*x^56 + 10*x^55 + 11*x^54 + 22*x^53 + 28*x^52 + 12*x^51 + 9*x^50 + 4*x^49 + 8*x^48 + 30*x^47 + 21*x^46 + 8*x^45 + 13*x^44 + 29*x^43 + 2*x^42 + 11*x^41 + 13*x^40 + 31*x^39 + 35*x^38 + 22*x^37 + 13*x^36 + 33*x^35 + 33*x^34 + 21*x^33 + 4*x^32 + 18*x^31 + x^30 + 12*x^29 + 34*x^28 + 29*x^27 + 37*x^26 + 14*x^24 + 26*x^23 + 31*x^22 + 38*x^21 + 5*x^20 + 21*x^19 + 23*x^18 + 40*x^17 + 37*x^16 + 12*x^15 + 26*x^14 + 39*x^13 + 12*x^12 + 17*x^11 + 21*x^10 + 18*x^9 + 9*x^8 + 39*x^7 + 35*x^6 + 2*x^5 + 15*x^4 + 38*x^3 + 6*x^2 + 36*x + 12
φ1 = 36*x^126 + 2*x^125 + 15*x^123 + 9*x^122 + 12*x^121 + 27*x^120 + 34*x^119 + 22*x^118 + 12*x^117 + 16*x^116 + 8*x^115 + 19*x^114 + 29*x^113 + x^112 + 11*x^111 + 18*x^110 + 21*x^109 + 19*x^108 + 13*x^107 + 21*x^106 + 38*x^105 + 21*x^104 + 3*x^103 + 15*x^102 + 26*x^101 + 28*x^100 + 36*x^99 + 29*x^98 + 22*x^97 + 15*x^96 + 14*x^95 + 13*x^94 + 25*x^93 + 10*x^92 + 28*x^91 + 10*x^90 + 36*x^89 + 31*x^88 + 9*x^87 + 7*x^86 + 18*x^85 + 23*x^84 + 27*x^83 + 20*x^82 + 3*x^81 + 20*x^80 + 20*x^79 + 22*x^78 + 20*x^76 + 15*x^75 + 18*x^74 + 4*x^73 + 35*x^72 + 28*x^71 + 39*x^70 + 28*x^69 + 30*x^68 + x^67 + 17*x^66 + 20*x^65 + 26*x^64 + 7*x^63 + 13*x^62 + 32*x^61 + 40*x^60 + 39*x^59 + 6*x^58 + 24*x^57 + 19*x^56 + 15*x^55 + 21*x^54 + 25*x^53 + 31*x^52 + 35*x^51 + 19*x^50 + 38*x^49 + 35*x^48 + 4*x^47 + 13*x^46 + 5*x^44 + 17*x^43 + 3*x^42 + 4*x^41 + 36*x^40 + 15*x^39 + 22*x^38 + 26*x^37 + 11*x^36 + 18*x^35 + 3*x^34 + x^33 + 31*x^32 + 18*x^31 + 37*x^30 + 29*x^29 + 30*x^28 + 36*x^27 + 9*x^26 + 26*x^25 + 31*x^24 + 10*x^23 + 40*x^22 + 31*x^21 + 30*x^20 + 10*x^19 + 5*x^18 + 5*x^17 + 36*x^16 + 12*x^15 + x^14 + x^13 + 8*x^12 + 3*x^11 + 14*x^10 + 4*x^9 + 17*x^8 + 33*x^7 + 28*x^6 + 20*x^5 + 24*x^4 + 19*x^3 + 38*x^2 + 38*x + 35
φ2 = 27*x^126 + 14*x^125 + 15*x^124 + 24*x^123 + 2*x^122 + 33*x^121 + 25*x^120 + 18*x^119 + 18*x^118 + 27*x^117 + 25*x^116 + 26*x^115 + 20*x^114 + 36*x^113 + 30*x^112 + 34*x^111 + 9*x^110 + 28*x^109 + 21*x^108 + 17*x^107 + 25*x^106 + 7*x^105 + 19*x^104 + 2*x^103 + 12*x^102 + 14*x^101 + 29*x^100 + x^99 + 2*x^98 + 29*x^97 + 17*x^96 + 6*x^95 + 38*x^94 + 20*x^93 + 7*x^92 + 7*x^91 + 13*x^90 + 28*x^89 + x^88 + 6*x^87 + 38*x^85 + 27*x^84 + 25*x^83 + 24*x^82 + 6*x^81 + 34*x^80 + 6*x^79 + 6*x^78 + 33*x^77 + x^76 + 11*x^75 + 20*x^74 + 28*x^73 + 8*x^72 + 29*x^71 + 38*x^70 + 18*x^69 + 9*x^68 + 34*x^67 + 3*x^66 + 26*x^65 + 21*x^64 + 25*x^63 + 12*x^62 + 35*x^61 + 15*x^60 + 40*x^59 + 36*x^58 + 5*x^57 + 30*x^56 + 25*x^55 + 19*x^54 + 39*x^53 + 18*x^52 + 35*x^51 + 11*x^50 + 22*x^49 + 28*x^48 + 13*x^47 + 40*x^46 + 27*x^45 + 31*x^44 + 19*x^43 + 15*x^42 + 8*x^41 + 36*x^40 + 12*x^39 + 30*x^38 + 23*x^37 + 2*x^36 + 17*x^35 + 11*x^34 + 37*x^33 + 31*x^32 + 7*x^31 + 11*x^30 + 32*x^29 + 22*x^28 + 13*x^27 + 22*x^26 + 33*x^25 + 25*x^24 + 5*x^23 + 26*x^22 + 5*x^21 + 37*x^20 + 35*x^19 + 14*x^18 + 18*x^16 + 29*x^15 + 16*x^14 + 25*x^13 + 19*x^12 + 25*x^11 + 35*x^10 + 15*x^9 + 15*x^8 + 6*x^7 + 29*x^6 + 33*x^5 + 10*x^4 + 20*x^3 + 11*x^2 + 24*x + 11
C1=5*x^127 + 21*x^126 + 38*x^125 + 30*x^124 + 23*x^123 + 36*x^122 + 35*x^121 + 2*x^120 + 26*x^119 + 32*x^118 + 3*x^117 + 26*x^116 + 13*x^115 + 11*x^114 + 17*x^113 + 3*x^112 + 35*x^111 + 23*x^110 + 36*x^109 + 28*x^108 + 20*x^107 + 28*x^106 + 22*x^105 + 2*x^104 + 40*x^103 + 8*x^102 + 9*x^101 + 8*x^100 + 10*x^99 + 6*x^98 + 36*x^97 + 13*x^96 + x^95 + 5*x^93 + 21*x^91 + 11*x^90 + 27*x^89 + 26*x^88 + 27*x^87 + 25*x^86 + 4*x^85 + 17*x^84 + 21*x^83 + 28*x^82 + 23*x^81 + 14*x^80 + 2*x^79 + 2*x^78 + 30*x^77 + 30*x^76 + 14*x^75 + 38*x^74 + 11*x^73 + 30*x^72 + 7*x^71 + 26*x^70 + 11*x^69 + 25*x^68 + 30*x^67 + 3*x^66 + 39*x^65 + 10*x^64 + 15*x^63 + 27*x^62 + 36*x^61 + 4*x^60 + 22*x^59 + 14*x^58 + 32*x^57 + 37*x^56 + 22*x^55 + 12*x^54 + 19*x^53 + 26*x^52 + 34*x^51 + 14*x^50 + 35*x^49 + 31*x^48 + 20*x^47 + 40*x^46 + 9*x^45 + 23*x^44 + 19*x^43 + 29*x^41 + 3*x^40 + 33*x^39 + 5*x^38 + 33*x^37 + 27*x^36 + 28*x^35 + 3*x^34 + 33*x^33 + 31*x^32 + x^31 + 19*x^30 + 22*x^29 + 23*x^28 + 27*x^27 + 40*x^26 + 22*x^25 + 40*x^24 + 14*x^23 + 16*x^22 + 32*x^21 + 12*x^20 + 29*x^19 + 34*x^18 + 7*x^17 + 33*x^16 + 14*x^15 + 17*x^14 + 4*x^13 + 9*x^12 + 9*x^11 + 27*x^10 + 28*x^9 + 20*x^8 + 36*x^7 + 16*x^6 + 9*x^5 + 40*x^4 + 10*x^3 + 32*x^2 + 16
C2=6*x^127 + 16*x^126 + 8*x^125 + 32*x^124 + x^123 + 16*x^122 + 19*x^121 + 35*x^120 + 5*x^119 + 15*x^118 + 4*x^117 + 13*x^116 + 26*x^115 + 24*x^114 + 2*x^113 + 32*x^112 + 4*x^111 + 2*x^110 + 25*x^109 + 14*x^108 + 19*x^107 + 14*x^106 + 37*x^105 + 36*x^104 + 16*x^103 + 7*x^102 + 37*x^101 + 24*x^100 + 9*x^99 + 20*x^98 + 29*x^97 + 8*x^96 + 32*x^95 + 39*x^94 + 36*x^93 + 32*x^92 + 30*x^91 + 32*x^90 + 34*x^89 + 7*x^88 + 15*x^87 + 13*x^86 + 40*x^85 + 15*x^84 + 12*x^83 + 22*x^82 + 37*x^81 + 33*x^80 + 20*x^79 + 31*x^78 + 9*x^77 + 21*x^76 + 27*x^74 + 7*x^73 + 29*x^72 + 18*x^71 + 40*x^70 + 10*x^69 + 33*x^68 + 4*x^67 + 9*x^66 + 28*x^65 + 24*x^64 + 29*x^63 + 37*x^62 + 2*x^61 + 23*x^60 + 29*x^59 + 35*x^58 + 10*x^57 + 13*x^56 + 10*x^55 + 30*x^54 + 8*x^53 + 21*x^52 + 6*x^51 + 26*x^50 + 6*x^49 + 27*x^48 + 33*x^47 + 34*x^46 + 40*x^45 + 39*x^44 + 32*x^43 + 32*x^42 + 33*x^41 + 20*x^40 + 17*x^39 + 39*x^38 + 5*x^37 + 18*x^36 + 35*x^35 + 5*x^34 + 40*x^33 + 15*x^32 + 39*x^31 + 2*x^30 + 20*x^29 + 12*x^28 + 23*x^27 + 36*x^26 + 3*x^25 + 33*x^24 + 39*x^23 + 25*x^22 + 32*x^21 + 39*x^20 + 18*x^19 + 4*x^17 + 31*x^16 + 9*x^15 + 26*x^14 + 12*x^13 + 10*x^12 + 7*x^11 + 2*x^10 + 8*x^9 + 37*x^8 + 17*x^7 + 2*x^6 + 36*x^5 + 4*x^4 + 34*x^3 + 10*x^2 + 18*x + 38
cipher1=b'\xddH\xa3\xad\r\x1c\xe0\x83\xf0\xbe:}\xd6\x01\xa8\xbb\x0e%#V\x94FT\xe6)\x82~y\xe9\x9d\x8e '
cipher2=b's\x15z2\x10t\x0c\x16E\x7fW\x99\x8c\xcf\xd5,D\xb8\x00>\xbe[s\xe5\xa8N\x81\xa6%tA#'
"""

主要改变的地方在于：

  • $\phi_2$变成了从$k_2$到$k_3$的同态
  • 没有给出$F_2$
  • 有两个分别用$\phi_1,\phi_2$计算的密文$C_1,C_2$

既然有两个密文，所以肯定要用上$F_2$和$\phi_2$了，而相比于上一个题目来说可以发现会多一个步骤，就是要求解出$F_2$才行。

强网杯那篇文章有提过，对于$k_2$中的多项式$t(x)$，计算$\phi_2(t(x))$的本质步骤是：

  • 把$k_2$的模多项式，也就是$F_1$放在$F_2$下求根，得到core，这个core其实也就是$\phi_2(x)$
  • 在$k_3$下计算$t(core)$，结果就是$\phi_2(t(x))$

所以在$k_3$中有：

这也就代表着：

所以我们分解$F_1(\phi_1(x))$，其中度为128且不可约的多项式就可能是$F_2(x)$，逐个解密即可。

exp：

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
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen()

F1 = x^128 + 13*x^127 + 25*x^126 + 12*x^125 + 36*x^124 + x^123 + 40*x^122 + 33*x^121 + 29*x^120 + 13*x^119 + 24*x^117 + 36*x^116 + 14*x^114 + 14*x^113 + 14*x^112 + 14*x^111 + 39*x^110 + 32*x^109 + 29*x^108 + 13*x^107 + 14*x^106 + 36*x^105 + 11*x^104 + 38*x^103 + 11*x^102 + 13*x^101 + 22*x^100 + 31*x^99 + 17*x^98 + 16*x^97 + 18*x^96 + 8*x^95 + 6*x^94 + 17*x^93 + 40*x^92 + 17*x^91 + 38*x^90 + 5*x^89 + 16*x^88 + 33*x^87 + 17*x^86 + 4*x^85 + 14*x^84 + 34*x^83 + 17*x^82 + 22*x^81 + 18*x^80 + 12*x^79 + 9*x^78 + 9*x^77 + 20*x^76 + 2*x^75 + 38*x^74 + 12*x^73 + 39*x^72 + 36*x^71 + x^70 + 15*x^69 + 28*x^68 + 27*x^67 + x^66 + x^65 + 14*x^64 + 21*x^63 + 28*x^62 + 12*x^61 + 34*x^60 + 12*x^59 + 11*x^58 + 29*x^57 + 34*x^56 + 10*x^55 + 11*x^54 + 22*x^53 + 28*x^52 + 12*x^51 + 9*x^50 + 4*x^49 + 8*x^48 + 30*x^47 + 21*x^46 + 8*x^45 + 13*x^44 + 29*x^43 + 2*x^42 + 11*x^41 + 13*x^40 + 31*x^39 + 35*x^38 + 22*x^37 + 13*x^36 + 33*x^35 + 33*x^34 + 21*x^33 + 4*x^32 + 18*x^31 + x^30 + 12*x^29 + 34*x^28 + 29*x^27 + 37*x^26 + 14*x^24 + 26*x^23 + 31*x^22 + 38*x^21 + 5*x^20 + 21*x^19 + 23*x^18 + 40*x^17 + 37*x^16 + 12*x^15 + 26*x^14 + 39*x^13 + 12*x^12 + 17*x^11 + 21*x^10 + 18*x^9 + 9*x^8 + 39*x^7 + 35*x^6 + 2*x^5 + 15*x^4 + 38*x^3 + 6*x^2 + 36*x + 12
φ1 = 36*x^126 + 2*x^125 + 15*x^123 + 9*x^122 + 12*x^121 + 27*x^120 + 34*x^119 + 22*x^118 + 12*x^117 + 16*x^116 + 8*x^115 + 19*x^114 + 29*x^113 + x^112 + 11*x^111 + 18*x^110 + 21*x^109 + 19*x^108 + 13*x^107 + 21*x^106 + 38*x^105 + 21*x^104 + 3*x^103 + 15*x^102 + 26*x^101 + 28*x^100 + 36*x^99 + 29*x^98 + 22*x^97 + 15*x^96 + 14*x^95 + 13*x^94 + 25*x^93 + 10*x^92 + 28*x^91 + 10*x^90 + 36*x^89 + 31*x^88 + 9*x^87 + 7*x^86 + 18*x^85 + 23*x^84 + 27*x^83 + 20*x^82 + 3*x^81 + 20*x^80 + 20*x^79 + 22*x^78 + 20*x^76 + 15*x^75 + 18*x^74 + 4*x^73 + 35*x^72 + 28*x^71 + 39*x^70 + 28*x^69 + 30*x^68 + x^67 + 17*x^66 + 20*x^65 + 26*x^64 + 7*x^63 + 13*x^62 + 32*x^61 + 40*x^60 + 39*x^59 + 6*x^58 + 24*x^57 + 19*x^56 + 15*x^55 + 21*x^54 + 25*x^53 + 31*x^52 + 35*x^51 + 19*x^50 + 38*x^49 + 35*x^48 + 4*x^47 + 13*x^46 + 5*x^44 + 17*x^43 + 3*x^42 + 4*x^41 + 36*x^40 + 15*x^39 + 22*x^38 + 26*x^37 + 11*x^36 + 18*x^35 + 3*x^34 + x^33 + 31*x^32 + 18*x^31 + 37*x^30 + 29*x^29 + 30*x^28 + 36*x^27 + 9*x^26 + 26*x^25 + 31*x^24 + 10*x^23 + 40*x^22 + 31*x^21 + 30*x^20 + 10*x^19 + 5*x^18 + 5*x^17 + 36*x^16 + 12*x^15 + x^14 + x^13 + 8*x^12 + 3*x^11 + 14*x^10 + 4*x^9 + 17*x^8 + 33*x^7 + 28*x^6 + 20*x^5 + 24*x^4 + 19*x^3 + 38*x^2 + 38*x + 35
φ2 = 27*x^126 + 14*x^125 + 15*x^124 + 24*x^123 + 2*x^122 + 33*x^121 + 25*x^120 + 18*x^119 + 18*x^118 + 27*x^117 + 25*x^116 + 26*x^115 + 20*x^114 + 36*x^113 + 30*x^112 + 34*x^111 + 9*x^110 + 28*x^109 + 21*x^108 + 17*x^107 + 25*x^106 + 7*x^105 + 19*x^104 + 2*x^103 + 12*x^102 + 14*x^101 + 29*x^100 + x^99 + 2*x^98 + 29*x^97 + 17*x^96 + 6*x^95 + 38*x^94 + 20*x^93 + 7*x^92 + 7*x^91 + 13*x^90 + 28*x^89 + x^88 + 6*x^87 + 38*x^85 + 27*x^84 + 25*x^83 + 24*x^82 + 6*x^81 + 34*x^80 + 6*x^79 + 6*x^78 + 33*x^77 + x^76 + 11*x^75 + 20*x^74 + 28*x^73 + 8*x^72 + 29*x^71 + 38*x^70 + 18*x^69 + 9*x^68 + 34*x^67 + 3*x^66 + 26*x^65 + 21*x^64 + 25*x^63 + 12*x^62 + 35*x^61 + 15*x^60 + 40*x^59 + 36*x^58 + 5*x^57 + 30*x^56 + 25*x^55 + 19*x^54 + 39*x^53 + 18*x^52 + 35*x^51 + 11*x^50 + 22*x^49 + 28*x^48 + 13*x^47 + 40*x^46 + 27*x^45 + 31*x^44 + 19*x^43 + 15*x^42 + 8*x^41 + 36*x^40 + 12*x^39 + 30*x^38 + 23*x^37 + 2*x^36 + 17*x^35 + 11*x^34 + 37*x^33 + 31*x^32 + 7*x^31 + 11*x^30 + 32*x^29 + 22*x^28 + 13*x^27 + 22*x^26 + 33*x^25 + 25*x^24 + 5*x^23 + 26*x^22 + 5*x^21 + 37*x^20 + 35*x^19 + 14*x^18 + 18*x^16 + 29*x^15 + 16*x^14 + 25*x^13 + 19*x^12 + 25*x^11 + 35*x^10 + 15*x^9 + 15*x^8 + 6*x^7 + 29*x^6 + 33*x^5 + 10*x^4 + 20*x^3 + 11*x^2 + 24*x + 11
C1=5*x^127 + 21*x^126 + 38*x^125 + 30*x^124 + 23*x^123 + 36*x^122 + 35*x^121 + 2*x^120 + 26*x^119 + 32*x^118 + 3*x^117 + 26*x^116 + 13*x^115 + 11*x^114 + 17*x^113 + 3*x^112 + 35*x^111 + 23*x^110 + 36*x^109 + 28*x^108 + 20*x^107 + 28*x^106 + 22*x^105 + 2*x^104 + 40*x^103 + 8*x^102 + 9*x^101 + 8*x^100 + 10*x^99 + 6*x^98 + 36*x^97 + 13*x^96 + x^95 + 5*x^93 + 21*x^91 + 11*x^90 + 27*x^89 + 26*x^88 + 27*x^87 + 25*x^86 + 4*x^85 + 17*x^84 + 21*x^83 + 28*x^82 + 23*x^81 + 14*x^80 + 2*x^79 + 2*x^78 + 30*x^77 + 30*x^76 + 14*x^75 + 38*x^74 + 11*x^73 + 30*x^72 + 7*x^71 + 26*x^70 + 11*x^69 + 25*x^68 + 30*x^67 + 3*x^66 + 39*x^65 + 10*x^64 + 15*x^63 + 27*x^62 + 36*x^61 + 4*x^60 + 22*x^59 + 14*x^58 + 32*x^57 + 37*x^56 + 22*x^55 + 12*x^54 + 19*x^53 + 26*x^52 + 34*x^51 + 14*x^50 + 35*x^49 + 31*x^48 + 20*x^47 + 40*x^46 + 9*x^45 + 23*x^44 + 19*x^43 + 29*x^41 + 3*x^40 + 33*x^39 + 5*x^38 + 33*x^37 + 27*x^36 + 28*x^35 + 3*x^34 + 33*x^33 + 31*x^32 + x^31 + 19*x^30 + 22*x^29 + 23*x^28 + 27*x^27 + 40*x^26 + 22*x^25 + 40*x^24 + 14*x^23 + 16*x^22 + 32*x^21 + 12*x^20 + 29*x^19 + 34*x^18 + 7*x^17 + 33*x^16 + 14*x^15 + 17*x^14 + 4*x^13 + 9*x^12 + 9*x^11 + 27*x^10 + 28*x^9 + 20*x^8 + 36*x^7 + 16*x^6 + 9*x^5 + 40*x^4 + 10*x^3 + 32*x^2 + 16
C2=6*x^127 + 16*x^126 + 8*x^125 + 32*x^124 + x^123 + 16*x^122 + 19*x^121 + 35*x^120 + 5*x^119 + 15*x^118 + 4*x^117 + 13*x^116 + 26*x^115 + 24*x^114 + 2*x^113 + 32*x^112 + 4*x^111 + 2*x^110 + 25*x^109 + 14*x^108 + 19*x^107 + 14*x^106 + 37*x^105 + 36*x^104 + 16*x^103 + 7*x^102 + 37*x^101 + 24*x^100 + 9*x^99 + 20*x^98 + 29*x^97 + 8*x^96 + 32*x^95 + 39*x^94 + 36*x^93 + 32*x^92 + 30*x^91 + 32*x^90 + 34*x^89 + 7*x^88 + 15*x^87 + 13*x^86 + 40*x^85 + 15*x^84 + 12*x^83 + 22*x^82 + 37*x^81 + 33*x^80 + 20*x^79 + 31*x^78 + 9*x^77 + 21*x^76 + 27*x^74 + 7*x^73 + 29*x^72 + 18*x^71 + 40*x^70 + 10*x^69 + 33*x^68 + 4*x^67 + 9*x^66 + 28*x^65 + 24*x^64 + 29*x^63 + 37*x^62 + 2*x^61 + 23*x^60 + 29*x^59 + 35*x^58 + 10*x^57 + 13*x^56 + 10*x^55 + 30*x^54 + 8*x^53 + 21*x^52 + 6*x^51 + 26*x^50 + 6*x^49 + 27*x^48 + 33*x^47 + 34*x^46 + 40*x^45 + 39*x^44 + 32*x^43 + 32*x^42 + 33*x^41 + 20*x^40 + 17*x^39 + 39*x^38 + 5*x^37 + 18*x^36 + 35*x^35 + 5*x^34 + 40*x^33 + 15*x^32 + 39*x^31 + 2*x^30 + 20*x^29 + 12*x^28 + 23*x^27 + 36*x^26 + 3*x^25 + 33*x^24 + 39*x^23 + 25*x^22 + 32*x^21 + 39*x^20 + 18*x^19 + 4*x^17 + 31*x^16 + 9*x^15 + 26*x^14 + 12*x^13 + 10*x^12 + 7*x^11 + 2*x^10 + 8*x^9 + 37*x^8 + 17*x^7 + 2*x^6 + 36*x^5 + 4*x^4 + 34*x^3 + 10*x^2 + 18*x + 38
cipher1=b'\xddH\xa3\xad\r\x1c\xe0\x83\xf0\xbe:}\xd6\x01\xa8\xbb\x0e%#V\x94FT\xe6)\x82~y\xe9\x9d\x8e '
cipher2=b's\x15z2\x10t\x0c\x16E\x7fW\x99\x8c\xcf\xd5,D\xb8\x00>\xbe[s\xe5\xa8N\x81\xa6%tA#'

############################################################## part1 get flag1
k2 = GF(q^n, name = 'b', modulus = F1)
b = k2.gen()
core1 = 36*b^126 + 2*b^125 + 15*b^123 + 9*b^122 + 12*b^121 + 27*b^120 + 34*b^119 + 22*b^118 + 12*b^117 + 16*b^116 + 8*b^115 + 19*b^114 + 29*b^113 + b^112 + 11*b^111 + 18*b^110 + 21*b^109 + 19*b^108 + 13*b^107 + 21*b^106 + 38*b^105 + 21*b^104 + 3*b^103 + 15*b^102 + 26*b^101 + 28*b^100 + 36*b^99 + 29*b^98 + 22*b^97 + 15*b^96 + 14*b^95 + 13*b^94 + 25*b^93 + 10*b^92 + 28*b^91 + 10*b^90 + 36*b^89 + 31*b^88 + 9*b^87 + 7*b^86 + 18*b^85 + 23*b^84 + 27*b^83 + 20*b^82 + 3*b^81 + 20*b^80 + 20*b^79 + 22*b^78 + 20*b^76 + 15*b^75 + 18*b^74 + 4*b^73 + 35*b^72 + 28*b^71 + 39*b^70 + 28*b^69 + 30*b^68 + b^67 + 17*b^66 + 20*b^65 + 26*b^64 + 7*b^63 + 13*b^62 + 32*b^61 + 40*b^60 + 39*b^59 + 6*b^58 + 24*b^57 + 19*b^56 + 15*b^55 + 21*b^54 + 25*b^53 + 31*b^52 + 35*b^51 + 19*b^50 + 38*b^49 + 35*b^48 + 4*b^47 + 13*b^46 + 5*b^44 + 17*b^43 + 3*b^42 + 4*b^41 + 36*b^40 + 15*b^39 + 22*b^38 + 26*b^37 + 11*b^36 + 18*b^35 + 3*b^34 + b^33 + 31*b^32 + 18*b^31 + 37*b^30 + 29*b^29 + 30*b^28 + 36*b^27 + 9*b^26 + 26*b^25 + 31*b^24 + 10*b^23 + 40*b^22 + 31*b^21 + 30*b^20 + 10*b^19 + 5*b^18 + 5*b^17 + 36*b^16 + 12*b^15 + b^14 + b^13 + 8*b^12 + 3*b^11 + 14*b^10 + 4*b^9 + 17*b^8 + 33*b^7 + 28*b^6 + 20*b^5 + 24*b^4 + 19*b^3 + 38*b^2 + 38*b + 35
M1 = matrix([(core1**i).list() for i in range(n)])
m1 = (vector(GF(q), C1.list())*M1^(-1)).list()
m1 = [int(i) % 2 for i in m1]
key1 = int(''.join(str(i) for i in m1) , 2)
aes1 = AES.new(long_to_bytes(key1), mode=AES.MODE_ECB)
flag1 = aes1.decrypt(cipher1)
print(flag1)

#NSSCTF{53ebbc09-18ab-4

############################################################## part2 get flag2
temp = list(F1(φ2).factor())

for i in temp:
    if(i[0].degree() == 128 and i[0].is_irreducible()):
        F2 = i[0]
        k3 = GF(q^n, name = 'c', modulus = F2)
        c = k3.gen()
        core2 = 27*c^126 + 14*c^125 + 15*c^124 + 24*c^123 + 2*c^122 + 33*c^121 + 25*c^120 + 18*c^119 + 18*c^118 + 27*c^117 + 25*c^116 + 26*c^115 + 20*c^114 + 36*c^113 + 30*c^112 + 34*c^111 + 9*c^110 + 28*c^109 + 21*c^108 + 17*c^107 + 25*c^106 + 7*c^105 + 19*c^104 + 2*c^103 + 12*c^102 + 14*c^101 + 29*c^100 + c^99 + 2*c^98 + 29*c^97 + 17*c^96 + 6*c^95 + 38*c^94 + 20*c^93 + 7*c^92 + 7*c^91 + 13*c^90 + 28*c^89 + c^88 + 6*c^87 + 38*c^85 + 27*c^84 + 25*c^83 + 24*c^82 + 6*c^81 + 34*c^80 + 6*c^79 + 6*c^78 + 33*c^77 + c^76 + 11*c^75 + 20*c^74 + 28*c^73 + 8*c^72 + 29*c^71 + 38*c^70 + 18*c^69 + 9*c^68 + 34*c^67 + 3*c^66 + 26*c^65 + 21*c^64 + 25*c^63 + 12*c^62 + 35*c^61 + 15*c^60 + 40*c^59 + 36*c^58 + 5*c^57 + 30*c^56 + 25*c^55 + 19*c^54 + 39*c^53 + 18*c^52 + 35*c^51 + 11*c^50 + 22*c^49 + 28*c^48 + 13*c^47 + 40*c^46 + 27*c^45 + 31*c^44 + 19*c^43 + 15*c^42 + 8*c^41 + 36*c^40 + 12*c^39 + 30*c^38 + 23*c^37 + 2*c^36 + 17*c^35 + 11*c^34 + 37*c^33 + 31*c^32 + 7*c^31 + 11*c^30 + 32*c^29 + 22*c^28 + 13*c^27 + 22*c^26 + 33*c^25 + 25*c^24 + 5*c^23 + 26*c^22 + 5*c^21 + 37*c^20 + 35*c^19 + 14*c^18 + 18*c^16 + 29*c^15 + 16*c^14 + 25*c^13 + 19*c^12 + 25*c^11 + 35*c^10 + 15*c^9 + 15*c^8 + 6*c^7 + 29*c^6 + 33*c^5 + 10*c^4 + 20*c^3 + 11*c^2 + 24*c + 11
        M2 = matrix([(core2**i).list() for i in range(n)])
        m2 = (vector(GF(q), C2.list())*M2^(-1)).list()
        m2 = [int(i) % 2 for i in m2]
        key2 = int(''.join(str(i) for i in m2) , 2)
        aes2 = AES.new(long_to_bytes(key2), mode=AES.MODE_ECB)
        flag2 = aes2.decrypt(cipher2)
        print(flag2)

#3cf-bb17-b1a1efdee73d}
#NSSCTF{53ebbc09-18ab-43cf-bb17-b1a1efdee73d}