北京邮电大学：《现代密码学基础》课程教学资源_习题参考答案

现代密码学基础部分习题参考答案 习题一 1.【答】密码体制、单向函数与伪随机序列生成器、数字签名与杂凑函数、消息认证和身份 识别、抗欺骗协议和零知识证明 2.【答】安全性定义有两种:基于信息论的方法和基于计算复杂性理论的方法 3.【答】密码分析(或称攻击)可分为下列四类 1)唯密文分析(攻击),密码分析者取得一个或多个用同一密钥加密的密文; 2)已知明文分析(攻击),除要破译的密文外,密码分析者还取得一些用同一密钥加 密的明密文对 3)选择明文分析(攻击),密码分析者可取得他所选择的任何明文所对应的密文(当 然不包括他要恢复的明文),这些明密文对和要破译的密文是用同一密钥加密的 4)选择密文分析(攻击),密码分析者可取得他所选择的任何密文所对应的明文(要 破译的密文除外),这些密文和明文和要破译的密文是用同一解密密钥解密的,它 主要应用于公钥密码体制。 4.【答】不严格地说,一个单向函数是一个函数y=f(x),由x计算函数值y是容易的, 但由y计算函数的逆x=f-(y)是困难的(在某种平均意义下),“容易”和“困难”的确 切含意由计算复杂性理论定义。单向函数是现代密码学的一个基本工具,大部分安全的密码 系统(包括协议)的构造依赖于“单向函数存在”这一假设,所以十分重要 5.【答】现在网络上应用的保护信息安全的技术如数据加密技术、数字签名技术、消息认证 与身份识别技术、防火墙技术以及反病毒技术等都是以密码学为基础的。电子商务中应用各 种支付系统如智能卡也是基于密码学来设计的,可以说密码学是信息安全技术的基础。由此 可见现代密码学的应用非常广泛。现在任何企业、单位和个人都可以应用密码学来保护自己 的信息安全 习题二 1.【答】将( help me)转换为整数(741115124),利用c=5m+7mod26)得到密文整数(16 1104151),得到密文( qbkepb) 2.【答】解密变换为d=15y-30(mod26),(VMWZ)转换为整数为(21122225),得到明 文整数(2520147),得到密文(ZUOH) 3.【答】使用统计特性分析 4.【答】密钥为(1201917823)明文为(1489813)(620138214)(17188192414) (51514181918)(013319411)(4214121220)(13820198)(141318),密文为 (134101610)(182062531)(218110611)(17157915)(12132210128)(1627 3 20 17)(258 1715)(013 11)X: nebagksugzdbcsbkglrphjbfmnwkmiqchdurzivrbfanl (14)()=(1611) 【答】 密文:qlz 习题三

