北方工业大学密码学平时作业答案公钥密码作业答案.pdf

NCUT 密码学 – 习题与答案 2011
四、公钥密码 (3加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是 C=10，
求明文 M
第 7 页NCUT 密码学 – 习题与答案 2011
解： 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 ≡ Cd mod n ≡ 105 mod 35 ≡ 5
5 m
快速指数算法求模幂 10 mod 35： a mon n m=(bi)2
5 = 4 + 1 = (101)2 bi=0, d←d*d mod n
bi - 1 0 1 bi=1, d←d*d*a mod n
d 1 10 30 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，猜测：
ordn(160) | 48 且 48 | ϕ(n)，即存在整数 k 满足ϕ(n)=48k
由 ϕ(n) 的定义可知， ϕ(n)