20220507-春秋杯网络安全联赛春季赛之勇者山峰-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 38k Reading time ≈ 34 mins.

 

notKnapsack

考点

  • Pohlig Hellman
  • MSSP

题目

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
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import random

from Crypto.Util.number import bytes_to_long
from secret import FLAG

assert FLAG.startswith(b'flag{') and FLAG.endswith(b'}')

q = 210767327475911131359308665806489575328083

flag_bin = bin(bytes_to_long(FLAG[5:-1]))[2:]
l = len(flag_bin)

n = random.randint(l, 2*l)
cipher = []
for _ in range(n):
    r = [random.randint(2, q-2) for _ in range(l)]
    s = 1
    for i in range(l):
        s = s * r[i] ** int(flag_bin[i]) % q
    cipher.append([r, s])

with open('output.txt', 'w') as f:
    f.write(str(cipher))

不是背包，是连乘的背包

已知$n$组$[r_k,s_k]$，$r_k$为长度为$l$的向量，其中$r_{k_i}\in[2,q-2]$，$q$为质数，$l\le n$，$s_k$满足
$$
s_k\equiv_q\prod_{i=0}^{l}r_{k_{i}}^{x_i}\tag{1}
$$
求向量$x$，$x_i\in{0,1}$

赛后复现[1] [2]

这其实是$n$ 组Modular Subset Product Problem(MSPP)[3]，下面的步骤揭示如何一步一步将MSPP转换成(Modular) Subset Sum Problem(SSP)，即背包问题，以及DLP，然后用Pohlig Hellman解离散对数的思想解决后者，用多元单模线性方程组[2]求解前者。

  • MSPP一般都可以转换成SSP：

    设群$G_1=\langle g\rangle={g^\alpha|\alpha\in \mathbb{Z}_q}$（有关$g$的选取在后面），显然$s_k,r_{k_i}$是$G_1$的元素，分别计算其离散对数，即$r_{k_i}\equiv_qg^{\alpha_{k_i}},s_k\equiv_q g^{\beta_k}$，得到$\alpha_{k_i},\beta_k$。为何要求离散对数呢？因为这样我们就能对$(1)$进行改造
    $$
    g^{\beta_k}\equiv s_k\equiv\prod_{i=0}^{l-1}r_{k_{i}}^{x_i}\equiv\prod_{i=0}^{l-1}g^{\alpha_{k_i}x_i}\equiv g^{\sum\limits_{i=0}^{l-1}\alpha_{k_i}x_i}\ (mod\ q)\notag
    $$
    再从幂指数上拿下来就变成了模子集和的问题
    $$
    \beta_k\equiv_{\varphi(q)}\sum\limits_{i=0}^{l-1}\alpha_{k_i}x_i\notag
    $$

  • 解线性方程组

    这里由于有$n$组这样的模子集和，展开来写成多元单模线性方程组（所以MSSP的一般方法有哪些呢）
    $$
    \begin{cases}
    \beta_1\equiv_{\varphi(q)} \alpha_{1,0}\cdot x_0+\alpha_{1,1}\cdot x_1+\dots+\alpha_{1,l-1}\cdot x_{l-1}\\
    \beta_2\equiv_{\varphi(q)} \alpha_{2,0}\cdot x_0+\alpha_{2,1}\cdot x_1+\dots+\alpha_{2,l-1}\cdot x_{l-1}\\
    \quad\ \ \vdots\\
    \beta_n\equiv_{\varphi(q)} \alpha_{n,0}\cdot x_0+\alpha_{n,1}\cdot x_1+\dots+\alpha_{n,l-1}\cdot x_{l-1}
    \end{cases}
    \notag
    $$
    即
    $$
    \begin{bmatrix}
    \beta_1\\
    \beta_2\\
    \vdots\\
    \beta_n
    \end{bmatrix}\equiv_{\varphi(q)}
    \begin{bmatrix}
    \alpha_{1,0} & \alpha_{1,1} & \cdots & \alpha_{1,l-1}\\
    \alpha_{2,0} & \alpha_{2,1} & \cdots & \alpha_{2,l-1}\\
    \vdots&\vdots&&\vdots&\\
    \alpha_{n,0} & \alpha_{n,1} & \cdots & \alpha_{n,l-1}
    \end{bmatrix}\begin{bmatrix}
    x_0\\
    x_2\\
    \vdots\\
    x_{l-1}
    \end{bmatrix}
    \notag
    $$

    $$
    v_{n\times 1}\equiv_{\varphi(q)} A_{n\times l}\cdot x_{l\times 1}\tag{2}
    $$

    解法可以参考[2]的，sage集成在solve_right里了。

  • DLP

    那么最后的问题就是如何求解离散对数。先说结论。直接用discrete_log应该够呛，而这里

    1
    q = 2 * 331 * 318379648755152766403789525387446488411 + 1

    2和331都是小的因子，令$o=2$或者$o=331$，$t=\frac{\varphi(q)}{o}$，因为
    $$
    1\equiv g^{\varphi(q)}\equiv (g^{t})^{o}\ (mod\ q)\notag
    $$
    所以我们设新的群$G_2=\langle g^t\rangle={(g^t)^{\alpha’}|\alpha’\in \mathbb{Z}_o}$，$G_2$是$G_1$的子群，其阶为$o$，显然在$G_2$上求解离散对数要比$G_1$容易许多。这样解决了DLP，再结合前面的解一个模线性方程组就能得到flag。

    但是为什么可以这样呢？$\alpha$和$\alpha’$有何关系？根据Pohlig Hellman算法的思想[6]，比如将$s\equiv_q g^{\beta}$两边同时$t$次方，得到
    $$
    s^t\equiv_q(g^t)^{\beta}\notag
    $$
    前面知道这个DLP是容易解的，即成所有小阶下离散对数的字典，然后计算pow(s,t,q)去查表，得到的$\beta$是在模$o$下的。$o$是$\varphi(q)$的一个因子，按照原本的Pohlig Hellman，是要求出模光滑数的所有因子，即$p-1=\prod\limits_{i=1}^mp_i^{k_i}$，模所有$p_i^{k_i}$的DLP，然后用CRT求出最小的本原元下的DLP，最后用拓展欧几里德求出真正的DLP。这里不需要，只需要求出在模$o$下的，因为在模$\varphi(q)$下成立，在模$o$下自然也成立，即
    $$
    \beta_1\equiv_{o} \alpha_{1,0}\cdot x_0+\alpha_{1,1}\cdot x_1+\dots+\alpha_{1,l-1}\cdot x_{l-1}\notag
    $$
    而$x_i\in{0,1}$，就可以限定矩阵和向量在有限域$GF(o)$下，就可以代入$(2)$中求解线性方程组。

  • 关于$g$的选取

    因为针对其他$q$的情况，如果$g$选取不当，可能导致DLP计算不全或或解出来乱码。结论是要保证pow(g,t,q)不等于0和1。

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
from re import findall
from random import randint

# read file
cipher = []
with open('output.txt', 'r') as fp:
    a = list(map(int, findall(r'\d+', fp.read())))
    # figure out n=517 by trying, but just set n = l
    l = 286
    n = l
    for i in range(n):
        r = []
        for j in range(l):
            r.append(a[i * (l + 1) + j])
        s = a[i * (l + 1) + l]
        cipher.append([r, s])

q = 210767327475911131359308665806489575328083
for order in [2, 331]:
    t = (q - 1) // order
    sub_gen = pow(randint(2, 10), t, q)
    while sub_gen == 1:
        sub_gen = pow(randint(2, 10), t, q)
    F = GF(order)

    dlp_dct = {sub_gen ^ i: F(i) for i in range(order)}

    A = Matrix(F, n, l)
    v = vector(F, n)

    for i in range(n):
        for j in range(l):
            A[i, j] = dlp_dct[pow(cipher[i][0][j], t, q)]
        v[i] = dlp_dct[pow(cipher[i][1], t, q)]

    x = A.solve_right(v)
    m = ''
    for i in x:
        m += str(i)
    flag = bytes.fromhex(hex(int(m, 2))[2:])
    print(flag, 'made by myself')
# b'2e585eb0-85ca-466f-a9f1-54a3ee9b548d' made by myself
# b'2e585eb0-85ca-466f-a9f1-54a3ee9b548d' made by myself

