DeCSS 4

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

암호화된 텍스트와 내용의 일부 바이트를 알고 있으면, 키 스트림의 대응하는 바이트를 구할 수 있다. 일부만 알려진 키 스트림 $T(K)$가 주어졌을 때, 위 방식으로 주어진 스트림과 일치하는 키 스트림을 만들어 내는 키 $K$ 하나를 구하라.

키 스트림 $T(K)$는 LFSR(Linear-feedback shift register)을 바탕으로 생성된다. LFSR의 상태는 $m$개의 비트 $b_1, b_2, \ldots, b_m$이며, 귀환 위치의 집합이 정해져 있다. 한 사이클에서 LFSR은 다음 순서로 출력 비트 하나를 만들고 상태를 바꾼다.

1. 귀환 위치의 비트를 모두 더한다. 합이 짝수이면 출력 비트 $b$는 0이고, 홀수이면 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: 키 스트림 생성

키 스트림은 다음 순서로 생성된다.

1. 두 LFSR을 키 $K$로 정해지는 초기 상태에 둔다.
2. $c$를 0으로 둔다.
3. $n$번 반복한다.
   1. LFSR17을 한 단계 진행하고, 그 결과를 $x$라 한다.
   2. LFSR25를 한 단계 진행하고, 그 결과를 $y$라 한다.
   3. $z = x + y + c$를 계산한다.
   4. $z \geq 256$이면 $z$에서 256을 뺀 값을 $z$로 하고 $c$를 1로 둔다. 그렇지 않으면 $c$를 0으로 둔다.
   5. 키 스트림의 다음 바이트는 $z$이다.

키 스트림의 일부 바이트는 알려져 있고 나머지는 알려져 있지 않다. 알려져 있지 않은 바이트는 -1로 주어진다. 위 과정으로 주어진 키 스트림과 일치하는 스트림을 만드는 키 $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}$를 공백 없이 한 줄에 출력하라.

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

아래 표는 키 스트림의 처음 네 바이트가 생성되는 과정이다. 첫 행은 초기 상태이고, 나머지 행은 각 사이클 또는 단계가 끝난 직후의 상태다. 원문 그림에서는 귀환 위치를 회색으로, 그 사이클의 출력 비트를 밑줄로 표시하였다.