You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在密码学中，代换-置换网络（或译作置换排列网络，英语：Substitution-Permutation Network，缩写作 SP-network 或 SPN）是乘积密码和分组加密的一种，美国数学家克劳德·香农在1949年为了找到利用简单的代换-置换方式进行加密的安全加密方式，发明了代换-置换网络。本题希望你实现代换-置换网络加密，对输入的明文字符串进行代换-置换加密并打印输出。

代换-置换网络

代换-置换网络包括两个变换，分别记为 $π_s 和 π_p$。

$\pi_s : \{0,1\}^l \rightarrow \{0,1\}^l$

$\pi_p : \{1,lm\} \rightarrow \{1,lm\}$

都是置换，置换 $\pi_s$ 叫做S盒，它用一个 lBit向量来替代另一个 lBit向量

换 $\pi_p$ 用来置换lm个Bit

给定一个lmBit的二元串 $x = (x_1,\ldots,x_{lm})$，可以将其看做m个lBit字串 $x_1,\ldots,x_m$的并联

因此 $x = x_1||\ldots||x_m$，且对于 $1\leq i \leq m$ ，我们有 $x = (x_{(i-1)l+1},\ldots,x_{il})$

下面给出的代换-置换网络由Nr轮组成，在每一轮我们先用异或操作混入该密钥，再用$\pi_s$进行m次代换，然后用$\pi_p$进行一次置换

密码体制：设l,m和Nr都是正整数， $\pi_s : \{0,1\}^l \rightarrow \{0,1\}^l 与 \pi_p : \{0,lm\} \rightarrow \{0,lm\}$均为置换

设 $P=C={0,1}，K \in ({0,1}^{lm})^{N_{r+1}}$ 是由初始密钥K用密钥编排算法生成的所有可能密钥编排方案之集

对一个密钥编排方案 $K^1,\ldots,K^{N_{r+1}}$，我们可以用下面的算法加密明文x

$$SPN(x,\pi_s,\pi_p,(K^l,\ldots,K^{N_{r+1}}) \\ w^0 \leftarrow x \\ for \enspace r \leftarrow 1 \enspace to \enspace N_{r-1} \\ do\begin{cases} u^r \leftarrow w^{r-1} \oplus K^r \\ for \enspace i \leftarrow 1 \enspace to \enspace m \\ do \enspace v^r_{(i)} \leftarrow \pi_s(u^r_{(i)}) \\ w^r \leftarrow (v^r_{\pi_{p(l)}},\ldots,v^r_{\pi_{p(lm)}}) \end{cases} \\ u^{N_r} \leftarrow w^{N_{r-1}} \oplus K^{N_r} \\ for \enspace i \leftarrow 1 \enspace to \enspace m \\ do \enspace v^{N_r}_{(i)} \leftarrow \pi_s(u^{N_r}_{(i)}) \\ y \leftarrow v^{N_r} \oplus K^{N_{r+1}} \\ output(y) $$

注意：⊕ 的意思是异或，上面S盒的代换是分组代换，也就是10进制数字变成二进制，每组四个位置。

$$在上面的算法中，u^r 是第 r 轮对S盒的输入，v^r是第r轮对S盒的输出。w^r是由v^r应用置换π_p得到，\\然后u^{r+1}由轮密钥 K^{r+1}异或w^r得到，最后一轮没有用置换π_p。如果对密钥编排方案做适当修改\\并用S盒的逆来取代S盒，那么该加密算法也能用来解密。 $$

下面用一个特定的代换-置换网络来说明上面的一般性描述

设$l=m=N_r=4,\pi_s$如下定义，这里输入 z 和输出 $\pi_s(z)$都以十六进制表示$（0 \leftrightarrow (0,0,0,0),1\leftrightarrow(0,0,0,1),\ldots,9\leftrightarrow(1,0,0,1),A\leftrightarrow(1,0,1,0),\ldots,F\leftrightarrow(1,1,1,1)）$

$\pi_{s(z)}$如下定义

z	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
$\pi_{s(z)}$	E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

$\pi_{p(z)}$如下定义

z	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$\pi_{p(z)}$	1	5	9	13	2	6	10	14	3	7	11	15	4	8	12	16

为了叙述方便，我们命名了16个 S 盒，$S^i_r(1 \geq i \geq 4,1 \geq \geq 4)$，它们都是基于同样的置换$π_s$。下面给出代换-置换网络的密钥编排算法。我们以一个32比特的密钥 $K=(k_1,...,k_32)∈{0,1}^32$ 开始。对轮数$1\leq r \leq 5$，定义$K^r$是由$K$中从$k_{4r−3}$开始的16个相邻比特组成的。

下面我使用该代换-置换网络来进行加密。所有的数据都用二元形式表示。

设密钥是：

$K=0011 1010 1001 0100 1101 0110 0011 1111$

则轮密钥如下：

$K1=0011 1010 1001 0100$

$K2=1010 1001 0100 1101$

$K3=1001 0100 1101 0110$

$K4=0100 1101 0110 0011$

$K5=1101 0110 0011 1111$

设明文为：

$x=0010 0110 1011 0111$

则加密$x$的过程如下：

$$w_0=0010 0110 1011 0111 \\ K_1=0011 1010 1001 0100 \\ u_1=0001 1100 0010 0011 \\ v_1=0100 0101 1101 0001 \\ w_1=0010 1110 0000 0111 \\ K_2=1010 1001 0100 1101 \\ u_2=1000 0111 0100 1010 \\ v_2=0011 1000 0010 0110 \\ w_2=0100 0001 1011 1000 \\ K_3=1001 0100 1101 0110 \\ u_3=1011 0101 0110 1110 \\ v_3=1001 1111 1011 0000 \\ w_3=1110 0100 0110 1110 \\ K_4=0100 1101 0110 0011 \\ u_4=1010 1001 0000 1101 \\ v_4=0110 1010 1110 1001 \\ K_5=1101 0110 0011 1111 $$

密文为：

$y = 1011 1100 1101 0110$

具体解释一下上面比较难以理解的由$u$到$v$的过程，这里分为四组，每组四个数字，分为四次进行$S$盒代换，一共代换16位，代换后的十进制数字再转成二进制数字填入$v$数组。

数据范围

• $ 0 \leq z，\pi_s(z) \leq 15，\pi_s(z)中A由10表示，B由11表示以此类推$

• $1 \leq z，\pi_s(z) \leq 16$

• 密钥K为32位二进制

• 需要加密的明文为16位二进制

输入

第一行和第二行输入各输入16个数字表示$\pi_s$盒置换

第三行和第四行输入各输入16个数字表示$\pi_p$盒置换

第五行输入密钥

第六行输入明文

输出

输出明文通过SPN加密后的结果

样例

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1

1011110011010110

12 1 9 2 0 11 7 3 4 15 8 5 14 13 10 6
11 14 7 15 3 4 8 6 10 1 5 0 13 9 12 2
13 2 10 3 1 12 8 4 5 16 9 6 15 14 11 7
12 15 8 16 4 5 9 7 11 2 6 1 14 10 13 3
1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0
0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1

0010001100011101

样例解释

样例一就是上面举得例子