암호화의 취약점 찾기

암호화하여 전송하고 싶은 데이터가 32비트 부호 없는 정수 8개로 주어진다.

$$ N_1\ N_2\ N_3\ \ldots\ N_8 $$

먼저 이 데이터가 올바른지 확인하기 위한 체크섬(checksum)을 구해 9번째 데이터로 추가한다. (체크섬은 데이터의 무결성을 확인하는 데 자주 쓰이는 방식이다.)

$$ N_9 = \left(\sum_{i=1}^{8} N_i\right) \bmod 2^{32} $$

그다음 32비트 키 $K$를 사용해 이 9개의 수를 암호화한다. 암호화는 XOR 연산으로 이루어진다고 하자. (XOR은 데이터 암호화에 자주 쓰이는 연산이다.)

$$ M_1 = N_1 \oplus K,\quad M_2 = N_2 \oplus K,\quad \ldots,\quad M_9 = N_9 \oplus K $$

이렇게 만든 9개의 데이터 $M_1$부터 $M_9$까지를 전송하면, $K$를 아는 사람은 원래 데이터 $N_1$부터 $N_8$까지를 복원할 수 있다. 그런데 $K$를 모르는 사람도 원래 데이터 $N_1$부터 $N_8$까지를 알아낼 수… 있다!

놀랍게도 이 방식에는 취약점이 있다. 그 취약점을 이용하여, 9개의 정수 $M_1$부터 $M_9$까지가 16진수로 주어질 때 키 $K$를 구하는 프로그램을 작성하라.

입력의 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 $1000$을 넘지 않는다.

그다음 각 테스트 케이스마다 9개의 정수 $M_1$부터 $M_9$까지가 16진수로 주어진다. 각 16진수는 숫자 0–9와 소문자 a–f로만 표기되며, 앞에 불필요한 0이 붙지 않는다. 한 테스트 케이스의 9개 수가 모두 한 줄에 주어지지 않을 수도 있다.

각 테스트 케이스마다 키 $K$를 소문자 16진수로 한 줄에 하나씩 출력한다. 앞에 불필요한 0은 출력하지 않는다.

스포일러 주의. 핵심은 $N_9 = \left(\sum_{i=1}^{8} N_i\right) \bmod 2^{32}$라는 관계다. 여덟 개의 $N_i = M_i \oplus K$를 더할 때, 각 비트 자리에서 합의 홀짝은 그 자리의 키 비트 $k_j$와 무관하다. 따라서 최하위 비트부터 덧셈의 자리올림을 따라가며 $K$의 각 비트를 하나씩 유일하게 결정할 수 있다.