DeCSS 7

Content Scramble System (CSS) is a method that encrypts the content on DVD media so that only licensed devices can access it. In the variant studied here, the key $K$ is a sequence of exactly 42 bits $k_1, k_2, \ldots, k_{42}$, and the content is a sequence of $n$ bytes. The content is encrypted by first generating a keystream $T(K)$ from the key. The keystream is also $n$ bytes long. Then the bitwise exclusive OR is applied to each content byte and the corresponding keystream byte.

If the ciphertext and some bytes of the content are known, the corresponding keystream bytes can be determined. Your task is to find one possible key $K$ based on the partially known keystream $T(K)$.

The keystream function $T(K)$ is based on a Linear-feedback shift register (LFSR) circuit. The state of an LFSR consists of $m$ bits $b_1, b_2, \ldots, b_m$, and its behavior is defined by a set of feedback positions. In one cycle, the LFSR outputs one bit and updates its state as follows.

1. Compute the output bit $b$ by summing the bits at the feedback positions. If the sum is even, $b$ is 0. Otherwise $b$ is 1. In other words, $b$ is the XOR of the bits at the feedback positions.
2. Shift all state bits one position to the left and discard $b_1$. Place $b$ in the last position. The new state is $b_2, b_3, \ldots, b_m, b$.

One step of the LFSR consists of 8 cycles. The result is one byte made of the output bits of the cycles, read from right to left. If the output bits of the cycles are $i_1, i_2, \ldots, i_8$ in order, the result is the integer from 0 to 255 whose binary representation is $(i_8 i_7 \ldots i_1)_2$.

CSS uses two such circuits.

• LFSR17 has 17 bits. Its feedback positions are 1 and 15. Its initial state is the key bits $k_1, k_2, \ldots, k_{17}$, in that order.
• LFSR25 has 25 bits. Its feedback positions are 1, 4, 5, and 13. Its initial state is the key bits $k_{18}, k_{19}, \ldots, k_{42}$, in that order.

Figure 1: Keystream generation

The keystream $T(K)$ is generated as follows.

1. Set LFSR17 and LFSR25 to their initial states using the key $K$, as described above.
2. Set $c$ to 0.
3. Repeat the following $n$ times.
   1. Perform one step of LFSR17 and let $x$ be the result.
   2. Perform one step of LFSR25 and let $y$ be the result.
   3. Compute $z = x + y + c$.
   4. If $z \ge 256$, subtract 256 from $z$ and set $c$ to 1. Otherwise set $c$ to 0.
   5. The next keystream byte is $z$.

You are given a keystream where some bytes are known and others are unknown. Find one key $K$ that produces a keystream matching the given bytes in the way described above.

The first line contains the natural number $n$, the length of the keystream. The second line contains $n$ integers $t_1, t_2, \ldots, t_n$, the keystream bytes. If the $k$-th byte is unknown, then $t_k = -1$. If it is known, then $0 \le t_k \le 255$.

Print the bits $k_1, k_2, \ldots, k_{42}$ of the key on one line, without spaces.

A solution always exists, but it is not necessarily unique.

Explanation of the first example

The following table shows the details of generating the first four bytes of the keystream. The first row is the initial state. Every other row is the state right after the given cycle or step.