# [crypto] matrix cipher - CakeCTF 2021
###### tags: `CakeCTF 2021`

with open("flag.txt", "rb") as f:
    flag = list(f.read().strip())

def hadamard(M):
    d = M.determinant()
    x = 1.0
    for row in M:
        x *= row.norm()
    return (d / x) ** (1.0/M.ncols())

def keygen(n, d):
    k = int(floor(sqrt(n) * d))
    while True:
        R = k * Matrix.identity(ZZ, n) + random_matrix(ZZ, n, n, x=-d, y=d)
        if  hadamard(R) >= 0.7:
            break

    B = R
    while True:
        U = random_matrix(ZZ, n, n, algorithm="unimodular")
        B = U * B
        if hadamard(B) <= 0.2:
            break

    return B, R

def encrypt(B, m):
    assert B.nrows() == len(m)
    return vector(ZZ, m) * B  + random_vector(ZZ, len(m), x=-50, y=50)

B, R = keygen(len(flag), 100)
c = encrypt(B, flag)

print(list(B))
print(c)

これはGGH Cryptosystemという暗号方式（たぶん）

なにやら $R$という行列を作った後、ユニモジュラ行列$U$をかけて$B = UR$を作っている。$R$は対角成分が比較的大きく、$R$はhadamard ratioが0.2以下と非常に小さい

暗号化は$c = mB + r$で$r$は比較的小さい乱数のベクトル

したがって復号するにはどうにかして$r$の影響を無視して$B^{-1}$をかけることになる。誤差の影響を$c$から$mB$を得るにはCVPを解くとよい。$B$で張られる格子の小さい基底がわかっていれば、Babai's RoundingによってCVPが解ける。

import ast

def babai_rounding(w, basis):
    b_, _ = basis.gram_schmidt()
    b = w
    for i in range(len(b))[::-1]:
        c = round(b_[i].dot_product(b) / (b_[i].norm() ** 2))
        b = b - c * basis[i]

    return w - b

def decrypt(B, R, c):
    mB = babai_rounding(c, R)
    return mB * B.inverse()

B, c = open("output.txt").read().strip().split("\n")
B = Matrix(ZZ, ast.literal_eval(B))
c = vector(ZZ, ast.literal_eval(c))

m = decrypt(B, B.LLL(), c)
print("".join([chr(c) for c in m]))