现代密码学-第4章公钥密码体制习题与解答-20091202

第4章 公钥密码体制

第4章 公钥密码体制

习题及参考答案

1．对于RSA密码系统，取47=p，59=q，17=e，计算 (1) 解密私钥d； (2) 明文115的密文； (3) 密文28的明文。

解：(1) 由题：φ(n) = (p-1)*(q-1) = 2668

又 e=17 且 e*d mod φ(n) = 1 所以 d = e-1 mod φ(n) = 157 (2) 密文 c = me mod n = 1751

(3) 密文28的明文为 m=cd mod n = 1377

2．在 ElGamal 密码系统中，若选取素数 p=71，生成元 α = 7。

(1) 若B的公钥 β=3，A随机选取整数 r=2，则明文 m=30 的密文是什么？ (2) 若A选取的整数 r 使得 m=30 的密文为 C= (59, c2)，则整数 c2 是什么？ 解：(1) c1= αrmod p=72mod 71= 49, c2 =m ·βrmod p =30 ·32mod 71= 57，

所以密文为(49, 57)。

(2) 首先由c1=59计算出r=3，所以 c2=30*33mod71=29。

3．令 y2=x3+9x+17是F23上的一个方程，计算该椭圆曲线方程在F23上的所有解。以P=(16,5)为底的Q =(4, 5)的离散对数是多少？ 解：

x 0 1 2 3 4 5 6 7 8 y2=x3+9x+17 17 4 21 2 2 3 11 9 3 y 是否平方剩余 否 是 否 是 是 是 否 是 是 2， 21 5， 18 5， 18 7， 16 3， 20 7， 16 y 第4章 公钥密码体制

9 10 11 12 13 14 15 16 17 18 19 20 21 22 22 3 21 13 8 12 8 2 0 8 9 9 14 7 否 是 否 是 是 是 是 是 是 是 是 是 否 否 7， 16 6， 17 10， 13 9， 14 10， 13 5， 18 0 10， 13 3， 20 3， 20 由上表可得所有的解为：（1，2）（1，21）（3，5）（3，18）（4，5）（4，18）（5，7）（5，16）（7，3）（7，20）（8，7）（8，16）（10，7）（10，16）（12，6）（12，17）（13，10）（13，13）（14，9）（14，14）（15，10）（15，13）（16，5）（16，18）（17，0）（18，10）（18，13）（19，3）（19，20）（20，3）（20，20）, ∞

以P=(16, 5)为底，通过公式计算容易知Q=(4, 5)=9P，所以离散对数为9。

4．已知F11上的椭圆曲线

E11(1,6):y2?x3?x?6(mod11)，

取P?(2,7)作为E11(1,6)的一个生成元。

(1)设用户B的密钥为a?3，求B的公钥Q?3P。

(2)设用户A欲发消息m?(10,9)给B，选择随机数k?5，求密文c。 (3)设B收到密文c?((7,2),(3,6))，试求明文。 我们首先计算2P?2(2,7)。

3x13?a3?22?12????2y12?73x3??2?2x1解：(1)Q?3P?2P?P。

mod11?2?4mod11?8

mod11?82?2?2mod11?5，

y3??(x1?x3)?y1?8(2?5)?7(mod11)?2。

故，2P?(5,2)。

第4章 公钥密码体制

现在计算3P?2P?P?(5,2)?(2,7)。

??y2?y17?2?x2?x12?5(mod11)?5?7(mod11)?2，

x3??2?x1?x2?22?5?2(mod11)?8，

y3??(x1?x3)?y1?2(5?8)?2(mod11)?3。

即Q?3P?(8,3)。

(2)c1?kP?5P?5(2,7)?(3,6)，

c2?m?kQ?(10,9)?5(8,3)?(10,9)?(5,2)?(5,9)。

即密文为c?((3,6),(5,9))。

(3)由密文c?((7,2),(3,6))，根据解密算法

m?c2?ac1?(3,6)?3(7,2)?(3,6)?(3,5)?(3,6)?(3,6)?(8,8)。

5．通过上网查找，试说明基于椭圆曲线的密码系统相对于基本ElGamal密码系统以及RSA密码系统有那些优点。

答：基于椭圆曲线的密码系统相对于基本ElGamal密码系统以及RSA密码系统的优点是：在等同的安全性下，密钥量小，灵活性好，易于应用推广。所以可以：

（1）节省实现成本 （2）节省存储空间 （3）节省占用带宽。

（4）节省处理时间

6．既然Rabin密码系统是被证明安全性等价于大整数的因子分解的困难性，为什么实际的系统却很少使用Rabin密码系统。 答略。

7．有哪些方法可以将较低安全级别密码系统转化为在适应性选择密文攻击下具有不可区分安全性的密码系统。答略。

8.（补充题）已知F11上的椭圆曲线 E11(1,6)：y2= x3+x+6 (mod 11)。

(1) 求E11(1,6)的所有点；

(2) 已知点P=(2,7) 在 E11(1,6)上，计算 P 的全部倍数，求 P 的阶，证明 P 是 E11(1,6) 的一个生成元；

(3) 以 P 作为E11(1,6)的生成元。设用户A的秘密钥为 a=2，求A的公钥 Q=2P。发送方 B 欲发消息 Pm=(10, 9)给A，选择随机数 r=3，求密文C。写出接受方A 从密文C 恢复明文 M 的解密过程。

第4章 公钥密码体制

解：(1) E11(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)，∞。

x3???x1?x2? ? P=?Q (2)由公式P?Q??，其中，

(x,y) P??Qy??(x?x)?y?333131?y2?y1?x?x?21???2?3x1?a??2y113P=∞。

(3) A的公钥为Q=2P=(5, 2)

因为c1=r·P=3P=(8, 3)，c2=Pm+r·Q =(10, 9)+6P=9P+6P=15P=2P=(5, 2)，所以密文C=(c1, c2)=((8, 3), (5, 2))。

解密：Pm= c2 - a·c1 = (5, 2)-2·(8, 3)= 2P-2·3P=2P-6P=-4P=9P=(10, 9)，对Pm进行相应解码即得到明文m。

2P??Q可算得：P=(2, 7)，2P=(5, 2)，3P=(8, 3)，4P=(10, 2)，5P=(3,6)，

P?Q6P=(7, 9)，7P=(7, 2)，8P=(3, 5)，9P=(10, 9)，10P=(8, 8)，11P=(5, 9)，12P=(2, 4)，

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库现代密码学-第4章公钥密码体制习题与解答-20091202在线全文阅读。