西华大学：《密码学 Cryptology》课程教学资源（习题）第1章 概论习题

第1章概论习题 1.就你所在单位的某个信息系统,试做一个概略的安全风险评估。 2.网络上查找出分组秘密码DES(基本型)原程序或资料,回答:DES的密钥空间大小? 3.在国标GB2312的6763个汉字“字符”集上(即取qF=6763),设计仿射密码,计算其密 钥量 4.在中途岛战争前,美军通过散布“中途岛淡水设备发生故障”的消息,在日军密报中确 认了中途岛的代号,从而破译了日军的密报。问:美军的此次密码分析属于哪种破译类型? 5.明文在整个消息空间中的一个很小的区域内,英语中某些字符不相等的频率就是这样 的一个例子。再给出两个也能说明英语明文消息有小的区域分布的例子 6.编制欧几里德算法程序求 gcd(u,v),假设初值满足0<uv≤N=20-1 7.假设x,e,n均为正整数(x<n),(1)如果n2x不超过计算机语言某基本变量类型允许记 录的最大整数,研究计算y= moan的快速算法;(2)如果n达到计算机语言某基本变 量类型允许记录的最大整数的32倍,研究计算y= x modn的快速算法;(3)查找不依赖 于通用计算机的求y= x mod n的快速算法 8.判定问题( decision problem)是仅有两个可能的解(“是”或“否”)的问题。判定问题∏ 的全部实例之集Dn存在划分D1=n+Nn,即解为“是”(“否”)的实例均在n(Nn) 中。比如“正整数n是素数吗?”就是一个判定问题。依赖概率图灵机PIM( Probabilistic Turing machine,即带有随机数发生器的DIM)可以定义概率算法( probabilistic algorithem) 如下:在PIM上使用算法R求解判定问题∏。用门]记实例的规模。如果存在时间复杂 度函数T,使得(1)V∈Dn,PM均在T(/p步内停机,并输出“是”或“否”(2) V∈Y,PIM输出“是”;(3)在Nn上的出错概率 P{ PTMoutput="是"|I∈Nn}≤l2 则称R是一个(解判定问题∏的)概率算法。在网络上查找到实际使用的求(不少于512 比特)大素数的计算机源程序,通过调小其内部循环次数的方法(使得对相同的大整数n在 调整前后有不相同的输出判决),证实它是一个概率算法

第1章 概论 习题 1．就你所在单位的某个信息系统，试做一个概略的安全风险评估。 2．网络上查找出分组秘密码 DES（基本型）原程序或资料，回答：DES 的密钥空间大小？ 3．在国标 GB2312 的 6763 个汉字“字符”集上（即取 q=6763），设计仿射密码，计算其密 钥量。 4．在中途岛战争前，美军通过散布“中途岛淡水设备发生故障”的消息，在日军密报中确 认了中途岛的代号，从而破译了日军的密报。问：美军的此次密码分析属于哪种破译类型？ 5．明文在整个消息空间中的一个很小的区域内，英语中某些字符不相等的频率就是这样 的一个例子。再给出两个也能说明英语明文消息有小的区域分布的例子。 6．编制欧几里德算法程序求 gcd( ) u,v ，假设初值满足 1024 0 < 2 -1 u,v N =  。 7．假设 x e n , , 均为正整数 ( ) x n  ，（1）如果 2 n x 不超过计算机语言某基本变量类型允许记 录的最大整数，研究计算 mod e y x n = 的快速算法；（2）如果 n 达到计算机语言某基本变 量类型允许记录的最大整数的 32 倍，研究计算 mod e y x n = 的快速算法；（3）查找不依赖 于通用计算机的求 mod e y x n = 的快速算法。 8．判定问题（decision problem）是仅有两个可能的解（“是”或“否”）的问题。判定问题  的全部实例之集 D 存在划分 D Y N    = + ，即解为“是”（“否”）的实例均在 Y N   （ ）。 中。比如“正整数 n 是素数吗？”就是一个判定问题。依赖概率图灵机 PTM（Probobilistic Turing machine, 即带有随机数发生器的 DTM）可以定义概率算法（probobilistic algorithem） 如下：在 PTM 上使用算法 R 求解判定问题  。用 l I[ ] 记实例 I 的规模。如果存在时间复杂 度函数 T，使得（1）  I D ，PTM 均在 T l I （ [ ]） 步内停机，并输出“是”或“否”；（2）  I Y ，PTM 输出“是”；（3）在 N 上的出错概率 { PTM output = " " | } 1/2 r p I N 是    则称 R 是一个（解判定问题  的）概率算法。在网络上查找到实际使用的求（不少于 512 比特）大素数的计算机源程序，通过调小其内部循环次数的方法（使得对相同的大整数 n 在 调整前后有不相同的输出判决），证实它是一个概率算法

8.为什么安全性基于NP完全问题的密码体制不一定是安全的? 9.说出下列问题的区别与联系: i)图灵可计算的 i)难处理的 i)易处理的 ⅳ)确定性多项式时间 v)实际有效的 10.为什么说一次一密加密抗窃听是无条件安全的? 11.虽然简单代换密码和换位密码对频度分析攻击是十分脆弱的,为什么它们仍被广泛使 用在现代加密方案和密码协议中? 12.加密算法为什么不应该包含秘密设计部分?

8．为什么安全性基于NP-完全问题的密码体制不一定是安全的？ 9．说出下列问题的区别与联系： i) 图灵可计算的 ii) 难处理的 iii) 易处理的 iv) 确定性多项式时间 v) 实际有效的 10．为什么说一次一密加密抗窃听是无条件安全的？ 11．虽然简单代换密码和换位密码对频度分析攻击是十分脆弱的，为什么它们仍被广泛使 用在现代加密方案和密码协议中？ 12．加密算法为什么不应该包含秘密设计部分？