现代密码学-复习题-答案

（一）信息的载体有（媒质）和（信道）。对信息载体的两种攻击为（被动攻击）和（主动

攻击）。密码学的两个分支是（密码编码学）和［密码分析学）。密码体制有（单钥密码体

质）和（双钥密码体质）。现代流密码的设计思想来源于古典密码中的（维吉尼亚密码）。

现代分组密码的设计思想来源于古典密码中的（多字母代换密码）。

（二）在信息保密系统中，攻击者Eve所拥有的根本资源有哪些？

Eve在不平安的公共信道上截获了密文Co

Eve知道加密算法E和解密算法Do

攻击者Eve可能拥有的更多资源有哪些？

Eve可能知道密文c所对应的明文m。（此时所进行的攻击称为明文攻击）

Eve可能拥有强大的计算能力。

Eve可能缴获了一台加密机（也称为加密黑盒子），可以任意地输入明文，输出密文。（此时

所进行的攻击称为选择明文攻击）

攻击者Eve不可能拥有的资源是什么？

Eve不知道加密密钥z和解密密钥鼠

（事实上，在进行平安性分析时，有时也假设Eve知道了密钥的一局部，但决不能全部知

道）

（三）表达明文攻击。

设攻击者Eve截获了密文c,并且知道了密文c所对应的明文m。（这种情况是怎样发生的

呢？当明文m是已经过期的消息，可能无法再保密，也可能必须将其公开。因此，这种情

况是经常发生的）于是：

,在解密方程m=O（c,k）中，Eve知道m和c,仅仅不知道解密密钥k。

,在加密方程c=E（m,z）中，Eve知道m和c,仅仅不知道加密密钥z。

•如果Eve从解密方程m=D（c,k）中计算出解密密钥k,那么Eve今后就可以像Bob一

样对任何密文J进行解密：m=DC,k）。

•如果Eve从加密方程c=E（m,z）中计算出加密密钥z,那么Eve今后就可以像Alice一

样对任何明文而进行加密：&E（gz）o

•还可以给更加宽松的条件。设攻击者Eve获得了以往废弃的n组明文/密文对：（mi，

q）,（m2，C2）,…，tmn,cn）0

•于是Eve获得了关于解密密钥k的方程组：

,mi=D（Ci,k）,

•rri2=D（C2,k）,

*mn=D(Cn,k)°

•S越大，解密密钥k就越容易确定。)

(四)表达无条件平安性。

对密码体制的任何攻击，都不优于(对明文)完全盲目的猜想，这样的密码体制就称为无

条件平安的(或完善保密的)。

什么样的加解密方式能够实现无条件平安性？

一次一密的加密方式容易实现无条件平安性。因为密钥时时更新，所以以往得到的任何明

文/密文对，对于破译新的密文没有任何帮助，只能做完全盲目的猜想。

(五)表达计算平安性。

计算平安是一个模糊的概念。我们可以给出以下三个级别的定义。

(1)对密码体制的任何攻击，虽然可能优于完全盲目的猜想，但超出了攻击者的计算能力。

这是最高级别的计算平安。

(2)对密码体制的任何攻击，虽然可能没有超出攻击者的计算能力，但所付出的代价远远

大于破译成功所得到的利益。这是第二级别的计算平安。

[3)对密码体制的任何攻击，虽然可能没有超出攻击者的计算能力，但破译成功所需要的

时间远远大于明文本身的有效期限。这也是第二级别的计算平安。

什么样的加解密方式能够实现计算平安性？

(六)设明文x,密文y,密钥zi，密钥Z2,均为8比特课文。加密算法为片(x*z""+"z2。

其中'"表示逐位(mod2)加法运算：”+"表示(mod28)加法运算。

试用2个明文/密文对解出密钥Z1和Z2各自的最低位，其中明文可以任意选择。你选择什

么明文？怎样解出？

在解出密钥Z1和Z2各自的最低位以后，试用2个明文/密文对解出密钥Z1和Z2各自的次最

低位，其中明文可以任意选择。你选择什么明文？怎样解出？

使用选择明文攻击，多少个经过选择的明文/密文对可以解出密钥Z1和Z2?

(七)设明文(X1X2X3X4X5),密文(yiy2y3y4y5)，密钥45x5阶方阵),密钥(bib2b3b4b5),满足域

