第四章作业参考答案

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

解：初始化：(1,0,119), (0,1,67)

1：Q=119/67=1，(0,1,67) , (1,-1,52)

2：Q=67/52=1，(1,-1,52), (-1,2,15)

3：Q=52/15=3，(-1,2,15), (4,-7,7)

4：Q=15/7=2，(4,-7,7), (-9,16,1)

所以67^－1 mod 119＝16

10．设通信双方使用RSA加密体制，接收方的公开钥是(e，n)＝(5,35)，接收到的密文是C＝10，求明文M。

解：由n＝35，易知35＝5×7，进而j(n)= j(35)=24，

由RSA加密体制可知，ed≡1 mod j(n)，即5d≡1 mod 24，所以d＝5

∴M=C^d mod n＝10⁵ mod 35＝5

11. 已知c^d mod n 的运行时间是O(log³n)，用中国剩余定理改进RSA的解密运算。如果不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。

证明：RSA的两个大素因子p，q的长度近似相等，约为模数n的比特长度logn的一半，即(logn)/2，而在中国剩余定理中要计算模p和模q两个模指数运算，与c^d mod n 的运行时间规律相似，每一个模指数运算的运行时间仍然是其模长的三次幂，即O[((logn)/2)³]= O(log³n)/8，这样在不考虑中国剩余定理计算代价的情况下，总的运行时间为两个模指数的运行时间之和，即O(log³n)/8＋O(log³n)/8＝O(log³n)/4，得证。

12. 设RSA加密体制的公开钥是(e，n)＝(77，221)。

(1) 用重复平方法加密明文160，得中间结果为

160²(mod 221)=185，160⁴(mod 221)=191，160⁸(mod 221)=16，160¹⁶(mod 221)=35，

160³²(mod 221)=120，160⁶⁴(mod 221)=35，160⁷²(mod 221)=118，160⁷⁶(mod 221)=217，

160⁷⁷(mod 221)=23，

若敌手得到以上中间结果就很容易分解n，问敌手如何分解n

解：由以上中间结果得160¹⁶(mod 221)=35＝160⁶⁴(mod 221)，

此即160⁶⁴－160¹⁶=0 (mod 221)

即 (160³²－160⁸) (160³²+160⁸)=0 (mod 221)

(120－16)(120＋16)=0 (mod 221)

104×136＝0 (mod 221)

由gcd(104,221)=13及gcd(136,221)=17，可知 221的分解为221＝13×17

(2) 求解密密钥d

d＝e^－1mod j(221)=77^-1 mod 12×16

由扩展Eucild算法可得d＝5。

13．在ElGamal体制中，设素数p＝71，本原根g＝7，

（1）如果接收方B的公开钥是y_B＝3，发送方A选择的随机整数k＝3，求明文M＝30所对应的密文。

解：C₁=g^k mod p＝7³ mod 71＝59

C₂=y_B^kM mod p＝3³×30 mod 71＝29

所以密文为(59，29)

（2）如果A选择另一个随机数k，使得明文M=30，加密后的密文是C＝（59，C₂），求C₂

解：由C₁=g^k mod p得59＝g^k mod p＝7^k mod 71，即k＝3

而C₂=y_B^kM mod p＝3³×30 mod 71＝29

14．设背包密码系统得超递增序列为（3，4，9，17，35），乘数为t＝19，模数k＝73，试对good night加密。

解：由A=（3，4，9，17，35），乘数为t＝19，模数k＝73，

