JNU2012密码学期末真题考题

精品文档密码学作业作业要求1 按下面各题要求回答问题；2 上机进行实验3 索引二篇公开发表有关计算机密码学的文章。时间发表在2009年以后4 考试当日，答题前交到监考老师处（二篇文章，本作业）二.密码体制分类密码体制从原理上可分为两大类，即单钥体制和双钥体制。单钥体制的加密密钥和解密密钥相同。采用单钥体制的系统的保密性主要取决于密钥的保密性，与算法的保密性无关，即由密文和加解密算法不可能得到明文。换句话说，算法无需保密，需保密的仅是密钥。换句话说，算法无需保密，需保密的仅是密钥。根据单钥密码体制的这种特性，单钥加解密算法可通过低费用的芯片来实现。密钥可由发送方产生然后再经一个安全可靠的途径（如信使递送）送至接收方，或由第三方产生后安全可靠地分配给通信双方。如何产生满足保密要求的密钥以及如何将密钥安全可靠地分配给通信双方是这类体制设计和实现的主要课题。密钥产生、分配、存储、销毁等问题，统称为密钥管理。这是影响系统安全的关键因素，即使密码算法再好，若密钥管理问题处理不好，就很难保证系统的安全保密。单钥体制对明文消息的加密有两种方式： 一是明文消息按字符（如二元数字）逐位地加密，称之为流密码；另一种是将明文消息分组（含有多个字符），逐组地进行加密，称之为分组密码。单钥体制不仅可用于数据加密，也可用于消息的认证。双钥体制是由Diffie和Hellman于1976年首先引入的。采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，可以像电话号码一样进行注册公布；另一个则是秘密的。因此双钥体制又称为公钥体制。双钥密码体制的主要特点是将加密和解密能力分开，因而可以实现多个用户加密的消息只能由一个用户解读，或由一个用户加密的消息而使多个用户可以解读。前者可用于公共网络中实现保密通信，而后者可用于实现对用户的认证。三.扩散和混淆扩散和混淆是由Shannon提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。七.什么是零知识证明?下图表示一个简单的迷宫，C与D之间有一道门，需要知道秘密口令才能将其打开。P向V证明自己能打开这道门，但又不愿向V泄露秘密口令。可采用什么协议?零知识证明起源于最小泄露证明。在交互证明系统中，设P知道某一秘密，并向V证明自己掌握这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明。进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议。 V在协议开始时停留在位置A。 P一直走到迷宫深处，随机选择位置C或位置D。 P消失后，V走到位置B，然后命令P从某个出口返回位置B。 P服从V的命令，必要时利用秘密口令打开C与D之间的门。 P和V重复以上过程n次。协议中，如果P不知道秘密口令，就只能从来路返回B，而不能走另外一条路。此外，P每次猜对V要求走哪一条路的概率是1/2，因此每一轮中P能够欺骗V的概率是1/2。假定n取16，则执行16轮后，P成功欺骗V的概率是1/216=1/65536。于是，如果P16次都能按V的要求返回，V即能证明P确实知道秘密口令。还可以看出，V无法从上述证明过程中获取丝毫关于P的秘密口令的信息，所以这是一个零知识证明协议。四.什么是密码分组链接（CBC）模式,请画出加密解密示意图它一次对一个明文分组加密，每次加密使用同一密钥,加密算法的输入是当前明文分组和前一次密文分组的异或，因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。一 根据下面图解释名词,明文,密文,加密,解密,加密算法,解密算法, 加密密钥和解密密钥通信双方采用保密通信系统可以隐蔽和保护需要发送的消息，使未授权者不能提取信息。发送方将要发送的消息称为明文，明文被变换成看似无意义的随机消息，称为密文，这种变换过程称为加密；其逆过程，即由密文恢复出原明文的过程称为解密。对明文进行加密操作的人员称为加密员或密码员。密码员对明文进行加密时所采用的一组规则称为加密算法。传送消息的预定对象称为接收者，接收者对密文进行解密时所采用的一组规则称为解密算法。加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。五.杂凑(Hash)函数应满足的条件杂凑函数应满足以下条件： 函数的输入可以是任意长。 函数的输出是固定长。 已知x，求H(x)较为容易，可用硬件或软件实现。 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向杂凑函数。 已知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数。 找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为强单向杂凑函数。第和第个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。六.迭代型杂凑函数的一般结构其中函数的输入M被分为L个分组Y0,Y1,YL-1，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填充。算法中重复使用函数ff 的输入有两项，一项是上一轮（第i-1轮）输出的n比特值CVi-1，称为链接变量，另一项是算法在本轮（第i轮）的b比特输入分组Yi。f 的输出为n比特值CVi，CVi又作为下一轮的输入。算法开始时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CVL即为最终产生的杂凑值。通常有bn，因此称函数f为压缩函数。算法可表达如下：CV0=IV=n比特长的初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVL算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构，由于f 和分组密码一样是由若干轮处理过程组成，所以对f 的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f 的碰撞。由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应保证找出其碰撞在计算上是不可行的。八.AES高级加密标准的轮函数由4个不同的计算部件组成，分别是：字节代换（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、密钥加（AddRoundKey）。根据下图写出字节代换（ByteSub）、行移位（ShiftRow）、(1) 字节代换（ByteSub）字节代换是非线形变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到： 首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，00映射到自己。 其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：(2) 行移位（ShiftRow）行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第2行循环左移C2个字节，第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关，由表3.10给出。（见66页表3.10）按指定的位移量对状态的行进行的行移位运算记为ShiftRow (State)图3.20是行移位示意图。十二、在RSA算法中,设公钥KU=7,187,私钥KR=23,187,设明文M=88, 求密文C（16分）答：887mod187=(884mod187)( 882mod187)( 881mod187) mod187881mod187=88882mod187=7744mod187=77884mod187=59969536 mod187=132887mod187=(88*77*132) mod187=894432mod187=11 所以 M=88 在公钥KU=7,187的计算下得到的密问C=11,解密时，我们计算M=1123 mod187 1123 mod187=(111 mod187)( 112 mod187)( 114 mod187(118 mod187)( 118mod187) mod187 111 mod187=11 112 mod187=121114 mod187=14641 mod187=55118 mod187=214365881 mod187=331123 mod187=(11*121*55*33*33) mod187=79720245 mod187=88用私钥KR=23,187计算出明文M=88,十三、根据下图S-DES收、发双方共享的10位密钥，计算出两个8位子密钥分别用在加密、解密的不同阶段。图中的P10、P8如下表，初始10位密钥为（1010000010）求图中的K1、K2P1035274101986P8637485109LS-1循环左移一位LS-2循环左移二位初始10位密钥为（1010000010）P10=1000001100LS1左=00001LS1右=11000K1= P8=10010010LS2左=00100LS2右=00011K2= P8=00001001十四、根据下图S-DES加密算法计算出当明文M=11110011，求密文？算法中的变换如表IP26314857IP-141357286E/P41232341P42431 S0=1032321002133132S1=0123201330102103解答如下：M=11110011IP10111101IP-110010110E/P10010010P40010（S0）1=00（S1）1=10（S0）2=10（S1）2=00明文C=10010110十五、通信双方使用RSA加密体制，接收放的公开密钥是（e,n）=（5，119） 接收到的密文是C=66，求明文m=? p(96例4.8)解：求n=119=pq，选p=7，q=17。(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1 mod 96且小于96的d，因为775=385=496+1，所以d为77，因此公开钥为5，119，秘密钥为77，119。设明文m=19，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为6677mod 11919练习题用RSA算法对下列数据实现加密和解密1）p=3;q=11;e=7;m=52) p=5;q=11;e=3m=93) p=7;q=11;e=1;m=84）p=11;q=13;e=11;m=75）p=17;q=31;e=7;m=2十六、是密钥分配的一个实例。根据下图，假定两个用户A、B分别与密钥分配中心KDC (key distribution center)有一个共享的主密钥KA和KB。A希望与B建立一个共享的一次性会话密钥，根据下图解释可通过几步来完成？密钥分配实例 A向KDC发出会话密钥请求。表示请求的消息由两个数据项组成，第1项是A和B的身份，第2项是这次业务的惟一识别符N1，称N1为一次性随机数，可以是时戳、计数器或随机数。 KDC为A的请求发出应答。应答是由KA加密的消息，因此只有A才能成功地对这一消息解密，并且A可相信这一消息的确是由KDC 发出的。消息中包括A希望得到的两项内容： 一次性会话密钥KS； A在中发出的请求，包括一次性随机数N1， 此外，消息中还有B希望得到的两项内容： 一次性会话密钥KS； A的身份（例如A的网络地址）IDA。这两项由KB加密，将由A转发给B，以建立A、B之间的连接并用于向B证明A的身份。 A存储会话密钥，并向B转发EKBKSIDA。因为转发的是由KB加密后的密文，所以转发过程不会被窃听。B收到后，可得会话密钥KS，并从IDA可知另一方是A，而且还从EKB知道KS的确来自KDC。这一步完成后，会话密钥就安全地分配给了A、B。然而还能继续以下两步工作： B用会话密钥KS加密另一个一次性随机数N2，并将加密结果发送给A。 A以f(N2)作为对B的应答，其中f是对N2进行某种变换（例如加1）的函数，并将应答用会话密钥加密后发送给B。十七、假定A、B双方已完成公钥交换，根据下图可按什么步骤建立共享会话密钥？：图5.7 具有保密性和认证性的密钥分配 A用B的公开钥加密A的身份IDA和一个一次性随机数N1后发往B，其中N1用于惟一地标识这一业务。 B用A的公开钥PKA加密A的一次性随机数N1和B新产生的一次性随机数N2后发往A。因为只有B能解读中的加密，所以B发来的消息中N1的存在可使A相信对方的确是B。 A用B的公钥PKB对N2加密后返回给B，以使B相信对方的确是A。 A选一会话密钥KS，然后将M=EPKBESKAKS发给B，其中用B的公开钥加密是为保证只有B能解读加密结果，用A的秘密钥加密是保证该加密结果只有A能发送。 B以DPKADSKBM恢复会话密钥。十八、MD5的算法的框图如下图所示。算法的输入为任意长的消息（图中为K比特），分为512比特长的分组，输出为128比特的消息摘要。请解释MD5对对消息填充、附加消息的长度用步骤、对MD缓冲区初始化处理过程？图6.5 MD5的算法框图处理过程有以下几步： 对消息填充对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的某一倍数减64，留出的64比特备第2步使用。步骤是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为448比特，则需填充512比特，使其长度变为960，因此填充的比特数大于等于1而小于等于512。填充方式是固定的，即第1位为1，其后各位皆为0。 附加消息的长度用步骤留出的64比特以little-endian方式来表示消息被填充前的长度。如果消息长度大于264，则以264为模数取模。Little-endian方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为big-endian方式。前两步执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为M0,N-1。 对MD缓冲区初始化算法使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A，B，C，D），每个寄存器都以littleendian方式存储数据，其初值取为（以存储方式）A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210，实际上为67452301，EFCDAB89，98BADCFE，10325476。十九、例7.1 下面给出的是具有仲裁方式数字签字，其中X表示发方，Y表示收方，A是仲裁者，M是消息，XY： 表示X给Y发送一消息M。请解释签字按如下过程是怎样实现的？ XA：MEKXAIDXH(M)。 AY：EKAYIDXMEKXAIDXH(M)T。其中E是单钥加密算法，KXA和KAY分别是X与A共享的密钥和A与Y共享的密钥，H(M)是M的杂凑值，T是时戳，IDX是X的身份。在中，X以EKXAIDXH(M)作为自己对M的签字，将M及签字发往A。在中A将从X收到的内容和IDX、T一起加密后发往Y，其中的T用于向Y表示所发的消息不是旧消息的重放。Y对收到的内容解密后,将解密结果存储起来以备出现争议时使用。如果出现争议，Y可声称自己收到的M的确来自X，并将EKAYIDXMEKXAIDXH(M)发给A，由A仲裁，A由KAY解密后，再用KXA对EKXAIDXH(M)解密，并对H(M)加以验证，从而验证了X的签字。以上过程中，由于Y不知KXA，因此不能直接检查X的签字，但Y认为消息来自于A因而是可信的。所以在整个过程中，A必须取得X和Y的高度信任： X相信A不会泄露KXA，并且不会伪造X的签字; Y相信A只有在对EKAYIDXMEKXAIDXH(M)T中的杂凑值及X的签字验证无误后才将之发给Y; X，Y都相信A可公正地解决争议。如果A已取得各方的信任，则X就能相信没有人能伪造自己的签字，Y就可相信X不能对自己的签字予以否认。本例中消息M是以明文形式发送的，因此未提供保密性，下面两个例子可提供保密性。二十、例7.2 下面给出的是具有仲裁方式数字签字，其中X表示发方，Y表示收方，A是仲裁者，M是消息，XY： 表示X给Y发送一消息M。请解释数字签字按如下过程是怎样实现的？例签字过程如下： XA: IDXEKXYMEKXAIDXH(EKXYM)。 AY: EKAYIDXEKXYMEKXAIDXH(EKXYM)T。其中KXY是X，Y共享的密钥，其他符号与例7.1相同。X以EKXAIDXH(EKXYM)作为对M的签字，与由KXY加密的消息M一起发给A。A对EKXAIDXH(EKXYM)解密后通过验证杂凑值以验证X的签字，但始终未能读取明文M。A验证完X的签字后，对X发来的消息加一时戳，再用KAY加密后发往Y。解决争议的方法与例7.1一样。本例虽然提供了保密性，但还存在与上例相同的一个问题，即仲裁者可和发方共谋以否认发方曾发过的消息，也可和收方共谋以伪造发方的签字。这一问题可通过下例所示的采用公钥加密技术的方法得以解决。二十一、例7.2 下面给出的是具有仲裁方式数字签字，其中X表示发方，Y表示收方，A是仲裁者，M是消息，XY： 表示X给Y发送一消息M。请解释签字按如下过程是怎样实现的？例签字过程如下： 例7.3 签字过程如下： XA：IDXESKXIDXEPKYESKXM。 AY：ESKAIDXEPKYESKXMT。其中SKA和SKX分别是A和X的秘密钥，PKY是Y的公开钥，其他符号与前两例相同。第步中，X用自己的秘密钥SKX和Y的公开钥PKY对消息加密后作为对M的签字，以这种方式使得任何第3方（包括A）都不能得到M的明文消息。A收到X发来的内容后，用X的公开钥可对ESKXIDXEPKYESKXM解密，并将解密得到的IDX与收到的IDX加以比较，从而可确信这一消息是来自于X的（因只有X有SKX）。第步，A将X的身份IDX和X对M的签字加上一时戳后，再用自己的秘密钥加密发往Y。与前两种方案相比，第3种方案有很多优点。首先，在协议执行以前，各方都不必有共享的信息，从而可防止共谋。第二，只要仲裁者的秘密钥不被泄露，任何人包括发方就不能发送重放的消息。最后，对任何第三方（包括A）来说，X发往Y的消息都是保密的。二十二、根据下图说明PGP中通过数字签字提供认证的过程？ 发送方产生消息M。 用SHA产生160比特长的消息摘要H(M)。 发送方用自己的秘密钥SKA按RSA算法对H(M)加密，并将加密结果EPSKAH(M)与M链接后发送。 接收方用发送方的公开钥对EPSKAH(M)解密得H(M)。 接收方对收到的M计算消息摘要，并与中的H(M)比较。如果一致，则认为M是真实的。过程中结合使用了SHA和RSA算法，类似地也可结合使用DSS算法和SHA算法。二十三、根据下图说明PGP为传输或存储的文件提供加密的保密性认证业务的过程？ 发送方产生消息M及一次性会话密钥KS。 用密钥KS按CAST-128（或IDEA或3DES）加密M。 用接收方的公开钥PKB按RSA算法加密一次性会话密钥KS，将、中的两个加密结果链接起来发往接收方。 接收方用自己的秘密钥按RSA算法恢复一次性会话密钥。 接收方用一次性会话密钥恢复发送方发来的消息。二十四、根据下图说明同一消息同时提供保密性与认证性的过程？、发送方首先用自己的秘密钥对消息签字，将明文消息和签字链接在一起，再使用一次性会话密钥按CAST-128（或IDEA或3DES）对其加密，同时用ElGamal算法对会话密钥加密，最后将两个加密结果一同发往接收方。这一过程中，先对消息签字再对签字加密。这一顺序优于先加密、再对加密结果签字。这是因为将签字与明文消息在一起存储比与密文消息在一起存储会带来很多方便，同时也给第三方对签字的验证带来方便。21、图2.9是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由2.2求出。图2.9 一个3级反馈移位寄存器参考答案表2.2 一个3级反馈移位寄存器的状态和输出状态（a1,a2,a3)输出1 0 11 1 01 1 10 1 11 0 11 1 0 101110既输出序列为101110111011,周期为4Rcon(9)与Rcon进行XOR后WI-4WI=tempwi-41B00000046A515D2EAD27321AC7766F322.计算AES的密钥编排EAD27321(32) B58DBAD2(33) 312BF560(34) 7F8D292F(35) 求W36 W37 W38 W39 K15K11K7K3K14K10K6K2K13K9K5K1K12K8K4K0W3w2w1w0w7w6w5w4gJ12345678910RCJ01020408102040801B36I(十进制)tempRubWord后Rcon(9)367F8D292F8D292F7F5DA515D2密钥扩展的计算第八轮密钥 EAD27321(32) B58DBAD2(33)312BF560(34) 7F8D292F(35) 字循环：使一个字的中的四个字节循环左移一个字节 W35 = temp=7F8D292FRotWord后7F8D292F盒对输入的每个字节进行代换SubWord=5DA515D27F经过s盒的代换得到5D3. 第步的结果SubWord=5DA515D2与轮常量进行Rcon9 5DA515D2=1B000000 5DA515D2 =46A515D2常量是一个字，最右边三个字节总是为RCONJ=(RCJ,0,0,0)G=46A515D2W36 = G W32 = 46A515D2 EAD27321 =AC7766F3W37= W33 W36W38= W34 W37W39= W35 W3823例2.3 图2.11是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为图2.11 一个5级线性反馈移位寄存器1001101001000010101110110001111100110周期为31。225 RSA算法密钥的产生 选两个保密的大素数p和q。 计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。 选一整数e，满足1e(n)，且gcd(n),e)=1。 计算d，满足de1 mod (n),即