密码学00

第1章 概论 习题

1．就你所在单位的某个信息系统，试做一个概略的安全风险评估。

2．网络上查找出分组秘密码DES（基本型）原程序或资料，回答：DES的密钥空间大小？

3．在国标GB2312的6763个汉字“字符”集上（即取q=6763），设计仿射密码，计算其密钥量。

4．在中途岛战争前，美军通过散布“中途岛淡水设备发生故障”的消息，在日军密报中确认了中途岛的代号，从而破译了日军的密报。问：美军的此次密码分析属于哪种破译类型？

5．明文在整个消息空间中的一个很小的区域内，英语中某些字符不相等的频率就是这样

的一个例子。再给出两个也能说明英语明文消息有小的区域分布的例子。

1024(u,v)027．假设x,e,n均为正整数(xn)，（1）如果nx不超过计算机语言某基本变量类型允许eyxmodn的快速算法；记录的最大整数，研究计算（2）如果n达到计算机语言某基本变量eyxmodn的快速算法；类型允许记录的最大整数的32倍，研究计算（3）查找不依赖于通eyxmodn的快速算法。 用计算机的求

8．判定问题（decision problem）是仅有两个可能的解（“是”或“否”）的问题。判定问题的全部实例之集D存在划分DYN，即解为“是”（“否”）的实例均在

Y（N）。中。比如“正整数n是素数吗？”就是一个判定问题。依赖概率图灵机PTM

（Probobilistic Turing machine, 即带有随机数发生器的DTM）可以定义概率算法（probobilistic algorithem）如下：在PTM上使用算法R求解判定问题。用l[I]记实

（l[I]）例I的规模。如果存在时间复杂度函数T，使得（1）ID，PTM均在T步内停机，

并输出“是”或“否”；（2）IY，PTM输出“是”；（3）在N上的出错概率

pr{ PTM output=\"是\"|I N}1/2

则称R是一个（解判定问题的）概率算法。在网络上查找到实际使用的求（不少于512比特）大素数的计算机源程序，通过调小其内部循环次数的方法（使得对相同的大整数n在调整前后有不相同的输出判决），证实它是一个概率算法。

8．为什么安全性基于NP-完全问题的密码不一定是安全的？

9．说出下列问题的区别与联系：

i) 图灵可计算的

ii) 难处理的

iii) 易处理的

iv) 确定性多项式时间

v) 实际有效的

10．为什么说一次一密加密抗窃听是无条件安全的？

11．虽然简单代换密码和换位密码对频度分析攻击是十分脆弱的，为什么它们仍被广泛使

用在现代加密方案和密码协议中？

12．加密算法为什么不应该包含秘密设计部分？