所以4p = （1,6）
3/6
3） 6 p 2 p 4 p
=(y2-y1)/(x2-x1)
modp=6−2 mod7=4
1−0
������3 = (2 − ������1 − ������2)mod7 = (42 − 0 − 1)mod7 = 1,
������3 = （ （ ������1 − ������3） − ������1）modp = （4（0 − 1） − 2）mod7 = 1mod7 = (42 − 0 −
模数 m=105，ω=31，设用户要加密的明文为：011000，求其密文，并对其解密出明文
（ω=31 模 105 的乘法逆元ω-1=61）。
解：先计算公钥：ai=biω mod m，i=1,2,3,…,6,
2×31≡62 mod 105,
3×31≡93 mod 105,
6×31≡81 mod 105,
(2)
������2 ������2′
≡
������������������������ ������������������������′
≡
������ ������′
mod71
57 13
≡
30 ������′
mod71
57M′ ≡ 30 × 13mod71 M′ = 33
2/6
8、 (10 分)（1）椭圆曲线 E：y2＝x3－4x－3(mod 7)，求其上的所有点（0 ≤ x < 7，0 ≤
2、 (10 分)试说明 DES 解密算法，并证明其正确性。 答：DES 解密算法同 DES 的加密算法，但子密钥的选取次序正好与加密算法的变换相反k1‘ = k16 ， ⋯ ������1’ 6 = ������1。
DES 算法可以表示为：DES=IP−1������16������15 ⋯ ������1������������，其中 IP 为置换变换，T������（i=1,2，, 16） 为 16 轮迭代变换，IP−1为逆置换算法。
（1）如果接收方B 的公开钥是y������=3，发送方A 选择的随机整数k=2，求明文M=30 所对 应的密文。
（2）如果用相同的k=2 加密另外一个明文m，加密后的密文为C= （49，13），求m
答：（1）������1=������������modp ≡ 72mod71 ≡ 49 ������2 = ������������������������modp ≡ 3230mod71 ≡ 57 C = (������1，������2) = (49，57)
（09）16=(000001001)2 = ������3 + 1
（57）16 ∙ （09）16 ≡（������6 + ������4 + ������2 + ������ + 1）∙ (������3 + 1) mod((������8 + ������4 + ������3 + x + 1) ≡ ������7 + ������6 + ������4 + ������3 + 1 mod(������8 + ������4 + ������3 + x + 1) ≡ (D9)16
1/6
所以明文消息m = 8 的密文为 c ≡ m������mod 21≡8mod 21=8 解密的过程如下m = ������������mod21 ≡ 85mod21 ≡ 8mod21 = 8
所以解密的结果为原来的明文
6、 已知背包公钥密码系统的超递增序列为 (2，3，6，13，27，52)
所以2p = (0,2) 2）求 4 p 2 p 2 p
3x12 a4 mod 7 2 y1
＝3（02）−4 mod7 = 6
2×2
x3 (2 2x1) mod 7 ＝(62 − 0 − 0)mod7 = 1 y3 [(x1 x3 ) y1] mod 7 ＝(6(0 − 1) − 2)mod7 = 6
3、 (10 分)DES 的密码组件之一是 S 盒。根据 S 盒表计算S2(111101)的值,并说明 S 函数在 DES 算法中的作用。
答： （11）2=3
（1110）2 = 14 ������2(3,14) = 14 = (1110)2 S 盒在 DES 算法中的作用：S 盒是 DES 算法的核心，它是算法中唯一的非线性部分。是 算法安全的关键。
13×31≡88 mod 105,
27×31≡102 mod 105, 52×31≡37 mod 105,
明文 011000 对应的密文为：
c a1m1 a2m2 a6m6 mod m
93 81 mod105 69
解密过程：
首先计算ω=31 模 105 的乘法逆元ω-1=61,即： 31×61≡ 1 mod 105
y < 7）。 （2）已知椭圆曲线 E：y2＝x3－4x－3(mod 7)， 上有一点 p（2，2），求点 2p，4p 和 6p
的坐标。
答：（1）
X
0
1

3
4
5
6
y2 ＝ x3 － 4x － 4
1
4
5
3
4
0
3(mod 7)
是否为 mod7 是
是
是
否
否
是
是
的平方剩余
Y
2 ，5 1, 6 2， 5
2， 5 0
《密码学与信息安全》期中大作业
1、 (10 分)计算 319935mod 77 答： 由n = 11 × 7 得 φ(n) = 6 × 10 = 60
定理������������(������) ≡ 1������������������ ������知： ������19935������������������77 ≡ 3332×60+15������������������77 ≡ (360)332315������������������77 ≡ 315������������������77 ≡ 34������������������77
由 1c 1a1m1 1a2m2 1anmn mod m
b1m1 b2m2 bnmn mod m
得
（69×61）mod 105=9=3+6 所以 69 对应的明文为 011000
7、 (10分)在ElGamal 加密体制中，设素数p=71，本原根g=7，
a4
a3
a2
a1
输出
1
1
1
0
1
1
2
1
1
1
0
0
3
0
1
1
1
1
4
0
0
1
1
1
5
1
0
0
1
1
6
0
1
0
0
0
7
1
0
1
0
0
8
1
1
0
1
1
所以输出为：101110010111001⋯，周期为 7
4/6
《密码学与信息安全》期末大作业
5/6
6/6
DES 的解密算法可表示为DES−1=IP−1������1������2 ⋯ ������16������������ DES−1（DES(m))=IP−1������1������2 ⋯ ������16������������IP−1������16������15 ⋯ ������1������������(������) =m 其中������������IP−1 = I
5、 (10 分)在 RSA 密码体制中，如果 p=3,q=7,n=pq=21,取公钥 e=5,如果明文消息为 m=8, 试用该算法加密 m 得到密文 c，并解密进行验证。
答：因为 p 3,q 7 所以有φ(n) ( p -1)(q -1) 2×6 12 同时������−1mod12 =5 −1mod12= 5mod12 → d = ������−1 = 5
4、 (10 分)AES 算法定义的 GF(28)中两个元素的乘法运算是模二元域 GF(2)上的一个 8 次不 可约多项式(M(x)= ������8 + ������4 + ������3 + x + 1)的多项式乘法，请计算(57)•(09) =？，其中 57 和 09 均是 16 进制数。
答：（57）16=(01010111)2 = ������6 + ������4 + ������2 + ������ + 1
1)mod7 = 1, 所以6p = （1,1）
9、(10 分)已知某线性反馈移位寄存器反馈函数为 f(a1 a2 a3 a4)=a1⊕a3⊕a4，求：
（1）求该移存器的线性递推式。
（2）设初始状态为(a1，a2，a3，a4)=(1，0，1，1)求最后输出的序列及周期。
答：（1）������n+1 = ������n−3 + ������n−1 + ������������ （2）
所以椭圆曲线上的点为{ O，（0,2），（0,5），（1,1），（1,6），（2,2），（2,5），（5,2），（5,5），（6，
0
）
}
（2）求 2 p
3x12 a4 mod 7 2 y1
＝3（−2）2−4 = 2mod7
2×2
x3 (2 2x1) mod 7 ＝22 − 2 × 2mod7 = 0 y3 [(x1 x3 ) y1] mod 7 ＝2(2 − 0)2mod7 = 2