GF(2)上的如下加密方程：

(yiy2y3y4y5)=(x1x2x3x4x5)4+(6162636465)。

取6组明文/密文对：

(00000)/(10110),(10000)/(01110),(01000)/(11010),

(00100)/(10000),(00010)/(10101),(00001)/(00111)o

试解出密钥A和密钥（bib2b3b4b5）。

此加密方程能够唯一解密吗？为什么？

（八）表达Golomb随机性假设（三条假设）。

（1）当。充分大时，kik2k3...心中0和1的个数各占约一半。

（2）当。充分大时，在kik2k3...kn中,长度为/的比特串10...01（称为0游程）的个数约

有个；长度为/的比特串01...10（称为1游程）的个数约有n〃个。

（3）假设Q0,当“充分大时，以下的值（称为异相自相关函数值）约为0。

（九）答复以下问题：

1.一个周期的布尔序列一定是线性反应移位存放器序列吗？为什么？

定理如果一个比特流是一个周期序列，那么它一定是线性反应移位存放器序列。

证明设比特流k的最小周期是N。那么

i>N后，ki=ki-No

因此比特流k为/V阶线性反应移位存放器序列，抽头系数为{Cl、C2..........CN}={0、0、...0、

1}（即极小多项式/（x）=l'+'内），初始状态为kik2k3…k.

2.。阶线性反应移位存放器序列的最小周期的上确界是什么？最小周期到达该上确

界的序列称为什么序列？（。阶m序列）当。阶线性反应移位存放器序列的最小周期到达

该上确界时，对Golomb随机性假设的符合程度是怎样的？

完全满足GOLOMB随机性假设.

（3.1）k在自己的一个最小周期内（即连续2"；个比特内），0出现次，1出现2ml

次。

（3.2）取定/,3<j<n,观察k的连续2"-1个长j的比特串:k/k任曲+2…幻+山/=1,2,…,2。-1。

10...01出现2回次；（长为卜2的0游程）

01...10出现2田次。（长为卜2的1游程）

nn

观察k的连续2-l个长n+1的比特串:krki+n，/=1-2-l010...01出现1次。（长为n-1的0

游程）

观察k的连续2"-1个长n+2的比特串:k广ki+n+i，/=1~2n-l.01...10出现1次。（长为n-1的

0游程）

（3.3）对任何1勺42"-2,下式接近0。（自相关函数）

这样的序列为什么不能直接作为密钥流？

不能直接作为密钥流的原因为:EVE如果得到任何一段连续2N个比特，就获得了一个关于抽

头系数的方程组，由于加法和乘法都是在域GF⑵上进行（M0D2运算），容易计算出抽头系数，

从而被攻破。

解法：

如果。阶线性反应移位存放器序列用作密钥流，攻击者Eve截获了密文段C"2c3…C2C，并知

道了对应的明文段m2n>因此计算出了对应的废弃密钥段k、k2k3...k2no

那么Eve获得了关于抽头系数｛Ci、C2............cj的以下方程组。

kl=Clkl.l'+'C2k1-2Cnkl.n，

其中l=n+l,n+2,2n0

注意到这是在有限域GF（2）上的线性方程组，很容易解出抽头系数©、C2............Cn｝o

实际上，当Eve获得了n阶线性反应移位存放器序列的任何一段的连续2n个比特柞如心…

kj+2n，他就获得了关于抽头系数｛Cl、C2............C"｝的以下方程组。

kl=Cikl-i'+'C2k1-2Cnkl-m

其中l=j+n+l,j+n+2,y+2n<,

以上方程组中的加法和乘法都是在域GF（2）上进行的［即（mod2）运算）。

以上事实说明，当Eve获得了。阶线性反应移位存放器序列的任意连续2n个比特，Eve

就获得了整个密钥流。

（3）当一个周期的布尔序列的线性复杂度为。时，该序列的长度为2〃的串就能完全解出

（综合出）该序列。怎样解出？（两种算法）

序列的综合的两种最著名的算法是B-M算法和Games-Chan算法。

（十）当非线性前馈序列用作密钥流时，哪三个局部可能作为通信伙伴的原始密钥？初始

