스테가노그래피

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

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

스테가노그래피는 사진이나 메시지 같은 정보에 다른 데이터를 몰래 숨기는 기법이다. 아래 노트를 읽으면 스테가노그래피가 무엇인지 자세히 알 수 있다. 창호가 개발한 스테가노그래피 기법은 2차원 좌표평면의 격자점 색깔로 정보를 숨긴다. 처음에는 모든 격자점이 색깔 $0$으로 칠해져 있다. 창호는 다음 두 가지 행동을 할 수 있다.

• 은닉: 주어진 점 하나를 주어진 색깔로 칠한다.
• 검사: 주어진 두 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$는 음이 아닌 정수다.

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

검사 행동마다 두 구간에 칠해진 패턴이 같으면 1, 다르면 0을 한 줄에 하나씩 출력한다.

스테가노그래피는 숨겨야 할 데이터를 다른 데이터 안에 넣어 감추는 기술이다. 보통 사진, 동영상, 음악에 아주 작은 변화를 주어 데이터를 넣는데, 이미지의 픽셀이나 오디오의 진동수를 미세하게 조정하는 식이다. 무심코 보면 알아채기 어렵지만, 은폐가 정교하지 않으면 원본과 다른 부분이 드러난다. 암호는 데이터 자체를 읽지 못하게 만들고, 스테가노그래피는 데이터를 단순히 숨긴다. 여러 줄로 이루어진 문장의 첫 글자를 이어 읽으면 숨은 뜻이 나타나는 세로드립도 스테가노그래피의 일종이라 할 수 있다.

MatKor도 예전에 스테가노그래피를 사용한 적이 있다. <제6회 고려대학교 MatKor Cup : 2025 Winter>의 본 대회 유의사항 탭의 사진이나, <제1회 MatDegy Cup>의 문제에서 스테가노그래피로 정보를 숨겨, 참가자가 숨겨진 문제를 찾도록 했다.

간단한 스테가노그래피는 누구나 쉽게 숨기고 해독할 수 있도록 공개된 도구가 많다. 구글에서 스테가노그래피 복호화나 암호화를 검색하면 무료 도구를 바로 쓸 수 있다.