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

1、NCUT密码学-习题与答案2011第7页NCUT密码学-习题与答案2011四、公钥密码 (3,4,5,6;10,12;13,18,19,20)3.用 Fermat 定理求 3 201 mod 11。解：对于模运算，有结论 (ax b) mod n = (a mod n)x (b mod n) mod n由Fermat定理，可知 310三1 mod 11,因此有(3 10)k三1 mod 11所以 3201 mod 11= (310)20 x 3 mod 11 = ( (310)20 mod 11)x (3 mod 11) mod 11 = 3Fermat定理：若p是素数，a是正整数且gcd(a

2、, p)=1，贝U aP 1 = 1 mod p。 若 gcd(a, p)=1，贝U a?(p) = 1 mod p。4.用推广的Euclid算法求67 mod 119的逆元。解：qguv1191067011521-1115-12374-721-916(注：1 = 119X (-9) + 67X 16 )所以-167 mod 119 = 165.求 gcd(4655, 12075)。解: 12075 = 2X 4655 + 27654655= 1X 2765 + 18902765= 1X 1890 + 8751890= 2X 875 + 140所以 gcd(4655, 12075)=35875

3、= 6X 140 + 35140= 4X 35+0?x =2 mod 36.求解下列同余方程组?x =1mod 5。?x =1mod 7解：根据中国剩余定理求解该同余方程组，记 a1=2, a2=1, a3=1, m 1=3, m2=5, m3=7,M=m1 X m2X m3=105,M 1=M/m 1=35,M 2=M/m 2=21,M 3=M/m 3=15,所以方程组的解为1 1M1 mod m1 = 35 mod 3 = 2,-1-1M2 mod m2 = 21 mod 5 = 1,-1-1M 3 mod m3 = 15 mod 7 = 1111x = (M1M1 a1 + M2M2 a

4、2 + M 3M3 a3) mod M=(35X 2X 2+21 X 1 X 1+15X 1 X 1) mod 105=176 mod 105=71 mod 10510.设通信双方使用 RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是 C=10，求明文M解： n=35 -> p=5, q=7?(n)=(p-1)(q-1)=24d三e-1 mod ?(n)三5-1 mod 24三5 mod 24.(因为 5X 5三 1 mod 24)am mon n m=(b i)2 bi=0, d J d*d mod n bi=1, d j d*d*a mod n所以，明文 M

5、三 Cd mod n三10 5 mod 35三5快速指数算法求模幂105 mod 35:5 = 4 + 1 = (101)2b-101d110 30 512.设RSA加密体制的公开钥是(e,n)=(77, 221)。(1)用重复平方法加密明文160,得中间结果为:k2 4 81163264727677160k mod 221185191 1635 1；>0 35 118217 23若敌手得到以上中间结果就很容易分解n,问敌手如何分解n?(2)求解密密钥d。解：(1)由 16016 三 16064 mod 221,可知(160 64 - 16016) mod 221 = 0即 16016(

6、16048 -1) mod 221 = 0，从而有 160 48 = 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

7、+q) - 4n),从而 p = (p+q) + (p-q) )/2, q =(p+q) - (p-q) )/2所以，可得n的分解为：n = 221 = 13X 17(2)解密密钥 d 为：d三e-1 mod ?(n) = 77-1 mod 192 = 5(v 77 x 5 - 192X2 = 1 )13.在EIGamal加密体制中，设素数 p=71，本原根g=7，(1) 如果接收方B的公开钥是yB=3,发送方A选择的随机整数k=2，求明文M=30所对应的密 文。(2) 如果A选择另一个随机整数 k,使得明文 M=30加密后的密文是 C=(59, C2)，求C?。解：(1) G三gk mod

8、p = 72 mod 71 = 49,C2三yBk M mod p = (3 2x 30) mod 71= 57所以密文为 C=(C 1, C2)=(49, 57)。(2)由 7k mod 71 = 59，穷举 k 可得 k=3。所以 C2 = (3kx 30) mod 71 = (33x 30) mod 71 = 29。& p)TXEIGamalS 制y-jf mod pC-(ChC2) M 三 CdG* mod p裁送舌加密>mod pnxMl p2318.椭圆曲线E11(1,6)表示y三x +x+6 mod 11，求其上的所有点第9页NCUT密码学-习题与答案2011x0

9、1 23 4 5 67 8 910x3+x+6 mod 116 8 53 8 4 84 9 7 4是否为mod 11的平方剩余No Noi yes yes,No yesNo yes，es No yesy4,75, 62,9 :!,93, 82 -59解:所以，En(1,6)上点为0, (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7,2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9) x2 三 c mod p?要确定c是否是一个模p的平方剩余，可以用 Euler准则来判断，即 如果p是一个奇素数，则c是模

10、p的平方剩余当且仅当c(P-1)/2三1 modp.- 当p三3 mod 4时，如果c是一个模p的平方剩余，则土c (p+1)/2 mod p , 即c(p+1)/2和p- c (p+1)/2，就是c的两个模p的平方根。19.已知点G=(2, 7)在椭圆曲线E11(1,6)上，求2G和3G23解：a=1, b=6, p=11, y 三 x +x+6 mod 11/ 2G = G + G入=(3< 22+1)/(2 x 7) mod 11=13/14 mod 11 = 2/3 mod 11 = 8x3=(82-2-2) mod 11=5,y3= 8(2-5)-7 mod 11=2 2G =

11、 (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 x3=(22-5-2) mod 11 = (-3) mod 11 = 8y3=2(5-8)-2 mod 11 = (-8) mod 11 = 3 3G = (8, 3)1(V 31 mod 11 = 4)(t 8*7=1 mod 11)设P(ryl)tQ = (x2ry1)E,则P + Q = I知用 其中Xj =- x1 x2 mod p丹二*佔一屯)一H modpif 册=x2,y1 = -y2else解:(1) A 的公开钥 Pa = nAG = 7G =亿 2)(2) C1=kG = 3G = (8, 3)C2=Pm + kPA=(10,9) + 3(7, 2) = (10,9) + (3, 5) = (10, 2)所以密文 Cm=C 1, C2 = (8,3), (10, 2) (3) 解密过程为C2 - nAC1= (Pm +