密码学基础2010题答案暨评分标准

A卷北京科技大学2010—2011学年度第一学期《密码学基础》试题答案及评分标准(注：此答案及评分标准应于评阅试卷一同存档)一、（10分）已知密文dgsddob使用的是凯撒加密，试解密（提示：明文为有意义的英文）。答：原文：dgsddob移动1位：cfrccna（1分）移动2位：beqbbmz（1分）移动3位：adpaaly（1分）移动4位：zcozzkx（1分）移动5位：ybnyyjw(1分）移动6位：xamxxiv（1分）移动7位：wzlwwhu（1分）移动8位：vykvvgt(1分）移动9位：uxjuufs（1分）移动10位：twitter（明文1分）二、（10分）playfair加密，密钥为DEATH,试给出其加密矩阵，并将LaboulayeLady加密，取填充字符为Q答：加密矩阵（2分）先填充为LA,BO,UL,AY,EL,AD,YQ(1分)加密LAMEBOIKULQOAYTXELCQADTEYQWS（每对1分）密文为MEIKQOTXCQADYQWS（1分）三、（15分）已知所用的密码体系为Hill密码（m=3），加密矩阵为DDEEAATTHHBBCCFFGGII//JJKKLLMMNNOOPPQQRRSSUVVWWXXYYZZ39201315725613K求明文ART的密文？（2）求出解密矩阵（3）计算出密文QPR对应明文.（注：文字编码A为0，B为1，以此类推，Z为25）解：（1）明文ART对应编码[0,17,19]TM（1分）密文编码3920053313131571738824(mod26)256131934911CKMK（3分）对应密文为NYL（1分）（2）39201315725613K*1533237233236461239675(mod26)2972077215256Kdet()54277(mod26)K17(mod26)15(mod26)123323719715675(mod26)12123(mod26)15256171112K(5分)（3）密文CVX对应编码[16,15,17]TC（1分）明文编码17197165162212123155980(mod26)1711121764117MKC（3分）对应明文为WAR（1分）（注1：若计算逆阵个别数字出错，使用错误的逆阵求解（3），计算结果视为正确答案给分，但扣一分,）四、（10分）使用Shank算法求231(mod41)x，已知2031(mod41)解：314114025p3e5q(2分)已知2031(mod41)所以3f，533(mod41)qgf（2分）50311(mod41)qba（2分）2(1)1(mod41)1m（2分）2410(1)(3)811(mod41)embbg（1分）4k1322231(3)25920(mod41)qkxag（1分）五、（10分）计算出AES算法中GF(28)中两个多项式‘B3’和‘E4’的加法和‘B3’+‘E4’以及乘法积‘B3’.‘E4’，并给出结果对应的多项式表达式。（注：乘法模多项式为8431xxxx）解：'3''4'101100111110010001010111'57'BE（2分）对应多项式为6421xxxx（2分）75476521413129121110711109687637652141387653265876532654376'3''4'10110011111001001(1)(1)1BExxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1086426425322435(mod())(mod())(1)1(mod())(mo(1)1d)xxmxmxxxxxxxxxxxxxxmxxxmx2'3''4'(00100000)'20'BE，对应多项式为5x（6分）六、（10分）解密超递增背包序列，已知公开序列为（7，21，35，30，20），密文对应数值为38，使用此方法试解出明文对应二进制串。解：(7,21,35,30,20)B前三者均是7的倍数，可取7t,则(1,3,5,,)Axy,其中,xy需满足1359,1359xyxx且730(mod),720(mod)xkyk其中135kxy,取10,20,40xyk满足要求，则(1,3,5,10,20)A,7,40tk，(6分)对应数值38，738(mod40)z34(mod40)z342051x34-20=141041x14-10=4530x4321x4-3=111x(2分)明文对应二进制串1,1,0,1,1x（2分）七、（10分）设某4级线性移位寄存器的的特征多项式为431xx，画出此线性移位寄存器的示意图，若其初始状态为1234,,,(1,0,0,0)aaaa，写出其输出序列并判断输出序列的周期解：（图2分）初始状态为1234(,,,)(1,0,0,0)aaaa则输出序列如下1000100110101111000（7分）1000000100100100100100110110110110100101101101111111111011001000（7分）周期为15（1分）八、(15分)（1）RSA加密体制中37p，41q，7e，使用扩展欧几里德算法计算出解密指数d（需要详细过程）（2）使用快速RSA计算明文512的加密密文,计算密文1414对应的明文（给出详细过程）解：（1）43p，59q，1517npq，()(1)(1)1440npq1440205757525221所以15225327144036177所以17617823(mod1440)（2分）（2）先求解1(mod)puq41374q37941所以13794103794110(mod41)u（1分）加密512，7733151266366(1)6(mod37)c（2分）77332512202040020(10)200008(mod41)c（2分）8610mod41376746c（2分）解密1414，8233115157731141488648272167293126806676m329*10290*10031*2680629（2分）2311115823225220204002031620961518903248(4114)4m8161285(mod41)（2分）5412910mod41372963729251m（2分）九、(10分)简述MD5算法的流程（注：不用叙述各逻辑函数的定义）答：MD5是R.Rivest在MIT开发研究的Hash函数输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位，对明文输入按512bit分组，最后要填充使其成为512bit的整数倍，且最后一组的后64bit用来表示消息长在mod264下的值K，故填充位数为1～512bit，填充数字图样为(100…0)，得Y0,Y1,…，YL-1。每轮输出为128bit，可用下述4个32bits字表示：A，B，C，D。•HMD5的运算，对512bit(16-字)组进行运算，Yq表示输入的第q组512bit数据，在各轮中参加运算。T[1,…,64]为64个元素表，分四组参与不同轮的计算。T[i]为232×abs(Sine(i))的整数部分，i是弧度。T[i]可用32bit二元数表示，T是32bit随机数源。MD5是四轮运算，各轮逻辑函数不同。每轮又要进行16步迭代运算，4轮共需64步完成。每步完成ab＋CLSS(a＋g(B,C,D)＋X[k]＋T[i])其中a,b,c,d=缓存器中的四个字，按特定次序变化。g=基本逻辑函数F,G,H,I中之一，算法的每一轮用其中之一。B卷北京科技大学2009—2010学年度第一学期《密码学基础》试题答案及评分标准(注：此答案及评分标准应于评阅试卷一同存档)三、一、（10分）（15分）已知所用的密码体系为Hill密码（m=3），加密矩阵为39201315725613K求明文ART的密文？（2）求出解密矩阵（3）计算出密文QPR对应明文.（注：文字编码A为0，B为1，以此类推，Z为25）解：（1）明文ART对应编码[0,17,19]TM（1分）密文编码3920053313131571738824(mod26)256131934911CKMK（3分）对应密文为NYL（1分）（2）39201315725613K*1533237233236461239675(mod26)2972077215256Kdet()54277(mod26)K17(mod26)15(mod26)123323719715675(mod26)12123(mod26)15256171112K(5分)（3）密文CVX对应编码[16,15,17]TC（1分）明文编码17197165162212123155980(mod26)1711121764117MKC（3分）对应明文为WAR（1分）（注1：若计算逆阵出错，使用错误的逆阵求解（3），计算结果视为正确答案给分，但扣一分）二、（10分）设某4级线性移位寄存器的的特征多项式为431xx，画出此线性移位寄存器的示意图，若其初始状态为1234,,,(1,0,0,0)aaaa，写出其输出序列并判断输出序列的周期解：解：（图2分）初始状态为1234(,,,)(1,0,0,0)aaaa则输出序列如下1000100110101111000（7分）1000000100100100100100110110110110100101101101111111111011001000（7分）周期为15（1分）三、计算出AES算法中GF(28)中两个多项式‘B3’和‘E4’的加法和‘B3’+‘E4’以及乘法积‘B3’.‘E4’，并给出结果对应的多项式表达式。（注：乘法模多项式为8431xxxx）解：'3''4'101100111110010001010111'57'BE（2分）对应多项式为6421xxxx（2分）75476521413129121110711109687637652141387653265876532654376'3''4'10110011111001001(1)(1)1BExxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx