DeCSS 9

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

암호문과 콘텐츠의 일부 바이트를 알고 있다면, 그에 대응하는 키 스트림 바이트를 구할 수 있다. 일부만 알려진 키 스트림 $T(K)$를 바탕으로, 그것을 만들어 낼 수 있는 키 $K$ 하나를 구하라.

키 스트림은 Linear-feedback shift register(LFSR)라는 논리 회로로 생성된다. LFSR의 상태는 $m$개의 비트 $b_1, b_2, \ldots, b_m$으로 이루어지며, 피드백 위치들의 집합이 정해져 있다. LFSR은 한 사이클마다 출력 비트 하나를 내보내고, 상태를 다음과 같이 바꾼다.

1. 피드백 위치에 있는 비트들을 더한다. 합이 짝수이면 $b=0$, 홀수이면 $b=1$로 둔다. 즉 $b$는 피드백 위치 비트들의 배타적 논리합이다.
2. 상태의 모든 비트를 왼쪽으로 한 칸씩 옮기고, $b_1$은 버린다. 그리고 $b$를 맨 끝 위치에 넣는다. 새 상태는 $b_2, b_3, \ldots, b_m, b$이다.

LFSR 한 단계는 8사이클로 이루어지며, 결과는 한 바이트이다. 사이클들의 출력 비트를 차례로 $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 \geq 256$이면 $z$에서 256을 빼고 $c$를 1로 둔다. 아니면 $c$를 0으로 둔다.
   5. 다음 키 스트림 바이트는 $z$이다.

키 스트림의 일부 바이트는 알려져 있고 나머지는 알려져 있지 않다. 주어진 바이트와 일치하는 키 $K$ 하나를 구하라. 그 키로 위 방식의 키 스트림을 만들었을 때, 알려진 바이트들이 모두 맞아야 한다.

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

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

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

첫 번째 예시를 설명한다. 아래 표는 키 스트림의 처음 네 바이트가 만들어지는 과정을 보여 준다. 첫 행은 초기 상태이고, 나머지 행은 각 사이클 또는 단계가 끝난 직후의 상태이다. 원문 표에서는 피드백 위치를 회색으로, 그 사이클의 출력 비트인 마지막 비트를 밑줄로 표시하였다.