P11304 [COTS 2016] 破译 DeCSS

译自 [Izborne Pripreme 2016 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2016/) D1T1。 提交答案时，采用文件名为 $\texttt{decss-*.out}$。

**这是一道提交答案题。** 输入文件可以在附件中下载。 ### 基本定义 **内容扰乱系统**（Content Scramble System，CSS）是一种对 DVD 进行加密的技术，以期保护版权。为了方便做题，此题对 CSS 进行了一定的简化。 **密钥** $k$ 是一个长度为 $42$ 的 $\texttt{01}$ 序列 $k_1,k_2,\cdots,k_{42}$。 **明文**、**密文**是由 $n$ 个字节组成的序列。 **密钥流** $T(k)$ 同样是由 $n$ 个字节组成的序列。 加密时，首先基于密钥 $k$ 生成密钥流 $T(k)$，然后将密钥流与明文按位异或，即得到密文。如果已知密文和部分明文，即可得到部分密钥流。 在本题中，你需要基于部分密钥流 $T(k)$ 确定一个可能的密钥 $k$。 --- ### LFSR 从密钥生成密钥流使用了线性反馈移位寄存器（LFSR）。 LFSR 的状态由 $m$ 位二进制位 $b_1\sim b_m$ 组成。定义**反馈位置集** $S\subseteq \{1,2,\cdots,m\}$，它控制输出时会基于哪些位进行运算。 在一个**周期**内，LFSR 会做如下的事情： - 输出 $\displaystyle b=\bigoplus_{i\in S} b_i$，其中 $\oplus$ 表示按位异或运算。 - 对于 $1\le i\lt m$，**同时**令 $b_i\gets b_{i+1}$，并让 $b_m\gets b$。 LFSR 的一**步**由 $8$ 个周期组成，一步输出一个字节。令这 $8$ 个周期输出的位为 $i_1\sim i_8$，则该步输出的字节为 $(\overline{i_8i_7i_6i_5i_4i_3i_2i_1})_2$。 CSS 使用的 LFSR 有： | 名称 | $m=$ | $S=$ | 初始状态 | | :--: | :--: | :--: | :--: | | LFSR17 | $17$ | $\{1,15\}$ | $k_1,k_2,\cdots,k_{17}$ | | LFSR25 | $25$ | $\{1,4,5,13\}$ | $k_{18},k_{19},\cdots,k_{42}$ | ------ ### 生成密钥流 接下来介绍 $T(k)$ 的生成方法。 1. 用 $k$ 将 LFSR17 和 LFSR25 初始化； 2. $c\gets 0$； 3. 重复以下操作 $n$ 次： - 令 $x$ 为 LFSR17 执行一步的结果； - 令 $y$ 为 LFSR25 执行一步的结果； - 令 $z\gets x+y+c$； - $c\gets \lfloor z/256\rfloor,z\gets z\bmod 256$； - 将 $z$ 新增到密钥流的末尾。 给定部分密钥流，确定一个可能的密钥 $k$，使得它能够生成符合条件的密钥流。

第一行，一个正整数 $n$。 第二行，$n$ 个整数 $t_1,t_2,\cdots,t_n$，描述一个密钥流。 - 如果 $t_i=-1$，表示 $t_i$ 未知。否则 $t_i\in [0,256)$。

输出一行一个长度为 $42$ 的 $\texttt{01}$ 串，表示密钥 $k$。 **数据保证有解。** 输出任意一组合法解均可。