bob’s enc

考点

  • 解同余方程
  • LWE

题目代码

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
from secret import * 
import random

prime =  2141
print len(flag)
flag = map(ord,flag)
flag1 = flag[:21]
flag2 = flag[21:]
row = 64

def add(msg1,msg2):
    return [(x+y)%prime for x,y in zip(msg1,msg2)]

def multi(msg1,msg2):
    out = []
    for l in msg1:
        s = 0
        for x,y in zip(l,msg2):
            s += (x*y)%prime
            s %= prime
        out.append(s)
    return out
def genkey(leng):
    l = [[] for i in range(row)]
    for x in range(row):
        for i in range(leng):
            l[x].append(random.randint(0,511))
    return l

key = genkey(len(flag1))
print key

cipher1 = multi(key,flag1)

print cipher1

cipher2 = multi(key,flag2)

noise = [random.randint(0,6) for i in range(row)]
print add(noise,cipher2)
# [[185, 96, 351, 118, 421, 449, 350, 349, 388, 95, 341, 327, 29, 156, 399, 283, 292, 461, 445, 120, 126], [495, 358, 192, 300, 279, 277, 478, 335, 231, 241, 178, 314, 453, 251, 133, 391, 213, 132, 254, 388, 46], [428, 44, 100, 483, 12, 311, 57, 443, 289, 90, 478, 495, 399, 89, 324, 275, 322, 99, 343, 489, 133], [420, 358, 472, 260, 267, 136, 303, 491, 390, 248, 430, 117, 154, 244, 62, 217, 204, 334, 277, 231, 325], [11, 96, 61, 67, 456, 361, 292, 278, 424, 237, 345, 109, 475, 473, 29, 250, 195, 430, 114, 13, 199], [17, 91, 330, 73, 384, 134, 437, 161, 166, 185, 499, 491, 342, 129, 348, 162, 478, 216, 189, 311, 502], [396, 437, 98, 421, 120, 443, 113, 432, 9, 476, 243, 122, 416, 508, 287, 45, 84, 322, 504, 287, 251], [187, 489, 407, 204, 127, 10, 302, 101, 389, 113, 469, 184, 249, 131, 113, 18, 350, 106, 486, 406, 295], [265, 425, 30, 478, 471, 211, 162, 323, 163, 205, 187, 422, 452, 226, 230, 367, 478, 229, 365, 395, 294], [360, 193, 180, 253, 337, 453, 16, 352, 243, 107, 171, 46, 25, 234, 46, 479, 267, 267, 171, 188, 127], [379, 360, 109, 360, 403, 343, 75, 306, 138, 40, 41, 253, 428, 401, 464, 495, 21, 296, 319, 410, 440], [28, 209, 1, 233, 458, 266, 301, 359, 469, 304, 264, 368, 339, 25, 490, 343, 404, 488, 275, 262, 274], [180, 372, 133, 341, 29, 352, 326, 89, 323, 479, 68, 76, 247, 225, 159, 163, 180, 160, 171, 7, 322], [322, 295, 28, 467, 361, 169, 190, 71, 456, 140, 456, 202, 295, 424, 428, 18, 286, 233, 470, 303, 429], [234, 37, 128, 175, 282, 509, 54, 186, 177, 23, 348, 487, 473, 377, 81, 225, 154, 511, 364, 120, 280], [262, 82, 383, 490, 128, 448, 289, 420, 239, 374, 392, 149, 217, 398, 441, 480, 453, 503, 318, 285, 418], [0, 347, 223, 381, 469, 208, 424, 435, 404, 64, 107, 73, 490, 116, 445, 392, 194, 287, 66, 325, 261], [99, 26, 489, 114, 3, 351, 494, 174, 369, 354, 379, 187, 90, 202, 286, 37, 48, 397, 298, 65, 499], [455, 114, 349, 401, 5, 139, 314, 227, 134, 258, 270, 135, 287, 332, 298, 272, 167, 43, 271, 484, 177], [448, 78, 479, 324, 170, 7, 230, 173, 214, 65, 91, 497, 68, 391, 44, 205, 364, 471, 460, 312, 122], [452, 360, 448, 169, 240, 496, 302, 3, 354, 266, 46, 22, 151, 498, 461, 314, 169, 88, 30, 487, 258], [282, 222, 260, 503, 106, 420, 315, 307, 202, 238, 224, 329, 351, 190, 137, 294, 171, 309, 19, 186, 391], [69, 501, 283, 96, 159, 459, 437, 192, 293, 479, 79, 49, 299, 205, 177, 360, 36, 414, 118, 194, 270], [6, 419, 459, 254, 97, 455, 445, 239, 277, 278, 226, 23, 146, 151, 273, 378, 141, 281, 480, 388, 213], [181, 508, 347, 447, 467, 351, 503, 262, 375, 74, 49, 48, 364, 492, 400, 305, 25, 207, 278, 163, 11], [320, 94, 400, 15, 201, 53, 130, 137, 219, 57, 20, 239, 467, 352, 373, 395, 58, 4, 446, 332, 41], [205, 385, 446, 185, 470, 268, 308, 461, 265, 75, 75, 104, 108, 14, 334, 499, 207, 363, 94, 505, 363], [299, 292, 112, 203, 7, 240, 499, 343, 396, 482, 383, 61, 476, 101, 187, 265, 428, 53, 24, 342, 201], [421, 286, 305, 79, 324, 216, 163, 193, 362, 57, 472, 449, 169, 33, 280, 202, 237, 376, 382, 2, 1], [379, 33, 151, 51, 353, 295, 145, 220, 147, 251, 90, 344, 96, 31, 185, 250, 270, 420, 365, 373, 356], [228, 299, 87, 113, 458, 52, 26, 228, 294, 97, 384, 493, 380, 209, 257, 20, 375, 2, 316, 129, 492], [479, 346, 57, 488, 183, 185, 18, 422, 209, 318, 461, 159, 469, 145, 44, 58, 441, 490, 510, 194, 192], [254, 398, 510, 159, 371, 280, 331, 23, 99, 150, 175, 151, 42, 473, 164, 35, 97, 174, 115, 24, 270], [280, 76, 254, 293, 491, 76, 128, 301, 240, 357, 192, 372, 343, 34, 386, 468, 313, 41, 285, 507, 282], [271, 91, 507, 16, 128, 8, 326, 102, 355, 371, 313, 292, 433, 2, 459, 14, 258, 498, 146, 446, 309], [386, 88, 502, 4, 399, 272, 49, 69, 51, 465, 291, 289, 417, 271, 374, 337, 46, 393, 19, 429, 91], [407, 35, 337, 51, 41, 460, 222, 448, 499, 381, 59, 468, 440, 216, 86, 236, 91, 18, 123, 68, 145], [384, 30, 454, 419, 275, 164, 72, 195, 489, 458, 419, 148, 269, 150, 358, 188, 109, 27, 42, 34, 123], [500, 184, 195, 193, 68, 19, 329, 511, 280, 69, 113, 124, 102, 274, 43, 374, 408, 64, 314, 309, 473], [72, 145, 242, 2, 367, 371, 143, 166, 325, 74, 414, 94, 269, 196, 124, 94, 14, 351, 111, 465, 503], [70, 47, 439, 170, 306, 82, 233, 36, 346, 234, 157, 468, 83, 85, 424, 157, 258, 120, 270, 136, 286], [442, 173, 254, 271, 420, 507, 297, 473, 296, 511, 98, 133, 37, 498, 468, 17, 260, 318, 168, 490, 124], [50, 35, 252, 472, 406, 400, 439, 89, 309, 393, 332, 324, 260, 215, 8, 322, 357, 252, 124, 358, 457], [93, 102, 478, 224, 428, 10, 238, 368, 113, 502, 148, 7, 395, 97, 73, 306, 40, 395, 9, 254, 319], [282, 277, 295, 425, 59, 21, 136, 230, 207, 1, 29, 170, 14, 337, 371, 437, 359, 10, 100, 374, 24], [3, 270, 289, 179, 434, 489, 470, 343, 478, 156, 177, 72, 13, 266, 475, 23, 148, 102, 210, 270, 323], [464, 466, 277, 191, 426, 20, 266, 33, 41, 249, 452, 475, 265, 421, 282, 250, 233, 287, 495, 170, 300], [379, 35, 137, 106, 155, 81, 154, 382, 30, 237, 294, 478, 321, 384, 48, 111, 150, 4, 454, 446, 28], [57, 355, 94, 253, 297, 424, 415, 480, 68, 356, 415, 73, 41, 171, 491, 130, 92, 180, 506, 326, 463], [279, 43, 202, 35, 397, 257, 120, 11, 231, 369, 221, 332, 47, 236, 58, 278, 75, 117, 33, 130, 358], [142, 335, 339, 112, 38, 82, 426, 211, 174, 389, 137, 96, 431, 113, 112, 500, 145, 44, 313, 96, 187], [246, 211, 400, 415, 294, 234, 367, 46, 371, 479, 412, 197, 204, 498, 18, 140, 67, 237, 510, 457, 298], [258, 3, 136, 284, 149, 161, 456, 122, 114, 383, 251, 240, 453, 227, 330, 33, 241, 160, 306, 254, 409], [391, 115, 92, 102, 359, 182, 489, 313, 204, 275, 206, 447, 436, 286, 229, 377, 374, 162, 22, 384, 40], [427, 491, 362, 240, 358, 296, 154, 178, 278, 284, 324, 422, 52, 295, 490, 56, 39, 378, 174, 202, 496], [29, 454, 436, 6, 287, 82, 154, 474, 92, 272, 400, 238, 352, 140, 386, 504, 19, 32, 334, 30, 450], [469, 123, 353, 422, 175, 260, 294, 18, 268, 479, 60, 114, 456, 55, 403, 446, 166, 259, 294, 215, 48], [404, 187, 426, 362, 296, 239, 226, 416, 306, 336, 1, 448, 47, 403, 367, 357, 501, 425, 310, 41, 303], [339, 115, 478, 416, 10, 90, 188, 229, 217, 441, 288, 152, 394, 219, 422, 376, 325, 375, 6, 454, 238], [226, 226, 149, 107, 418, 419, 209, 108, 87, 127, 202, 320, 179, 234, 87, 335, 195, 5, 273, 142, 115], [464, 177, 77, 101, 76, 19, 73, 397, 296, 34, 360, 107, 491, 460, 510, 342, 198, 118, 105, 337, 239], [464, 25, 191, 113, 455, 129, 247, 488, 303, 27, 242, 423, 336, 125, 283, 332, 244, 372, 175, 276, 49], [211, 367, 406, 314, 177, 496, 320, 385, 193, 51, 423, 80, 258, 44, 154, 362, 215, 296, 260, 424, 160], [384, 161, 92, 402, 414, 443, 129, 279, 272, 224, 294, 319, 75, 169, 242, 85, 315, 402, 4, 268, 88]]
# [1702, 795, 740, 373, 535, 1308, 1050, 502, 40, 672, 1354, 1843, 515, 231, 774, 65, 978, 1340, 455, 2137, 733, 307, 1604, 723, 1023, 1253, 275, 1817, 404, 2035, 267, 1475, 14, 2127, 15, 487, 317, 757, 290, 541, 100, 951, 2049, 1042, 1404, 1676, 655, 1460, 1532, 273, 916, 1454, 1690, 1628, 1751, 1656, 139, 156, 2102, 264, 243, 455, 1564, 2072]
# [884, 1584, 681, 1713, 1916, 609, 1840, 177, 1723, 1049, 254, 864, 1671, 121, 2021, 1353, 1290, 1891, 556, 1786, 1553, 1548, 727, 1967, 1800, 422, 1559, 1290, 642, 1406, 441, 1928, 395, 279, 1125, 1273, 99, 1131, 395, 76, 733, 416, 924, 571, 506, 822, 877, 887, 860, 1755, 1385, 1861, 1754, 1851, 1046, 1724, 1866, 1427, 378, 351, 146, 1367, 756, 505]

