密码学习题解.doc

习题2.1 设英文字母A, B, C, , Z分别编码伪0, 1, 2, 3, , 25。已知单表加密变换为 c5m7（mod 26）其中m表示明文，c表示密文。试对明文HELPME加密。解. 明文 H E L P M E对应的编码值分别是 7 4 11 15 12 4。 用加密变换将上述6个编码值分别加密并转换为字母是c577 （mod 26）16 Qc547 （mod 26）1 Bc5117 （mod 26）10 Kc5157 （mod 26）4 Ec5127 （mod 26）15 Pc547 （mod 26）1 B从而得到密文QBKEPB。习题2.2 设英文字母A, B, C, , Z分别编码伪0, 1, 2, 3, , 25。已知单表加密变换为 c11m2（mod 26）其中m表示明文，c表示密文。试对密文VMWZ解密。解. 首先从加密变换求出解密变换m111（c2）（mod 26）19（c2）（mod 26） 其中19111（mod 26）。其次将密文字母转换为编码值V M W Z 21 12 22 25。最后用解密变换将上述4个编码值分别解密并转换为字母是m19(212) （mod 26）23 Xm19(122) （mod 26）8 Im19(222)（mod 26）16 Qm19(252)（mod 26）21 V从而得到明文XIQV。习题2.5 设英文字母A, B, C, , Z分别编码伪0, 1, 2, 3, , 25。已知Hill密码中的明文分组长度为2，密钥K是Z26上的一个2阶可逆方阵。假设明文Friday所对应的密文为pqcfku，试求密钥K。 解. 明文 f r i d a y对应的编码值分别是 5 17 8 3 0 24。密文 p q c f k u对应的编码值分别是 15 16 2 5 10 20。设加密变换为CMK，则可取，从而得到。如果矩阵M可逆，就可求得。事实上，|M|53817136 9 （mod 26），且913（mod 26）， 从而。从而可求得密钥。注：(1)矩阵M的逆矩阵也可通过初等置换可求得：(2)矩阵K也可通过待定系数法可求得：设 ，则 ，即从 ，所以解得从，所以解得取，则有和，类似以上解法可得和于是可得或或或经检验得到一个解。再类似，的情形。习题4.0 根据电子教案画出DES解密算法的流程图（注意：输入是密文，输出是明文）。密文C解：流程图如下：初始置换IPL0R0K16fK15R1=L0f(R0,K16)L1fK1R15=L14f(R14,K2)L15fL16R16=L15f(R15,K1)逆初始置换IP1明文m习题4.1 求出用DES的8个S盒将48比特串70a990f5fc36压缩置换输出的32比特串（用16进制写出每个S盒的输出）。解：比特串70a990f5fc36用二进制表示为011100 001010 100110 010000 111101 011111 110000 110110，每6比特一组共8组，分别用8个S盒变换如下：S1(011100)S1(00,1110)S1(0,14)000000；S2(001010)S2(00,0101)S2(0,5)111011=b；S3(100110)S3(10,0011)S3(2,3)910019；S4(010000)S4(00,1000)S4(0,8)100011；S5(111101)S5(11,1110)S5(3,14)501015；S6(011111)S6(01,1111)S6(1,15)810008；S7(110000)S7(10, 1000)S7(2,8)101010a；S8(110110)S8(10,1011)S8(2,11)131101d，故8个S盒的输出为 00001011 10010001 01011000 10101101即 0b9158ad。习题4.2 设F28的不可约多项式为x8+ x4+x3+ x+1。写出F28中二进制表示的元素10011111和01010111的多项式表示，并求多项式乘法（10011111）（01010111）。解：10011111表示的多项式是 x7+ x4+x3+x2+ x+1。01010111表示的多项式是 x6+ x4+x2+ x+1。因为： x8+ x4+x3+ x+1的向量表示是100011011，又1 0 0 1 1 1 1 10 1 0 1 0 1 1 11 0 0 1 1 1 1 11 0 0 1 1 1 1 11 0 0 1 1 1 1 11 0 0 1 1 1 1 11 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 11 0 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 11 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 所以（10011111）（01010111）00001111。习题4.3 设mb5c9179eb1cc1199b9c51b92b5c8159d。对m使用AES中的字节替换运算SubBytes，即求出SubBytes(m)的输出（用16进制表示）。解：查AES的SubBytes表分别得到：SubBytes(b5)d5; SubBytes(c9)dd; SubBytes(17)f0; SubBytes(9e)0b; SubBytes(b1)c8; SubBytes(cc)4b;SubBytes(11)82; SubBytes(99)ee; SubBytes(b9)56; SubBytes(c5)a6; SubBytes(1b)af; SubBytes(92)4f;SubBytes(b5)d5; SubBytes(c8)e8; SubBytes(15)59; SubBytes(9d)5e。故SubBytes(m)d5ddf00bc84b82ee56a6af4fd5e8595e。习题5.0 计算57和93的最大公约数(57,93),并找出整数s和t，使得57s93t(57,93)。解： 用Euclidean算法。9315736，5713621，3612115，211156，15263，6230，逆推得到：31526152（21115）3152213（36121）2213365213365（57136）8365578（93157）5578931357，故得到57和93的最大公约数(57,93)3；s13，t8使得(57,93)93t57s89313573。习题5.1 利用扩展Euclidean算法计算如下乘法逆：（1） 171 mod 101，（2） 3571 mod 1234。解：（1）10151716 171161逆推得到：117116 171（101517） 6171101，故得到171 mod 1016。（2） 123433571633572163311635318313878171逆推得到：1817 81（3138）48131 4（163531416321（3572163）4616321357 46（12343357）21357 461234159357，故得到3571 mod 1234159 mod 12341075。 习题5.2 设p43，q59，npq2537。设公钥(n, e)(2537,13),（1） 求私钥(p, q, d)。（2） 利用英文字母表的顺序：a为01，b为02，y为24，z为25，求出用上述参数对明文public 使用RSA加密的密文。解：（1）f(n)42382436。用Euclidean算法可求得de1 mod f(n)131 mod 2436937，故私钥(p, q, d)(43, 59, 937)。（2） 将明文public分块为：pu bl ic，对应编码为 1520 0111 0802。分别加密得到： 152013 mod 25370095，11113 mod 2537164880213 mod 25371410，即，对明文public 使用RSA加密的密文是0095 1648 1410。另外，若将明文public分块为：p u b l i c，对应编码为 15 20 01 11 08 02。分别加密得到： 1513 mod 25372116，2013 mod 25370793，0113 mod 25370001，1113 mod 25370821，0813 mod 25370156，0213 mod 25370581，即，对明文public 使用RSA加密的密文是2116 0793 0001 0821 0156 0581。 注：用平方-乘算法计算上述结果。如 152013 mod 2537152017306 mod 2537152017773 mod 2537167217772 mod 253716721701 mod 25370095。又如 1513 mod 2537152256 mod 25371524223 mod 253781224222 mod 2537812540 mod 25372116。试计算0813 mod 2537。提供以下参数：64644096，155915592430481，8155912472，23243581340。0813 mod 25378646 mod 2537815593 mod 2537232415592 mod 2537232435 mod 25370156。习题5.3 设p11，E是由y2x3x6 （mod 11）所确定的有限域Z11上的椭圆曲线。设MenezesVabstone椭圆曲线密码体制中的a(2, 7)，解密私钥d7，试求（1）bda，（2）对明文x(10, 9)加密的密文，（3）将密文恢复成明文。解：（1）bda7(2, 7)(7, 2)。（2）随机选取数k12，分别计算y0ka12(2, 7)(2, 4)，(c1, c2)kb12(7, 2)84(2, 7)6(2, 7)(7, 9)，y1c1x1 mod p710 mod 114，y2c2x2 mod p99 mod 114。x(10, 9)加密的密文是y（y0, y1, y2）=（(2, 4), 4, 4）。（3）先计算(c1, c2)d y07(2, 4)712(2, 7)6(2, 7)(7, 9)，故有x（y1c11 mod p， y2c21 mod p）（471 mod 11， 491 mod 11）（48 mod 11， 45 mod 11）（10，9）。再解：（1）bda7(2, 7)(7, 2)。（2）随机选取数k6，分别计算y0ka6(2, 7)(7, 9)，(c1, c2)kb6(7, 2)42