#### 评分方式 对于 $100\%$ 的数据，保证 $1\le n\le 500$，**保证有解**。 令 $m$ 表示已知的密钥流中元素的个数。 | 输入文件名 | $n\le $ | $m\le $ |得分 | | :--: | :--: | :--: | :--: | | $\texttt{decss-1.in}$ | $ 20 $ | $20$ | $ 8 $ | | $\texttt{decss-2.in}$ | $ 25 $ | $21$ | ^ | | $\texttt{decss-3.in}$ | $ 20 $ | $8$ | ^ | | $\texttt{decss-4.in}$ | $ 30 $ | $10$ | ^ | | $\texttt{decss-5.in}$ | $ 31 $ | $8$ | $ 9 $ | | $\texttt{decss-6.in}$ | $ 30 $ | $20$ | ^ | | $\texttt{decss-7.in}$ | $ 200 $ | $9$ | $ 12 $ | | $\texttt{decss-8.in}$ | $ 300 $ | $12$ | ^ | | $\texttt{decss-9.in}$ | $ 500 $ | ^ | $ 13 $ | | $\texttt{decss-10.in}$ | ^ | ^ | ^ | #### 样例解释 | 步数 | 周期 | LFSR17 | LFSR25 | $x$ | $y$ | $c$ | $z$ | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 初态 | | 1 1100 0110 0101 0010 | 1 1001 1000 0000 0000 0011 1011 | | | $0$ | | | | 1 | 1 1000 1100 1010 0100 | 1 0011 0000 0000 0000 0111 0110 | | | | | | | 2 | 1 0001 1001 0100 1000 | 0 0110 0000 0000 0000 1110 1101 | | | | | | | 3 | 0 0011 0010 1001 0001 | 0 1100 0000 0000 0001 1101 1011 | | | | | | | 4 | 0 0110 0101 0010 0010 | 1 1000 0000 0000 0011 1011 0110 | | | | | | | 5 | 0 1100 1010 0100 0100 | 1 0000 0000 0000 0111 0110 1101 | | | | | | | 6 | 1 1001 0100 1000 1001 | 0 0000 0000 0000 1110 1101 1011 | | | | | | | 7 | 1 0010 1001 0001 0011 | 0 0000 0000 0001 1101 1011 0110 | | | | | | | 8 | 0 0101 0010 0010 0111 | 0 0000 0000 0011 1011 0110 1101 | | | | | | 1 | | | | $228$ | $182$ | $1$ | $154$ | | | 9 | 0 1010 0100 0100 1111 | 0 0000 0000 0111 0110 1101 1011 | | | | | | | 10 | 1 0100 1000 1001 1111 | 0 0000 0000 1110 1101 1011 0111 | | | | | | | 11 | 0 1001 0001 0011 1110 | 0 0000 0001 1101 1011 0110 1110 | | | | | | | 12 | 1 0010 0010 0111 1101 | 0 0000 0011 1011 0110 1101 1101 | | | | | | | 13 | 0 0100 0100 1111 1010 | 0 0000 0111 0110 1101 1011 1011 | | | | | | | 14 | 0 1000 1001 1111 0100 | 0 0000 1110 1101 1011 0111 0110 | | | | | | | 15 | 1 0001 0011 1110 1001 | 0 0001 1101 1011 0110 1110 1101 | | | | | | | 16 | 0 0010 0111 1101 0011 | 0 0011 1011 0110 1101 1101 1010 | | | | | | 2 | | | | $203$ | $91$ | $1$ | $39$ | | | 17 | 0 0100 1111 1010 0110 | 0 0111 0110 1101 1011 1011 0100 | | | | | | | 18 | 0 1001 1111 0100 1101 | 0 1110 1101 1011 0111 0110 1001 | | | | | | | 19 | 1 0011 1110 1001 1011 | 1 1101 1011 0110 1110 1101 0010 | | | | | | | 20 | 0 0111 1101 0011 0111 | 1 1011 0110 1101 1101 1010 0100 | | | | | | | 21 | 0 1111 1010 0110 1111 | 1 0110 1101 1011 1011 0100 1000 | | | | | | | 22 | 1 1111 0100 1101 1111 | 0 1101 1011 0111 0110 1001 0001 | | | | | | | 23 | 1 1110 1001 1011 1110 | 1 1011 0110 1110 1101 0010 0010 | | | | | | | 24 | 1 1101 0011 0111 1100 | 1 0110 1101 1101 1010 0100 0101 | | | | | | 3 | | | | $62$ | $162$ | $0$ | $225$ | | | 25 | 1 1010 0110 1111 1000 | 0 1101 1011 1011 0100 1000 1011 | | | | | | | 26 | 1 0100 1101 1111 0001 | 1 1011 0111 0110 1001 0001 0110 | | | | | | | 27 | 0 1001 1011 1110 0011 | 1 0110 1110 1101 0010 0010 1101 | | | | | | | 28 | 1 0011 0111 1100 0110 | 0 1101 1101 1010 0100 0101 1011 | | | | | | | 29 | 0 0110 1111 1000 1100 | 1 1011 1011 0100 1000 1011 0111 | | | | | | | 30 | 0 1101 1111 0001 1001 | 1 0111 0110 1001 0001 0110 1111 | | | | | | | 31 | 1 1011 1110 0011 0010 | 0 1110 1101 0010 0010 1101 1110 | | | | | | | 32 | 1 0111 1100 0110 0101 | 1 1101 1010 0100 0101 1011 1101 | | | | | | 4 | | | | $166$ | $189$ | $1$ | $99$ |