状态，极小多项式，非线性布尔函数。

（十一）分组密码与流密码相比，有什么优点？

［分组密码与流密码相比,优点:加解密算法简洁快速，占用的计算资源小，易于软件和硬件的

实现;加解密算法参数固定，比流密码容易实现标准化;由于明文流被分段加密,因此容易实现

同步,而且传输错误不会向后扩散

有什么缺点？

（不容易使用硬件实现，平安性很难被证明，至多证明局部平安性

分组密码的5个设计准那么是什么？

（平安性，简洁性,有效性，透明性和灵活性，加解密的相似性.）

（十二）写出Feistel网络的算法步骤，并画出图。

将明文m分为等长的两局部m=(L(O),R(0)):

使用由密钥k控制的高度非线性函数F,

(1)计算：

(£；R')=(L(OY+'F(R(O),k),R(0))；

⑵计算密文：c=(L(l),R(l))=

(十三)在DES中，

32比特课文XT扩充变换ET548比特密钥k~>8个S盒932比特课文Y

是可逆的；这就是说，当密钥k确定时，不同的X一定得到不同的九说明这是为什么。

这种可逆性设计有什么意义。

为了使扩充变换£>8个S盒(32比特玲32比特〕整体是一个可逆函数，必须使得8个S

盒总体输出是8个S盒总体输入的第2~5、8~11,14~17、20-23>26~29、32~35、38~41、

44~47比特的可逆函数。(回忆扩充变换E：扩充变换E的作用是将32比特的课文膨胀为

48比特，且扩充变换后的第1、6、7、12、13、18、19、24>25、30、31、36、37、42、

43、48比特为扩充局部。)

(十四)在DES、RijndaeKSafer+中，不具有加解密相似性的有

DES是加解密相似的。

RUNDAEL不是加解密相似的。

SAFER+解密算法就是简单地将加密算法的操作逆向进行。

(十五)IDEA是加解密相似的。设加密算法的密钥子块的标号顺序为

(Z11,Z12,Z13,214)；(Z1S,Z16)；(Z21,Z22,Z23,^24)；(225,^26)；—；

(Z81,Z82,Z83,Z84)；(Z85,Z86)；(Z91,Z92,Z93,Z94)。

现在把解密过程用加密算法来实现，问：第3轮的6个密钥子块依次是什么？

((Z71",-Z73,-Z72,Z74")；(Z65,266))

第8轮的10个密钥子块依次是什么？

((z2T1,-Z23,-Z22,Z24'1)；(Z15,Z16)；(Z11-1,-Z12,<13,Zl「))

在IDEA中，“X”表示(mod216+i)乘法运算。计算215G”2叽(49153)

(十六)写出Rijndael轮函数(普通轮)的四个不同的计算部件名称。

RUNDAEL的轮函数由四个不同的计算部件所组成，分别是：

字节代替(ByteSub)

行移位(ShiftRow)

列混合(MixColumn)

加密钥(AddRoundKey)

设Rijndael的字节代替函数为y=bytesub(x)。计算sub(0)»

(1)首先，将字节看作GFQ8)上的元素，映射到自己的乘法逆；0字节影射到它自身。

(2)其次，将字节看作GF⑵上的8维向量，做如下的(GR2)上的；可逆的)仿射变换：

(11000110)

(十七)

在Safer+中，计算指数盒的值X(0),计算对数盒的值1(0)。

字节内的混淆采用字节非线性可逆变换函数X6和£('),其中X9)称为指数变换，

X(x)=45x(mod257)(mod256),■)是X9)的逆变换，称为对数变换。

X(0)=l

£(0)=128

Safer+线性层变换矩阵M有何特点，为什么这样设计。

