密码学两次作业题及答案

作业1一、名次解释1、DES的弱密钥2、素根3、本原多项式解：1、DES算法在每次迭代时都有一个子密钥供加密用。如果对于给定初始密钥k,它生成的各轮子密钥都相同，即有1216,kkk就称该密钥k为弱密钥。2、如果a的阶m等于n，则称a为n的本原根（或称素根）。3、设min|1lnmlpxx整除，称m为n次多项式npx的阶，阶为21n的不可化约多项式称为本原多项式。二、已知仿射密码的加密方法为：C=EK(m)=(am+b)mod26，其中秘钥K=(a,b)=(7,3)，求密文0,23,6对应的明文。解：因-17mod26=15，解密函数kmDc=15(c-3)mod26=(15c-19)mod26，则c=0时，0kmD=-19mod26=7,c=23时，23kmD=(1523-19)mod26=14，c=6时，6kmD=(156-19)mod26=19。三、计算319935mod77解：因77=711，且7和11都为素数，则77=711=7-111-1=60，又3和77互素，则由欧拉定理有77603=3=1mod77，再有3mod77=3,23mod77=9,43mod77=29mod77=4,83mod77=24mod77=16,故33219935602483mod7733333mod77=332602483mod773mod773mod773mod773mod77mod77=(139416)mod77=34.四、在AES分组密码中，涉及到有限域GF(28)上的乘法运算。即取不可化约多项式843()1mxxxxx,()()axbx和为GF(28)上的多项式，()()axbx定义为:()()()()mod()axbxaxbxmx＝,若642()1axxxxx，4()1bxx，求()()axbx。解：()()()()mod()axbxaxbxmx＝=64248431+1mod1xxxxxxxxx=108528431mod1xxxxxxxxx=64xx。五、已知背包公钥密码系统的超递增序列为（2，9，21，45，103），乘数ω＝29，模数m＝229，设用户要加密的明文为：10111，11100，01011，求其密文，并对密文解密，解密出明文。（179）解：先计算公钥：mod,1,2,3,4,5iiabwmi，229=58mod229,929=32mod229,2129=151mod229,4529=160mod229,10329=10mod229,故公钥为（58，32，151，160，10），加密10111：c=（58+151+160+10）mod229=150,加密11100：c=（58+32+151）mod229=12,加密01011：c=（32+160+10）mod229=202,解密时，由11122334455()modmwcbmbmbmbmbm有1234579(292145103)mod229cbbbbb,故c=150时，（79150）mod229=171=2+21+45+103,对应明文为10111，c=12时，（7912）mod229=32=2+9+21,对应明文为11100，c=202时，（79202）mod229=157=9+45+103,对应明文为01011。作业21、判断方程383mod32是否有解？如果有解，求出其中的一个解。解：3383＝31383122383(1)()3＝383(1)()3＝2(1)3＝（－1）（－1）＝1所以原方程有解。又383mod4＝3，所以它的一个根是383143mod383＝224另外383－224＝159也是它的一个根。2、将836483分解成素数的乘积解：836483914，2915836483742，而742不是整数29168364832573，而2573不是整数29178364834406，而4406不是整数29188364836241，而2624179所以：2283648391879(91879)(91879)＝997×8393、设数据库中某条记录含有以下四个字段：f1＝（0111）2＝7，f2＝（1001）2＝9，f3＝（1100）2＝12，f4＝（1111）2＝15。取四个素数p1＝11，p2＝19，p3＝23，p4＝29。试利用中国剩余定理对条记录进行加密，而个别字段可以独立解密，则：（1）求密文c；（2）由c求出f3；（3）若令f3＝13，则新的密文c‘是多少？解：（1）解联立同余式：7mod119mod1912mod2315mod29ccccM＝11×19×23×29＝139403119232912673M，21123297337M，31119296061M41119234807M下面求1modiiiyMp，解得y1＝1，y2=13y3=2y4=4，所以111222333444CyMfyMfyMfyMf＝1381024mod139403126397（2）3126397mod2312f（3）若令313f，则33[(1312)]mod139403ccyM＝1385194、已知椭圆曲线E：y2＝x3－4x－3(mod7),上有一点p（－2，2），求点2p，4p和6p的坐标。解:（1）求2p21413mod72xay＝23(2)4mod722＝1(84)mod7＝2231(2)mod7xx＝2(22(2))mod7＝13131[()]mod7yxxy＝[2(21)2]mod7＝6所以2(1,6)p（2）求422ppp23433mod72xay＝23(1)4mod726＝1(15)mod7＝4243(2)mod7xx＝2(421)mod7＝04343[()]mod7yxxy＝[4(10)6]mod7＝5所以4p＝（0，5）(3）624ppp4343mod7yyxx＝56mod701＝12534()mod7xxx＝2(110)mod7＝05353[()]mod7yxxy＝[1(10)6]mod7＝2所以6p=(0，2)。5、设有一个如图所示的基于LFSR的加密系统，请回答下列问题：a3a2a1密钥流明文密文1）写出该LFSR的递推关系式和特征多项式pn(x)；2）若该LFSR初始状态（t＝0）为（a3a2a1）=(101)，LFSR的输出作为密钥，明文m＝110，求对应的密文c和这时LFSR的状态；3）求q(x),使得pn(x)q(x)=x7+1;4)利用特征多项式判断该LFSR的周期是多少？为什么？解：（1）递推关系式：13kkkaaa，k3特征多项式：331pxxx（2）由iiicmk，有c=mk=(110)(101)=011，此时LFSR状态654aaa=100,(3)331pxxx，7342()(1)(1)1qxxxxxxx，（4）由于多项式73|1pxx，且不存在m7，使得3|1mpxx，故3()px的阶是7。另外3()px的不可约性由x,x+1,21xx都不能被3()px整除得以验证，所以3()px是一个本原多项式，故以其为特征多项式的该LFSR的周期为32-1=7。