Crypto CTF 2021 | Hyper Normal

#cryptoctf2021

#!/usr/bin/env python3

import random
from flag import FLAG

p = 8443

def transpose(x):
    result = [[x[j][i] for j in range(len(x))] for i in range(len(x[0]))]
    return result

def vsum(u, v):
    assert len(u) == len(v)
    l, w = len(u), []
    for i in range(l):
        w += [(u[i] + v[i]) % p]
    return w

def sprod(a, u):
    w = []
    for i in range(len(u)):
        w += [a*u[i] % p]
    return w

def encrypt(msg):
    l = len(msg)
    hyper = [ord(m)*(i+1) for (m, i) in zip(list(msg), range(l))]
    V, W = [], []
    for i in range(l):
        v = [0]*i + [hyper[i]] + [0]*(l - i - 1)
        V.append(v)
    random.shuffle(V)
    for _ in range(l):
        R, v = [random.randint(0, 126) for _ in range(l)], [0]*l
        for j in range(l):
            v = vsum(v, sprod(R[j], V[j]))
        W.append(v)
    random.shuffle(transpose(W))
    return W

enc = encrypt(FLAG)
print(enc)

フラグからなる対角行列を作って行シャッフルしたあと、以下のようにを作 り、列シャッフルする

は行シャッフルされた対角行列であったことを思い出すと、シャッフル前のについて、次のように簡略化できる

の値は小さいので共通のが復元される（例えば）を探索すればの候補がでる。あとはが順序付けされていそうなことを考えて順番を復元すればOK

import ast
from collections import Counter

with open("output.txt") as f:
    W = ast.literal_eval(f.read().strip())

p = 8443
n = len(W)


chars = []
for x in range(n):
    appears = []
    for y in range(n):
        for r in range(1, 126):
            v = W[y][x] * pow(r, -1, p) % p
            if v == 0:
                continue
            appears.append(v)

    counter = Counter(appears)
    chars.append(counter.most_common()[0][0])

print(bytes([c // (i + 1)for i, c in enumerate(chars)]))
# used = set()
# # chars = sorted(chars)
# flag = []
# for i in range(len(chars)):
#     for j in range(len(chars)):
#         if j in used:
#             continue
#         if chars[j] % (i+1) == 0:
#             used.add(j)
#             flag.append(chars[j] // (i + 1))
#             break
#     else:
#         flag.append(0)
#         # raise ValueError("warikirenai")
# print(bytes(flag))