DeCSS 6

Content Scramble System(CSS)은 DVD 미디어의 내용을 암호화하는 방식으로, 라이선스를 받은 장치만 내용에 접근할 수 있게 한다. 이 문제에서 다루는 CSS 변형에서 키 $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사이클로 이루어지며, 결과는 0에서 255 사이의 정수 하나이다. 사이클의 출력 비트를 차례로 $i_1, i_2, \ldots, i_8$이라 하면, 결과는 이진수 $(i_8 i_7 \ldots i_1)_2$로 표기되는 정수이다.

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}$를 공백 없이 첫 줄에 출력한다.

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

아래 표는 첫 번째 입력에 대해 키 스트림의 처음 네 바이트를 만드는 과정을 자세히 보여 준다. 첫 행은 초기 상태이고, 나머지 행은 각 사이클이나 스텝이 끝난 직후의 상태이다. 표에서 각 LFSR의 귀환 위치와 사이클의 마지막 출력 비트를 확인할 수 있다.