DeCSS 2

Content Scramble System (CSS) is a method that encrypts content on DVD media so that only licensed devices can access it. In the variant of this system covered here, the key $K$ is a bit string 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 a sequence of $n$ bytes. Each content byte is then combined with the corresponding keystream byte by bitwise XOR.

If the encrypted text and some content bytes are known, the corresponding keystream bytes can be determined. Your task is to find one possible key $K$ based on a 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 a set of feedback positions is defined. In one cycle, an LFSR produces one output bit and updates its state as follows:

1. Compute the output bit $b$ by XORing the bits at the feedback positions. If the result is even, $b$ is 0. Otherwise, $b$ is 1.
2. Shift all state bits left. Bit $b_1$ is discarded, and $b$ is placed in the last position. The new state is $b_2, b_3, \ldots, b_m, b$.

One step of an LFSR consists of 8 cycles, and its result is one byte. If the output bits of the cycles are $i_1, i_2, \ldots, i_8$ in order, the result is the integer between 0 and 255 whose binary form is $(i_8 i_7 \ldots i_1)_2$.

CSS uses two such circuits:

• LFSR17 has 17 bits, with feedback positions 1 and 15. Its initial state is filled in order with key bits $k_1$ through $k_{17}$.
• LFSR25 has 25 bits, with feedback positions 1, 4, 5, and 13. Its initial state is filled in order with key bits $k_{18}$ through $k_{42}$.

Figure 1: Keystream generation

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

1. Set LFSR17 and LFSR25 to the initial states determined by the key $K$.
2. Set the variable $c$ to 0.
3. Repeat $n$ times:
   1. Perform one step of LFSR17, and let $x$ be its result.
   2. Perform one step of LFSR25, and let $y$ be its result.
   3. Compute $z = x + y + c$.
   4. If $z \geq 256$, subtract 256 from $z$ and set $c$ to 1. Otherwise, set $c$ to 0.
   5. The next keystream byte is $z$.

A partially known keystream is given, where some bytes are known and some are unknown. Find one possible key $K$ that produces a keystream matching the given one when generated in the way described above.

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

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

A solution always exists, but it may not be unique.

The table below shows how the first four keystream bytes of the first example are generated. The first row is the initial state. Every other row is the state right after the given cycle or step ends. In each LFSR, the shaded positions are the feedback positions, and the underlined last bit is the output bit of that cycle.