密码学第五版部分课后答案

2.4已知下面的密文由单表代换算法产生：请将它破译。提示：1、正如你所知，英文中最常见的字母是e。因此，密文第一个或第二个（或许第三个）出现频率最高的字符应该代表e。此外，e经常成对出现（如meet,fleet,speed,seen,been,agree,等等）。找出代表e的字符，并首先将它译出来。2、英文中最常见的单词是“the”。利用这个事实猜出什么字母t和h。3、根据已经得到的结果破译其他部分。解：由题意分析：“8”出现次数最多，对应明文为“e”，“；48”代表的明文为“the”，“）”、“*”、“5”出现频率都比较高，分别对应“s”、“n”、“a”，由此破译出密文对应的明文为：AgoodglassintheBishop’shostelintheDevil’sseat-twenty-onedegreesandthirteenminutes-northeastandbynorth-mainbranchseventhlimbeastside-shootfromthelefteyeofthedeath’shead-abeelinefromthetreethroughtheshotfiftyfeetout.2.20在多罗的怪诞小说中，有一个故事是这样的：地主彼得遇到了下图所示的消息，他找到了密钥，是一段整数：7876565434321123434565678788787656543432112343456567878878765654343211234a.破译这段消息。提示：最大的整数是什么？b.如果只知道算法而不知道密钥，这种加密方案的安全性怎么样？c.如果只知道密钥而不知道算法，这种加密方案的安全性又怎么样？解：A.根据提示，将密文排成每行8字母的矩阵，密钥代表矩阵中每行应取的字母，依次取相应字母即可得明文。明文为：Hesittethbetweenthecherubims.Theislesmaybegladthereof.AstheriversintheSouth.B.安全性很好。若密文的字母数为8n，则共有8n种可能的密钥，不易攻破。C.安全性较差。将字母总数与密钥总数相除，得每组8个字母，即可破译。3.8这个问题给出了用一轮DES加密的具体数字的例子。假设明文和密钥K有相同的位模式，即：用十六进制表示：0123456789ABCDEF用二进制表示：0000000100100011010001010110011110001001101010111100110111101111a.推导第一轮的子密钥解：经过表3.4（b）PC-1置换，得：C0：1111000011001100101010100000D0：1010101011001100111100000000经过表3.4（d）左移，得：C1’：1010000110011001010101000001D1’：0101010110011001111000000001经过表3.4（c）置换选择，得：K1：000010110000001001100111100110110100100110100101用十进制表示为：0B02679B49A5b.推导L0，R0解：经过表3.2（a）置换，得L0：11001100000000001100110011111111R0：11110000101010101111000010101010c.扩展R0求E（R0）解：根据表3.2（C）扩充置换，得：E(R0)=01110100001010101010101011110100001010101010101d.计算A=E(R0)K1解：根据a、c可得A=011100010001011100110010111000010101110011110000e.把（d）的48位结果分成6位（数据）的集合并求对应S盒代换的值解：根据表3.3S盒代换得(1110)=(14)=0(10进制)=0000(2进制)(1000)=(8)=12(10进制)=1100(2进制)(1110)=(14)=2(10进制)=0010(2进制)(1001)=(9)=1(10进制)=0001(2进制)(1100)=(12)=6(10进制)=0110(2进制)(1010)=(10)=13(10进制)=1101(2进制)(1001)=(9)=5(10进制)=0101(2进制)(1000)=(8)=0(10进制)=0000(2进制)f.利用（e）的结论来求32位的结果B解：B=00001100001000010110110101010000g.利用置换求P(B)解：根据表3.2（d），得P(B)=10010010000111000010000010011100h.计算R1=P(B)L0解：R1=01011110000111001110110001100011i.写出密文解：L1=R0，连接L1、R1可得密文为：MEYE823.1216个密钥（K1、K2……K16）在DSE解密过程中是逆序使用的。因此，图3.5的右半部分不再正确。请模仿表3.4（d）为解密过程设计一个合适的密钥移位扩展方案。解：选代轮数12345678910111213141516移位次数01222222122222213.10（a）解：T16(L15||R15)=L16||R16T17(L16||R16)=R16||L16IP[IP–1(R16||L16)]=R16||L16TD1(R16||L16)=L16||R16f(L16,K16)=R15||L15f(R15,K16)f(R15,K16)=R15||L15（b）解：T16(L15||R15)=L16||R16IP[IP–1(L16||R16)]=L16||R16TD1(R16||L16)=R16||L16f(R16,K16)=L15f(R15,K16)||R15f(R16,K16)≠L15||R153.15For1≤i≤128,takeci{0,1}128tobethestringcontaininga1inpositioniandthenzeroselsewhere.Obtainthedecryptionofthese128ciphertexts.Letm1,m2,...,m128bethecorrespondingplaintexts.Now,givenanyciphertextcwhichdoesnotconsistofallzeros,thereisauniquenonemptysubsetoftheci’swhichwecanXORtogethertoobtainc.LetI(c){1,2,...,128}denotethissubset.Observec=ÅiÎIc()ci=ÅiÎIc()Emi()=EÅiÎIc()miæèçöø÷Thus,weobtaintheplaintextofcbycomputingiÎIc()mi.Let0betheall-zerostring.Notethat0=00.FromthisweobtainE(0)=E(00)=E(0)E(0)=0.Thus,theplaintextofc=0ism=0.Hencewecandecrypteveryc{0,1}128.4.15a.gcd(24140,16762)=gcd(16762,7378)=gcd(7378,2006)=gcd(2006,1360)=gcd(1360,646)=gcd(646,68)=gcd(68,34)=gcd(34,0)=34b.gcd(4655,12075)=gcd(12075,4655)=gcd(4655,2765)=gcd(2765,1890)=gcd(1890,875)=gcd(875,140)=gcd(140,35)=gcd(35,0)=354.17a.Euclid:gcd(2152,764)=gcd(764,624)=gcd(624,140)=gcd(140,64)=gcd(64,12)=gcd(12,4)=gcd(4,0)=4Stein:A1=2152,B1=764,C1=1;A2=1076,B2=382,C2=2;A3=538,B3=191,C3=4;A4=269,B4=191,C4=4;A5=78,B5=191,C5=4;A6=39,B6=191,C6=4;A7=152,B7=39,C7=4;A8=76,B8=39,C8=4;A9=38,B9=39,C9=4;A10=19,B10=39,C10=4;A11=20,B11=19,C11=4;A12=10,B12=19,C12=4;A13=5,B13=19,C13=4;A14=14,B14=5,C14=4;A15=7,B15=5,C15=4;A16=2,B16=5,C16=4;A17=1,B17=5,C17=4;A18=4,B18=1,C18=4;A19=2,B19=1,C19=4;A20=1,B20=1,C20=4;故gcd(2152,764)=1´4=4b.在每一步算法中，Euclid算法所进行的除法运算比较复杂，而Stein算法只需完成除以2、相等、求差或取最小值的简单运算，减小了运算复杂度。4.23a.9x2+7x+7b.5x3+7x2+2x+64.25a.1b.1c.x+1d.x+787.2因为Xn+1=(aXn)mod24，易知若a为偶数，则经过n轮之后Xn+1必恒等于0，故a必为奇数。且a16,分别取a=3,5,7,9,11,13,15，得：a=3,则Xn=1,3,9,11,1,3，……或Xn=5,15,13,7,5,15，……a=5,则Xn=1,5,9,13,1,5，……或Xn=3,15,11,7,3,15，……a=7,则Xn=1,7,1……舍去a=9,则Xn=1,9,1……舍去a=11,则Xn=1,11,9,3,1,11，……或Xn=5,7,13,15,5,7，……a=13,则Xn=1,13,9,5,1,13，……或Xn=3,7,11,15,3,7，……故：（a）最大周期为4（b）a=3或5或11或13（c）与a必为奇数同理，种子必须为奇数。7.4两个发生器产生的伪随机数分别为：1,6,10,8,9,2,12,7,3,5,4,11,1,...1,7,10,5,9,11,12,6,3,8,4,2,1,...从中可以看出，第二个发生器产生的伪随机数存在一部分Xn+1=2Xn的现象，所以第一个伪随机数发生器的随机性更好一些。8.5a==9794mod73==12而0a72,73为素数，故取a=128.8因为φ(35)=24，x^φ(35)==1mod35所以x^85mod35=(((x^24mod35)^3)*(x^12mod35)*(xmod35))mod35=(((x^12mod35)*(xmod35))mod35又因为x^24mod35=1所以x^12mod35=1或-1所以x^85mod35=xmod35或-xmod35=6故x=6或x=29,代入验证得x=69.3因为n=35所以35)=24因为35);e=5所以d=5所以M=Cdmodn=59.5不安全因为在已知n的情况下易知n)，根据密钥产生原则：（1）选择e使其与n)互素且小于n)（2）确定d使得de==1(modn))且dn)可以得出e、d的可能值，再通过进一步观察即可求出e和d，特别是在n很小的情况下，只需通过简单的计算就可以破解密钥。8.21离散对数表如下图所示：a1234567891011121314Log2,29(a)248163112241991871428a1516171819202122232425262728Log2,29(a)27252113262317510201122156B.因为17x2==10（mod29）所以[dlog2,29(17)+2dlog2,29(x)](mod28)==23[21+2log2,29(x)](mod28)==23所以21+2log2,29(x)=23或21+2log2,29(x)