0CTF Finals 2021 | ezmat

#0ctf2021finals

from hashlib import sha256
from secret import flag

global p, alphabet
p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'

flag = flag.lstrip('flag{').rstrip('}')
assert len(flag) == 24
assert sha256(flag.encode()).hexdigest() == '95cb911a467482cc0f879861532e9ec7680b0846b48a9de25fb13b01c583d9f8'

def cross(m):
    return alphabet.index(m)

def prepare(msg):
    A = zero_matrix(GF(p), 11, 11)
    for k in range(len(msg)):
        i, j = 5*k // 11, 5*k % 11
        A[i, j] = cross(msg[k])
    return A

def keygen():
    R = random_matrix(GF(p), 11, 11)
    while True:
        S = random_matrix(GF(p), 11, 11)
        if S.rank() == 11:
            _, L, U = S.LU()
            return R, (L, U)

def encrypt(A, pk, sk):
    R, L, U = pk, sk[0], sk[1]
    S = L * U
    X = A + R
    Y = S * X
    E = L.inverse() * Y
    return E

A = prepare(flag)
pk, sk = keygen()
E = encrypt(A, pk, sk)
print(f'E = \n{E}')
print(f'pk = \n{pk}')
'''
E = 
[31 45 41 12 36 43 45 51 25  2 64]
[68 24 32 35 52 13 64 10 14  2 40]
[34 34 64 32 67 25 21 57 31  6 56]
[ 7 17 12 33 54 66 28 25 40 23 26]
[14 65 70 35 67 55 47 36 36 42 57]
[68 28 33  0 45 52 59 29 52 41 46]
[60 35  0 21 24 44 49 51  1  6 35]
[20 21 44 57 23 35 30 28 16 23  0]
[24 64 54 53 35 42 40 17  3  0 36]
[32 53 39 47 39 56 52 15 39  8  9]
[ 7 57 43  5 38 59  2 25  2 67 12]
pk = 
[53 28 20 41 32 17 13 46 34 37 24]
[ 0  9 54 25 36  1 21 24 56 51 24]
[61 41 10 56 57 28 49  4 44 70 34]
[47 58 36 53 68 66 34 69 22 25 39]
[ 4 70 21 36 53 26 59 51  3 44 28]
[41 23 39 37  1 28 63 64 37 35 51]
[43 31 16 36 45  5 35 52  7 45 41]
[26  3 54 58 50 37 27 49  3 46 11]
[14 48 18 46 59 64 62 31 42 41 65]
[17 50 68 10 24 40 58 46 48 14 58]
[46 24 48 32 16  1 27 18 27 17 20]
'''

問題設定はCrypto CTF 2021 | Onludeとほとんど同じで、与えられるパラメータだけが異なっている。

今回はとだけしかもらえず、この2値の間には

という関係がある。

ここでが上三角行列、またのほとんどの要素は0であることを考えると、なんかz3とかで頑張って解けないか、という気分になってくる。実際は難しいところは解けないのだが、5バイトを除いては解けるので、あとは5バイトを全探索する

groebner basisでがんばった

p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
names = ["a{}".format(i) for i in range(24)] + ["u{}".format(i) for i in range(66)]
PR = PolynomialRing(GF(p), names=names)
gens = PR.gens()
a, u = gens[:24], gens[24:]

def makeA(a):
    A = zero_matrix(PR, 11, 11)
    for k in range(len(a)):
        i, j = 5*k // 11, 5*k % 11
        A[i, j] = a[k]
    return A

def makeU(u):
    A = zero_matrix(PR, 11, 11)
    k = 0
    for i in range(11):
        for j in range(i, 11):
            A[i,j] = u[k]
            k += 1
    return A

R = [
    [53, 28, 20, 41, 32, 17, 13, 46, 34, 37, 24],
    [0, 9, 54, 25, 36, 1, 21, 24, 56, 51, 24],
    [61, 41, 10, 56, 57, 28, 49, 4, 44, 70, 34],
    [47, 58, 36, 53, 68, 66, 34, 69, 22, 25, 39],
    [4, 70, 21, 36, 53, 26, 59, 51, 3, 44, 28],
    [41, 23, 39, 37, 1, 28, 63, 64, 37, 35, 51],
    [43, 31, 16, 36, 45, 5, 35, 52, 7, 45, 41],
    [26, 3, 54, 58, 50, 37, 27, 49, 3, 46, 11],
    [14, 48, 18, 46, 59, 64, 62, 31, 42, 41, 65],
    [17, 50, 68, 10, 24, 40, 58, 46, 48, 14, 58],
    [46, 24, 48, 32, 16, 1, 27, 18, 27, 17, 20]]
E = [
    [31,45,41,12,36,43,45,51,25,2,64],
    [68,24,32,35,52,13,64,10,14,2,40],
    [34,34,64,32,67,25,21,57,31,6,56],
    [7,17,12,33,54,66,28,25,40,23,26],
    [14,65,70,35,67,55,47,36,36,42,57],
    [68,28,33,0,45,52,59,29,52,41,46],
    [60,35,0,21,24,44,49,51,1,6,35],
    [20,21,44,57,23,35,30,28,16,23,0],
    [24,64,54,53,35,42,40,17,3,0,36],
    [32,53,39,47,39,56,52,15,39,8,9],
    [7,57,43,5,38,59,2,25,2,67,12],
]

U = makeU(u)
A = makeA(a)
R = matrix(PR, R)
E = matrix(PR, E)

flag = ["_" for _ in range(len(a))]

X = U*(A + R)

polys = []
for i in range(11):
    for j in range(11):
        polys.append( X[i,j] - E[i,j] )

I = Ideal(polys)
polys = []
G = I.groebner_basis()
for eq in list(G):
    if not eq.is_univariate():
        continue
    r = eq.univariate_polynomial().roots()[0][0]
    v = eq.variables()[0]

    if v in a:
        k = a.index(v)
        i, j = 5*k // 11, 5*k % 11
        A[i, j] = int(r)
        flag[k] = alphabet[r]
    elif v in u:
        idx = u.index(v)
        k = 0
        for i in range(11):
            for j in range(i, 11):
                if k == idx:
                    U[i,j] = int(r)
                k += 1
    else:
        print(v)


from itertools import product
from hashlib import sha256
from tqdm import tqdm

for a1,a2,a3,a4,a5 in (product(list(range(71)), repeat=5)):
    # I know a3 + 11*a4 + 35
    # a3 = -(11*a4 + 35) % p
    # assert (a3 + 11*a4 + 35) % p == 0

    flag[0] = alphabet[a1]
    flag[1] = alphabet[a2]
    flag[2] = alphabet[a3]
    flag[3] = alphabet[a4]
    flag[4] = alphabet[a5]

    if sha256("".join(flag).encode()).hexdigest() == '95cb911a467482cc0f879861532e9ec7680b0846b48a9de25fb13b01c583d9f8':
        print(flag)
        quit()