四、公钥密码(3,4,5,6;10,12;13,18,19,20)
3. 用Fermat定理求3201 mod 11 。

解：对于模运算，有结论(a×b) mod n = [ (a mod n)×(b mod n)] mod n 由Fermat定理，可知310≡1 mod 11，因此有 (310)k ≡1 mod 11
所以3201 mod 11= [(310)20×3] mod 11 = [( (310)20 mod 11)×(3 mod 11)] mod 11 = 3。

4. 用推广的Euclid算法求67 mod 119的逆元。

解：q g u v
~ 119 1 0
~ 67 0 1
1 5
2 1 -1
1 15 -1 2
3 7
4 -7
2 1 -9 16 ( 注：1 = 119×(-9) + 67×16 )
所以67-1mod 119 = 16
5.求gcd(4655, 12075) 。

解：12075 = 2×4655 + 2765
4655 = 1×2765 + 1890
2765 = 1×1890 + 875
1890 = 2×875 + 140
875 = 6×140 + 35
140 = 4×35+0 所以gcd(4655, 12075)=35。

6.求解下列同余方程组
2mod3
1mod5
1mod7
x
x
x
≡
⎧
⎪
≡
⎨
⎪≡
⎩。

解：根据中国剩余定理求解该同余方程组，
记a1=2, a2=1, a3=1, m1=3, m2=5, m3=7, M=m1×m2×m3=105,
M1=M/m1=35, M1-1 mod m1 = 35-1 mod 3 = 2,
M2=M/m2=21, M2-1 mod m2 = 21-1 mod 5 = 1,
M3=M/m3=15, M3-1 mod m3 = 15-1 mod 7 = 1
所以方程组的解为x≡(M1M1-1a1 + M2M2-1a2 + M3M3-1a3) mod M
≡(35×2×2+21×1×1+15×1×1) mod 105
≡176 mod 105≡71 mod 105
10.设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M
解： n=35 -> p=5, q=7
ϕ(n)=(p-1)(q-1)=24
d ≡
e -1 mod ϕ(n)≡5-1 mod 24≡5 mod 24 .... (因为 5×5≡1 mod 24) 所以，明文M ≡ C d mod n ≡ 105 mod 35 ≡ 5
12. 设RSA 加密体制的公开钥是(e,n)=(77, 221)。

(1) 用重复平方法加密明文160，得中间结果为：
k 2 4 8 16 32 64 72 76 77 160k mod 221 185 191 16 35 120 35 118 217 23 若敌手得到以上中间结果就很容易分解n ，问敌手如何分解n ？
(2) 求解密密钥d 。

解：(1) 由16016 ≡16064 mod 221，可知 (16064 - 16016) mod 221 = 0
即 16016(16048 – 1) mod 221 = 0，从而有 16048 = 1 mod 221。

由Euler 定理及定理4-7，猜测：
ord n (160) | 48 且 48 | ϕ(n)，即存在整数k 满足ϕ(n)=48k
由 ϕ(n) 的定义可知， ϕ(n) 比 n 略小。

而当取k=4时，ϕ(n)=192为<221且与221最接近，因此猜测 ϕ(n)=192。

由ϕ(n)=(p-1)(q-1), n=pq ，可知 p+q = n - ϕ(n) + 1 = 221 - 192 + 1 = 30
所以 p 、q 为一元二次方程 X 2 - 30X + 221 = 0 的两个根，求得为13、17。

或： p-q = sqrt((p+q)2- 4n), 从而p = ((p+q) + (p-q) )/2, q =((p+q) - (p-q) )/2
所以，可得n 的分解为： n = 221 = 13×17
(2) 解密密钥d 为：d ≡e -1 mod ϕ(n) = 77-1 mod 192 = 5 (∵ 77×5 - 192×2 = 1 )
13. 在ElGamal 加密体制中，设素数p=71，本原根g=7，
(1)如果接收方B 的公开钥是y B =3，发送方A 选择的随机整数k=2，求明文M=30所对应的密文。

(2)如果A 选择另一个随机整数k ，使得明文M=30加密后的密文是C=(59, C 2)，求C 2。

解： (1) C 1≡g k mod p = 72 mod 71 = 49， C 2≡y B k M mod p = (32×30) mod 71= 57 所以密文为 C=(C 1, C 2)=(49, 57)。

(2)由 7k mod 71 = 59 ，穷举k 可得k=3 。

所以 C 2 = (3k ×30) mod 71 = (33×30) mod 71 = 29。

18. 椭圆曲线E 11(1,6)表示y 2≡x 3
+x+6 mod 11，求其上的所有点。

解：
x
0 1 2 3 4 5 6 7 8 9 10 x 3+x+6 mod 11
6 8 5 3 8 4 8 4 9
7 4 是否为mod 11的
平方剩余 No No yes yes No yes No yes yes No yes
y
4, 7 5, 6 2, 9 2, 9 3, 8 2, 9
所以，E 11(1, 6)上点为 { O, (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7,2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9) }
19. 已知点G=(2, 7) 在椭圆曲线E 11(1,6)上，求2G 和3G 。

解： a=1, b=6, p=11, y 2≡x 3+x+6 mod 11
∵ 2G = G + G , λ=(3×22+1)/(2×7) mod 11=13/14 mod 11 = 2/3 mod 11 = 8 (∵ 3-1 mod 11 = 4)
x3=(82-2-2) mod 11=5, y3= [8(2-5)-7] mod 11=2
∴ 2G = (5, 2)
∵ 3G = 2G + G = (5, 2) + (2, 7),
λ=(7−2)/(2−5) mod 11=5/(-3) mod 11=5/8 mod 11=5*7 mod 11= 2 (∵ 8*7=1 mod 11) x3=(22-5-2) mod 11 = (-3) mod 11 = 8
y3=[2(5-8)-2] mod 11 = (-8) mod 11 = 3
∴ 3G = (8, 3)
20. 利用椭圆曲线实现ElGamal 密码体制，设椭圆曲线是E 11(1,6)，生成元G=(2,7)，接收方A 的秘密钥n A =7。

(1) 求A 的公开钥P A 。

(2) 发送方B 欲发送消息P m =(10,9)，选择随机数k=3，求密文C m 。

(3) 显示接收方A 从密文C m 恢复消息P m 的过程。

解： (1) A 的公开钥 P A = n A G = 7G = (7, 2)
(2) C 1=kG = 3G = (8, 3)
C 2=P m + kP A =(10,9) + 3(7, 2) = (10,9) + (3, 5) = (10, 2)
所以密文 C m ={C 1, C 2} = { (8,3), (10, 2) }
(3) 解密过程为
C 2 - n A C 1= (P m + kP A ) – n A (kG) = (10, 2) – 7(8,3) = (10, 9) = P m。