密码学复习题答案

密码学复习题答案

二、计算题（要求有具体过程）

1、计算319935 mod 77

2、判断方程 2 3mod383是否有解？如果有解，求出其中的一个解。

3、将836483分解成素数的乘积

1．解：由n 11 7得 (n) 10 6 60

由欧拉定理a (n) 1modn知： 319935mod77

＝3332 60 15mod77

3mod77 ＝1

＝34

3 1383 1383 3 22( 1)() 2、解： ＝ 3 383 15

＝( 1)(

所以原方程有解。 383 2 )＝( 1) ＝（－1）（－1）＝1 3 3

383 1

4又383 mod 4＝3，所以它的一个根是3mod383＝224

另外383－224＝159也是它的一个根。

3

、解： 914 915 836483

742不是整数 2

9162 836483

2573

9172 836483

4406

9182 836483

6241 792 所以：836483 918 79 (918 79)(918 79)＝997×839

22

密码学复习题答案

三．叙述RSA公钥密码的加密和解密算法，并证明其有效性。给出利用RSA进行数字签名的协议。

四、在AES分组密码中，涉及到有限域GF(28)上的乘法运算。即取不可化约多

项式m(x) 8x 4x 3x x 1,a(x)和b(x)为GF(28)上的多项式，a(x) b(x)定义为:

a(x) b(x)＝a(x)b(x)modm(x),若a(x) x6 x4 x2 x 1，b(x) x4 1，

b(x)。 求a(x)

解： a(x)b(x) x10 x8 x5 x2 x 1

a(x) b(x) x6 x4

五、已知背包公钥密码系统的超递增序列为 (2，3，6，13，27，52)

模数m=105，ω=31，设用户要加密的明文为：011000，求其密文，并对解密解密出明文。

解：解：先计算公钥：ai=biω mod m，i=1,2,3,…,6,

2×31≡62 mod 105, 3×31≡93 mod 105,

6×31≡81 mod 105, 13×31≡88 mod 105,

27×31≡102 mod 105, 52×31≡37 mod 105,

明文011000对应的密文为： c a1m1 a2m2 a6m6 modm

93 81 mod105 69

解密过程：

首先计算ω=31模105的乘法逆元ω-1=61,即：

31×61≡ 1 mod 105

由 1c 1a1m1 1a2m2 1anmnmodm

b1m1 b2m2 bnmn modm

得

（69×61）mod 105=9=3+6

所以69对应的明文为011000

六、设p＝151，q＝223，n＝p×q＝33673， p≡q ≡3 mod 4，设明文m＝31280，

密码学复习题答案

试对其进行加密，并对解密解密出明文m。

解：加密：

c≡m2 mod n，即

c＝(31280)2 mod 33673＝2039

解密：先计算出：

r1=c(p+1)/4=203938 mod 151=128

r2=p-r1=151-128=23

s1=c(q+1)/4=203956 mod 223=60

s2=q-s1=223-60=163

下面利用中国剩余定理分别求解以下四个联立同余式：

z 128mod151 z 128mod151 z 23mod151 z 23mod151 z 60mod 223 z 163mod223 z 60mod223 z 163mod223

利用中国剩余定理可得它们的解分别为：

24590，2393，31280 和 9083。

真正的明文31280 在上述四个解中

七、已知椭圆曲线E：y2＝x3－4x－3(mod 7), 上有一点p（－2，2），求点2p，4p和6p的坐标。

解:1）求2p

3x12 a4 mod7 2y1

3 ( 2)2 4mod7＝(8 4 1)mod7＝ 2 ＝2 2

x3 ( 2 2x1)mod7＝(22 2 ( 2))mod7＝1

y3 [ (x1 x3) y1]mod7＝[2( 2 1) 2]mod7＝6 所以2p (1,6)

2）求4p 2p 2p

密码学复习题答案

3x12 a4 mod7 2y1

3 (1)2 4mod7＝( 1 5 1)mod7＝ 4 ＝2 6

x3 ( 2 2x1)mod7＝(42 2 1)mod7＝0

y3 [ (x1 x3) y1]mod7＝[4(1 0) 6]mod7＝5

所以4p＝（0，5）

3）6p 2p 4p＝（0，2）

八. 设有一个如图所示的基于LFSR的加密系统，请回答下列问题：

明文

1）写出该LFSR的递推关系式和特征多项式pn(x)；

2）若该LFSR初始状态（t＝0）为（a3a2a1）=(101)，LFSR的输出作为密钥，明文

m＝110，求对应的密文c和这时LFSR的状态；

3) 利用特征多项式判断该LFSR的周期是多少？为什么？