提示: 欢迎访问OurACM平台。
Problem 1849 S_DES

Accept: 9    Submit: 10
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

S_DES加密算法是以8位明文和10位密钥作为输入,产生8位分组密文输出。其解密算法用同一密钥对8位密文分组产生原来的明文分组,如下图所示,它描述了S_DES的算法流程。


图中各符号的含义如下:
IP:预定义的初始置换;
fk:包含置换、替代操作且依赖于密钥的变换;
SW:将输入的数据进行高四位和低四位交换;
IP^-1:IP的逆置换。
由图可知,S_DES加密算法由5个步骤组成:首先对输入的8位明文分组d执行一次初始置换IP(d);然后执行一个fk;接着将数据的高四位和低四位进行交换;再执行一次fk;最后执行IP^-1产生逆密文输出H,并且:

解密是加密的逆变换,即:


其中密钥k1, k2都是8位子密钥,由10位输入密钥产生。
1.S_DES密钥的生成
S_DES密钥是一个10位码,由一随机数字发生器产生,并由发送、接收双方共享。两个8位子密钥由10位输入密钥按如上图所示流程生成。子密钥k1, k2 ,生成过程如下:
(1) 对10位码a进行10阶置换P10,P10置换矩阵定义如下图所示:


设a=(b1,b2,b3,b4,b5,b6,b7,b8,b9,b10),则:
a1=P10(a)=a×Arr1(i,j)=(b3,b5,b2,b7,b4,b10,b1,b9,b8,b6)
例如,a=(1001100101),则a1=P10(a)=(0100111010)。
(2) 将a1分成左右两部分,每一部分分为连续5位码,即a1=a1L&a1R,将a1L和a1R分别循环左移一位,输出a2,a2仍为10位码,如上例。
a1L=(01001),循环左移一次:RLC_1(a1L)=(10010);
a1R=(11010),循环左移一词:RLC_1(a1R)=(10101);
则a2=RLC_1(a1L)&RLC_1(a1R)=(1001010101)。
(3) 做10位转8位的变换P8,P8变换矩阵定义如下图所示。


P8(a2)=a2×Arr2(i,j)=(b6,b3,b7,b4,b8,b5,b10,b9),得到子密钥k1,如上例。
K1=P8(a2)=P8(1001010101)=(10011010)。
(4) 再将a2分成左右两部分,每一部分为连续5位码,即a2=a2L&a2R,将a2L和a2R分别循环左移两次,输出a3,a3仍为10位码,如上例。
a2L=(10010),循环左移两次:RLC_2(a2L)=(01010);
a2R=(10101),循环左移两次:RLC_2(a2R)=(10110);
则a3=RLC_2(a2L)&RLC_2(a2R)=(0101010110)。
(5) 再做一次10位转8位的变换P8,得到子密钥k2。
2.S_DES的加密操作
S_DES加密操作首先执行一个8位的置换IP,IP转换矩阵定义如下图所示。


设8位明文d=(b1,b2,b3,b4,b5,b6,b7,b8),则d1=IP(d)=d× Arr3(i,j)=(b2,b6,b3,b1,b4,b8,b5,b7)。
IP逆置换的实现,只要将Arr3矩阵转置90度,即将Arr3的第n行变成第n列,得到IP逆置换矩阵,然后再与待进行逆置换的数据相乘。IP的逆置换矩阵定义如下图所示。


加密操作中最复杂的是fk(),fk()是若干置换和代换的组合,如下图所示。


fk(L,R)=(L⊕P4((S0&S1)(E/P(R)⊕Key)))&R
其中:
L,R分别是输入字节的左半4位和右半四位;
E/P是一个4位到8位的扩展变换,变换矩阵如下图所示。


则有:
E/P(b1,b2,b3,b4)=(b4,b1,b2,b3,b2,b3,b4,b1)。
⊕是按位异或运算。
S0,S1分别是4位到2位的变换盒,S0作用于8位字节的左4位,S1作用于8位字节的右4位。
S0,S1分别定义如下图:


变换盒S的操作过程是将4位输入码的第0、3位作为2位数值i,第1,2作为2位数值j,则盒中元素Sij即为输出。例如S0(0011)=3=(11)。
P4是一个4位置换,置换矩阵定义如下图所示。


则有:
P4(b1,b2,b3,b4)=(b2,b4,b3,b1)
&表示两个位串的连接。
编程任务:
现在你的任务是对于一系列命令,完成加密或解密并输出。

Input


输入的每一行首先是一个数字,表示命令的序号。
1表示加密,2表示解密,3表示输入结束。
1命令之后有一个8位的01串,表示明文,接着是一个10位的01串,表示密钥;
2命令之后有一个8位的01串,表示密文,接着是一个10位的01串,表示密钥;
3命令之后表示输入结束,不做任何处理。

Output

对于1和2命令,分别输出对应的8位01串,表示明文/密文,每行一个。

Sample Input

1 11011110 1001101010 2 10110010 1001101010 3

Sample Output

10110010 11011110

Source

FOJ有奖月赛-2009年10月——稚鹰翱翔

Submit  Back  Status  Discuss