허술한 암호화

운영체제의 역사에서 보안은 늘 중요한 문제였고, 특히 비밀번호를 안전하게 저장하는 방법이 오랫동안 연구되어 왔다. 비밀번호는 평문으로 저장해서는 안 되므로, 오늘날 많은 시스템은 비밀번호를 해시(예: MD5)로 저장한다.

해시 기반 저장에 대한 공격 중 하나는, 흔히 쓰이는 비밀번호들을 미리 해시해 둔 뒤 저장된 해시와 비교하는 것이다. 이를 막기 위해 어떤 회사는 사용자 이름과 비밀번호를 함께 암호화하면 안전하다고 주장했지만, 이 방식은 생각만큼 안전하지 않다. 우리는 이 허술함을 증명하기 위해 어떤 서버에서 사용자 이름 목록, 비밀번호 목록, 그리고 암호화된 문자열을 확보했다.

암호화 방식은 다음과 같다. 암호화할 단어를 $w$라 하고, 그 문자들을 $w_0, w_1, \dots, w_{n-1}$라 하자. 각 문자는 일반 ASCII 인코딩에 따라 8비트로 표현된다. $c_i$를 $w$의 앞 $i+1$개 문자를 암호화한 결과라 하며, $c_i$는 문자들의 나열이 아니라 하나의 비트열로 취급한다. 암호화 규칙은 다음과 같다.

$c_0 = w_0$

$c_i = (c_{i-1} \ll 4) \oplus w_i \quad (i \ge 1)$

여기서 $\ll$는 비트 왼쪽 시프트다. 예를 들어 비트열 00101011을 왼쪽으로 2비트 시프트하면 0010101100이 된다. 암호화 과정에서 비트열은 계속 길어질 수 있으며 어떤 비트도 버려지지 않는다. 0인 비트도 의미가 있으므로, 맨 왼쪽의 0비트라도 무시하지 않는다. 시프트의 효과는 비트열 오른쪽에 0비트를 붙이는 것이다.

$\oplus$는 비트 단위 XOR로, 두 비트가 같으면 0, 다르면 1을 낸다. 예를 들어 100011 XOR 0101 = 100110이다. (짧은 쪽은 오른쪽에 맞춰 정렬한다.)

암호화할 단어는 사용자 이름과 비밀번호를 이어 붙인 것, 즉 사용자이름 + 비밀번호이다.

첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에, 크래킹해야 할 '암호화된 사용자 이름과 비밀번호'가 주어진다. 비트열은 대문자 16진수로 표현되며, 4비트마다 16진수 한 자리로 나타낸다. 예를 들어 비트열 110010101101은 CAD로 표현된다.
• 한 줄에 시스템의 사용자 수 $m$ ($1 \le m \le 10^5$)이 주어진다.
• 이어지는 $m$개의 줄에 각각 사용자 이름이 하나씩 주어진다.
• 이어지는 $m$개의 줄에 각각 비밀번호가 하나씩 주어진다.

사용자 이름과 비밀번호는 다음 문자만 포함한다: a-z, A-Z, 0-9, 그리고 특수문자 _ - = + ! @ # $ % { } & * ( ) [ ] \ | / < > , .. 사용자 이름과 비밀번호의 길이는 각각 8 이상 30 이하이다. 암호화할 때는 각 문자의 ASCII 값을 사용한다.

모든 사용자 이름은 서로 다르며, 모든 비밀번호도 서로 다르다.

각 테스트 케이스마다, 입력으로 주어진 '암호화된 사용자 이름+비밀번호'를 만들어 내는 사용자 이름과 비밀번호를 두 줄에 걸쳐 출력한다. 첫 줄에 사용자 이름을, 둘째 줄에 비밀번호를 출력한다. 입력은 각 테스트 케이스마다 유일한 해가 존재하도록 주어진다.