现代密码学-清华大学-杨波-部分习题答案

NCUT密码学–习题与答案2010第1页（声明：非标准答案，仅供参考）一、古典密码（1,2,4）字母ABCDEFGHIJKLMNOPQRSTUVWXYZ数字0123456789101112131415161718192021222324251.设仿射变换的加密是E11,23(m)≡11m+23(mod26)，对明文“THENATIONALSECURITYAGENCY”加密，并使用解密变换D11,23(c)≡11-1(c-23)(mod26)验证你的加密结果。解：明文用数字表示：M=[19741301981413011184220178192406413224]密文C=E11,23(M)≡11*M+23(mod26)=[24221510232472110231413151992724123111510191]=YWPKXYHVKXONPTJCHYBXLPKTB∵11*19≡1mod26(说明：求模逆可采用第4章的“4.1.6欧几里得算法”，或者直接穷举1~25)∴解密变换为D(c)≡19*(c-23)≡19c+5(mod26)对密文C进行解密：M’=D(C)≡19C+5(mod26)=[19741301981413011184220178192406413224]=THENATIONALSECURITYAGENCY2.设由仿射变换对一个明文加密得到的密文为edsgickxhuklzveqzvkxwkzukvcuh，又已知明文的前两个字符是“if”。对该密文解密。解：设解密变换为m=D(c)≡a*c+b(mod26)由题目可知密文ed解密后为if，即有：D(e)=i：8≡4a+b(mod26)D(d)=f：5≡3a+b(mod26)由上述两式，可求得a=3，b=22。因此，解密变换为m=D(c)≡3c+22(mod26)密文用数字表示为：c=[4318682102372010112521416252110232210252010212207]则明文为m=3*c+22(mod26)=[85241420201317403197818197013100194072417]=ifyoucanreadthisthankateahcer4.设多表代换密码Ci≡AMi+B(mod26)中，A是2×2矩阵，B是0矩阵，又知明文“dont”被加密为“elni”，求矩阵A。解：dont=(3,14,13,19)=elni=(4,11,13,8)设abAcd⎡⎤=⎢⎥⎣⎦，则有：43(mod26)1114abcd⎡⎤⎡⎤⎡⎤=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦，1313(mod26)819abcd⎡⎤⎡⎤⎡⎤=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦可求得1013923A⎡⎤=⎢⎥⎣⎦NCUT密码学–习题与答案2010第2页二、流密码（1,3,4）1.3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。解：设反馈函数为f(a1,a2,a3)=a1⊕c2a2⊕c1a3当c1=0，c2=0时，f(a1,a2,a3)=a1，输出序列为101101…，周期为3。当c1=0，c2=1时，f(a1,a2,a3)=a1⊕a2，输出序列如下10111001011100…，周期为7。当c1=1，c2=0时，f(a1,a2,a3)=a1⊕a3，输出序列为10100111010011…，周期为7。当c1=1，c2=1时，f(a1,a2,a3)=a1⊕a2⊕a3，输出序列为10101010…，周期为2。3.设n=4，f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。解：列出该非线性反馈移位寄存器的状态列表和输出列表：状态(a1,a2,a3,a4)f(a1,a2,a3,a4)输出(1,1,0,1)11(1,0,1,1)11(0,1,1,1)10(1,1,1,1)01(1,1,1,0)11(1,1,0,1)11………因此，输出序列为1101111011…，周期为5。4.密钥流由m=2s级的LFSR产生，前m+2个比特是(01)s+1，即s+1个01，请问第m+3个比特有无可能是1，为什么？解：根据题目条件，可知初始状态s0为：0121(,,,,)(0,1,...,0,1)smmsaaaa−==L注：个01设该LFSR的输出序列满足如下递推关系：1121,1mkmkmmkacacacak++−−=++≥L则第m+1,m+2个比特为：11211211211222101smmmmjjsmmmmjjacacacacacacacac+−−=++==++===++==∑∑LL而第m+3比特应为：31221341143123412111010100mmmmmmmsmmjjacacacacacacaccccccc+++−−−−==++++++=⋅+⋅+⋅+⋅++⋅+⋅==∑LLL即第m+3比特为0，因此不可能为1.M的散列值相同。NCUT密码学–习题与答案2010第3页三、分组密码（1,2,3,4）1.(1)设M’是M的逐比特取补，证明在DES中，如果对明文分组和密文分组都逐比特取补，那么得到的密文也是原密文的逐比特取补，即如果Y=DESK(X)，那么Y’=DESK’(X’)提示：对任意两个长度相等的比特串A和B，证明(A⊕B)’=A’⊕B。证：(i)容易验证，在DES中所有的置换操作，包括初始置换IP、逆初始置换IP-1、选择扩展算法E、置换运算P以及置换选择PC1、置换选择PC2，都满足如下性质：如果N=PO(M)，则N’=PO(M’)，其中PO是某种置换操作即有(PO(M))’=PO(M’)(ii)容易验证，密钥生成过程中的左循环移位LS满足如下性质：如果N=LS(M)，那么N’=LS(M’)，即有(LS(M))’=LS(M’)结合(1)可知，如果记子密钥为(K1,…,K16)，K为初始密钥，KG为密钥生成算法，则有如下性质：如果(K1,…,K16)=KG(K)，那么(K1',…,K16')=KG(K’)(iii)对于任意两个比特a和b，有(a⊕b)’=a⊕b⊕1=(a⊕1)⊕b=a’⊕b（=a⊕(b⊕1)=a⊕b’），因此对任意两个长度相等的比特串A和B，有(A⊕B)’=A’⊕B=A⊕B’成立。(iv)DES的轮变换为()111,iiiiiiLRRLFRK−−−=⎧⎪⎨=⊕⎪⎩，其中轮函数F可写为(),((()))FRKPSERK=⊕。因此有如下推理：()()'''''1111''1111''111()'(')(,)(,)(i)(ii)(,)'(,)'(iii)(,)(,)((())KKiiiiiiiiiiiiiiiiiiiiYDESXYDESXRLFRKRLFRKLFRKLFRKFRKFRKPSERK−−−−−−−−−−−=⇒=⇔=⊕⇒=⊕⇔⊕=⊕⇔=⇔⊕根据根据''1''11'''111'''11''11)((()))()()()()(())(())(())()(())()(i)iiiiiiiiiiiiiiiiiiPSERKERKERKiiiERKERKERKERKERKERER−−−−−−−−−−=⊕⇔⊕=⊕⊕=⊕=⊕⇔⊕=⊕⇔=根据可知由知此式成立(2)对DES进行穷举搜索攻击时，需要在由256个密钥构成的密钥空间进行。能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。解：(1)根据取补的性质，密钥空间K可分成两部分K1/2和K’1/2，即K=K1/2∪K’1/2对于任意一个k∈K1/2，它的取补k’∈K’1/2；对于任意一个k∈K’1/2，它的取补k’∈K1/2。即，K1/2和K’1/2是一一对应的；它们的空间大小都是256/2=255。(2)选择明文攻击时，假设有Ek0(x)=y，其中x、y分别为明文和密文，E为DES加密算法，k0为真实的密钥。NCUT密码学–习题与答案2010第4页穷举搜索密钥空间K1/2，对于某个k∈K1/2，假设(i)Ek(x)=y1，如果y1=y，则说明k0=k而且k0∈K1/2。(ii)Ek(x’)=y2，如果y2=y’，则说明k=k0’，即k0=k’而且k0∈K’1/2。综上可知：对于选定的明文密文对(x,y)，只需遍历K1/2中的所有密钥即可，此时密钥空间大小少为255。2.证明DES的解密变换是加密变换的逆。证明：定义T是把64位数据左右两半交换位置的操作，即T(L,R)=(R,L)，则T2(L,R)=(L,R)，即T2=I，其中I为恒等变换。定义DES中第i轮的主要运算为fi，即()11111(,)(,),iiiiiiifLRLFRKR−−−−−=⊕则有，()()211111111111111(,)(,),((,),)((,))(,),(,)iiiiiiiiiiiiiiiiiiiifLRLFRKRfLFRKRLFRKFRKRLR−−−−−−−−−−−−−−=⊕=⊕=⊕⊕=即2ifI=。DES的加密为：()()116151()()cDESmIPfTfTfIPm−==⋅⋅⋅⋅⋅⋅⋅L…(*)解密为：()()111216()()DEScIPfTfTfIPc−−=⋅⋅⋅⋅⋅⋅⋅L…(#)把(*)式代入(#)式，可得1(())DESDESmm−=，由此可知DES的解密变换是加密变换的逆。3.在DES的ECB模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C1中的一个错误明显地将影响到P1和P2的结果。(1)P2后的分组是否受到影响?(2)设加密前的明文分组P1中有1比特的错误，问这一错误将在多少个密文分组中传播?对接收者产生什么影响?解：CBC的加密：C0=IV,Ci=DESK[Pi⊕Ci-1],i≥2解密：Pi=DESK-1[Ci]⊕Ci-1,i≥1(1)如果解密过程中C1有错误，由于P2=DESK-1[C2]⊕C1，所以P2将受到影响；但是当i≥3时，Pi=DESK-1[Ci]⊕Ci-1，与C1无关，因此Pi≥3不会受到影响。(2)加密前P1有错误，则加密后C1也是错误的；由于Ci=DESK[Pi⊕Ci-1],i≥2，因此Ci≥2也都是错误的，即P1中这一个比特的错误会在加密过程中传递到每一个密文分组。由加密和解密的方式可知，如果密文Ci在从发送者到接收者的传递过程中没有改变（出错），那么密文解密后必然等于加密时输入的明文。因此对于接收者来说，由于加密前的明文分组P1中有l比特的错误，那CBC模式示意图NCUT密码学–习题与答案2010第5页么解密后的P1跟加密前一样，同样有一个比特的错误，而对于Ci≥2能够解密得到无错误的明文。4.在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远。解：该错误将传播到后面的(64+8-1)/8=8⎢⎥⎣⎦个单元，共9个单元解密得到错误的明文。CFB模式示意NCUT密码学–习题与答案2010第6页四、公钥密码1.3.用Fermat定理求3201mod11。解：对于模运算，有结论(a×b)modn=[(amodn)×(bmodn)]modn由Fermat定理，可知310≡1mod11，因此有(310)k≡1mod11所以3201mod11=[(310)20×3]mod11=[((310)20mod11)×(3mod11)]mod11=3。4.用推广的Euclid算法求67mod119的逆元。解：qguv~11910~67011521-1115-12374-721-916(注：1=119×(-9)+67×16)所以67-1mod119=165.求gcd(4655,12075)。解：12075=2×4655+27654655=1×2765+18902765=1×1890+8751890=2×875+140875=6×140+35140=4×35+0所以gcd(4655,12075)=35。6.求解下列同余方程组2mod31mod51