[zer0pts] nibelung

문제에서는 fglg.py , server.py 두 파일이 제공되었는데 server.py에서 fglg.py를 불러와서 사용하는 형태이다.

fglg.py는 단순히 그냥 행렬과 일반적인 연산을 만들어둔 코드이다.

 

 

def bytes2gl(b, n, p=None):
    assert len(b) <= n * n
    X = FiniteGeneralLinearGroup(n, p)
    padlen = n * n - len(b)
    b = bytes([padlen]) * padlen + b # 앞에 패딩 길이 만큼 padding
    for i in range(n):
        for j in range(n):
            X.set_at((j, i), b[i*n + j])
    return X

def recv_message(n, p):
    print("Data: ", end="", flush=True)
    b = base64.b64decode(input())
    return bytes2gl(b, n, p)

def encrypt(U, X):
    return U * X * U**-1

def decrypt(U, X):
    return U**-1 * X * U

if __name__ == '__main__':
    # Create flag F
    n = math.ceil(math.sqrt(len(flag))) # len(flag) : 26~36
    F = bytes2gl(flag, n)
    p = F.p

    # Generate private key
    U = FiniteGeneralLinearGroup(n, p)
    while U.determinant() == 0:
        U.set_random()

 

주요 함수는 위의 4개인데,

byte2gl은, 입력을 받아서 앞에 패딩을 한 후 fglg.py에서 만든 형태로 행렬로 만든다.

recv_message를 보면 base64 인코딩된 입력을 받아서 이를 디코딩 한 뒤, 그것을 행렬로 바꾸어준다.

encrypt 와 decrypt는 단순 행렬 연산이다.

그리고 enc / dec 에서 곱하는 U는 determinant가 0으로, 역행렬이 존재하지 않는 것이다.

허나 fglg.py에서 U**-1를 정의해놓았기 때문에 저렇게 연산은 가능하다.

우리가 해야하는 것은 다음과 같다.

 

U ** -1 * flag * U

 

하지만 입력을 항상 base64 인코딩한 값만 넣기 때문에 0~255사이의 값으로 된 input만 입력할 수 있다.

만약 위 flag를 0~255 사이의 값들로 바꿀 수 있다면 우리는 서버의 기능으로 마음대로 enc / dec 할 수 있다는 의미이다.

여기서 생각할 수 있는 것은 homomorphism이다.

 

dec(A+B) = dec(A) + dec(B) 
dec(A-B) = dec(A) - dec(B)

 

행렬의 단순 연산이기 때문이 위 연산이 성립한다.

우리는 flag를 받아서 이를 0~255 사이의 값들로 이루어진 행렬로 쪼개어 dec 후 더해준다면

flag를 얻어낼 수 있다.

문제에서 다루고 있는 행렬은 6 * 6 행렬이기 때문에 단순 무식하게 연산을 했다.

(i,j) 만 1이고 나머지 모두 0인 행렬을 만들어서 flag에서 (i,j) 값을 곱해주면 flag의 (i,j)번째 항을 만들 수 있다.

이렇게 36번만 반복하면 우리는 flag를 쪼갤 수 있고, flag를 얻어낼 수 있다.