第三章作业参考答案
1．(1)设M¢是M的逐比特取反，证明：若Y＝DESK(X)则Y¢= DESK¢(X¢)
证：①以PD记DES中的所有置换，包括循环移位、左右交换，则PD满足如下性质：
若T=PD(Z)，则T¢=PD(Z¢)
在DES中，异或运算显然满足性质a¢Åb¢＝aÅb，及a¢Åb＝(aÅb)¢
因而DES中的函数F(Ri－1, Ki)在S盒前是异或运算，所以F(R¢i－1, K¢i)＝F(Ri－1, Ki)
②由密钥编排方案中的运算部件知，
若K的子密钥为K1,K2,…,K16，那么K¢的子密钥为K¢1,K¢2,…,K¢16
③若X经初始置换IP后记为L0||R0，则X¢经初始置换IP后记为L¢0||R¢0，
用K对X加密的第i轮输入为Li－1||Ri－1，输出为Li||Ri，
其中，Li＝Ri－1，Ri＝Li－1ÅF(Ri－1, Ki)
设用K¢对X¢加密的第i轮输入为L¢i－1||R¢i－1，则其第i轮的输出满足
左半部分＝R¢i－1＝L¢i
右半部分＝L¢i－1ÅF(R¢i－1, K¢i)＝L¢i－1ÅF(Ri－1, Ki)＝(Li－1ÅF(Ri－1, Ki))¢＝R¢i
即L¢i||R¢i，
④由归纳法知，前16轮的输出均满足逐比特取反的关系，在经过左右交换盒IP-1两个置换运算，输出密文也满足取反关系 #
(2)由(1)的结论，在对DES进行穷搜索攻击时，选择两个明密文对(M,C1)和(M¢,C2)，然后选择KÎF256，对M加密C＝DESK(M)，判断C=C1或C¢=C2则分别说明K或K¢为正确密钥，否则K和K¢都不是密钥，从而一次加密运算可同时验证一对互反密钥，使搜索量减少一半
2．证明：DES的解密变换是加密变换的逆
证：DES的加密变换由IP，16轮迭代，左右交换，IP-1四部分构成，注意到解密时子密钥逆续使用，16轮迭代与左右交换一起刚好构成Feistel网络，若Feistel网络输入为X，输出为Y，即Y＝Feistel(X,K)，其中K为密钥，如果K的子密钥逆续使用则记为Inv(K)，那么由Feistel网络的性质有X=Feistel(Y,Inv(K))。
对任意的明文消息M加密可表示为C=IP-1[Feistel(IP(M),K)]
即IP(C)=Feistel(IP(M),K)
由Feistel网络的性质有IP(M)=Feistel(IP(C),Inv(K))
而对密文C解密，即为明文＝IP-1[Feistel(IP(C),Inv(K))]＝IP-1[IP(M)]＝M，所以解密变换是加密变换的逆 #
3．在DES的CBC模式中C1的一个错误明显地将影响P1和P2的结果
（1）P2以后的分组不受影响，这是因为C1以后的密文都是正确的，而恢复明文主要看对应密文分组和其前一个密文分组的正确性。
（2）加密前的明文分组P1有1比特错误，则这一错误将在所有后续密文分组中传播，但接受者能够正确解密，除了P1的一个错误比特之外。这是因为相当于发送者将明文改变了1比特得到一个新明文，而该明文的对应密文正确的传送给了接受方。
4．在8bitCFB中密文字符中出现1比特错误，该错误将影响包括该密文的连续9组密文的解密。
5．在实现IDEA时，最困难的部分是模216＋1乘法运算，设a和b是两个n比特的非0整数，记(ab mod 2n)为ab的n个最低有效位，(ab div 2n)为ab右移n位
(1) 证明存在惟一的非负整数q和r，使得ab＝q(2n+1)+r
证：令q为ab/(2n+1)的商，r为ab/(2n+1)的余数，均非负，则ab＝q(2n+1)+r
若存在另一对数q1，r1满足ab＝q1(2n+1)+r1
两式相减的(r1－r)＝(q－q1)(2n+1)
由于|(r1－r)|£2n，所以当且仅当r1＝r，q1＝q时上式才成立 #
(2) 求q和r的上下界
解：由(1)知，r为余数，所以有0£r£2n
又a和b的最大值为2n－1，所以0£q£[ab/(2n+1)]£[(2n－1)2/(2n－1)]＝[2n－3＋4/(2n+1)]= 2n－3对于n³2时都成立，当n＝1时，q＝0
所以，q的上下界为0£q£2n－3 （n³2）n＝1时，q＝0
(3) 证明q＋r<2n+1
证：q＋r£2n－3＋2n＝2n+1－3<2n+1
(4)，(5) 求(ab div 2n)关于q的表达式和(ab mod 2n)关于q和r的表达式
解：设ab＝q12n+r1，则显然有q1＝(ab div 2n)，r1＝(ab mod 2n)
又ab＝q(2n+1)+r，记为(a)式
当q1£ r1时，ab＝q12n+r1＝q1(2n+1)+(r1- q1) 记为(b)式
此时0£ (r1- q1)£ r1£2n－1
由(1)的唯一性结论,比较(a),(b)两式知，q1＝q，r1- q1＝r
即q1＝(ab div 2n)＝q，r1＝(ab mod 2n)＝r＋q1＝r＋q
当q1> r1时，ab＝q12n+r1＝(q1-1)(2n+1)+(r1- q1)+(2n+1) 记为(c)式
此时，由假设q1> r1，知(r1- q1)<0，及(q1-1)³0所以
0<(r1- q1)+(2n+1)£ 2n
即(r1- q1)+(2n+1)为ab/(2n+1)的余数
所以比较两式(a),(c)两式知(q1-1)＝q，(r1- q1)+(2n+1)＝r
即q1＝(ab div 2n)＝q+1，r1＝(ab mod 2n)＝r＋q1-(2n+1)＝r＋(q+1)-(2n+1)
综上所述有
q1＝(ab div 2n)＝＝
r1＝(ab mod 2n)＝＝
(6) 用(4)和(5)的结果求r的表达式，说明r的含义
当q1£ r1时，r＝(r+q)-q=(r1- q1) =(ab mod 2n)- (ab div 2n)
当q1> r1时, r=( r＋q-2n)-(q+1)+ (2n+1)= (r1- q1) + (2n+1)= (ab mod 2n)- (ab div 2n) + (2n+1)
所以r=ab mod (2n＋1)=
6. （1）在IDEA模乘运算中，将模数取为216＋1，是因为它是素数，从而所有非0元都有逆元
(2) 在IDEA的模加运算中，模数取为216使所有元素都有逆元，构成群运算，同时刚好在16位子段上运算，求模运算易于实现，而取为216＋1时则必须做额外处理
复习题&&答案
4.11. 试分析一下CBC、CFB、OFB运行模式的错误传播情况。
CBC的错误传播只影响当前分组和下一分组的解密
CFB的错误传播影响当前分组的对应bit解密和后续的ë64/j û或ë64/j û+1个分组的解密
OFB的错误传播只影响当前分组的对应比特解密，无错误传播
4. 14. Rijndael算法是建立在GF(28)有限域上的，且模多项式为m(x)=x8+x4+x3+x+1，试计算(x6+x2+x+1)×(x4+x+1) mod m(x)，该计算用x乘来表示时，试给出计算过程。
解：上述乘法即求’47’ ×’13’
’47’ ×’02’=xtime(47)=’8E’ //×x
’47’ ×’04’=xtime(8E)=’07’ //×x2
’47’ ×’08’=xtime(07)=’0E’ //×x3
’47’ ×’10’=xtime(0E)=’1C’ //×x4
而’13’=’01’+ ’02’+ ’10’
所以’47’ ×’13’=’47’ ×(’01’+ ’02’+ ’10’)= ’47’+ ’8E’+ ’1C’=’D5’
即(x6+x2+x+1)×(x4+x+1) mod m(x)= x7+ x6+ x4+x2+1
5.3 试证明：在Feistel结构密码中解密过程第1轮的输出等于加密过程最后一轮输入左右两半交换值
证明：假设加密过程的最后一轮输入左右两半分别表示为LE15，RE15，输出的左右两半分别表示为LE15，RE15，第16轮子密钥为K16
解密过程取密文作为同一算法的输入，由于加密最后一轮输出后又进行了左右交换，所以解密第1轮输入是RE16‖LE16
在加密过程中：
LE16＝RE15 ； RE16＝LE15ÅF(RE15, K16)
在解密过程中
LD1＝RD0=LE16＝RE15
RD1＝LD0ÅF(RD0, K16)＝RE16ÅF(RE15, K16)
＝[LE15ÅF(RE15, K16)] ÅF(RE15, K16)＝LE15
证毕#