스테가노그래피

MatKor는 2022년 1학기 활동과 여름에 열린 <제1회 MatKor Cup:2022 Summer>를 토대로 2학기 사이버국방학과 동아리로 인준되었다. 이제 MatKor는 동아리 부원을 공개적으로 모집하고 세미나와 프로젝트 등 다양한 활동을 시작하였다.

또 다른 사이버국방학과 동아리인 AlKor는 MatKor를 견제하려 한다. 이를 알아챈 MatKor의 회장인 창호는 스테가노그래피(Steganography)를 이용해 정보를 숨기려고 한다.

스테가노그래피는 사진이나 메시지 등 어떤 정보에 다른 데이터를 몰래 숨기는 기법을 의미한다. 스테가노그래피와 관련된 자세한 내용은 아래 노트를 통해 스테가노그래피가 무엇인지 한 번 읽어보도록 하자. 구체적으로 창호가 개발한 스테가노그래피 기법은 2차원 좌표평면의 격자점의 색깔을 이용해 정보를 숨기는 것으로, 처음에는 모든 격자점이 색깔 $0$으로 칠해져 있다. 창호는 다음 두 가지 은닉과 검사 행동을 할 수 있다.

• 은닉: 주어진 점 하나를 주어진 색깔로 색칠한다.
• 검사: 주어진 두 2차원 구간에 색칠된 패턴이 동일한지 판단한다. 두 2차원 구간 $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$와 $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$에 색칠된 패턴이 동일하다는 것은, 모든 정수 $0\le i\le w$, $0\le j\le h$에 대해 $(x_1+i,y_1+j)$의 색깔과 $(x_2+i,y_2+j)$의 색깔이 동일하다는 것을 의미한다.

검사 행동이 주어졌을 때 창호를 도와 주어진 두 2차원 구간에 색칠된 패턴이 동일한지 판단해 보자.

첫 번째 줄에 창호가 시행하는 행동의 수 $Q(1\le Q\le 10^5)$가 주어진다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 창호가 시행하는 행동이 다음과 같은 형식으로 주어진다.

• 은닉 행동의 경우 1 $x$ $y$ $c$의 형식으로 주어진다. 이는 점 $(x,y)$를 색깔 $c$로 색칠함을 의미한다.
• 검사 행동의 경우 2 $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ $w$ $h$의 형식으로 주어진다. 이는 두 2차원 구간 $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$와 $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$에 색칠된 패턴이 동일한지 판단해야 함을 의미한다.
• 모든 입력은 $-10^{9}$ 이상, $10^{9}$ 이하의 정수이며, $w$와 $h$의 경우 음이 아닌 정수이다.

검사 행동이 한 번 이상 주어진다.

첫 번째 줄부터 $2$번 쿼리가 주어졌을 때, 두 2차원 구간에 색칠된 패턴이 동일하면 1, 아니면 0을 한 줄에 한 개씩 출력한다.

스테가노그래피는 숨겨야 할 데이터를 또 다른 데이터에 넣어 은폐하는 기술이다. 주로 사진, 동영상, 음악 등에 아주 미세한 변화를 주어 데이터를 넣게 되며, 무심코 지나치면 인지할 수 없지만 실제로는 이미지의 픽셀이나 오디오의 진동수 등을 미세하게 조정하여 기존과 다른 부분이 존재하기 때문에, 은폐가 정교하지 않다면 은폐했다는 사실을 눈치챌 수 있다. 암호는 데이터 자체를 읽지 못하게 만드는 반면, 스테가노그래피는 단순히 숨기는 기법으로, 스테가노그래피의 일종으로 여러 줄로 이루어진 문장의 첫 글자를 읽으면 숨겨진 뜻이 나타나는 세로드립 역시 스테가노그래피라 할 수 있다.

실제로 MatKor에서 진행한 <제6회 고려대학교 MatKor Cup : 2025 Winter>의 본 대회 유의사항 탭의 사진이나, <제1회 MatDegy Cup>의 문제에서 스테가노그래피를 통해 정보를 은닉해 참여자들이 숨겨진 문제를 찾게 한 적이 있다. 간단한 스테가노그래피는 누구나 쉽게 숨기고 해독할 수 있도록 공개되어 있는 도구들이 많으며, 단순히 구글에 스테가노그래피 복호화나 암호화와 관련된 검색만 하면 무료로 도구를 사용할 수 있다.