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

NCUT 密码学 习题与答案 2011 第 7 页 四、公钥密码四、公钥密码 (3,4,5,6;10,12;13,18,19,20) 3. 用 Fermat 定理求 3201 mod 11 。 解：对于模运算，有结论 (ab) mod n = (a mod n)(b mod n) mod n 由 Fermat 定理，可知 3101 mod 11，因此有 (310)k 1 mod 11 所以 3201 mod 11= (310)203 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 52 1 -1 1 15 -1 2 3 7 4 -7 2 1 -9 16 ( 注： 1 = 119(-9) + 6716 ) 所以 67-1 mod 119 = 16 5. 求 gcd(4655, 12075) 。 解：12075 = 24655 + 2765 4655 = 12765 + 1890 2765 = 11890 + 875 1890 = 2875 + 140 875 = 6140 + 35 140 = 435+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=m1m2m3=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 (3522+2111+1511) mod 105 176 mod 10571 mod 105 10. 设通信双方使用 RSA 加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是 C=10， 求明文 M Fermat 定理：定理：若若 p 是素数，是素数，a 是正整数且是正整数且 gcd(a, p)=1，则，则 ap-11 mod p。 若若 gcd(a, p)=1，则，则 a (p)1 mod p。 NCUT 密码学 习题与答案 2011 第 8 页 解： n=35 - p=5, q=7 (n)=(p-1)(q-1)=24 de-1 mod (n)5-1 mod 245 mod 24 . (因为 551 mod 24) 所以，明文 M Cd 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，猜测： ordn(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 为一元二次方程 X2 - 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 = 1317 (2) 解密密钥 d 为：de-1 mod (n) = 77-1 mod 192 = 5 ( 775 - 1922 = 1 ) 13. 在 ElGamal 加密体制中，设素数 p=71，本原根 g=7， (1)如果接收方 B 的公开钥是 yB=3，发送方 A 选择的随机整数 k=2，求明文 M=30 所对应的密 文。 (2)如果 A 选择另一个随机整数 k，使得明文 M=30 加密后的密文是 C=(59, C2)，求 C2。 解： (1) C1gk mod p = 72 mod 71 = 49， C2yBk M mod p = (3230) mod 71= 57 所以密文为 C=(C1, C2)=(49, 57)。 (2)由 7k mod 71 = 59 ，穷举 k 可得 k=3 。 所以 C2 = (3k30) mod 71 = (3330) mod 71 = 29。 18. 椭圆曲线 E11(1,6)表示 y2x3+x+6 mod 11，求其上的所有点。 快速指数算法求模幂 105 mod 35： am mon n m=(bi)2 5 = 4 + 1 = (101)2 bi=0, dd*d mod n bi - 1 0 1 bi=1, dd*d*a mod n d 1 10 30 5 NCUT 密码学 习题与答案 2011 第 9 页 解： x 0 1 2 3 4 5 6 7 8 9 10 x3+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 所以，E11(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) 在椭圆曲线 E11(1,6)上，求 2G 和 3G。 解： a=1, b=6, p=11, y2x3+x+6 mod 11 2G = G + G, =(322+1)/(27) 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), =(72)/(25) 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 密码体制，设椭圆曲线是 E11(1,6)，生成元 G=(2,7)，接收方 A 的秘密钥 nA=7。 (1) 求 A 的公开钥 PA。 (2) 发送方 B 欲发送消息 Pm=(10,9)，选择随机数 k=3，求密文 Cm。 (3) 显示接收方 A 从密文 Cm恢复消息 Pm的过程。 解： (1) A 的公开钥 PA = nAG = 7G = (7, 2) (2) C1=kG = 3G = (8, 3) C2=Pm + kPA=(10,9) + 3(7, 2) = (10,9) + (3, 5) = (10, 2) 所以密文 Cm=C1, C2 = (8,3), (10, 2) (3) 解密过程为 C2 - nAC1= (Pm + kPA) nA (kG) = (10, 2) 7(8,3) = (10, 9) = Pm x 2 c mo