第一个加密，即
$$
\begin{cases}
c_0\equiv_p m_0\cdot k_{0,0}+m_1\cdot k_{0,1}+\dots+m_{20}\cdot k_{0,20}\\
c_1\equiv_p m_0\cdot k_{1,0}+m_1\cdot k_{1,1}+\dots+m_{20}\cdot k_{1,20}\\
\quad\ \vdots\\
c_{62}\equiv_p m_0\cdot k_{62,0}+m_1\cdot k_{62,1}+\dots+m_{20}\cdot k_{62,20}\\
c_{63}\equiv_p m_0\cdot k_{63,0}+m_1\cdot k_{63,1}+\dots+m_{20}\cdot k_{63,20}
\end{cases}\notag
$$
而第二个加密则在第一个基础上，加了噪音

前一半Gröbner basis解模$p$下的方程组，后一半LWE，用网上的脚本[7]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# sage
from re import findall

prime = 2141
key = [[185, 96, 351, 118, 421, 449, 350, 349, 388, 95, 341, 327, 29, 156, 399, 283, 292, 461, 445, 120, 126], [495, 358, 192, 300, 279, 277, 478, 335, 231, 241, 178, 314, 453, 251, 133, 391, 213, 132, 254, 388, 46], [428, 44, 100, 483, 12, 311, 57, 443, 289, 90, 478, 495, 399, 89, 324, 275, 322, 99, 343, 489, 133], [420, 358, 472, 260, 267, 136, 303, 491, 390, 248, 430, 117, 154, 244, 62, 217, 204, 334, 277, 231, 325], [11, 96, 61, 67, 456, 361, 292, 278, 424, 237, 345, 109, 475, 473, 29, 250, 195, 430, 114, 13, 199], [17, 91, 330, 73, 384, 134, 437, 161, 166, 185, 499, 491, 342, 129, 348, 162, 478, 216, 189, 311, 502], [396, 437, 98, 421, 120, 443, 113, 432, 9, 476, 243, 122, 416, 508, 287, 45, 84, 322, 504, 287, 251], [187, 489, 407, 204, 127, 10, 302, 101, 389, 113, 469, 184, 249, 131, 113, 18, 350, 106, 486, 406, 295], [265, 425, 30, 478, 471, 211, 162, 323, 163, 205, 187, 422, 452, 226, 230, 367, 478, 229, 365, 395, 294], [360, 193, 180, 253, 337, 453, 16, 352, 243, 107, 171, 46, 25, 234, 46, 479, 267, 267, 171, 188, 127], [379, 360, 109, 360, 403, 343, 75, 306, 138, 40, 41, 253, 428, 401, 464, 495, 21, 296, 319, 410, 440], [28, 209, 1, 233, 458, 266, 301, 359, 469, 304, 264, 368, 339, 25, 490, 343, 404, 488, 275, 262, 274], [180, 372, 133, 341, 29, 352, 326, 89, 323, 479, 68, 76, 247, 225, 159, 163, 180, 160, 171, 7, 322], [322, 295, 28, 467, 361, 169, 190, 71, 456, 140, 456, 202, 295, 424, 428, 18, 286, 233, 470, 303, 429], [234, 37, 128, 175, 282, 509, 54, 186, 177, 23, 348, 487, 473, 377, 81, 225, 154, 511, 364, 120, 280], [262, 82, 383, 490, 128, 448, 289, 420, 239, 374, 392, 149, 217, 398, 441, 480, 453, 503, 318, 285, 418], [0, 347, 223, 381, 469, 208, 424, 435, 404, 64, 107, 73, 490, 116, 445, 392, 194, 287, 66, 325, 261], [99, 26, 489, 114, 3, 351, 494, 174, 369, 354, 379, 187, 90, 202, 286, 37, 48, 397, 298, 65, 499], [455, 114, 349, 401, 5, 139, 314, 227, 134, 258, 270, 135, 287, 332, 298, 272, 167, 43, 271, 484, 177], [448, 78, 479, 324, 170, 7, 230, 173, 214, 65, 91, 497, 68, 391, 44, 205, 364, 471, 460, 312, 122], [452, 360, 448, 169, 240, 496, 302, 3, 354, 266, 46, 22, 151, 498, 461, 314, 169, 88, 30, 487, 258], [282, 222, 260, 503, 106, 420, 315, 307, 202, 238, 224, 329, 351, 190, 137, 294, 171, 309, 19, 186, 391], [69, 501, 283, 96, 159, 459, 437, 192, 293, 479, 79, 49, 299, 205, 177, 360, 36, 414, 118, 194, 270], [6, 419, 459, 254, 97, 455, 445, 239, 277, 278, 226, 23, 146, 151, 273, 378, 141, 281, 480, 388, 213], [181, 508, 347, 447, 467, 351, 503, 262, 375, 74, 49, 48, 364, 492, 400, 305, 25, 207, 278, 163, 11], [320, 94, 400, 15, 201, 53, 130, 137, 219, 57, 20, 239, 467, 352, 373, 395, 58, 4, 446, 332, 41], [205, 385, 446, 185, 470, 268, 308, 461, 265, 75, 75, 104, 108, 14, 334, 499, 207, 363, 94, 505, 363], [299, 292, 112, 203, 7, 240, 499, 343, 396, 482, 383, 61, 476, 101, 187, 265, 428, 53, 24, 342, 201], [421, 286, 305, 79, 324, 216, 163, 193, 362, 57, 472, 449, 169, 33, 280, 202, 237, 376, 382, 2, 1], [379, 33, 151, 51, 353, 295, 145, 220, 147, 251, 90, 344, 96, 31, 185, 250, 270, 420, 365, 373, 356], [228, 299, 87, 113, 458, 52, 26, 228, 294, 97, 384, 493, 380, 209, 257, 20, 375, 2, 316, 129, 492], [479, 346, 57, 488, 183, 185, 18, 422, 209, 318, 461, 159, 469, 145, 44, 58, 441, 490, 510, 194, 192], [254, 398, 510, 159, 371, 280, 331, 23, 99, 150, 175, 151, 42, 473, 164, 35, 97, 174, 115, 24, 270], [280, 76, 254, 293, 491, 76, 128, 301, 240, 357, 192, 372, 343, 34, 386, 468, 313, 41, 285, 507, 282], [271, 91, 507, 16, 128, 8, 326, 102, 355, 371, 313, 292, 433, 2, 459, 14, 258, 498, 146, 446, 309], [386, 88, 502, 4, 399, 272, 49, 69, 51, 465, 291, 289, 417, 271, 374, 337, 46, 393, 19, 429, 91], [407, 35, 337, 51, 41, 460, 222, 448, 499, 381, 59, 468, 440, 216, 86, 236, 91, 18, 123, 68, 145], [384, 30, 454, 419, 275, 164, 72, 195, 489, 458, 419, 148, 269, 150, 358, 188, 109, 27, 42, 34, 123], [500, 184, 195, 193, 68, 19, 329, 511, 280, 69, 113, 124, 102, 274, 43, 374, 408, 64, 314, 309, 473], [72, 145, 242, 2, 367, 371, 143, 166, 325, 74, 414, 94, 269, 196, 124, 94, 14, 351, 111, 465, 503], [70, 47, 439, 170, 306, 82, 233, 36, 346, 234, 157, 468, 83, 85, 424, 157, 258, 120, 270, 136, 286], [442, 173, 254, 271, 420, 507, 297, 473, 296, 511, 98, 133, 37, 498, 468, 17, 260, 318, 168, 490, 124], [50, 35, 252, 472, 406, 400, 439, 89, 309, 393, 332, 324, 260, 215, 8, 322, 357, 252, 124, 358, 457], [93, 102, 478, 224, 428, 10, 238, 368, 113, 502, 148, 7, 395, 97, 73, 306, 40, 395, 9, 254, 319], [282, 277, 295, 425, 59, 21, 136, 230, 207, 1, 29, 170, 14, 337, 371, 437, 359, 10, 100, 374, 24], [3, 270, 289, 179, 434, 489, 470, 343, 478, 156, 177, 72, 13, 266, 475, 23, 148, 102, 210, 270, 323], [464, 466, 277, 191, 426, 20, 266, 33, 41, 249, 452, 475, 265, 421, 282, 250, 233, 287, 495, 170, 300], [379, 35, 137, 106, 155, 81, 154, 382, 30, 237, 294, 478, 321, 384, 48, 111, 150, 4, 454, 446, 28], [57, 355, 94, 253, 297, 424, 415, 480, 68, 356, 415, 73, 41, 171, 491, 130, 92, 180, 506, 326, 463], [279, 43, 202, 35, 397, 257, 120, 11, 231, 369, 221, 332, 47, 236, 58, 278, 75, 117, 33, 130, 358], [142, 335, 339, 112, 38, 82, 426, 211, 174, 389, 137, 96, 431, 113, 112, 500, 145, 44, 313, 96, 187], [246, 211, 400, 415, 294, 234, 367, 46, 371, 479, 412, 197, 204, 498, 18, 140, 67, 237, 510, 457, 298], [258, 3, 136, 284, 149, 161, 456, 122, 114, 383, 251, 240, 453, 227, 330, 33, 241, 160, 306, 254, 409], [391, 115, 92, 102, 359, 182, 489, 313, 204, 275, 206, 447, 436, 286, 229, 377, 374, 162, 22, 384, 40], [427, 491, 362, 240, 358, 296, 154, 178, 278, 284, 324, 422, 52, 295, 490, 56, 39, 378, 174, 202, 496], [29, 454, 436, 6, 287, 82, 154, 474, 92, 272, 400, 238, 352, 140, 386, 504, 19, 32, 334, 30, 450], [469, 123, 353, 422, 175, 260, 294, 18, 268, 479, 60, 114, 456, 55, 403, 446, 166, 259, 294, 215, 48], [404, 187, 426, 362, 296, 239, 226, 416, 306, 336, 1, 448, 47, 403, 367, 357, 501, 425, 310, 41, 303], [339, 115, 478, 416, 10, 90, 188, 229, 217, 441, 288, 152, 394, 219, 422, 376, 325, 375, 6, 454, 238], [226, 226, 149, 107, 418, 419, 209, 108, 87, 127, 202, 320, 179, 234, 87, 335, 195, 5, 273, 142, 115], [464, 177, 77, 101, 76, 19, 73, 397, 296, 34, 360, 107, 491, 460, 510, 342, 198, 118, 105, 337, 239], [464, 25, 191, 113, 455, 129, 247, 488, 303, 27, 242, 423, 336, 125, 283, 332, 244, 372, 175, 276, 49], [211, 367, 406, 314, 177, 496, 320, 385, 193, 51, 423, 80, 258, 44, 154, 362, 215, 296, 260, 424, 160], [384, 161, 92, 402, 414, 443, 129, 279, 272, 224, 294, 319, 75, 169, 242, 85, 315, 402, 4, 268, 88]]
cipher1 = [1702, 795, 740, 373, 535, 1308, 1050, 502, 40, 672, 1354, 1843, 515, 231, 774, 65, 978, 1340, 455, 2137, 733, 307, 1604, 723, 1023, 1253, 275, 1817, 404, 2035, 267, 1475, 14, 2127, 15, 487, 317, 757, 290, 541, 100, 951, 2049, 1042, 1404, 1676, 655, 1460, 1532, 273, 916, 1454, 1690, 1628, 1751, 1656, 139, 156, 2102, 264, 243, 455, 1564, 2072]
cipher2 = [884, 1584, 681, 1713, 1916, 609, 1840, 177, 1723, 1049, 254, 864, 1671, 121, 2021, 1353, 1290, 1891, 556, 1786, 1553, 1548, 727, 1967, 1800, 422, 1559, 1290, 642, 1406, 441, 1928, 395, 279, 1125, 1273, 99, 1131, 395, 76, 733, 416, 924, 571, 506, 822, 877, 887, 860, 1755, 1385, 1861, 1754, 1851, 1046, 1724, 1866, 1427, 378, 351, 146, 1367, 756, 505]

