DeCSS 2

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

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

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

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

LFSR의 한 단계는 8사이클로 이루어지며, 결과는 1 byte이다. 사이클의 출력 비트를 차례로 $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_{17}$까지를 차례로 채운다.
• LFSR25는 25비트이고, 피드백 위치는 1, 4, 5, 13이다. 초기 상태는 키의 비트 $k_{18}$부터 $k_{42}$까지를 차례로 채운다.

그림 1: 키 스트림 생성

키 스트림 $T(K)$는 다음과 같이 생성한다.

1. LFSR17과 LFSR25를 키 $K$로 정해지는 초기 상태에 놓는다.
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. 키 스트림의 다음 byte는 $z$이다.

일부 byte만 알려진 키 스트림이 주어진다. 위 방식으로 생성했을 때 주어진 키 스트림과 맞는 키 $K$를 하나 구하라.

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

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

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

다음 표는 첫 번째 예제에서 키 스트림의 처음 네 byte가 생성되는 과정을 보여준다. 첫 줄은 초기 상태이고, 나머지 줄은 해당 사이클 또는 단계가 끝난 직후의 상태이다. 각 LFSR에서 회색으로 표시된 칸이 피드백 위치이고, 밑줄 친 마지막 비트가 그 사이클의 출력 비트이다.