得B=t×A mod k＝(57，3，25，31，8）

名文“good night”的编码为“00111”，“01111”，“01111”，“00100”，“00000”，“01110”“01001”“00111”“01000”“10100”

f(00111)=25+31+8=64，f(01111)=3+25+31+8=67，f(01111)=3+25+31+8=67，f(00100)=25

f(00000)=0，f(01110)=3+25+31=59，f(01001)=3+8=11，f(00111)=25+31+8=64，

f(01000)=3，f(10100)=57＋25=82＝9 mod 73

相应的密文为（64，67，67，25，0，59，11，64，3，9）

15．设背包密码系统的超递增序列为（3，4，8，17，33），乘数为t＝17，模数k＝67，试对密文25，2，72，92解密。

解：t^－1mod k＝17^－1 mod 67＝4 mod 67

所以4×(25，2，72，92)mod 67＝(33,8,20,33)

从而可得4个明文分组为(00001,00100,10010,00001)，所以由表4－5明文为：“ADRA”

16.已知n＝pq，p，q都是素数，x，yÎZ_n^*，其Jacobi符号都是1，其中Z_n^*＝Z_n－{0},证明：

（1）xy(mod n)是模n的平方剩余，当且仅当x，y都是模n的平方剩余或x，y都是模n的非平方剩余。

证明：必要性：若xy(mod n)是模n的平方剩余，即存在t使得xy＝t² mod n，

而n＝pq，显然必有xy＝t² mod p 及，xy＝t² mod q，

所以xy也同时是模p和模q的平方剩余，即(xy/p)=1且(xy/q)=1

也即(x/p)(y/p)=1和(x/q)(y/q)=1， (a)

又由题设(x/n)＝1和(y/n)＝1由雅可比符号定义，此即

(x/p)(x/q)=1和(y/p)(y/q)=1 (b)

所以当(x/p)＝1时由(a)中(x/p)(y/p)=1知(y/p)=1，而由(b)中(y/p)(y/q)=1知(y/q)=1，再由(a)中(x/q)(y/q)=1知(x/q)=1，即x同时是p和q的平方剩余，y也同时是p和q的平方剩余，所以x和y都是n的平方剩余。

若(x/p)＝－1时由(a)中(x/p)(y/p)=1知(y/p)=－1，而由(b)中(y/p)(y/q)=1知(y/q)=－1，再由(a)中(x/q)(y/q)=1知(x/q)=－1，即x同时是p和q的非平方剩余，y也同时是p和q的非平方剩余，所以x和y都是n的非平方剩余。

充分性：若x和y都是模n的平方剩余，则x和y也都是模p和模q的平方剩余，则(x/p)＝(x/q)＝(y/p)＝(y/q)＝1，所以xy也是模p和模q的平方剩余，所以xy是模n的平方剩余

若x和y都是模n的非平方剩余，则它们对于模p和模q至少有一种情况是非平方剩余，不妨设(x/p)＝－1和(y/p)＝－1则由(b)式知(x/q)=－1，且(y/q)＝－1，即x和y也都是模p和模q的非平方剩余。所以(x/p)(y/p)＝(xy/p)＝(－1)(－1)＝1以及(xy/q)＝1，即xy同时是模p和模q的平方剩余。所以xy是模n的平方剩余。#

（2）x³y⁵(mod n)是模n的平方剩余，当且仅当x，y都是模n的平方剩余或x，y都是模n的非平方剩余。

证明：若x³y⁵(mod n)是模n的平方剩余，则x³y⁵模p和模q也是平方剩余，所以(x³y⁵/p)=1=(x/p)³(y/p)⁵，由于勒让得符号的偶数次方肯定为1(p|x情况除外) 即有1=(x/p)(y/p)，以下证明如(1)。

17．在Rabin密码体制中，设p＝47，q＝59

（1）确定1在模n下的四个平方根。

解：由x²＝1 mod 47，得x₁＝1 mod 47，x₂＝p－1＝46 mod 47

由y²＝1 mod 59，得y₁＝1 mod 59，y₂＝q－1＝59 mod 47

n=47*59=2773

由中国剩余定理CRT，1在模n下的四个平方根分别为

U₁=CRT(x₁，y₁)＝CRT(1，1)＝1*59*[59^-1(mod 47)]+1*47*[47^-1(mod 59)] (mod n)

＝1*59*4+1*47*54 (mod 2773)=1

U₂=CRT(x₁，y₂)＝CRT(1，58)＝1*59*4+58*47*54 (mod 2773)=471

U₃=CRT(x₂，y₁)＝CRT(46，1)＝46*59*4+1*47*54 (mod 2773)=2302

U₄=CRT(x₂，y₂)＝CRT(46，58)＝2772

（2）求明文消息2347所对应的密文

解：2347²(mod 2773)＝1231

（3）对上述密文确定可能的明文

解：由x²＝9 mod 47，得x₁＝3 mod 47，x₂＝p－3＝44 mod 47

由y²＝51 mod 59，得y₁＝46 mod 59，y₂＝59－46＝13 mod 59

由中国剩余定理CRT，1231在模n下的四个可能明文分别为

U₁=CRT(x₁，y₁)＝CRT(3，46)＝3*59*[59^-1(mod 47)]+46*47*[47^-1(mod 59)] (mod n)

＝3*59*4+46*47*54 (mod 2773)=990

U₂=CRT(x₁，y₂)＝CRT(3，13)＝3*59*4+13*47*54 (mod 2773)=426

U₃=CRT(x₂，y₁)＝CRT(44，46)＝44*59*4+46*47*54 (mod 2773)=2347

U₄=CRT(x₂，y₂)＝CRT(44，13)＝2773－990＝1783

18．椭圆曲线E₁₁(1,6)表示y²＝x³＋x＋6 (mod 11)，求其上的所有点

解：模11的平方剩余有1，4，9，5，3

x＝1，4，6时，y²＝8 (mod 11)，无解，x＝9时，y²＝7 (mod 11)，无解，x＝0时无解

x＝2时，y²＝2 (mod 11)，y＝4或7，x＝3时，y²＝3 (mod 11)，y＝5或6

x＝5，7，10时，y²＝4 (mod 11)，y＝2或9，x＝8时，y²＝9 (mod 11)，y＝3或8

所以，E₁₁(1,6)上所有点为：

{（2，4）,（2，7）,（3，5）,（3，6）,（5，2）,（5，9）,（7，2）,（7，9）,（8，3）,（8，8）,（10，2）,（10，9），O }

19．已知点G=（2，7）在椭圆曲线E₁₁(1,6)上，求2G和3G

解：求2G:

λ=(3×2²＋1)/(2×7) mod11＝13×4 mod11＝8

x₃＝8²－2－2 mod 11＝5，y₃＝8(2－5)－7 mod 11＝2

所以2G＝（5，2）

求3G＝2G＋G＝（5，2）＋（2，7）

λ=(7－2)/(2－5) mod11＝5×7 mod11＝2

x₃＝2²－5－2 mod 11＝8，y₃＝2(5－8)－2 mod 11＝3

所以3G＝（8，3）

20．利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E₁₁(1,6)，生成元G=（2，7），接收方A的秘密钥n_A＝7

（1）求A的公开钥P_A

解：P_A＝7G＝2×2G＋3G

先求2×2G

λ=(3×5²＋1)/2×2 mod11＝10×3 mod11＝8

x₃＝8²－5－5 mod 11＝10，y₃＝8(5－10)－2 mod 11＝2

所以2×2G＝2×(5，2)＝(10，2)

P_A＝(10，2)＋(8，3）

由于λ=(3－2)/(8－10) mod11＝1×5 mod11＝5

x₃＝5²－10－8 mod 11＝7，y₃＝5(10－7)－2 mod 11＝2

所以P_A＝(7，2)

（2）发送方B欲发送P_m＝(10，9)，选择随机数k＝3，求密文C

解：C=(kG，P_m＋kP_A)，kG＝3G＝（8，3），kP_A＝2P_A＋P_A＝3G+7G＝(2，7)＋(7，2)

由于λ=(2－7)/(7－2) mod11＝－1

x₃＝(－1)²－2－7 mod 11＝3，y₃＝－1(2－3)－7 mod 11＝5

P_m＋kP_A＝(10，9)＋(3，5)

由于λ=(5－9)/(3－10) mod11＝－1

x₃＝(－1)²－10－3 mod 11＝10，y₃＝－1(10－10)－9 mod 11＝2

所以C=(kG，P_m＋kP_A)＝（（8，3），（10，2））

（3）显示接收方A从密文C_m恢复消息P_m的过程

解：P_m＝（P_m＋kP_A）－n_A(kG)＝（10，2）－7（8，3）＝（10，2）－（3，5）

＝（10，2）＋（3，6）＝(10，9)

复习题&&答案

4. 16. 试给出椭圆曲线群E₅(1,1)上的所有点。

解，分别以x=0，1，2，3，4带入到椭圆曲线y²=x³+x+1 mod 5 求解y得到如下点：

(0, ±1) , (2, ±1), (3, ±1), (4, ±2),

所以E₅(1,1)={(0,1), (0,4), (2,1), (2,4), (3,1), (3,4), (4,1), (4,4),O }

5.3．对于RSA算法中两个大素数p，q，试分析如果2p与3q的差值很小，也能被快速分解

证明：由于(2p+3q)²=4x2x3n+(2p-3q)²=24n+(2p-3q)²，对24n+x²从x=1开始搜索满足y²=24n+x²的x取值，如果找到则可通过计算gcd(24n, x+y)和gcd(24n, x-y)来分解n，当2p与3q的差值很小时，上述搜索将很快发现满足条件的x，所以2p与3q的差值很小时也能被快速分解