P.< a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u > = PolynomialRing(Zmod(prime))

# for i in range(64):
#        print(f'a * key[{i}][0] + b * key[{i}][1] + c * key[{i}][2] + d * key[{i}][3] + e * key[{i}][4] + f * key[{i}][5] + g * key[{i}][6] + h * key[{i}][7] + i * key[{i}][8] + j * key[{i}][9] + k * key[{i}][10] + l * key[{i}][11] + m * key[{i}][12] + n * key[{i}][13] + o * key[{i}][14] + p * key[{i}][15] + q * key[{i}][16] + r * key[{i}][17] + s * key[{i}][18] + t * key[{i}][19] + u * key[{i}][20] - cipher1[{i}]', end=', ')

G = [a * key[0][0] + b * key[0][1] + c * key[0][2] + d * key[0][3] + e * key[0][4] + f * key[0][5] + g * key[0][6] + h * key[0][7] + i * key[0][8] + j * key[0][9] + k * key[0][10] + l * key[0][11] + m * key[0][12] + n * key[0][13] + o * key[0][14] + p * key[0][15] + q * key[0][16] + r * key[0][17] + s * key[0][18] + t * key[0][19] + u * key[0][20] - cipher1[0], a * key[1][0] + b * key[1][1] + c * key[1][2] + d * key[1][3] + e * key[1][4] + f * key[1][5] + g * key[1][6] + h * key[1][7] + i * key[1][8] + j * key[1][9] + k * key[1][10] + l * key[1][11] + m * key[1][12] + n * key[1][13] + o * key[1][14] + p * key[1][15] + q * key[1][16] + r * key[1][17] + s * key[1][18] + t * key[1][19] + u * key[1][20] - cipher1[1], a * key[2][0] + b * key[2][1] + c * key[2][2] + d * key[2][3] + e * key[2][4] + f * key[2][5] + g * key[2][6] + h * key[2][7] + i * key[2][8] + j * key[2][9] + k * key[2][10] + l * key[2][11] + m * key[2][12] + n * key[2][13] + o * key[2][14] + p * key[2][15] + q * key[2][16] + r * key[2][17] + s * key[2][18] + t * key[2][19] + u * key[2][20] - cipher1[2], a * key[3][0] + b * key[3][1] + c * key[3][2] + d * key[3][3] + e * key[3][4] + f * key[3][5] + g * key[3][6] + h * key[3][7] + i * key[3][8] + j * key[3][9] + k * key[3][10] + l * key[3][11] + m * key[3][12] + n * key[3][13] + o * key[3][14] + p * key[3][15] + q * key[3][16] + r * key[3][17] + s * key[3][18] + t * key[3][19] + u * key[3][20] - cipher1[3], a * key[4][0] + b * key[4][1] + c * key[4][2] + d * key[4][3] + e * key[4][4] + f * key[4][5] + g * key[4][6] + h * key[4][7] + i * key[4][8] + j * key[4][9] + k * key[4][10] + l * key[4][11] + m * key[4][12] + n * key[4][13] + o * key[4][14] + p * key[4][15] + q * key[4][16] + r * key[4][17] + s * key[4][18] + t * key[4][19] + u * key[4][20] - cipher1[4], a * key[5][0] + b * key[5][1] + c * key[5][2] + d * key[5][3] + e * key[5][4] + f * key[5][5] + g * key[5][6] + h * key[5][7] + i * key[5][8] + j * key[5][9] + k * key[5][10] + l * key[5][11] + m * key[5][12] + n * key[5][13] + o * key[5][14] + p * key[5][15] + q * key[5][16] + r * key[5][17] + s * key[5][18] + t * key[5][19] + u * key[5][20] - cipher1[5], a * key[6][0] + b * key[6][1] + c * key[6][2] + d * key[6][3] + e * key[6][4] + f * key[6][5] + g * key[6][6] + h * key[6][7] + i * key[6][8] + j * key[6][9] + k * key[6][10] + l * key[6][11] + m * key[6][12] + n * key[6][13] + o * key[6][14] + p * key[6][15] + q * key[6][16] + r * key[6][17] + s * key[6][18] + t * key[6][19] + u * key[6][20] - cipher1[6], a * key[7][0] + b * key[7][1] + c * key[7][2] + d * key[7][3] + e * key[7][4] + f * key[7][5] + g * key[7][6] + h * key[7][7] + i * key[7][8] + j * key[7][9] + k * key[7][10] + l * key[7][11] + m * key[7][12] + n * key[7][13] + o * key[7][14] + p * key[7][15] + q * key[7][16] + r * key[7][17] + s * key[7][18] + t * key[7][19] + u * key[7][20] - cipher1[7], a * key[8][0] + b * key[8][1] + c * key[8][2] + d * key[8][3] + e * key[8][4] + f * key[8][5] + g * key[8][6] + h * key[8][7] + i * key[8][8] + j * key[8][9] + k * key[8][10] + l * key[8][11] + m * key[8][12] + n * key[8][13] + o * key[8][14] + p * key[8][15] + q * key[8][16] + r * key[8][17] + s * key[8][18] + t * key[8][19] + u * key[8][20] - cipher1[8], a * key[9][0] + b * key[9][1] + c * key[9][2] + d * key[9][3] + e * key[9][4] + f * key[9][5] + g * key[9][6] + h * key[9][7] + i * key[9][8] + j * key[9][9] + k * key[9][10] + l * key[9][11] + m * key[9][12] + n * key[9][13] + o * key[9][14] + p * key[9][15] + q * key[9][16] + r * key[9][17] + s * key[9][18] + t * key[9][19] + u * key[9][20] - cipher1[9], a * key[10][0] + b * key[10][1] + c * key[10][2] + d * key[10][3] + e * key[10][4] + f * key[10][5] + g * key[10][6] + h * key[10][7] + i * key[10][8] + j * key[10][9] + k * key[10][10] + l * key[10][11] + m * key[10][12] + n * key[10][13] + o * key[10][14] + p * key[10][15] + q * key[10][16] + r * key[10][17] + s * key[10][18] + t * key[10][19] + u * key[10][20] - cipher1[10], a * key[11][0] + b * key[11][1] + c * key[11][2] + d * key[11][3] + e * key[11][4] + f * key[11][5] + g * key[11][6] + h * key[11][7] + i * key[11][8] + j * key[11][9] + k * key[11][10] + l * key[11][11] + m * key[11][12] + n * key[11][13] + o * key[11][14] + p * key[11][15] + q * key[11][16] + r * key[11][17] + s * key[11][18] + t * key[11][19] + u * key[11][20] - cipher1[11], a * key[12][0] + b * key[12][1] + c * key[12][2] + d * key[12][3] + e * key[12][4] + f * key[12][5] + g * key[12][6] + h * key[12][7] + i * key[12][8] + j * key[12][9] + k * key[12][10] + l * key[12][11] + m * key[12][12] + n * key[12][13] + o * key[12][14] + p * key[12][15] + q * key[12][16] + r * key[12][17] + s * key[12][18] + t * key[12][19] + u * key[12][20] - cipher1[12], a * key[13][0] + b * key[13][1] + c * key[13][2] + d * key[13][3] + e * key[13][4] + f * key[13][5] + g * key[13][6] + h * key[13][7] + i * key[13][8] + j * key[13][9] + k * key[13][10] + l * key[13][11] + m * key[13][12] + n * key[13][13] + o * key[13][14] + p * key[13][15] + q * key[13][16] + r * key[13][17] + s * key[13][18] + t * key[13][19] + u * key[13][20] - cipher1[13], a * key[14][0] + b * key[14][1] + c * key[14][2] + d * key[14][3] + e * key[14][4] + f * key[14][5] + g * key[14][6] + h * key[14][7] + i * key[14][8] + j * key[14][9] + k * key[14][10] + l * key[14][11] + m * key[14][12] + n * key[14][13] + o * key[14][14] + p * key[14][15] + q * key[14][16] + r * key[14][17] + s * key[14][18] + t * key[14][19] + u * key[14][20] - cipher1[14], a * key[15][0] + b * key[15][1] + c * key[15][2] + d * key[15][3] + e * key[15][4] + f * key[15][5] + g * key[15][6] + h * key[15][7] + i * key[15][8] + j * key[15][9] + k * key[15][10] + l * key[15][11] + m * key[15][12] + n * key[15][13] + o * key[15][14] + p * key[15][15] + q * key[15][16] + r * key[15][17] + s * key[15][18] + t * key[15][19] + u * key[15][20] - cipher1[15], a * key[16][0] + b * key[16][1] + c * key[16][2] + d * key[16][3] + e * key[16][4] + f * key[16][5] + g * key[16][6] + h * key[16][7] + i * key[16][8] + j * key[16][9] + k * key[16][10] + l * key[16][11] + m * key[16][12] + n * key[16][13] + o * key[16][14] + p * key[16][15] + q * key[16][16] + r * key[16][17] + s * key[16][18] + t * key[16][19] + u * key[16][20] - cipher1[16], a * key[17][0] + b * key[17][1] + c * key[17][2] + d * key[17][3] + e * key[17][4] + f * key[17][5] + g * key[17][6] + h * key[17][7] + i * key[17][8] + j * key[17][9] + k * key[17][10] + l * key[17][11] + m * key[17][12] + n * key[17][13] + o * key[17][14] + p * key[17][15] + q * key[17][16] + r * key[17][17] + s * key[17][18] + t * key[17][19] + u * key[17][20] - cipher1[17], a * key[18][0] + b * key[18][1] + c * key[18][2] + d * key[18][3] + e * key[18][4] + f * key[18][5] + g * key[18][6] + h * key[18][7] + i * key[18][8] + j * key[18][9] + k * key[18][10] + l * key[18][11] + m * key[18][12] + n * key[18][13] + o * key[18][14] + p * key[18][15] + q * key[18][16] + r * key[18][17] + s * key[18][18] + t * key[18][19] + u * key[18][20] - cipher1[18], a * key[19][0] + b * key[19][1] + c * key[19][2] + d * key[19][3] + e * key[19][4] + f * key[19][5] + g * key[19][6] + h * key[19][7] + i * key[19][8] + j * key[19][9] + k * key[19][10] + l * key[19][11] + m * key[19][12] + n * key[19][13] + o * key[19][14] + p * key[19][15] + q * key[19][16] + r * key[19][17] + s * key[19][18] + t * key[19][19] + u * key[19][20] - cipher1[19], a * key[20][0] + b * key[20][1] + c * key[20][2] + d * key[20][3] + e * key[20][4] + f * key[20][5] + g * key[20][6] + h * key[20][7] + i * key[20][8] + j * key[20][9] + k * key[20][10] + l * key[20][11] + m * key[20][12] + n * key[20][13] + o * key[20][14] + p * key[20][15] + q * key[20][16] + r * key[20][17] + s * key[20][18] + t * key[20][19] + u * key[20][20] - cipher1[20], a * key[21][0] + b * key[21][1] + c * key[21][2] + d * key[21][3] + e * key[21][4] + f * key[21][5] + g * key[21][6] + h * key[21][7] + i * key[21][8] + j * key[21][9] + k * key[21][10] + l * key[21][11] + m * key[21][12] + n * key[21][13] + o * key[21][14] + p * key[21][15] + q * key[21][16] + r * key[21][17] + s * key[21][18] + t * key[21][19] + u * key[21][20] - cipher1[21], a * key[22][0] + b * key[22][1] + c * key[22][2] + d * key[22][3] + e * key[22][4] + f * key[22][5] + g * key[22][6] + h * key[22][7] + i * key[22][8] + j * key[22][9] + k * key[22][10] + l * key[22][11] + m * key[22][12] + n * key[22][13] + o * key[22][14] + p * key[22][15] + q * key[22][16] + r * key[22][17] + s * key[22][18] + t * key[22][19] + u * key[22][20] - cipher1[22], a * key[23][0] + b * key[23][1] + c * key[23][2] + d * key[23][3] + e * key[23][4] + f * key[23][5] + g * key[23][6] + h * key[23][7] + i * key[23][8] + j * key[23][9] + k * key[23][10] + l * key[23][11] + m * key[23][12] + n * key[23][13] + o * key[23][14] + p * key[23][15] + q * key[23][16] + r * key[23][17] + s * key[23][18] + t * key[23][19] + u * key[23][20] - cipher1[23], a * key[24][0] + b * key[24][1] + c * key[24][2] + d * key[24][3] + e * key[24][4] + f * key[24][5] + g * key[24][6] + h * key[24][7] + i * key[24][8] + j * key[24][9] + k * key[24][10] + l * key[24][11] + m * key[24][12] + n * key[24][13] + o * key[24][14] + p * key[24][15] + q * key[24][16] + r * key[24][17] + s * key[24][18] + t * key[24][19] + u * key[24][20] - cipher1[24], a * key[25][0] + b * key[25][1] + c * key[25][2] + d * key[25][3] + e * key[25][4] + f * key[25][5] + g * key[25][6] + h * key[25][7] + i * key[25][8] + j * key[25][9] + k * key[25][10] + l * key[25][11] + m * key[25][12] + n * key[25][13] + o * key[25][14] + p * key[25][15] + q * key[25][16] + r * key[25][17] + s * key[25][18] + t * key[25][19] + u * key[25][20] - cipher1[25], a * key[26][0] + b * key[26][1] + c * key[26][2] + d * key[26][3] + e * key[26][4] + f * key[26][5] + g * key[26][6] + h * key[26][7] + i * key[26][8] + j * key[26][9] + k * key[26][10] + l * key[26][11] + m * key[26][12] + n * key[26][13] + o * key[26][14] + p * key[26][15] + q * key[26][16] + r * key[26][17] + s * key[26][18] + t * key[26][19] + u * key[26][20] - cipher1[26], a * key[27][0] + b * key[27][1] + c * key[27][2] + d * key[27][3] + e * key[27][4] + f * key[27][5] + g * key[27][6] + h * key[27][7] + i * key[27][8] + j * key[27][9] + k * key[27][10] + l * key[27][11] + m * key[27][12] + n * key[27][13] + o * key[27][14] + p * key[27][15] + q * key[27][16] + r * key[27][17] + s * key[27][18] + t * key[27][19] + u * key[27][20] - cipher1[27], a * key[28][0] + b * key[28][1] + c * key[28][2] + d * key[28][3] + e * key[28][4] + f * key[28][5] + g * key[28][6] + h * key[28][7] + i * key[28][8] + j * key[28][9] + k * key[28][10] + l * key[28][11] + m * key[28][12] + n * key[28][13] + o * key[28][14] + p * key[28][15] + q * key[28][16] + r * key[28][17] + s * key[28][18] + t * key[28][19] + u * key[28][20] - cipher1[28], a * key[29][0] + b * key[29][1] + c * key[29][2] + d * key[29][3] + e * key[29][4] + f * key[29][5] + g * key[29][6] + h * key[29][7] + i * key[29][8] + j * key[29][9] + k * key[29][10] + l * key[29][11] + m * key[29][12] + n * key[29][13] + o * key[29][14] + p * key[29][15] + q * key[29][16] + r * key[29][17] + s * key[29][18] + t * key[29][19] + u * key[29][20] - cipher1[29], a * key[30][0] + b * key[30][1] + c * key[30][2] + d * key[30][3] + e * key[30][4] + f * key[30][5] + g * key[30][6] + h * key[30][7] + i * key[30][8] + j * key[30][9] + k * key[30][10] + l * key[30][11] + m * key[30][12] + n * key[30][13] + o * key[30][14] + p * key[30][15] + q * key[30][16] + r * key[30][17] + s * key[30][18] + t * key[30][19] + u * key[30][20] - cipher1[30], a * key[31][0] + b * key[31][1] + c * key[31][2] + d * key[31][3] + e * key[31][4] + f * key[31][5] + g * key[31][6] + h * key[31][7] + i * key[31][8] + j * key[31][9] + k * key[31][10] + l * key[31][11] + m * key[31][12] + n * key[31][13] + o * key[31][14] + p * key[31][15] + q * key[31][16] + r * key[31][17] + s * key[31][18] + t * key[31][19] + u * key[31][20] - cipher1[31], a * key[32][0] + b * key[32][1] + c * key[32][2] + d * key[32][3] + e * key[32][4] + f * key[32][5] + g * key[32][6] + h * key[32][7] + i * key[32][8] + j * key[32][9] + k * key[32][10] + l * key[32][11] + m * key[32][12] + n * key[32][13] + o * key[32][14] + p * key[32][15] + q * key[32][16] + r * key[32][17] + s * key[32][18] + t * key[32][19] + u * key[32][20] - cipher1[32], a * key[33][0] + b * key[33][1] + c * key[33][2] + d * key[33][3] + e * key[33][4] + f * key[33][5] + g * key[33][6] + h * key[33][7] + i * key[33][8] + j * key[33][9] + k * key[33][10] + l * key[33][11] + m * key[33][12] + n * key[33][13] + o * key[33][14] + p * key[33][15] + q * key[33][16] + r * key[33][17] + s * key[33][18] + t * key[33][19] + u * key[33][20] - cipher1[33], a * key[34][0] + b * key[34][1] + c * key[34][2] + d * key[34][3] + e * key[34][4] + f * key[34][5] + g * key[34][6] + h * key[34][7] + i * key[34][8] + j * key[34][9] + k * key[34][10] + l * key[34][11] + m * key[34][12] + n * key[34][13] + o * key[34][14] + p * key[34][15] + q * key[34][16] + r * key[34][17] + s * key[34][18] + t * key[34][19] + u * key[34][20] - cipher1[34], a * key[35][0] + b * key[35][1] + c * key[35][2] + d * key[35][3] + e * key[35][4] + f * key[35][5] + g * key[35][6] + h * key[35][7] + i * key[35][8] + j * key[35][9] + k * key[35][10] + l * key[35][11] + m * key[35][12] + n * key[35][13] + o * key[35][14] + p * key[35][15] + q * key[35][16] + r * key[35][17] + s * key[35][18] + t * key[35][19] + u * key[35][20] - cipher1[35], a * key[36][0] + b * key[36][1] + c * key[36][2] + d * key[36][3] + e * key[36][4] + f * key[36][5] + g * key[36][6] + h * key[36][7] + i * key[36][8] + j * key[36][9] + k * key[36][10] + l * key[36][11] + m * key[36][12] + n * key[36][13] + o * key[36][14] + p * key[36][15] + q * key[36][16] + r * key[36][17] + s * key[36][18] + t * key[36][19] + u * key[36][20] - cipher1[36], a * key[37][0] + b * key[37][1] + c * key[37][2] + d * key[37][3] + e * key[37][4] + f * key[37][5] + g * key[37][6] + h * key[37][7] + i * key[37][8] + j * key[37][9] + k * key[37][10] + l * key[37][11] + m * key[37][12] + n * key[37][13] + o * key[37][14] + p * key[37][15] + q * key[37][16] + r * key[37][17] + s * key[37][18] + t * key[37][19] + u * key[37][20] - cipher1[37], a * key[38][0] + b * key[38][1] + c * key[38][2] + d * key[38][3] + e * key[38][4] + f * key[38][5] + g * key[38][6] + h * key[38][7] + i * key[38][8] + j * key[38][9] + k * key[38][10] + l * key[38][11] + m * key[38][12] + n * key[38][13] + o * key[38][14] + p * key[38][15] + q * key[38][16] + r * key[38][17] + s * key[38][18] + t * key[38][19] + u * key[38][20] - cipher1[38], a * key[39][0] + b * key[39][1] + c * key[39][2] + d * key[39][3] + e * key[39][4] + f * key[39][5] + g * key[39][6] + h * key[39][7] + i * key[39][8] + j * key[39][9] + k * key[39][10] + l * key[39][11] + m * key[39][12] + n * key[39][13] + o * key[39][14] + p * key[39][15] + q * key[39][16] + r * key[39][17] + s * key[39][18] + t * key[39][19] + u * key[39][20] - cipher1[39], a * key[40][0] + b * key[40][1] + c * key[40][2] + d * key[40][3] + e * key[40][4] + f * key[40][5] + g * key[40][6] + h * key[40][7] + i * key[40][8] + j * key[40][9] + k * key[40][10] + l * key[40][11] + m * key[40][12] + n * key[40][13] + o * key[40][14] + p * key[40][15] + q * key[40][16] + r * key[40][17] + s * key[40][18] + t * key[40][19] + u * key[40][20] - cipher1[40], a * key[41][0] + b * key[41][1] + c * key[41][2] + d * key[41][3] + e * key[41][4] + f * key[41][5] + g * key[41][6] + h * key[41][7] + i * key[41][8] + j * key[41][9] + k * key[41][10] + l * key[41][11] + m * key[41][12] + n * key[41][13] + o * key[41][14] + p * key[41][15] + q * key[41][16] + r * key[41][17] + s * key[41][18] + t * key[41][19] + u * key[41][20] - cipher1[41], a * key[42][0] + b * key[42][1] + c * key[42][2] + d * key[42][3] + e * key[42][4] + f * key[42][5] + g * key[42][6] + h * key[42][7] + i * key[42][8] + j * key[42][9] + k * key[42][10] + l * key[42][11] + m * key[42][12] + n * key[42][13] + o * key[42][14] + p * key[42][15] + q * key[42][16] + r * key[42][17] + s * key[42][18] + t * key[42][19] + u * key[42][20] - cipher1[42], a * key[43][0] + b * key[43][1] + c * key[43][2] + d * key[43][3] + e * key[43][4] + f * key[43][5] + g * key[43][6] + h * key[43][7] + i * key[43][8] + j * key[43][9] + k * key[43][10] + l * key[43][11] + m * key[43][12] + n * key[43][13] + o * key[43][14] + p * key[43][15] + q * key[43][16] + r * key[43][17] + s * key[43][18] + t * key[43][19] + u * key[43][20] - cipher1[43], a * key[44][0] + b * key[44][1] + c * key[44][2] + d * key[44][3] + e * key[44][4] + f * key[44][5] + g * key[44][6] + h * key[44][7] + i * key[44][8] + j * key[44][9] + k * key[44][10] + l * key[44][11] + m * key[44][12] + n * key[44][13] + o * key[44][14] + p * key[44][15] + q * key[44][16] + r * key[44][17] + s * key[44][18] + t * key[44][19] + u * key[44][20] - cipher1[44], a * key[45][0] + b * key[45][1] + c * key[45][2] + d * key[45][3] + e * key[45][4] + f * key[45][5] + g * key[45][6] + h * key[45][7] + i * key[45][8] + j * key[45][9] + k * key[45][10] + l * key[45][11] + m * key[45][12] + n * key[45][13] + o * key[45][14] + p * key[45][15] + q * key[45][16] + r * key[45][17] + s * key[45][18] + t * key[45][19] + u * key[45][20] - cipher1[45], a * key[46][0] + b * key[46][1] + c * key[46][2] + d * key[46][3] + e * key[46][4] + f * key[46][5] + g * key[46][6] + h * key[46][7] + i * key[46][8] + j * key[46][9] + k * key[46][10] + l * key[46][11] + m * key[46][12] + n * key[46][13] + o * key[46][14] + p * key[46][15] + q * key[46][16] + r * key[46][17] + s * key[46][18] + t * key[46][19] + u * key[46][20] - cipher1[46], a * key[47][0] + b * key[47][1] + c * key[47][2] + d * key[47][3] + e * key[47][4] + f * key[47][5] + g * key[47][6] + h * key[47][7] + i * key[47][8] + j * key[47][9] + k * key[47][10] + l * key[47][11] + m * key[47][12] + n * key[47][13] + o * key[47][14] + p * key[47][15] + q * key[47][16] + r * key[47][17] + s * key[47][18] + t * key[47][19] + u * key[47][20] - cipher1[47], a * key[48][0] + b * key[48][1] + c * key[48][2] + d * key[48][3] + e * key[48][4] + f * key[48][5] + g * key[48][6] + h * key[48][7] + i * key[48][8] + j * key[48][9] + k * key[48][10] + l * key[48][11] + m * key[48][12] + n * key[48][13] + o * key[48][14] + p * key[48][15] + q * key[48][16] + r * key[48][17] + s * key[48][18] + t * key[48][19] + u * key[48][20] - cipher1[48], a * key[49][0] + b * key[49][1] + c * key[49][2] + d * key[49][3] + e * key[49][4] + f * key[49][5] + g * key[49][6] + h * key[49][7] + i * key[49][8] + j * key[49][9] + k * key[49][10] + l * key[49][11] + m * key[49][12] + n * key[49][13] + o * key[49][14] + p * key[49][15] + q * key[49][16] + r * key[49][17] + s * key[49][18] + t * key[49][19] + u * key[49][20] - cipher1[49], a * key[50][0] + b * key[50][1] + c * key[50][2] + d * key[50][3] + e * key[50][4] + f * key[50][5] + g * key[50][6] + h * key[50][7] + i * key[50][8] + j * key[50][9] + k * key[50][10] + l * key[50][11] + m * key[50][12] + n * key[50][13] + o * key[50][14] + p * key[50][15] + q * key[50][16] + r * key[50][17] + s * key[50][18] + t * key[50][19] + u * key[50][20] - cipher1[50], a * key[51][0] + b * key[51][1] + c * key[51][2] + d * key[51][3] + e * key[51][4] + f * key[51][5] + g * key[51][6] + h * key[51][7] + i * key[51][8] + j * key[51][9] + k * key[51][10] + l * key[51][11] + m * key[51][12] + n * key[51][13] + o * key[51][14] + p * key[51][15] + q * key[51][16] + r * key[51][17] + s * key[51][18] + t * key[51][19] + u * key[51][20] - cipher1[51], a * key[52][0] + b * key[52][1] + c * key[52][2] + d * key[52][3] + e * key[52][4] + f * key[52][5] + g * key[52][6] + h * key[52][7] + i * key[52][8] + j * key[52][9] + k * key[52][10] + l * key[52][11] + m * key[52][12] + n * key[52][13] + o * key[52][14] + p * key[52][15] + q * key[52][16] + r * key[52][17] + s * key[52][18] + t * key[52][19] + u * key[52][20] - cipher1[52], a * key[53][0] + b * key[53][1] + c * key[53][2] + d * key[53][3] + e * key[53][4] + f * key[53][5] + g * key[53][6] + h * key[53][7] + i * key[53][8] + j * key[53][9] + k * key[53][10] + l * key[53][11] + m * key[53][12] + n * key[53][13] + o * key[53][14] + p * key[53][15] + q * key[53][16] + r * key[53][17] + s * key[53][18] + t * key[53][19] + u * key[53][20] - cipher1[53], a * key[54][0] + b * key[54][1] + c * key[54][2] + d * key[54][3] + e * key[54][4] + f * key[54][5] + g * key[54][6] + h * key[54][7] + i * key[54][8] + j * key[54][9] + k * key[54][10] + l * key[54][11] + m * key[54][12] + n * key[54][13] + o * key[54][14] + p * key[54][15] + q * key[54][16] + r * key[54][17] + s * key[54][18] + t * key[54][19] + u * key[54][20] - cipher1[54], a * key[55][0] + b * key[55][1] + c * key[55][2] + d * key[55][3] + e * key[55][4] + f * key[55][5] + g * key[55][6] + h * key[55][7] + i * key[55][8] + j * key[55][9] + k * key[55][10] + l * key[55][11] + m * key[55][12] + n * key[55][13] + o * key[55][14] + p * key[55][15] + q * key[55][16] + r * key[55][17] + s * key[55][18] + t * key[55][19] + u * key[55][20] - cipher1[55], a * key[56][0] + b * key[56][1] + c * key[56][2] + d * key[56][3] + e * key[56][4] + f * key[56][5] + g * key[56][6] + h * key[56][7] + i * key[56][8] + j * key[56][9] + k * key[56][10] + l * key[56][11] + m * key[56][12] + n * key[56][13] + o * key[56][14] + p * key[56][15] + q * key[56][16] + r * key[56][17] + s * key[56][18] + t * key[56][19] + u * key[56][20] - cipher1[56], a * key[57][0] + b * key[57][1] + c * key[57][2] + d * key[57][3] + e * key[57][4] + f * key[57][5] + g * key[57][6] + h * key[57][7] + i * key[57][8] + j * key[57][9] + k * key[57][10] + l * key[57][11] + m * key[57][12] + n * key[57][13] + o * key[57][14] + p * key[57][15] + q * key[57][16] + r * key[57][17] + s * key[57][18] + t * key[57][19] + u * key[57][20] - cipher1[57], a * key[58][0] + b * key[58][1] + c * key[58][2] + d * key[58][3] + e * key[58][4] + f * key[58][5] + g * key[58][6] + h * key[58][7] + i * key[58][8] + j * key[58][9] + k * key[58][10] + l * key[58][11] + m * key[58][12] + n * key[58][13] + o * key[58][14] + p * key[58][15] + q * key[58][16] + r * key[58][17] + s * key[58][18] + t * key[58][19] + u * key[58][20] - cipher1[58], a * key[59][0] + b * key[59][1] + c * key[59][2] + d * key[59][3] + e * key[59][4] + f * key[59][5] + g * key[59][6] + h * key[59][7] + i * key[59][8] + j * key[59][9] + k * key[59][10] + l * key[59][11] + m * key[59][12] + n * key[59][13] + o * key[59][14] + p * key[59][15] + q * key[59][16] + r * key[59][17] + s * key[59][18] + t * key[59][19] + u * key[59][20] - cipher1[59], a * key[60][0] + b * key[60][1] + c * key[60][2] + d * key[60][3] + e * key[60][4] + f * key[60][5] + g * key[60][6] + h * key[60][7] + i * key[60][8] + j * key[60][9] + k * key[60][10] + l * key[60][11] + m * key[60][12] + n * key[60][13] + o * key[60][14] + p * key[60][15] + q * key[60][16] + r * key[60][17] + s * key[60][18] + t * key[60][19] + u * key[60][20] - cipher1[60], a * key[61][0] + b * key[61][1] + c * key[61][2] + d * key[61][3] + e * key[61][4] + f * key[61][5] + g * key[61][6] + h * key[61][7] + i * key[61][8] + j * key[61][9] + k * key[61][10] + l * key[61][11] + m * key[61][12] + n * key[61][13] + o * key[61][14] + p * key[61][15] + q * key[61][16] + r * key[61][17] + s * key[61][18] + t * key[61][19] + u * key[61][20] - cipher1[61], a * key[62][0] + b * key[62][1] + c * key[62][2] + d * key[62][3] + e * key[62][4] + f * key[62][5] + g * key[62][6] + h * key[62][7] + i * key[62][8] + j * key[62][9] + k * key[62][10] + l * key[62][11] + m * key[62][12] + n * key[62][13] + o * key[62][14] + p * key[62][15] + q * key[62][16] + r * key[62][17] + s * key[62][18] + t * key[62][19] + u * key[62][20] - cipher1[62], a * key[63][0] + b * key[63][1] + c * key[63][2] + d * key[63][3] + e * key[63][4] + f * key[63][5] + g * key[63][6] + h * key[63][7] + i * key[63][8] + j * key[63][9] + k * key[63][10] + l * key[63][11] + m * key[63][12] + n * key[63][13] + o * key[63][14] + p * key[63][15] + q * key[63][16] + r * key[63][17] + s * key[63][18] + t * key[63][19] + u * key[63][20] - cipher1[63]]
B = Ideal(G).groebner_basis()

flag1 = ''
for i in B:
    t = prime - int(findall(r"\d+", str(i))[0])
    flag1 += chr(t)
# flag{14e6f236-9eb9-46
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 sage.modules.free_module_integer import IntegerLattice
from itertools import starmap
from operator import mul


# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small


m = 64
n = 21
q = prime

A_values = key
b_values = cipher2

A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))
for i in ingredients:
    print(chr(i), end='')

for row, b in zip(A_values, b_values):
    effect = sum(starmap(mul, zip(map(int, ingredients), row))) % q
    assert (abs(b - effect) < 2 ** 37)
# fc-b636-4c54c3732e5f}

Reference

  1. 【WP】2022年春秋杯春季赛Misc、Crypto类题目解析
  2. Tover. L-DLP、Knapsack、和2022春秋杯的notKnapsack
  3. PRODUCT SUBSET PROBLEM: APPLICATIONS TO NUMBER THEORY AND CRYPTOGRAPHY
  4. PRODUCT SUBSET PROBLEM: APPLICATIONS TO NUMBER THEORY AND CRYPTOGRAPHY-github
  5. 55-AA-模线性方程组在密码分析中的应用
  6. Lazzzaro-离散对数
  7. Lazzaro-格密码