密码学两次作业题及答案.doc

作业1
一、名次解释
1、DES的弱密钥 2、素根 3、本原多项式
解：1、DES算法在每次迭代时都有一个子密钥供加密用。如果对于给定初始密钥k,它生成的各轮子密钥都相同，即有 就称该密钥k为弱密钥。
2、如果a的阶m等于，则称a为n的本原根（或称素根）。
3、设，称m为n次多项式的阶，阶为 的不可化约多项式称为本原多项式。
二、已知仿射密码的加密方法为：C=EK(m)=(am+b) mod 26，其中秘钥K=(a,b)=(7, 3) ，求密文0, 23, 6对应的明文。
解：因mod 26=15，解密函数=15(c-3) mod 26=(15c-19) mod 26，
则 c=0时，=-19 mod 26=7,
c=23时，=(1523-19) mod 26=14，
c=6时，=(156-19) mod 26=19。
三、计算319935 mod 77
解：因77=711，且7和11都为素数，则，又3和77互素，则由欧拉定理有，
再有3mod77=3, mod77=9, mod77=mod77=4, mod77=mod77=16,
故
=
=(139416) mod 77=34.
四、在AES分组密码中，涉及到有限域GF(28)上的乘法运算。即取不可化约多项式,为GF(28)上的多项式，定义为:,若，，求。
解：
=
= =。
五、已知背包公钥密码系统的超递增序列为（2，9，21，45，103），乘数ω＝29，模数m＝229，设用户要加密的明文为：10111，11100，01011，求其密文，并对密文解密，解密出明文。（）
解：先计算公钥： ，
229=58 mod 229, 929=32 mod 229, 2129=151 mod 229,
4529=160 mod 229, 10329=10 mod 229,
故公钥为（58，32，151，160，10），
加密10111：c=（58+151+160+10）mod 229=150,
加密11100：c=（58+32+151）mod 229=12,
加密01011：c=（32+160+10）mod 229=202,
解密时，由
有 ,
故 c=150时，（79150）mod 229=171=2+21+45+103,对应明文为10111，
c=12时，（7912）mod 229=32=2+9+21,对应明文为11100，
c=202时，（79202）mod 229=157=9+45+103,对应明文为01011。
作业2
1、判断方程是否有解？如果有解，求出其中的一个解。
解：＝ ＝＝＝（－1）（－1）＝1
所以原方程有解。又383 mod 4＝3，所以它的一个根是＝224
另外383－224＝159也是它的一个根。

2、将836483分解成素数的乘积
解： ，而不是整数
，而不是整数
，而不是整数
，而
所以：＝997×839
3、设数据库中某条记录含有以下四个字段：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）解联立同余式：

M＝11×19×23×29＝139403
，，

下面求，解得
y1＝1， y2=13 y3=2 y4=4，
所以＝1381024 mod 139403126397
（2）
（3）若令，则＝138519
4、已知椭圆曲线E：y2＝x3－4x－3(mod 7), 上有一点p（－2，2），求点2p，4p和6p的坐标。
解:（1）求
＝＝＝ 2 ＝＝1
＝＝6
所以
（2）求
＝＝＝ 4
＝＝0
＝＝5
所以4p＝（0，5）
(3）
＝＝1
＝＝0
＝＝2
所以 6p=(0，2)。
5、设有一个如图所示的基于LFSR的加密系统，请回答下列问题：

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）递推关系式： ，k>3
特征多项式：
（2）由 ，有c=mk=(110) (101)=011，
此时LFSR状态=100,
(3)， ，
（4）由于多项式，且不存在m<7，使得， 故 的阶是7。另外的不可约性由x,x+1, 都不能被整除得以验证，所以是一个本原多项式，故以其为特征多项式的该LFSR的周期为 。