应用密码学第3讲

1第三讲多表代替密码2复习►影射►置换►群►代替密码►几种常见的代替密码移位代替密码乘法代替密码仿射代替密码密钥短语密码3多表代替密码yyyyxxxxEnnnk),......,,())(),......,(),(()(212211什么是多表代替密码？在上述公式中满足什么条件？4本节内容►单表代替密码能被破解的原因►一次一密密码►维吉尼亚密码►博福特密码►滚动密钥密码►弗纳姆密码►转轮密码►M-209密码5单表代替密码能被破解的原因►明文字母和密文字母之间存在一一对应即一个给定的明文字母总是用同一个密文字母代替►自然语言的各种基本特性都转移到密文之中►与明文字母相比，除了字母名称外，所有语言特性都没有变化6一次一密密码在公式)),m(),m(()m(Ec2211中若密钥K是非周期序列，则对每一个明文字母都采用不同的代替表进行加密，称之为一次一密密码。这是一种在理论上唯一不可破的密码。这种密码对于明文的特点可实现完全隐蔽,但由于需要的密钥量和明文信息的长度相同而难于广泛使用。为了减少密钥量,在实际应用中多采用周期多表代替密码，即代替表个数有限且重复地使用,此时代替表序列,......),,......,,,,......,,(12121ddkd=1和d为无穷大时分别是什么密码7维吉尼亚密码►历史上最有名的周期多表代替密码是由法国密码学家BlaisedeVigenere设计的。d个移位(加法)代替表由d个字母构成的序列决定，ki(i=1,2...,d)是确定加密明文第i+td个字母(t=0，1，2,…)的代替表的移位数,即维吉尼亚密码的解密变换为：dqdZkkkk),......,,(21))(mod()(qkmmEcitditdiktdii))(mod()(qkccDmitditdiktdii8维吉尼亚密码例题2.7令q=26,m=polyalphabeticcipher,密钥字K=RADIO分析：周期d=5,则有k1703814明文m=polyalphabetIccIpher密钥K=RADIORADIORADIORADIO怎样计算？9博福特密码加密：解密：以为密钥的代替表是密文字母表为英文字母表逆序排列进行循环右移次形成的。例如,若ki=3(相当于字母D),则明文和密文的对应关系如下:明文:abcdefghijklmnopqrstuvwxyz密文:DCBAZYXWVUTSRQPONMLKJIHGFE))(mod()(qmkmctdiitdiitdi))(mod()(qckcmtdiitdiitdi10滚动密钥密码►对于周期多表代替密码，保密性将随周期d加大而增加。当d的长度和明文一样长时就变成了滚动密钥密码。如果其中所采用的密钥不重复就是一次一密体制。一般，密钥可取一本书或一篇报告作为密钥源,可由书名,章节号及标题来限定密钥起始位置。11弗纳姆密码►当字母表字母数q=2时的滚动密钥密码就变成弗纳姆密码。它将英文字母编成五单元波多电码。波多电码见表2.4.1所示。选择随机二元数字序列作为密钥,以表示。明文字母变成二元向量后也可以表示成二元序列加密：解密：例如：m=hello，k=00100，111000，10101，01010，11011求：c=？221,......(,......,,Fkkkkkii),......(,......,,221Fmmmmmiiiiikmciiikcm12转轮密码►第一次世界大战以后,人们开始研究用机械操作方式来设计极大周期的多表代替密码，这就是转轮密码(rotorcipher)体制。转轮密码机(rotormachine)是由一组布线轮和转动轴组成的可以实现长周期的多表代替密码机。它是机械密码时期最杰出的一种密码机，曾广泛应用于军事通信中。►德军的Enigma密码机►美军的Hagelin密码机（其中Hagelinc-48即M-209）►日本的紫密和蓝密密码机13转轮密码转轮密码由一组(N个)串联起来的布线轮组成。用一根可以转动的轴把N个园盘串接起来，使得相邻两个园盘上的接点能够接触就构成了一个简易的转轮密码机。其中转动轴是可以转动的，而且每个园盘在转动轴上也是可以转动的。有N个园盘的转轮密码体制的密钥由下面两方面组成:(1)N个园盘实现的代替表pi(i=1,2,...,N)(2)每个园盘的起点(i=1,2,....,N)。如果一个转轮密码体制只是各园盘的合成组成，则此转轮密码体制只相当于单表代替密码体制。)0(ik14M-209密码机印字轮圆盘凸片鼓状滚筒销钉15M-209密码机►每个园盘的外缘上分别刻有26,25,23,21,19,17个字母,每个字母下面都有一根销钉(或称为针)，每个销钉可向园盘的左侧或右侧凸出来，向右凸出时为有效位置,向左凸出时为无效位置。►在使用密码机之前，需要将各园盘上的每根销钉置好位（向右或向左）。如果我们用0表示销钉置无效位，用1表示销钉置有效位，则第一个园盘上的销钉位置可以用长为26的0，1序列表示，第二个园盘上的销钉位置可以用长为25的0，1序列表示，……第六个园盘上的销钉位置可以用长为17的0，1序列表示，如表2.6.2所示。16M-209密码机►鼓状滚筒上有27根与其轴平行的杆等间隔地配置在凸片鼓状滚筒的外圈上,每根杆上有8个可能的位置,其中六个位置与六个园盘对准，另两个位置不与任何园盘对应。在每根杆上面，有两个可移动的凸片，可以将其置于上述8个可能的位置(标为1,0,2,3,4,5,0,6)中任何两个上。如果凸片被置于与0对应的位置，则它不起作用，称其为凸片的无效位置，否则称其为凸片的有效位置。►当凸片对应园盘i(i=1,2,3,4,5,6)，凸片可以与园盘i上的有效销钉接触。我们可以用下述方式来描述凸片鼓状滚筒:对应于六个园盘中的每一个,如果凸片鼓状滚筒上的某根杆上在此处安置有一个凸片，标上1，否则标上0。这样，每根杆对应的六个园盘中哪些安有凸片就可以用顶多含有两个1的二元6维向量表示。表2.6.1(P40)就是凸片鼓状滚筒上的27根杆中的每一根对应六个园盘上凸片的一种配置。17M-209密码机01010101…….01(010001)圆盘上销钉配置滚筒杆上凸片配置AZ无效位有效位18M-209密码机►凸片鼓状滚筒的每根杆上的凸片的配置（如表2.6.1所示）和每个园盘上销钉的配置（如表2.6.2所示）称为M-209的基本密钥。基本密钥在较长一段时间内（例如半年、一年等）不会改变。►加密：c≡25+k–m(mod26)►解密：m≡25+k–m(mod26)其中k是凸片滚筒在一次完整旋转中选中的杆数。19M-209密码机►例题：例2.6.1设要加密的消息是►nowisthetimeforallgoodmen►将单词之间插入间隔z后为►nowzisztheztimezforzallzgoodzmen►用表2.7的第一列001010作开始加密的基本销钉,此时选中的杆数为10,公式可以得到►25+1013≡22(mod26)►即第一个明文字母n加密成w。在n加密好之后,每个园盘都转动一个位置。这也相当于表2.7的每一列向左移动一位，因而新的基本销钉位置为010110,此时选中的杆数为22，并把明文字母o加密成h。如此下去,得到的密文是:►WHDFCDPCDRFZQNRWVYFUXYESSRKHWJBI2021222324M-209密码机2526小结►数论知识►单表代替►多表代替►密码机