DeCSS 7

Content Scramble System(CSS)은 DVD 미디어의 콘텐츠를 암호화해서 라이선스가 있는 기기만 접근할 수 있게 하는 방식이다. 이 문제에서 다루는 변형에서 키 $K$는 정확히 42비트 $k_1, k_2, \ldots, k_{42}$로 이루어진 수열이고, 콘텐츠는 $n$바이트로 이루어진 수열이다. 콘텐츠는 먼저 키로부터 길이 $n$의 키 스트림 $T(K)$를 만든 뒤, 콘텐츠의 각 바이트와 그에 대응하는 키 스트림 바이트에 비트 단위 배타적 논리합(XOR)을 적용해서 암호화된다.

암호문과 콘텐츠의 일부 바이트를 알고 있으면 대응하는 키 스트림 바이트를 구할 수 있다. 여러분의 과제는 일부만 알려진 키 스트림 $T(K)$를 바탕으로 가능한 키 $K$를 하나 구하는 것이다.

키 스트림을 만드는 함수 $T(K)$는 선형 피드백 시프트 레지스터(LFSR) 회로에 기반한다. LFSR의 상태는 $m$개의 비트 $b_1, b_2, \ldots, b_m$으로 이루어지며, 피드백 위치들의 집합에 따라 동작이 정해진다. LFSR은 한 사이클마다 출력 비트 하나를 만들고 다음과 같이 상태를 바꾼다.

1. 피드백 위치에 있는 비트들의 합이 짝수이면 출력 비트 $b$는 0이고, 홀수이면 1이다. 즉 $b$는 피드백 위치 비트들의 XOR이다.
2. 상태의 모든 비트를 왼쪽으로 한 칸 옮기고 $b_1$은 버린다. 그리고 $b$를 마지막 위치에 놓는다. 새 상태는 $b_2, b_3, \ldots, b_m, b$이다.

LFSR의 한 단계는 8사이클로 이루어진다. 결과는 각 사이클의 출력 비트를 오른쪽에서 왼쪽으로 읽어 만든 1바이트이다. 사이클의 출력 비트가 차례로 $i_1, i_2, \ldots, i_8$이면 결과는 이진수 표기가 $(i_8 i_7 \ldots i_1)_2$인 0 이상 255 이하의 정수이다.

CSS는 이런 회로를 두 개 사용한다.

• LFSR17은 17비트이고, 피드백 위치는 1번과 15번이다. 초기 상태는 키의 비트 $k_1, k_2, \ldots, k_{17}$을 순서대로 넣은 것이다.
• LFSR25는 25비트이고, 피드백 위치는 1번, 4번, 5번, 13번이다. 초기 상태는 키의 비트 $k_{18}, k_{19}, \ldots, k_{42}$를 순서대로 넣은 것이다.

그림 1: 키 스트림 생성

키 스트림 $T(K)$는 다음 순서로 생성된다.

1. 위에서 설명한 방식대로 키 $K$를 이용해 LFSR17과 LFSR25를 초기 상태로 설정한다.
2. 변수 $c$를 0으로 둔다.
3. 다음 과정을 $n$번 반복한다.
   1. LFSR17의 한 단계를 수행하고, 결과를 $x$라고 한다.
   2. LFSR25의 한 단계를 수행하고, 결과를 $y$라고 한다.
   3. $z = x + y + c$를 계산한다.
   4. $z \ge 256$이면 $z$에서 256을 빼고 $c$를 1로 둔다. 그렇지 않으면 $c$를 0으로 둔다.
   5. 키 스트림의 다음 바이트는 $z$이다.

일부 바이트는 알려져 있고 나머지는 알려져 있지 않은 키 스트림이 주어진다. 위 방식으로 생성했을 때 주어진 바이트와 일치하는 키 스트림을 만드는 키 $K$를 하나 구하시오.

첫 줄에 키 스트림의 길이인 자연수 $n$이 주어진다. 둘째 줄에는 키 스트림의 바이트 $t_1, t_2, \ldots, t_n$이 주어진다. $k$번째 바이트를 모르면 $t_k = -1$이고, 알면 $0 \le t_k \le 255$이다.

키의 비트 $k_1, k_2, \ldots, k_{42}$를 공백 없이 한 줄에 출력한다.

해는 항상 존재하지만, 유일하지 않을 수 있다.

첫 번째 예시 설명

다음 표는 키 스트림의 처음 네 바이트가 만들어지는 과정을 보여준다. 첫 행은 초기 상태이고, 나머지 행은 각 사이클 또는 단계가 끝난 직후의 상태이다.