第四章部分课后题参考答案
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，进而
(n)=
(35)=24，
由 RSA 加密体制可知，ed≡1 mod
(n)，即 5d≡1 mod 24，所以 d＝5
∴M=C
d
mod n＝10
5
mod 35＝5
11. 已知 c
d
mod n 的运行时间是 O(log
3
n)，用中国剩余定理改进 RSA 的解密运算。如果不
考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的 4 倍。
证明：RSA 的两个大素因子 p，q 的长度近似相等，约为模数 n 的比特长度 logn 的一半，即
(logn)/2，而在中国剩余定理中要计算模 p 和模 q 两个模指数运算，与 c
d
mod n 的运
行时间 规 律 相 似 ， 每 一 个 模 指数运算的 运 行 时 间 仍 然 是 其 模 长的三次幂 ， 即
O[((logn)/2)
3
]= O(log
3
n)/8，这样在不考虑中国剩余定理计算代价的情况下，总的运行
时间为两个模指数的运行时间之和，即 O(log
3
n)/8＋O(log
3
n)/8＝O(log
3
n)/4，得证。
12. 设 RSA 加密体制的公开钥是(e，n)＝(77，221)。
(1) 用重复平方法加密明文 160，得中间结果为
160
2
(mod 221)=185，160
4
(mod 221)=191，160
8
(mod 221)=16，160
16
(mod 221)=35，
160
32
(mod 221)=120，160
64
(mod 221)=35，160
72
(mod 221)=118，160
76
(mod 221)=217，
160
77
(mod 221)=23，
若敌手得到以上中间结果就很容易分解 n，问敌手如何分解 n
解：由以上中间结果得 160
16
(mod 221)=35＝160
64
(mod 221)，
此即 160
64
－160
16
=0 (mod 221)
即 (160
32
－160
8
) (160
32
+160
8
)=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
－
1
mod (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
1
=g
k
mod p＝7
3
mod 71＝59
C
2
=y
B
k
M mod p＝3
3
×30 mod 71＝29
所以密文为(59，29)
（2）如果 A 选择另一个随机数 k，使得明文 M=30，加密后的密文是 C＝（59，C
2
），求 C
2
解：由 C
1
=g
k
mod p 得 59＝g
k
mod p＝7
k
mod 71，即 k＝3
而 C
2
=y
B
k
M mod p＝3
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，
下载后可阅读完整内容，剩余3页未读，立即下载
老许的花开
- 粉丝: 29
- 资源: 328
我的内容管理
展开
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析：故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全：高效编程的秘密武器
- 网页制作入门：常用代码详解
- TX2440A开发板网络远程监控系统移植教程：易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析：Socket基础与应用
- 掌握Struts1：Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全：字体、文本、列表样式详解
- Proteus元件库大全：从基础到高级组件
- 74HC08芯片：高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题：设置字符集为GB2312
- C语言的诞生与演进：从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