线性层是环({0,1汽+(mod256),x(mod256))上的一个16维可逆线性变换，作为字节之间的快

速扩散。

线性层运算就是将输入课文看作环({0*}8,+(mod256),x(mod256))上的16维向量，右乘矩阵

Mo从上式可以看出，矩阵M中的元素都是2的暴，这种设计的目的是使模28乘法运算简

化成为“左移位，右补0”,简单快速。

(十八)写出RSA的密钥生成过程。

密钥的产生：

(1)选择两个保密的大素数P和q；

(2)计算夕(〃)=(厂1)(仁1),其中0(〃)是〃的欧拉函数值；

(3)选一整数e,满足〈e(〃)，且gcd(*(〃)，e)=l；

(4)计算d,满足d*e=\mode®,即d是e在模*(A)下的乘法逆元。因e与。(〃)

互素，模9(力的乘法逆元一定存在；

⑸以匕力为公开钥，{dp,正为秘密钥。

(十九)写出根本RSA的加密过程和解密过程。

加密：加密时首先将明文比特串分组，使得每个分组对应的十进制数小于〃，即分组长度

小于log2〃；然后对每个明文分组创作加密运算：c三/modn；

解密：对密文分组的解密运算为：/»=/modno

(二十)设夕是奇素数，且0是4的倍数加3。设c是一个(mod°)平方剩余。关于未知数

x的二次方程L*(mod夕)一共有几个解？它们怎样计算。

两个解

由题设知左叱是整数,

因为c是模p的二次剩余,

p一\

所以:a2=1(modp)

p+\p-\

a2=a2a=(2(mod〃)

即有土〃4为C模p的两个平方根。

(二十二)设A招Q是两个不同的奇素数的乘积。设C是一个(mod〃)平方剩余。关于未知数

X的二次方程片*(mod.)一共有几个解？如果给出2个不同的解，它们关于(mod。)同余，

关于(modq)不同余，那么能够得到什么结果。

(重要！由题设知，pq必须都是Blum数)

解方程组

显然该方程组有4组解。

其关于(modn)也不同余

(二十二)写出ElGamal的密钥生成过程，加密过程，解密过程。

ElGamal的密钥生成

选择一个大的素数0。

选择g,l<g<p»

选择x,l<x<p-lo

计算产g'modp0

Bob的公钥是(p,g,y),对外公布。

Bob的私钥是x,自己私藏。

ElGamal的加密过程

Alice欲发送明文加给Bob,其中

0<亦夕。

Alice选择随机数A,{k,p—1)=1,计算:

yi=/modp（随机数4被加密）o

再用Bob的公钥力计算：

匕=/〃y"modp（明文被随机数A和公钥y加密）

密文由必、％级连构成，即密文c=yj|%。

ElGamal的解密过程：Bob收到密文。后，用自己的私钥x计算

iipyjy\-m^//=/ng"/g"modp。

（二十三）表达杂凑函数应该满足的3条性质。

1.等长性,2.单向性.3.无碰撞性.

（二十四）写出只使用杂凑函数构造的公平提交方案。

散列编码的用途

用途一：公平提交方案

Alice猜想了一个号码为，但不知道中奖号码为;

Bob设置了中奖号码吊，但不知道Alice猜想的号码由。

Alice希望首先获得Xa,然后重新确定不使得小=场。

Bob希望首先获得由，然后重新确定也使得也#为。

防止两人作弊的方案称为“公平提交方案”。

两人使用一个公开的杂凑函数产，5）。方案如下：

[1）Alice随机选择时，计算必=〃（为,力），并将必发送给Bob。

（2）Bob随机选择々，计算的=〃（吊，n），并将先发送给Alice。

⑶Alice收到先后，将（苟，力）发送给Bob。

（4）Bob收到力后,将（莅,翁）发送给Alice。

（5）Alice收到（岛上）后，检验是否%=〃（%,八），假设是那么总是真实的中奖号码。

（6）Bob收到（小，力）后，检验是否必=〃（几动,假设是那么由是Alice的真实的猜想号

码。

方案分析：

Alice发送必给Bob,Bob发送必给Alice,这叫做承诺。

Alice发送（a,打）给Bob,Bob发送（鸟不）给Alice,这叫做践诺。

当承诺值确定以后，无法改变践诺值。

当对方发送来了承诺值以后，己方无法计算出对方的践诺值，因而无法“随机应变地”确

定自己的践诺值，以重合或避开对方的践诺值。

综上所述，杂凑函数阻止了双方作弊。

（二十五）表达数字签名应该满足的3条性质。

1.完整性,2.身份唯一性（不可伪造性），3.不可否认性（公开可验证性）.

（二十六）写出公钥密码数字签名方案（二）。

额外使用一个公开的杂凑函数设Alice欲发消息加给Bobo

⑴Alice用〃将消息力进行处理，得左，（勿）。

（2）Alice用自己的私钥A对方“解密”所〃血A）,s就是对消息亚的签名值，（加，s）就

是一个签名消息。

（3）Alice将（加，s）发送给Bob。

⑷Bob收到（r,s）后，用Alice的公钥z,将消息勿与签名s做如下的检验:是否4（血=夙s,

z）。假设是那么（加，s）是Alice发送的签名消息。

在上述方案中，

■签名方程是广（血，Q。

■验证方程是，（加）=£（s,z）o

■任何人只要拥有Alice的公钥z,都可以对签名消息（加，s）进行验证。

■设攻击者Eve知道Alice的公钥z,他试图伪造一个（加，s）,让Bob相信（勿，6）是

Alice的签名消息。伪造的（加，s）必须满足验证方程〃（加）=£（s,z）。

Eve面临着两难问题：

■如果选定消息如再匹配签名值s,那么在验证方程〃（4=£（s,z）中无法解出s。

（这是公钥密码的根本平安性）

■如果选定签名值s,再匹配消息处那么在验证方程〃（加）=£（$,z）中能够解出〃（血，

却无法得到加。（这是杂凑函数的性质）

如此看来，签名方案（二）似乎具有身份唯一性和不可伪造性。

（二十七）写出D.Chaum盲签名方案。

D.Chaum曾提出第一个实现盲签名的算法，他采用了RSA算法。令B的公钥为e,秘

密钥为&模为

（a）A需要B对消息r进行盲签名，选n,作片加心（mod〃）->B。

（b）B对大签名,〃=（成"）"（mod〃）->A。

（c）A计算s=「'/*（mod〃）得

s=（R4"）"/A（mod〃）=，（mod/7）,

（勿，s）就是B对加按RSA体制的合法签名，任何知道公钥e的人都能验证s三加（mod〃）。

（二十八）完整地写出ElGamal数字签名方案和Schnorr数字签名方案。（密钥生成、签名、

验证）。表达Schnorr数字签名方案与ElGamal数字签名方案相比的优点。

ElGamal数字签名

ElGamal的密钥生成：选择一个大的素数?选择g为域切（0）的本原元素。选择正整

数X。计算尸才（口0”7）。

Alice的公钥是（p,g,y},私钥是x。

签名方案是上述的签名方案（二），额外使用一个公开的杂凑函数"设Alice欲发消息加

给Bobo

（1）Alice用〃将消息勿进行处理，得加〃（加。

（2）Alice选择秘密随机数在，满足

Q<k<p-l,且（A,p-l）=l,

计算

r=g（mod/?）；

s={h-xr）k'（mod（/?-1））。

（3）Alice将（加，r,s）发送给Bob。

14）Bob用Alice的公钥，检验是否

yf-gM（modp）o

假设是那么（加，r,s）是Alice发送的签名消息。

Schnorr数字签名

Alice拥有3个正整数（0,q,g）,向自己的通信伙伴公开。其中：

■P是模数（即将要进行（mod。）模数运算），它是一个素数，值的范围在到2陞之间

（即P是一个长度为512的比特串）o

■q也是模数（即将要进行（modq）模数运算），它是一个素数，2.<q（即q是一个

长度不小于160的比特串），并且q是“1的一个因子。

■g是域6/（0）的元素，且/=l（mod°）。

■Alice选择x,其中

■Alice计算片@<modp）。

■Alice的公钥是（夕，q,g,y）,Alice的私钥是x。

■签名方案是上述的签名方案（二），额外使用一个公开的杂凑函数，，，的输出长度

是160比特。设Alice欲发消息加给Bobo

■（1）Alice选择秘密随机数A,满足0〈A〈q,计算

■r=g(mod。)；

■e=H{r,m)；

■折A+xe(modq)。

■⑶Alice将(卬,e,s)发送给Bob。

■⑷Bob用Alice的公钥，计算r'=g'y"(modp)0检验是否

■e=H{r',勿)。

■假设是那么(加，e,s)是Alice发送的签名消息。

Schnorr签名与ElGamal签名的不同点：

在ElGamal体制中，g为域切(夕)的本原元素；而在Schnorr体制中，g只是域6户(0)

的阶为q的元素，而非本原元素。因此，虽然两者都是基于离散对数的困难性，然而ElGamal

的离散对数阶为bl,Schnorr的离散对数阶为小尸1。从这个角度上说，ElGamal的平

安性似乎高于Schnorr。

签名长度比拟：Schnorr比ElGamal签名长度短。

ElGamal：(m,r,s),其中r的长度为I",s的长度为|厂1|。

Schnorr：(加，e,s),其中e的长度为|q|,s的长度为

•在Schnorr签名中，尸g*(modp)可以预先计算，4与加无关，因而签名只需一次modq

乘法及减法。所需计算量少，速度快，适用于灵巧卡采用。

(二十九)Shamir门限秘密共享方案。设：p=17；炉5；t=3；

(Ml),力("⑴))=(1,8)；

(m2),力(以⑵))=(2,7)；

(勿⑶,力(以⑶))=(3,10)；

("(4),方(、(4)))=(4,0)；

(M5),力(、(5)))=(5,ll)o

当第1位~第3位参与者同时到场，解出共享的秘密

切+,3户1及x2

(三十)表达Schnorr电子现金支付协议。

在Schnorr协议的初始化阶段，选择一个大素数“一个正整数g。。和g都被公开。

设顾客的身份秘密信息是(勿，6),其中力和6都是正整数。

顾客的身份公开信息是(c,ri),其中

c=^(mod/?)；n=g(,modp)o

Schnorr支付协议如下。

第一步：顾客出示电子现金。电子现金上有其身份公开信息（G〃）。

第二步：商家随机地选择一个正整数X,发送给顾客。〔询问）

第三步：顾客用自己的身份秘密信息（加，6）,计算：片加广仅model）。顾客将y发送给商

家。（答复）

第四步：商家用顾客的身份公开信息（c,力，验证是否有

g=nc（.modp）。

假设成立那么接受这个电子现金；否那么拒绝接受该电子现金。（检验）

Schnorr电子现金支付协议怎样保证防止重复花费？

一次使用该电子现金不会暴露顾客的身份秘密信息（以，份。

商家知道了顾客的身份公开信息（c,ri）,又通过询问值x得到了顾客的答复值外商家还

知道才与y的关系为：尸0用6（modpl）。但是商家计算出（饵的途径只能有两条：

第一条途径是通过方程组｛k/（mod。），炉外（mod。）｝计算（加，6）,该计算问题是离散

对数问题。

第二条途径是通过方程产"^（modbl）来计算（饵力。该方程无法唯一地解出（饵。）。

两次使用该电子现金将暴露顾客的身份秘密信息（///,。）。

第一次使用该电子现金，询问值/答复值为（4力。

第二次使用该电子现金，询问值/答复值为

于是商家获得了两个方程：

片zay+ZKmod/zT）；r=/»y+，（mod/7T）。

这是一个“二元一次方程组”，解出的值为：

1

nF（v-y）（u-x）（mod/7-1）；b=o

一旦发现重复使用的电子现金，就能够追踪重复使用者的身份。未重复使用的电子现

金，使用者的身份不会暴露。

（三十一）写出互联网（Internet）的5种根本效劳。

电子邮件，信息浏览，文件传输,远程登录，电子公告牌.

（三十二）IPsec属于（网络层）层。IPsec的2个协议是（认证报头协议AH）和（封

装平安负载协议ESP）。IPsec的2个数据库是（平安策略数据库SPD）和（平安关联数据

库SAD）。

（三十三）邮件文本经过加密或签名，变成了非文本课文。在解决这个问题时，S/MIME采

用什么方法？

S/MIME处理非文本课文时,采用MIME增加非文本的对象到邮件主体中去,按照S/MIME,

发送者将普通的MIME格式的消息封装成为S/MIME平安对象,并将其按照普通消息的发送方

式发送出去,接收者把S/MIME平安对象解封装为普通的MIME格式消息.

PGP采用什么方法？

PGP利用电子邮件兼容性效劳将被加密或被签名的邮件每三个字节为一组，扩充为四个

字节,扩充后的每个字节都是一个ASCII字符.这种转换称为基数64变换,为消息扩展了

33%.

（三十四）消息认证