现代密码学基础部分习题参考答案 习题一 1.【答】密码体制、单向函数与伪随机序列生成器、数字签名与杂凑函数、消息认证和身份 识别、抗欺骗协议和零知识证明。 2.【答】安全性定义有两种：基于信息论的方法和基于计算复杂性理论的方法 3.【答】密码分析（或称攻击）可分为下列四类： 1） 唯密文分析（攻击），密码分析者取得一个或多个用同一密钥加密的密文； 2） 已知明文分析（攻击），除要破译的密文外，密码分析者还取得一些用同一密钥加 密的明密文对； 3） 选择明文分析（攻击），密码分析者可取得他所选择的任何明文所对应的密文（当 然不包括他要恢复的明文），这些明密文对和要破译的密文是用同一密钥加密的； 4） 选择密文分析（攻击），密码分析者可取得他所选择的任何密文所对应的明文（要 破译的密文除外），这些密文和明文和要破译的密文是用同一解密密钥解密的，它 主要应用于公钥密码体制。 4.【答】不严格地说，一个单向函数是一个函数 y = f (x) ，由 x 计算函数值 y 是容易的， 但由 y 计算函数的逆 ( ) 1 x f 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.【答】 ) (25 9) 3 7 4 9 (18 19)( ) (16 11) 3 7 4 9 (1 4)( = = ，密文：qlzj 习题三

1.【答】H(M)=-(1/4*b\*2+1/8*bg,1 2.【答】HM=-(1/3*kg21+815*b2+215*k +3/16*2*bog 8 H(K)=-(12+bg21+14*2+kog21 密文空间概率分布: 1234 1/57/2017/601/6 根据公式可分别求得H(C)、HMC)、H(KC 习题七 1.【答】输出序列为:000111100101 4.【答】设明文m为(0,1,0,0,0,1,0,0,0,1),密文c为(1,0,1,0,1,1,0, 1,1,0)。破译者计算m⊕c得到密钥序列为 k=(k1,k2,…,k6,k,ks3,k,k10)=(1,110,1,0,0,1,1,1),则从线性移位寄存器的结构很容 易得到下列矩阵方程式 k, k2, k2k,ksc=ks Lk3k4kc2」k 所以110c1=1。 01lc2 可以得到c0=1,c1=0,c2=1,所以特征多项式p(x)=x3+x2+1。 6.【答】输出序列为:11011111110 周期为10 习题八 10011010 01110111 11010010 3.【答】P变换后111100 0 1101 000 10001000

1.【答】H(M)＝ ) 16 3 3/16* 2*log 8 1 * 2 1/ 8*log 4 1 − (1/ 4*log 2 + 2 + 2 2.【答】H(M)＝ ) 15 2 2 /15*log 15 8 8/15*log 3 1 − (1/ 3*log 2 + 2 + 2 H(K)＝ ) 4 1 1/ 4* 2*log 2 1 − (1/ 2*log 2 + 2 密文空间概率分布： 1/ 5 7 / 20 17 / 60 1/ 6 1 2 3 4 根据公式可分别求得 H(C)、H(M|C)、H(K|C) 习题七 1.【答】输出序列为：000111101011001…… 4.【答】设明文 m 为（0，1，0，0，0，1，0，0，0，1），密文 c 为（1，0，1，0，1，1，0， 1 ， 1 ， 0 ） 。 破 译 者 计 算 mc 得 到 密 钥 序 列 为 ( , ,..., , , , , ) (1, 1,1,0, 1, 0, 0, 1,1,1,1) k = k1 k2 k6 k7 k8 k9 k10 = ，则从线性移位寄存器的结构很容 易得到下列矩阵方程式           =                     6 5 4 2 1 3 4 5 2 3 4 1 2 3 0 k k k c c c k k k k k k k k k ， 所以           =                     0 1 0 1 0 1 1 1 0 1 1 1 2 1 0 c c c 。 可以得到 c0 =1, c1 = 0, c2 =1 ，所以特征多项式 ( ) 1 3 2 p x = x + x + 。 6.【答】输出序列为：110111101111011110…… 周期为 10 习题八 3.【答】IP 变换后                           1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1

l1010110 10=11010010 R0=10100101 0 00100101 0111 0 11000 1 0 111010 00100 0 00 LI=RO: RI=Loef (RO, K1 习题九 1.【答】一个公钥密码体制是这样的一个5元组C,K,Ex,Dx}且满足如下的条件: 1M是可能消息的集合; 2C是可能的密文的集合 3.密钥空间K是一个可能密钥的有限集 4.对每一个K={k1,K2}∈K,都对应一个加密算法Ek,∈E,EK,M→C和解密算法 Dk2∈DDk2C→M满足对于任意的m∈M都有c=Ek,(m,m=Dk2()=Dk2Ek,m)=m 5.对于所有的K∈K,在已知Ex的情况下推出Dx是计算上不可能的 4【答】m3(mod35)=10,10=2×5,所以p=2,q=5,中(n)=4 AI 5d=1(mod 4), ged(d, 4)=1 则d=5,m=5 5.【答】y2=x32+17,已知其上的点P1=-2,3)P2=(2.5) (a)设P1+P2=(x,y3),则2=2-y=12 (x1-x3)y 33/8 (b)设2P1=(x3,y3)则23x2+0=2 2 y

L0＝                 0 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 R0＝                 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 K1＝                           1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 L1＝R0； R1＝L0⊕f（R0，K1） 习题九 1.【答】一个公钥密码体制是这样的一个5元组{M,C, K ，E K ，D K }，且满足如下的条件： 1.M 是可能消息的集合； 2.C 是可能的密文的集合； 3. 密钥空间 K 是一个可能密钥的有限集； 4．对每一个  ={  1， 2 }  K，都对应一个加密算法 E K1  E, E K1 :M → C 和解密算法 D K2  D,D K2 :C → M,满足对于任意的m  M,都有c= E K1 （m）,m= D K2 (c)=D K2 (E K1 （m）)=m； 5．对于所有的   K，在已知 E K 的情况下推出 D K 是计算上不可能的； 4.【答】 (mod 35) 10 5 m = ，10＝2×5，所以 p=2，q＝5，φ(n)＝4 则 5d＝1（mod 4），gcd(d, 4)＝1 则 d＝5，m＝5 5.【答】:y 2 =x 3 +17，已知其上的点 P 1 =(-2,3),P 2 =(2,5) （a）设 P1＋P2＝（x 3 , y 3 ），则  = 2 1 2 1 x x y y − − ＝1/2 x 3 =  2 -x 1 -x 2 ＝1/4 y 3 =  (x 1 -x 3 )-y 1 .＝－33/8 （b）设 2P1＝（x 3 , y 3 ）则  = 1 2 1 2 3 y x + a ＝2

y3=(x1-x3) 6.【答】 (1)Y=9=g (mod P)=2(mod 11),X,=6 (2)K=(X)(modP)=(3)°(mod1)=3 7.【答】GF(23)域上的bg54,则B=4,a=5,p=23 (1)计算 anode,i∈[0.m-],按第二个坐标排序m个有序对( i a modp), 得到表T1 22216411819610392014211787121551311 12345678910111213141516171819202122 (2)计算β a"modp, j∈0,m-1],按第二个坐标排序m个有序对(j Ba-modp),得到表T 42102238 176125918191411211315 12345678910111213141516171819202122 (3)从T1、T2中分别各自寻找一对(3,10)∈T1和(1,10)∈T2定义 log b=mi+jmod(p-1)=4+22mod22=4 习题十 1.【答】一个签名方案是一个5元组(MA,K,S,),满足如下的条件 (1)M是一个可能消息的有限集 (2)A是一个可能签名的有限集 (3)密钥空间K是一个可能密钥的有限集 (4)对每一个K=(k1,k2)∈K,都对应一个签名算法Sgk2∈S和验证算法werk,eV 每一个Sigk,:M→>A和Verx:M×A→>{ TRUE FALSE}是一个对每一个消息x∈ M和每一个签名y∈A满足下列方程的函数 TRUE当y=Sgk,(x) 1FALS当y≠sgk(x) 对每一个K∈K,函数Sigk,和Verk,都是为多项式时间可计算的函数。werk,是一个公开函

x 3 =  2 -x 1 -x 2 ＝4 y 3 =  (x 1 -x 3 )-y 1＝－11 （c）－P1＝（－2，－3） 6.【答】 （1）Y A =9=g x (mod P)＝2 x (mod 11)，则 X A ＝6 （2）K=(X ' ) x (mod P)＝(3) 6 (mod 11)＝3 7.【答】GF(23)域上的 log 5 4 ，则  ＝4， ＝5，p＝23 （1）计算  mi modp,i  [0,m-1]，按第二个坐标排序 m 个有序对（i,  mi modp）， 得到表 T 1＝         2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2 16 4 1 18 19 6 10 3 9 20 14 21 17 8 7 12 15 5 13 11 1 22 （2）计 算   − j modp,j  [0,m-1] ，按第二个坐标排序 m 个有序对（ j,   − j modp），得到表 T 2 .         2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2 10 22 3 8 7 20 16 1 17 6 12 5 9 18 19 14 11 21 13 15 1 4 （3）从 T 1 、T 2 中分别各自寻找一 对（3,10）  T 1 和（1,10）  T 2 定义 log   =mi+jmod(p-1)＝4＋22mod22＝4 习题十 1.【答】一个签名方案是一个 5 元组（M,A, K,S,V）,满足如下的条件： (1) M 是一个可能消息的有限集； (2) A 是一个可能签名的有限集； (3) 密钥空间 K 是一个可能密钥的有限集； (4) 对每一个  =（ 1 k ， 2 k ）  K，都对应一个签名算法 Sig K2  S 和验证算法 Ver K1  V。 每一个 Sig K2 : M → A 和 Ver K1 : M  A → {TRUE ,FALSE}是一个对每一个消息 x  M 和每一个签名 y  A 满足下列方程的函数： Ver(x,y)=     = y ( ) ( ) 2 2 FALSE Sig x TRUE y Sig x K K 当 当 对每一个   K，函数 Sig K2 和 Ver K1 都是为多项式时间可计算的函数。Ver K1 是一个公开函

数,K1称作公钥;而Sgk,是一个秘密函数,K2称作私钥,由用户秘密地保存。 2.【答】 R Rg-门m×g,如m)-(gym×g2 ∑xmdp-1)∑smdp-1)∑ ∑x1(R+m)md(p-1) g3) 5.【答】可以基于离散对数问题建立盲签名 习题十 1.【答】e-g2≡e"g(modp) 则x+x2log,g=x3+x:log,g,所以kg,g=3-x 1459-7431 2.【答】bog1542307= 5564-954 4.【答】h2(x)=h1(h1(x1)h1(x2)=h2(x2)=h1(h1(x1)h1(x2”) 令y=h(x1)h1(x2),y=h(x1)h1(x2”) 习题十二 1.【答】识别( identification)和身份验证( authentication)是不同的。当说到身份验证时, 通常存在一些承载信息的消息在通信双发之间交换,其通信的一方或双方需要被验证。识别 (有时称为实体验证)是对一个用户身份的实时验证,它不需要交换承载信息的消息。 2.【答】一个安全的识别协议至少应该满足以下两个条件: 1)证明者A能向验证者B证明他的确是A 2)在证明者A向验证者B证明他的身份后,验证者B没有获得任何有用的信息,B 不能模仿A向第三方证明他是A 3.【答】 由于X=y2ymdn=y4101360°=y2336056°(mdn),则 y=m0=101360modn)

数， K1 称作公钥；而 Sig K2 是一个秘密函数， K2 称作私钥，由用户秘密地保存。 2.【答】 R= = n i r i i r 1 modp S=s 1 +s 2 +…+s n modp-1 Rg S ＝= n i r i i r 1 modp× s1+s2+...+snmod( p−1) g ＝= n i x r i i g 1 ( ) modp× mod( 1) 1  − = s p n i i g ＝ = − n i xi ri p g 1 mod( 1) × mod( 1) 1  − = s p n i i g ＝ = + − n i si xi ri p g 1 ( ) mod( 1) ＝ x (R+m' ) mod( 1) 1  i − = p n i g ＝ = + n i x R m g p i 1 ' ( ) mod ＝y m +R ' 5.【答】可以基于离散对数问题建立盲签名 习题十一 1.【答】 1 2 x x e g  3 4 x x e g （modp） 则 x1 + x2 log e g = x3 + x4 log e g ，所以 2 4 3 1 log x x x x e g − − = 2.【答】 5564 954 1459 7431 log154 2307 − − = 4.【答】 2 h （x）= 1 h ( 1 h ( x 1 ) 1 h ( x 2 ))＝ 2 h （x’）= 1 h ( 1 h ( x 1 ’) 1 h ( x 2 ’)) 令 y＝ 1 h ( x 1 ) 1 h ( x 2 )，y’＝ 1 h ( x 1 ’) 1 h ( x 2 ’) 习题十二 1.【答】识别（identification）和身份验证（authentication）是不同的。当说到身份验证时， 通常存在一些承载信息的消息在通信双发之间交换，其通信的一方或双方需要被验证。识别 （有时称为实体验证）是对一个用户身份的实时验证，它不需要交换承载信息的消息。 2.【答】一个安全的识别协议至少应该满足以下两个条件： 1） 证明者 A 能向验证者 B 证明他的确是 A； 2） 在证明者 A 向验证者 B 证明他的身份后，验证者 B 没有获得任何有用的信息，B 不能模仿 A 向第三方证明他是 A。 3.【答】 由于 X v y n e b = mod ＝ 101360 36056 (mod ) 456 257 v v n b b  ，则 36056(mod ) 101360(mod ) 257 456 y rm n y rm n = = = =

4【答】有一个标准的方法可将一个识别协议转化为一个签名方案。基本的观点是用一个公 开的Hash函数来代替验证者B 5.【答】针对一般交互式用户身份证明协议,都必须满足以下三种性质 (1)完全性( Completeness):若用户与验证者双方都是诚实地执行协议,则有非常大 的 概率(趋近于1),验证者将接受用户的身份。 (2)健全性或合理性( Soundness):若用户根本不知道与用户名字相关的密钥,且验证 者是诚实的,则有非常大的概率,验证者将拒绝接受用户的身份 (3)隐藏性( Witness hiding):若用户是诚实的,则不论协议进行了多少次以及不论任 何 人(包括验证者)都无法从协议中推出用户的密钥,并且无法冒充用户的身份 习题十 四 2.【答】 (1)b=a"modp,则9=2modl1,所以a=6 (2)kuy =a t mod p=by od p=3 mod 11=3 3.【答】设多项式为h(x)=a2x2+a1x+a (x-2)x-3)。(x-2)x-3) 8 =8·(2mod17)(x-2x-3) (1-2)(1-3) (-1)-2) 8·9(x-2x-3)=72(x-2x-3) (x-1)(x-3)(x-1)(x-3) =7·(-1)modl7)(x-1)(x-3) (1)(-1) 7·16(x-1)(x-3)=112(x-1)x-3) (x-1)(x-2)n(x-2)x-1) (3-2)(3-1) 10·9(x-2)(x-1)=90(x-2(x-1) 则h(x)=2x2-14x+6 K=6 4.【答】{76)(9,3)(14)即构成(23门限方案。 若知道{7.6)(9,3)},可建立方程组 三 3mod9≡k 解之得k≡(9×4×6+7×4×3)mod63=48

4.【答】有一个标准的方法可将一个识别协议转化为一个签名方案。基本的观点是用一个公 开的 Hash 函数来代替验证者 B。 5.【答】针对一般交互式用户身份证明协议，都必须满足以下三种性质。 （1） 完全性（Completeness）：若用户与验证者双方都是诚实地执行协议，则有非常大 的 概率（趋近于 1），验证者将接受用户的身份。 （2） 健全性或合理性（Soundness）：若用户根本不知道与用户名字相关的密钥，且验证 者是诚实的，则有非常大的概率，验证者将拒绝接受用户的身份。 （3） 隐藏性（Witness hiding）：若用户是诚实的，则不论协议进行了多少次以及不论任 何 人（包括验证者）都无法从协议中推出用户的密钥，并且无法冒充用户的身份。 习题十四 2.【答】 （1） b p aU U =  mod ，则 9 2 mod11 aU = ，所以 aU = 6 （2） mod mod 3 mod11 3 6 k , = p = b p = = U V aU V a a U V  3.【答】设多项式为 1 0 2 2 h(x) = a x + a x + a 8 9( 2)( 3) 72( 2)( 3) 8 (2 mod17) ( 2)( 3) ( 1)( 2) ( 2)( 3) 8 (1 2)(1 3) ( 2)( 3) 8 1 =  − − = − − =   − − − − − − = − − − − − x x x x x x x x x x 7 16( 1)( 3) 112( 1)( 3) 7 (( 1) mod17) ( 1)( 3) (1)( 1) ( 1)( 3) 7 (2 1)(2 3) ( 1)( 3) 7 1 =  − − = − − =  −  − − − − − = − − − − − x x x x x x x x x x 10 9( 2)( 1) 90( 2)( 1) 10 (2 mod 17) ( 2)( 1) (1)(2) ( 2)( 1) 10 (3 2)(3 1) ( 1)( 2) 10 1 =  − − = − − =   − − − − = − − − − − x x x x x x x x x x 则 ( ) 2 14 6 2 h x = x − x + K＝6 4.【答】 (7,6),(9,3),(11,4) 即构成(2,3)门限方案。 若知道 (7,6),(9,3) ，可建立方程组      ' ' 3mod 9 6mod 7 k k 解之得 (9 4 6 7 4 3)mod 63 48 ' k    +   