现代密码学简答题及计算题.doc

第七章 简答题及计算题公钥密码体制与对称密码体制相比有哪些优点和不足？答：对称密码一般要求： 1、加密解密用相同的密钥 2、收发双方必须共享密钥 安全性要求： 1、密钥必须保密 2、没有密钥，解密不可行 3、知道算法和若干密文不足以确定密钥公钥密码一般要求：1、加密解密算法相同，但使用不同的密钥 2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥 安全性要求： 1、两个密钥之一必须保密 2、无解密密钥，解密不可行 3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥RSA算法中n11413，e7467，密文是5859，利用分解11413101113，求明文。解：显然，公钥e=7467，满足1e，且满足，通过公式求出，由解密算法得在RSA算法中，对素数p和q的选取的规定一些限制，例如：p和q的长度相差不能太大，相差比较大；P-1和q-1都应有大的素因子；请说明原因。答：对于p，q参数的选取是为了起到防范的作用，防止密码体制被攻击p，q长度不能相差太大是为了避免椭圆曲线因子分解法。因为需要p，q为强素数，所以需要大的素因子在ElGamal密码系统中，Alice发送密文（7，6），请确定明文m。上的椭圆曲线E：，且m=3。请确定该椭圆曲线上所有的点；生成元G=（2,7），私钥，明文消息编码到上，加密是选取随机数k=3，求加解密过程。解：取x=0,1，10 并计算，现以x=0为例子。因为x=0，没有模11的平方根，所以椭圆上不存在横坐标为0 的点；同理依次可以得到椭圆上的点有（2 , 4） （2，7） （3 , 5） （3，6） （5,9） （5 , 2） （7 , 9） （7 ，2） （8 , 8） （8 , 3） （10 , 9） (10 , 2)密钥生成：由题得B的公钥为E: ，私钥为与RSA密码体制和ElGamal密码体制相比，简述ECC密码体制的特点。答：椭圆曲线密码体制的安全性不同于RSA的大整数因子分解问题及ElGamal素域乘法群离散对数问题。自公钥密码产生以来，人们基于各种数学难题提出了大量的密码方案，但能经受住时间的考验又广泛为人们所接受的只有基于大整数分解及离散对数问题的方案，且不说这两种问题受到亚指数的严重威胁，就如此狭窄的数学背景来说，也不能不引起人们的担忧，寻找新的数学难题作为密码资源早就是人们努力的一个方向，而椭圆曲线为公钥密码体制提供一类新型的机制。椭圆曲线资源丰富。同在一个有限域上存在着大量不同的椭圆曲线，这位安全性增加了额外的保障。效率方面。在同等安全水平上，椭圆曲线密码体制的密钥长度与RSA，ElGamal的密钥小得多，所以，计算量小，处理速度快，存储空间占用小，传输带宽要求低，特别在移动信号，无线设备上的应用前景非常好。安全性。而显然是任何密码体制的必备条件，椭圆曲线密码体制的安全性分析因而也引起了各国密码学家及有关部门的关注和重视，但成果并不丰硕。也许这可视为椭圆曲线密码体制具有高安全性的一种证据，因此，大多是密码学家对其前景持乐观态 第六章 4.简答题（1）简要说明散列（哈希）函数的特点。 答：哈希函数有如下特点:输入数字串与输出数字串具有唯一的对应关系;输入数字串中 任何变化会导致输出数字串也发生变化;从输出数字串不能够反求出输入数字串。哈希函数算法有多种,它受到广泛的应用,在信息安全领域,它是实现数字签名和认证的重要工具。 （3）简述MD5算法。答：Md5的全称是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由Mit Laboratory For Computer Science和Rsa Data Security Inc的Ronaldl.rivest开发出来，经md2、md3和md4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被“压缩”成 一种保密的格式。MD5是一个安全的散列算法，输入两个不同的明文不会得到相同的输出值，根据输出值，不能得到原始的明文，即其过程不可逆；所以要解密MD5没有现成的算 法，只能用穷举法，把可能出现的明文，用MD5算法散列之后，把得到的散列值和原始的数据形成一个一对一的映射表，通过比在表中比破解密码的MD5算法散 列值，通过匹配从映射表中找出破解密码所对应的原始明文。（4）MD5在MD4基础上做了哪些改进，其改进的目的是什么?答：MD5在MD4基础上增加了Safety-Belts，所以MD5又被称为是“系有安全带的MD4”，它虽然比MD4慢一点，但更为安全。(5)简述SHA1算法。答：SHA1也叫安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标 准（Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于264位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的 过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。 SHA1有如下特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。（6）简述SHA256算法。答：SHA256算法是SHA家族算法里面的一种，它的输入时最大长度小于264的消息，输出是256bit消息摘要，输入以512bit的分组为单位处理。该过程包括：附加填充位和长度，初始化散列缓冲区，以512bit分组为单位处理消息，经过64轮操作。（7）简述HMAC算法。答：HMAC是密钥相关的哈希运算消息认证码（keyed-Hash Message Authentication Code）,HMAC运算利用哈希算法，以一个密钥和一个消息为输入，生成一个消息摘要作为输出。 HMAC引擎提供HMAC运算功能，发挥两方面的作用： a）验证TPM接受的授权数据和认证数据； b）确认TPM接受到的命令请求是已授权的请求，并且，命令在传送的过程中没有被改动过。 （9）如图6-17所示的认证码是基于分组密码的CBC模式，其他模式是否也可以用来认证消息？请简要说明原因。答：可以的，依据数据认证算法的思想，可选用其他分组密码算法来生产数据认证码，同时考虑安全性分组长度应选择更长。（10）数字签名算法中，对消息的Hash值签名，而不对消息本身签名有哪些好处？答：由于安全的Hash函数具有抗碰撞性，所以利用消息散列值实现数字签名，能够满足消息的完整性，防伪造性以及不可否认性等特点，而且签名短，更容易管理，有利于签名的扩展。第五章 （1）简述序列密码算法和分组密码算法的不同。序列密码分组密码明文长度可以小于1字节，有记忆；加密不仅与密钥和明文有关，还与当前状态有关，也叫状态密码；设计关键在于密钥序列产生器，使生成的密钥序列尽可能高的不可预测性。明文分成比较大的块，无记忆；每块使用相同的加密函数进行处理；增加记忆模块，形成一种序列密码；设计关键在于加解密算法，是明文密文之间的关联在密钥控制下尽可能复杂；（2） 密钥序列生成器是序列密码算法的核心，请说出至少5点关于密钥序列生成器的基本要求。种子密钥K的长度足够大，一般应在128位以上；KG生成的密钥序列ki具极大周期；ki具有均匀的n元分布；利用统计分析方法由ki提取关于KG结构或K的信息在计算上不可行；混乱性，即ki的每一比特位均与K的大多数比特有关；扩散性，即K的任一比特的改变要引起ki在全貌上的变化；序列密钥ki不可预测，密文和相应明文的部分信息，不能确定整个ki。（4）简述RC4算法的实现过程。 详见166页。（5）简述A5算法的实现过程。详见169页。（6）简述SEAL算法的实现过程。 详见171页。（7）简述WAKE算法的实现过程。详见176页。（8） 简述PKZIP算法的实现过程。详见177页。（9）简述FCSR算法的实现过程。详见161页。第四章 、简答题（1）分组密码的设计应满足的要求是什么？答：分组要足够长。假设n为分组长度，则要使分组代换字母表中的元素个数2n足够大，以防止明文穷举攻击。密钥长度要足够长，以防止密钥穷举攻击。但密钥又不能过长，这不利于密钥的管理且影响加解密的速度。由密钥确定的置换算法要足够复杂，足以抵抗各种已知的攻击，如查分攻击和线性攻击等，使攻击者除了利用穷举攻击外，无其他更好的攻击方法。加密解密运算简单，易于软件和硬件的快速实现。为了便于软件编程和通过逻辑电路实现，算法中的运算应尽量简单，如二进制加法或移位运算，参与运算的参数长度也应选择在8的整数倍，可以充分发挥计算机中字节运算的优势。一般无数据扩展，即明文和密文长度相同。在采用同态置换和随机话加密技术时可引入数据扩展。差错传播尽可能的小。设计密码时，的安全性为必要条件，同时还需考虑。归纳起来，一个分组密码在实际应用中需要在安全性和实用性之间寻求一种平衡，使算法在足够安全的同时，又具有尽可能短的密钥，尽可能小的存储空间以及尽可能快的运行速度。（2）简述分组密码设计的准则。答：分组长度分组长度越长意味着安全性越高，但是会影响加密解密的速度。1977年之后，由于计算速度和分析技术的提高，建议使用分组长度128位。密钥长度密钥越长同样意味着安全性越高，但会影响加密和解密的速度。现在一般认为64位的密钥是不安全的，通常使用的密钥长度为128位。轮函数F轮函数F通常之迭代分组密码中单轮加密解密算法的实现部分，是分组密码结构的核心，由其实现数据的混乱和扩散。在设计中，轮函数要遵循雪崩效应准则和位独立准则。评价轮函数实际质量的指标有安全性，速度和灵活性。迭代的轮数迭代分组密码的本质是单轮不能提供足够的安全性而多伦迭代增强其安全性。一般而言，迭代轮数越多，密码分析越困难，但过多的迭代会使输入和输出的关系复杂化，影响加解密速度，而安全性增强不明显，一般而言，决定迭代轮数的准则是：是密码分析的难度大于简单穷举攻击的难度。子密钥的生成方法理论设计目标是子密钥的统计独立性和密钥更换的有效性。包括：实现简单，便于硬件实现，子密钥的生成不影响迭代轮函数的执行；不存在简单关系；种子密钥的所有比特对每个子密钥比特影响大致相同；没有弱密钥或弱密钥容易避开；保证密钥和密文符合位独立准则和雪崩效应。（3）简述DES算法中S盒的特点？答： S盒是DES中唯一的非线性部分，DES的安全强度主要取决于S盒的安全强度。DES中8个S盒，输入均为6位，输出为4位。有以下特点：具有良好的非线性，即输出地每一个比特与全部输入比特有关；每一行包括所有16种4位二进制。两个输入相差1bit比特时，输出相差2bit。如果两个输入刚好在中间2个比特上不同，则输出至少有2个比特不同。如果两个输入前2位不同而最后2位相同，则输出一定不同。相差6bit的输入共32对，在这32对中有不超过8对的输出相同。（4）DES算法具有互补性，而这个特性会使DES在选择明文攻击下所需的工作量减半。简要说明原因。 答： 在选择明文攻击下，C1=Ek（m）, （1）C2= Ek（） （2） 根据互补性， =E(m) (3) 根据（1）式穷举搜索密钥k时，入输出密文是C1，则加密密钥就是多应用的密钥；若输出密文是，根据（3）可知加密密钥是多应用的密钥的补，这样，利用一个密钥的加密尝试，能够检测两个密钥是否为真正的加密密钥。因此，DES的互补性会使DES在选择明文攻击下所需的工作量减半。（6）简述利用差分分析攻击DES算法的基本过程。答：过程如下：首先攻击者选择具有固定差分（在DES分析中，“差分”定义为异或运算）的一对明文，这两个明文可以随机选取，攻击者甚至不必知道他们的值，但要求它们符合特定的差分条件；然后，使用输出密文中的差分，分析可能的密钥；随着分析的密文对越来越多有一个的概率明显增大，它就是正确的密钥。（7）简述线性攻击的基本原理。答：基本原理是寻求明文、密文和密钥间有效的线性逼近，当该逼近的线性偏差足够大时，就可以由一定量的明密文对推测出部分密钥信息。线性分析的关键是确定有效线性方程的线性偏差和线性组合系数。（8）简述AES算法的正变换矩阵比逆变换矩阵简单的原因。答：逆S盒比S盒复杂，需要将逆S盒中的每个字节映射到它在有限域GF（）中的逆。输出值不能通过一个简单的函数变换输入值所得到。S盒必须是可逆的，即SSa=a,而Sa=S-1a不成立，在这个意义上S盒不是自逆的。（9）简述AES的子密钥生成过程 答：AES首先将初始密钥输入到一个4*4矩阵中。这个4*4矩阵的每一列的4个字节组成一个字，矩阵4列的4个字依次命名为w0w1w2和w3。它们构成了一个以字为单位的数组w。接着，对w数组扩充40个新列，构成总共44列的扩展密码数组。新列以如下的递归方式产生：（1） 如果i不是4的倍数，那么第i列由如下等式确定：wi=wi-4 wi-1（2） 如果i是4的倍数，那么第i列由如下等式确定： wi=wi-4 T（wi-1）其中，T是一个复杂的函数。函数T由三个部分组成：自循环、字节代换和轮常量异或，这三部分的作用分别如下：（1） 字循环：将1个字中的4个字节循环左移1个字节。（2） 字节代换：对字循环的结果使用S盒进行字节代换。（3） 轮常量抑或：将前两步的结果同轮常量Rconj进行异或，其中J表示轮数。（10）简述DES与AES的相同之处答：二者的轮函数都是由3层构成，非线性层、线性混合层、子密钥异或，只是顺序不同。 AES的子密钥异或对应于DES中S盒之间的子密钥异或。 AES的列混合运算的目的是让不同的字节相互影响，和DES中F函数的输出与左边一半数据相加也有类似的效果。AES的非线性运算是字节代换，对应于DES中唯一的非线性运算S盒。行移位运算保证了每一行的字节不仅仅影响其他行对应的字节，而且影响其他行所有的字节，这与DES中置换P相似。（11）简述实际分组密码的工作模式应遵循的基本原则。答：工作模式的运行应当简单；工作模式应当不会损害算法的安全性；工作模式应当不会明显的降低基本密码的效率；工作模式应易于实现。 第三章（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(%d,&a); scanf(%d,&b); printf(the greatest common factor of %d and %d is ,a,b); printf(%dn,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） 利用欧拉定理可简化大指数的幂运算，计算21000 000 mod99gcd（2，99）=1(99)=(9*11)=(32*11)=9*（1-1/3）*11=661000000=16666*60+4021000 000 mod99216666*60+40 mod99240 mod9910244 mod99344mod99672mod9934（4） 设Z2x的两个元a(x)=2x4+2,b(x)=x5+2,求gcda(x),b(x)=g(x),并找出s(x),t(x)使g(x)=s(x)a(x)+t(x)b(x)。x5+22x(2x4+2)+(2x+2)2x4+2(x3+2x2+x+2)(2x+2)+112x4+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） （韩信点兵问题）有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。x1mod5x5mod6x4mod7x10mod11m1 =5, m2 =6, m3 =7, m4 =11a1 =1, a2 =5, a3 =4, a4 =10M=5*6*7*11=2310M1 =6*7*11=462, M2 =5*7*11=385, M3 =5*6*11=330,M4 =5*6*7=210Mb1modm462b11mod5 b13mod5385b21mod6 b21mod6330b31mod7 b31mod7210b41mod11 b41mod111*3*462+5*1*385+4*1*330+1*10*2102111mod2310兵数2111mod2310。（6） 设在Z+中，。为a。b=a+b+a.b,a,bZ+ ,这里+ ，.分别为数的加法和乘法，证明（Z+，。）是半群。证明：封闭性a,bZ+a+b+a.bZ+a。bZ+（Z+，。）满足封闭性结合律（a。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)（7） 设密文空间共含有5个信息mi,(1i5),并且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回路，最大团问题等。 第二章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 e15 11 4 0 18 4 10 42 14 12 15 20 19 4 1717 25 16 15 12 23 14 21R Z Q P M X O Ve p y h i s m e4 15 19 7 8 18 12 42 14 12 15 20 19 4 176 3 5 22 2 11 16 21G D F W C L Q Vs s a g e i n s18 18 0 6 4 8 13 182 14 12 15 20 19 4 1720 6 12 21 24 1 17 9U G M V Y B R Je c r e t4 2 17 21 92 14 12 15 206 16 3 19 13G Q D T N得到的密文是：RZQPMXOVGFWCLQVUGMVYBRJGQDTN（3）用Playfair密码加密明文“hide the gold in the tree stump”密钥是“cryptography”试求其密文。由密钥得出的矩阵如下： P=hide the gold in the tree stump所以密文为：IQEFPBMEDUEKYSGIPCIMKMCZRQ（ee中间加q）(4)用Hill密码加密明文“hill”,使用的密钥是： K= C=(7,8,11,11)=(269,268,268,258)mod26=(mod26)=(9,8,8,24) 密文为：JIIY(5) 题目：已知一下密文是由仿射密码得到的试求其明文。“FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH”解答：统计得出：A：2 I:0 Q:0 Y：1B：1 J:0 R:8 Z:0C：0 K:5 S:3D：7 L:2 T:0E：5 M:2 U:2F：4 N:1 V:4G：0 O:1 W:0H：5 P:2 X:2根据统计规律我们猜想R是e加密得到的，D是t加密得到的，因为t，e出现频率较高，得到同余方程组（4a+b）mod26=17（19a+b）mod26=13得到a=6b=19仿射密码要求gcd（a，26）=1，所以此解错误。再次猜想R是e加密的得到的，k是t加密得到的，从而得到a=3，b=5，将此解带入密文测试发现k=（3,5）正确，推出解密函数d（y）=9y-19得到解密结果：algorith msarequitegeneraldefinitionsofarithmeticprocesses（8）简述单表代换密码和多表代换密码的基本思想及其优缺点单表代换多表代换基本思想明文消息中相同的字母，在加密时都是用同一固定的字母代换。明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换而是根据其出现的位置次序用不同的字母代换。优点破译难度稍高，密钥更改便捷，增加了单表代换密码体制的灵活性。多表代换密码的破译则相对复杂，因为明文的统计特性通过多个表的平均作用而而被隐藏起来了，能更好的抵抗明文分析。缺点通过统计分析地方法很容易破解。Hill密码体制，可能抵抗不了已知明文攻击。 第一章（1） 信息安全中常用的攻击分别指什么？分别使用什么密码技术能抵御这些攻击？ 答：常用的攻击形式有：中断、截取、篡改、伪造和重放五类。