第三章习题（个人答案，可能有错误）
1.判断题
（1）现在使用大多数密码系统的安全性都是从理论上证明它是不可攻破的。（×）
（2）根据香农的理论，在加密明文之前，利用压缩技术压缩明文，将增加攻击者破译的难度。（√）
（3）从理论上讲，穷举攻击可以破解任何密码系统，包括一次一密密码系统。（×）解析：一次一密系统具有完全保密性。
（4）设计密码系统的目标就是使其达到理论保密性。（×）解析：不能单纯追求理论保密性，应考虑实际情况。
如一次一密系统要传送大量密钥到接收方，致使密钥管理非常脆弱而易受攻击。（5）任何一个密码体制都可以通过迭代来提高其安全强度。（×）解析：分组密码通过迭代可提高安全性。
（6）在问题的复杂度中，P类不大于NP类。（√）解析：NP类包括P类，但目前没有“P类严格小于NP类”的证明。
2.选择题
（1）16模20的逆元是（D）。
A．3 B. 4 C. 5 D.不存在
解析：gcd(16,20)!=1，不存在逆元。
（2）下面（D）不是代数系统（R，+，）构成一个环的必要条件。
A. (a+b)+c=a+(b+c), a,b,c∈R
B. a+b=b+a, a,b∈R
C. (ab)c=a(bc),a,b,c∈R
D. 对于R中的任何非零元a，存在逆元a-1 ∈R，使aa-1=1
（3）下列整数中属于Blum数的是（A）。
A．21 B. 28 C. 35 D. 42
解析：21=3*7，且3，7都模4余3，21为Blum数。
（4）雅可比符号J(384,443)=（A）
A. 1
B. -1
C. 0
D. 以上结果都不对
解析：J(384,443)=J(59,443)=-J(443,59)=-J(30,59)=-J(2,59)*J(15,59)=J(15,59)=-J(59,15)
=-J(13,15)=-J(15,13)=-J(2,13)=1
（5）下面的描述中（B）是错误的。
A．互信息量等于先验的不确定性减去尚存的不确定性。
B．互信息量不能为负值。
C．当X表示信道的输入，Y表示信道的输出时，条件熵H(X|Y)表示X未被Y所泄露的信息量的均值。
D．任何两个事件之间的互信息量不可能大于其中任一事件的自信息量。
解析：互信息量可正可负。互信息量为正，表示有助于事件的出现，反之，则是不利的。
（6）计算复杂性是密码分析技术中分析计算量和研究破译密码的固有难度的基础，算法的运行时间为难解的是（D）。
A．O(1) B. O(n) C.O(n2) D. O(2n)
3.填空题模拟人生3mod使用
（1）模运算是等价运算，这是因为模运算具有自反性、对称性和传递性的性质。（2）设m为一个非0，非±1的整数，若gcd（a,m）=1，则a对模m的逆存在。
（3）设E是一个域，F是E的一个子集，如果F关于E上的运算自身也构成一个域，则称F为E的子域，E为F的扩域。
（4）1949年，香农（Claude Shannon）在《Bell System Technical Journal》上发表题为《保密系统的通信理论》的论文从信息论的角度对保密通信问题作了全面的阐述，建立了保密通信系统的数学理论，它对后来密码学的发展产生了巨大影响。
（5）自然语言的字符之间不是毫无关联的，为了衡量自然语言信源符号间的依赖程度，本文引入相关性和冗余度的概念。
（6）一般而言，容易的算法的时间复杂度要求是______________。
（7）密码的强度是破译该密码所用的算法的计算复杂性决定的，而算法的计算复杂性由它所需的时间复杂度T 和空间复杂度S来度量的。
4.简答题及计算题
（1）用C语言编写欧几里德算法的程序。
#include<stdio.h>
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("%d",&a);
scanf("%d",&b);
printf("the greatest common factor of %d and %d is ",a,b);
printf("%d\n",Gcd(a,b));
}
（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）利用欧拉定理可简化大指数的幂运算，计算2
1000 000 mod99 gcd （2，99）=1
φ(99)=φ(9*11)=φ(32*11)=9*（1-1/3）*11=66
1000000=16666*60+40
2
1000 000 mod99≡216666*60+40 mod99≡240 mod99≡10244 mod99≡344mod99≡672
mod99≡34
（4）设Z 2[x]的两个元a(x)=2x 4+2,b(x)=x 5+2，求gcd[a(x),b(x)]=g(x)，并出s(x),t(x)使g(x)=s(x)a(x)+t(x)b(x)。
x 5+2≡2x(2x 4+2)+(2x+2)
2x 4+2≡(x 3+2x 2+x+2)(2x+2)+1
1≡2x 4+2-(x 3+2x 2+x+2)(2x+2)
≡2x 4+2-(x 3+2x 2+x+2)[(x 5+2)-2x(2x 4+2)]
≡(2x 4+4x 3+2x 2+4x+1)(2x 4+2)+(2x 3+x 2+2x+1)(x 5+2)
≡(2x 4+x 3+2x 2+x+1)(2x 4+2)+(2x 3+x 2+2x+1)(x 5+2)
所以，g(x)=1，s(x)=2x 4+x 3+2x 2+x+1，t(x)=2x 3+x 2+2x+1。
（5）（韩信点兵问题）有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。
x ≡1mod5
x ≡5mod6
x ≡4mod7
x ≡10mod11
m 1 =5, m 2 =6, m 3 =7, m 4 =11
a 1 =1, a 2 =5, a 3 =4, a 4 =10
M=5*6*7*11=2310
M 1 =6*7*11=462, M 2 =5*7*11=385, M 3 =5*6*11=330,M 4 =5*6*7=210
Mb ≡1modm
462b 1≡1mod5 b 1≡3mod5
385b 2≡1mod6 b 2≡1mod6
330b 3≡1mod7 b 3≡1mod7
210b 4≡1mod11 b 4≡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+
。b∈Z+
∴a
。）满足封闭性
∴（Z+，
②结合律
。b）。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。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)
∴（a
（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)
=-（2*（1/4log1/4）+1/8log1/8+2*（3/16log3/16））=23/8-3/8log3
（8）请给出一个NP完全类问题的例子。
旅行商问题（TSP Travelling Salesman Problem）该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。可以用回溯法和贪心算法解决。
还有子集和问题，Hamilton回路，最大团问题等。
（8）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论