??根据（1）式穷举搜索密钥k时，入输出密文是C1，则加密密钥就是多应用的密钥；若输出密文是c2，根据（3）可知加密密钥是多应用的密钥的补，这样，利用一个密钥的加密尝试，能够检测两个密钥是否为真正的加密密钥。因此，DES的互补性会使DES在选择明文攻击下所需的工作量减半。 （6）简述利用差分分析攻击DES算法的基本过程。
答：过程如下：首先攻击者选择具有固定差分（在DES分析中，“差分”定义为异或运算）的一对明文，这两个明文可以随机选取，攻击者甚至不必知道他们的值，但要求它们符合特定的差分条件；然后，使用输出密文中的差分，分析可能的密钥；随着分析的密文对越来越多有一个的概率明显增大，它就是正确的密钥。
（7）简述线性攻击的基本原理。
答：基本原理是寻求明文、密文和密钥间有效的线性逼近，当该逼近的线性偏差足够大时，就可以由一定量的明密文对推测出部分密钥信息。线性分析的关键是确定有效线性方程的线性偏差和线性组合系数。
（8）简述AES算法的正变换矩阵比逆变换矩阵简单的原因。
答：逆S盒比S盒复杂，需要将逆S盒中的每个字节映射到它在有限域GF（２８）中的逆。输出值不能通过一个简单的函数变换输入值所得到。S盒必须是可逆的，即S[S[a]]=a,而S[a]=S-1[a]不成立，在这个意义上S盒不是自逆的。
（9）简述AES的子密钥生成过程
答：AES首先将初始密钥输入到一个4*4矩阵中。这个4*4矩阵的每一列的4个字节组成一个字，矩阵4列的4个字依次命名为w[0]w[1]w[2]和w[3]。它们构成了一个以字为单位的数组w。
接着，对w数组扩充40个新列，构成总共44列的扩展密码数组。新列以如下的递归方式产生： （1） 如果i不是4的倍数，那么第i列由如下等式确定：
w[i]=w[i-4] ⊕w[i-1]
（2） 如果i是4的倍数，那么第i列由如下等式确定： w[i]=w[i-4] ⊕T（w[i-1]） 其中，T是一个复杂的函数。
函数T由三个部分组成：自循环、字节代换和轮常量异或，这三部分的作用分别如下： （1） 字循环：将1个字中的4个字节循环左移1个字节。 （2） 字节代换：对字循环的结果使用S盒进行字节代换。
（3） 轮常量抑或：将前两步的结果同轮常量Rcon[j]进行异或，其中J表示轮数。
（10）简述DES与AES的相同之处
答：①二者的轮函数都是由3层构成，非线性层、线性混合层、子密钥异或，只是顺序不同。 ②AES的子密钥异或对应于DES中S盒之间的子密钥异或。
③AES的列混合运算的目的是让不同的字节相互影响，和DES中F函数的输出与左边一半数据相加也
有类似的效果。
④AES的非线性运算是字节代换，对应于DES中唯一的非线性运算S盒。
⑤行移位运算保证了每一行的字节不仅仅影响其他行对应的字节，而且影响其他行所有的字节，这与DES中置换P相似。
（11）简述实际分组密码的工作模式应遵循的基本原则。
答：①工作模式的运行应当简单；
5
②工作模式应当不会损害算法的安全性； ③工作模式应当不会明显的降低基本密码的效率； ④工作模式应易于实现。 第三章
（1）用C语言编写欧几里德算法的程序。 #include
unsigned int Gcd( unsigned int M, unsigned int N ) {
unsigned int Rem; while( N > 0 ) {
Rem = M % N; M = N; N = Rem; } return M; } void main() {
int temp; int a,b; scanf(\ scanf(\
printf(\ printf(\ }
（2）用欧几里德算法计算gcd（1024，888）。
1024=888*1+136 gcd（888，136） 888=136*6+72 gcd（136，72） 136=72*1+64 gcd（72，64） 72=64*1+8 gcd（64，8） 64=8*8+0 gcd（8，0） gcd（1024，888）=8
（3）利用欧拉定理可简化大指数的幂运算，计算21000 000 mod99 gcd（2，99）=1
φ(99)=φ(9*11)=φ(32*11)=9*（1-1/3）*11=66 1000000=16666*60+40
21000 000 mod99≡216666*60+40 mod99≡240 mod99≡10244 mod99≡344mod99≡672mod99≡34
（4）设Z2[x]的两个元a(x)=2x4+2,b(x)=x5+2,求gcd[a(x),b(x)]=g(x),并找出s(x),t(x)使
6
g(x)=s(x)a(x)+t(x)b(x)。
x5+2≡2x(2x4+2)+(2x+2)
2x4+2≡(x3+2x2+x+2)(2x+2)+1
1≡2x4+2-(x3+2x2+x+2)(2x+2)
≡2x4+2-(x3+2x2+x+2)[(x5+2)-2x(2x4+2)]
≡(2x4+4x3+2x2+4x+1)(2x4+2)+(2x3+x2+2x+1)(x5+2) ≡(2x4+x3+2x2+x+1)(2x4+2)+(2x3+x2+2x+1)(x5+2) 所以，g(x)=1，s(x)=2x4+x3+2x2+x+1，t(x)=2x3+x2+2x+1。
（5）（韩信点兵问题）有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。 x≡1mod5 x≡5mod6 x≡4mod7 x≡10mod11
m1 =5, m2 =6, m3 =7, m4 =11 a1 =1, a2 =5, a3 =4, a4 =10 M=5*6*7*11=2310
M1 =6*7*11=462, M2 =5*7*11=385, M3 =5*6*11=330,M4 =5*6*7=210 Mb≡1modm
462b1≡1mod5 b1≡3mod5 385b2≡1mod6 b2≡1mod6 330b3≡1mod7 b3≡1mod7 210b4≡1mod11 b4≡1mod11
1*3*462+5*1*385+4*1*330+1*10*210≡2111mod2310 兵数2111mod2310。
。。）是半群。 （6）设在Z+中，为a。b=a+b+a.b,a,b∈Z+ ,这里+ ，.分别为数的加法和乘法，证明（Z+，证明： ?封闭性 ∵a,b∈Z+
∴a+b+a.b∈Z+ ∴a。b∈Z+ （Z+，。）满足封闭性 ∴?结合律
。c=(a+b+a.b)。c=(a+b+a.b)+c+(a+b+a.b)*c=a+b+c+ac+bc+ab+abc （a。b） a。(b。c)= a。(b+c+b.c)=a+b+c+b.c+a*(b+c+b.c)=a+b+c+ac+bc+ab+abc
。∴（a。b）c=a。(b。c)
（7）设密文空间共含有5个信息mi,(1≤i≤5),并且p(m1)=p(m2)=1/4,p(m3)=1/8,p(m4)=p(m5)=3/16,求H（m）。
H(x)=-∑p(xi)log(p(xi)) (i=1,2,3,4)
7
=-（2*（1/4log1/4）+1/8log1/8+2*（3/16log3/16））=23/8-3/8log3
（8）请给出一个NP完全类问题的例子。
旅行商问题 （TSP Travelling Salesman Problem）该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。可以用回溯法和贪心算法解决。 还有子集和问题 ，Hamilton回路，最大团问题等。
第二章
4、简答题及计算题 （1）求置换
的逆置换。
6=错误！未找到引用源。=(1 5 6 8 3 7 4 2)
6的逆=错误！未找到引用源。=(1 2 4 7 3 8 6 5)错误！未找到引用源。错误！未找到引用源。
(2) 用维吉尼亚密码加密明文“please keep this message in secret”其中使用的密钥为“computer”试求其密文。
K=computer 所以k=（2，14，12，15，20，19，4，17） p l e a s e k e 15 11 4 0 18 4 10 4 2 14 12 15 20 19 4 17 17 25 16 15 12 23 14 21 R Z Q P M X O V
e p y h i s m e 4 15 19 7 8 18 12 4 2 14 12 15 20 19 4 17 6 3 5 22 2 11 16 21 G D F W C L Q V
s s a g e i n s 18 18 0 6 4 8 13 18 2 14 12 15 20 19 4 17 20 6 12 21 24 1 17 9 U G M V Y B R J
e c r e t 4 2 17 21 9 2 14 12 15 20 6 16 3 19 13 G Q D T N
得到的密文是：RZQPMXOVGFWCLQVUGMVYBRJGQDTN
8
