现代密码学基础部分习题参考答案 习题一 1.【答】密码体制、单向函数与伪随机序列生成器、数字签名与杂凑函数、消息认证和身份识别、抗欺骗协议和零知识证明。 2.【答】安全性定义有两种：基于信息论的方法和基于计算复杂性理论的方法 3.【答】密码分析（或称攻击）可分为下列四类： 唯密文分析（攻击），密码分析者取得一个或多个用同一密钥加密的密文； 已知明文分析（攻击），除要破译的密文外，密码分析者还取得一些用同一密钥加密的明密文对； 选择明文分析（攻击），密码分析者可取得他所选择的任何明文所对应的密文（当然不包括他要恢复的明文），这些明密文对和要破译的密文是用同一密钥加密的； 选择密文分析（攻击），密码分析者可取得他所选择的任何密文所对应的明文（要破译的密文除外），这些密文和明文和要破译的密文是用同一解密密钥解密的，它主要应用于公钥密码体制。 4.【答】不严格地说，一个单向函数是一个函数，由x计算函数值y是容易的，但由y计算函数的逆是困难的（在某种平均意义下），“容易”和“困难”的确切含意由计算复杂性理论定义。单向函数是现代密码学的一个基本工具，大部分安全的密码系统（包括协议）的构造依赖于“单向函数存在”这一假设，所以十分重要。 5.【答】现在网络上应用的保护信息安全的技术如数据加密技术、数字签名技术、消息认证与身份识别技术、防火墙技术以及反病毒技术等都是以密码学为基础的。电子商务中应用各种支付系统如智能卡也是基于密码学来设计的，可以说密码学是信息安全技术的基础。由此可见现代密码学的应用非常广泛。现在任何企业、单位和个人都可以应用密码学来保护自己的信息安全。 习题二 1.【答】将（help me）转换为整数（7 4 11 15 12 4），利用c=5m+7(mod 26)得到密文整数（16 1 10 4 15 1），得到密文（qbkepb）。 2.【答】解密变换为d＝15y-30（mod 26），（VMWZ）转换为整数为（21 12 22 25），得到明文整数（25 20 14 7），得到密文（ZUOH）。 3.【答】使用统计特性分析 4.【答】密钥为（12 0 19 17 8 23）明文为（1 4 8 9 8 13）（6 20 13 8 21 4 ）（17 18 8 19 24 14）（5 15 14 18 19 18 ）（0 13 3 19 4 11 ）（4 2 14 12 12 20）（13 8 2 0 19 8）（14 13 18），密文为（13 4 1 0 16 10）（18 20 6 25 3 1）（2 18 1 10 6 11）（17 15 7 9 1 5）（12 13 22 10 12 8）（16 2 7 3 20 17）（25 8 21 17 1 5）（0 13 11）密文：nebaqksugzdbcsbkglrphjbfmnwkmiqchdurzivrbfanl。 6.【答】，密文：qlzj 习题三 1.【答】H(M)＝ 2.【答】H(M)＝ H(K)＝ 密文空间概率分布：  根据公式可分别求得H(C)、H(M|C)、H(K|C) 习题七 1.【答】输出序列为：000111101011001…… 4.【答】设明文为（0，1，0，0，0，1，0，0，0，1），密文为（1，0，1，0，1，1，0，1，1，0）。破译者计算得到密钥序列为，则从线性移位寄存器的结构很容易得到下列矩阵方程式 ， 所以。 可以得到，所以特征多项式。 6.【答】输出序列为：110111101111011110…… 周期为10 习题八 3.【答】IP变换后 L0＝ R0＝ K1＝ L1＝R0； R1＝L0⊕f（R0，K1） 习题九 1.【答】一个公钥密码体制是这样的一个5元组{M,C,，E，D}，且满足如下的条件： 1.M是可能消息的集合； 2.C是可能的密文的集合； 3. 密钥空间是一个可能密钥的有限集； 4．对每一个={，}K，都对应一个加密算法EE, E:MC和解密算法DD,D:CM,满足对于任意的mM,都有c= E（m）,m= D(c)=D(E（m）)=m； 5．对于所有的K，在已知E的情况下推出D是计算上不可能的； 4.【答】，10＝2×5，所以p=2，q＝5，φ(n)＝4 则5d＝1（mod 4），gcd(d, 4)＝1 则d＝5，m＝5 5.【答】:y=x+17，已知其上的点P=(-2,3),P=(2,5) （a）设 P1＋P2＝（x, y），则=＝1/2 x=-x-x＝1/4 y=(x-x)-y.＝－33/8 （b）设2P1＝（x, y）则=＝2 x=-x-x＝4 y=(x-x)-y＝－11 （c）－P1＝（－2，－3） 6.【答】 （1）Y=9=g(mod P)＝2(mod 11)，则X＝6 （2）K=(X)(mod P)＝(3)(mod 11)＝3 7.【答】GF(23)域上的，则＝4，＝5，p＝23 计算modp,i[0,m-1]，按第二个坐标排序m个有序对（i, modp），得到表T＝  计算modp,j[0,m-1]，按第二个坐标排序m个有序对（j, modp），得到表T.  从T、T中分别各自寻找一对（3,10）T和（1,10）T定义 log=mi+jmod(p-1)＝4＋22mod22＝4 习题十 1.【答】一个签名方案是一个5元组（M,A, K,S,V）,满足如下的条件： M是一个可能消息的有限集； A是一个可能签名的有限集； 密钥空间K是一个可能密钥的有限集； 对每一个=（，）K，都对应一个签名算法SigS和验证算法VerV。每一个Sig: M A和Ver: M A{TRUE ,FALSE}是一个对每一个消息x M和每一个签名yA满足下列方程的函数： Ver(x,y)= 对每一个K，函数Sig和Ver都是为多项式时间可计算的函数。Ver是一个公开函数，称作公钥；而Sig是一个秘密函数，称作私钥，由用户秘密地保存。 2.【答】 R=modp S=s+s+…+smodp-1 Rg＝modp×＝modp× ＝×＝ ＝＝＝y 5.【答】可以基于离散对数问题建立盲签名 习题十一 1.【答】（modp） 则，所以 2.【答】 4.【答】（x）=(( x)( x))＝（x’）=(( x’)( x’)) 令y＝( x)( x)，y’＝ ( x’)( x’) 习题十二 1.【答】识别（identification）和身份验证（authentication）是不同的。当说到身份验证时，通常存在一些承载信息的消息在通信双发之间交换，其通信的一方或双方需要被验证。识别（有时称为实体验证）是对一个用户身份的实时验证，它不需要交换承载信息的消息。 2.【答】一个安全的识别协议至少应该满足以下两个条件： 证明者A能向验证者B证明他的确是A； 在证明者A向验证者B证明他的身份后，验证者B没有获得任何有用的信息，B不能模仿A向第三方证明他是A。 3.【答】 由于＝，则  4.【答】有一个标准的方法可将一个识别协议转化为一个签名方案。基本的观点是用一个公开的Hash函数来代替验证者B。 5.【答】针对一般交互式用户身份证明协议，都必须满足以下三种性质。 完全性（Completeness）：若用户与验证者双方都是诚实地执行协议，则有非常大的 概率（趋近于1），验证者将接受用户的身份。 健全性或合理性（Soundness）：若用户根本不知道与用户名字相关的密钥，且验证者是诚实的，则有非常大的概率，验证者将拒绝接受用户的身份。 隐藏性（Witness hiding）：若用户是诚实的，则不论协议进行了多少次以及不论任何 人（包括验证者）都无法从协议中推出用户的密钥，并且无法冒充用户的身份。 习题十四 2.【答】 （1），则，所以 （2） 3.【答】设多项式为    则 K＝6 4.【答】即构成(2,3)门限方案。 若知道，可建立方程组  解之得。