Null CTF 2025 대회 crypto-Classically

음 클래식 이라는 힌트와 아래 압축 파일을 열어보았다.

두 개의 파일이 존재 했다. M.py 와 main.py 그 안에는 다음과 같은 여러가지 숫자들이 존재함

 

 

[M.py 파일]

"""Statically defined 64x64 matrix for the linear system."""

 

M = [

    [57121, 19227, 32536, 277, 59722, 59191, 63981, 65014, 21161, 58022, 20206, 57613, 62723, 57302, 43570, 52022, 39155, 8180, 53332, 26348, 10715, 35123, 51712, 31978 ..................

 

[main.py 파일]

from M import M

flag = open("./flag.txt", "r").read().encode()

n = 64
assert len(flag) == n and flag[:4] == b"ctf{" and flag[-1:] == b"}"
mod = 0x10001

result = []

assert len(M) == n
for v in M:
assert len(v) == n

for i in range(n):
dot = 0
for j in range(n):
dot += M[i][j] * flag[j]
result.append(dot % mod)

print(result)
# [29839, 662, 50523, 15906, 32667, 25159, 5172, 11685, 5618, 62174, 54405, 34902, 12259, 59526, 12299, 37286, 6055, 16813, 42488, 40708, 7662, 24263, 24047, 55429, 64420, 18167, 36330, 18325, 61471, 559, 32085, 23807, 26543, 26886, 24249, 45980, 23360, 15196, 42894, 33054, 22073, 23786, 63308, 44883, 60088, 38633, 54798, 42893, 29049, 25567, 33563, 49913, 63714, 51666, 60112, 19656, 13133, 11756, 34277, 55622, 14539, 54580, 48536, 1337]

 

M.py 파일은 선형 시스템을 위해 정적으로 정의된 64x64 행렬을 나타냄

main.py 파일은

 

Python과 선형 대수 라이브러리를 사용하여 코드로 해결해야 함

따라서 python을 설치해줌

이 후 Numpy or Sympy를 선택해줌 둘의 차이는 

NumPy는 대규모 배열과 행렬을 효율적으로 처리하기 위한 파이썬의 핵심 라이브러리

SymPy는 수학적 기호를 그대로 사용하여 계산하고, 결과를 대수적 표현으로 반환하는 라이브러리

 

우선 Numpy를 실행했떠니 numpy.linalg.LinAlgError: Singular matrix 라고 나옴

이게 무엇인가 하니

이 Traceback은 modInverse 함수에서 **Exception: Zero division**이 발생했음을 보여줌

이것은 $\text{det}(\mathbf{M})$ (행렬식) 값이 모듈로 연산에서 $\mathbf{0}$이 되거나, $\text{det}(\mathbf{M}) \pmod{m}$ 값이 $\mathbf{0}$이 되었음을 의미

>> 오류의 원인: 비가역 행렬 (Singular Matrix)

 

따라서 Sympy를 설치하고 코드를 실행해줌

우선 여기서 중요 한게 앞서 말한 파일 두 개로 cd를 통해 이동해 주고 파이썬을 실행해야 함

설치 :  python -m pip install sympy

코드 실행

import numpy as np

import M

from sympy import Matrix

 

n = 64

mod = 0x10001

C = np.array([29839, 662, 50523, 15906, 32667, 25159, 5172, 11685, 5618, 62174, 54405, 34902, 12259, 59526, 12299, 37286, 6055, 16813, 42488, 40708, 7662, 24263, 24047, 55429, 64420, 18167, 36330, 18325, 61471, 559, 32085, 23807, 26543, 26886, 24249, 45980, 23360, 15196, 42894, 33054, 22073, 23786, 63308, 44883, 60088, 38633, 54798, 42893, 29049, 25567, 33563, 49913, 63714, 51666, 60112, 19656, 13133, 11756, 34277, 55622, 14539, 54580, 48536, 1337])

M_matrix_sympy = Matrix(M.M)

-------------------------------------------------------------------------------------

try:

         M_inv_sympy = M_matrix_sympy.inv_mod(mod)

except Exception as e:

           raise

M_inv_np = np.array(M_inv_sympy.tolist(), dtype=np.int64)

flag_vec = np.dot(M_inv_np, C) % mod

flag_bytes = bytes(flag_vec.astype(np.uint8))

print(flag_bytes)

 

위에 인자값을 순서대로 넣어주면 

 

출력된 바이트 문자열을 플래그 형태로 변환하면

 

ctf{s0lve_th3_equ4t10n5_t0_f1nd_fl4g_h3r3_w4s_easy_en0ugh_NO???}

 

문제 해결 과정을 요약하면

 

1. 문제 식별: $64 \times 64$ 행렬 $\mathbf{M}$과 암호문 벡터 $\mathbf{C}$를 사용하는 힐 암호(Hill Cipher) 문제

2. 모듈로 확인: 암호화 코드(main.py)에서 모듈로 값 $\text{mod} = 0\text{x}10001 = 65537$ 임을 확인

3. 복호화 공식 적용: $\mathbf{flag} = (\mathbf{M}^{-1} \cdot \mathbf{C}) \pmod{\text{mod}}$ 공식을 사용

4. 도구 사용: 대규모 정수 행렬의 정확한 모듈로 역행렬을 계산하기 위해 SymPy 라이브러리를 사용

5. 성공: 역행렬 계산 후 암호문 벡터와 곱하여 플래그를 복원