应用密码学课件

第1章密码学概述密码学与信息安全密码体制与密码分析密码体制的安全性香农理论简介计算复杂性理论简介*密码学与信息安全密码学：研究信息的保密和复原保密信息以获取其真实内容的学科称为密码学(cryptology)。它包括密码编码学和密码编码学(cryptography)：研究对信息进行编码实现隐蔽信息的一门学科。密码分析学(cryptanalytics)：研究复原保密信息或求解加密算法与密钥的学科。密码应用举例古希腊信使（兽皮文字加密）我国4千年前的象形文字周朝姜太公发明的阴书*密码学与信息安全密码学的发展史初等密码、机械密码、近代电子密码(20世纪50年代)、现代密码(20世纪70年代)密码学发展的标志性事件19世纪末，无线电的发明使密码学的发展进入一个开始发展的时期。这一时期的密码的主要标志是以手工操作或机械操作实现的,通常称之为机械密码。1949年,香农发表了<<秘密体制的通信理论>>(TheCommunicationTheoryofSecrecySystems),它证明了密码编码学是如何置于坚实的数学基础之上，从此密码学发展成为一个专门学科。*密码学与信息安全密码学发展的标志性事件1976年,Diffie和Hellman发表的革命性论文<<密码学新方向>>(Newderyctionsincryptography),突破了传统密码体制使用秘密密钥所带来的密钥管理难题,使密码的发展进入了一个全新的发展时期。应用举例二次世界大战时,德国人认为自己的“恩格尼玛”密码是不可破的。1940年被英军破获。1941年12月,日本海军采用无线电静默和战略伪装,骗过了美国人,成功地偷袭了珍珠港。但是,1942年6月,日本海军对中途岛发起的登陆作战因日本密码被破译,终于遭到毁灭性的失败,太平洋战争从此出现转机。*密码学与信息安全应用举例在1962年的古巴导弹危机中,苏美剑拔弩张,形势严峻。据悉，美国人心生一计，故意用能被苏联截收、破译的密码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁晓夫。甲午海战中北洋水师的覆灭，虽然其根本的原因在于清朝廷的腐败,但是日本人破译了清军的密码也是一个重要的原因。二战中,美国还利用破译密码所获得的情报为其外交服务。*密码学与信息安全应用举例1994年,因为美国的情报机构通过截获的国际电讯，得知法国与沙特阿拉伯正在进行一笔数亿美元的军火交易，从而使美国先行一步从法国人手中抢下了这笔大生意。当今的密码学当今时代，高新技术发展日新月异，计算机网络的建设方兴未艾。电子政府、知识经济、数字化部队、信息化战争等等均立足于计算机网络之上，融合于计算机网络发展之中。而要解决计算机网络的安全保密问题,必须建立信息安全保障体系。这个体系由保护、检测、反应和恢复四大部分构成。其中信息安全保护是信息安全保障体系的核心和基础。*第1章密码学概述密码学与信息安全密码体制与密码分析密码体制的安全性香农理论简介计算复杂性理论简介*密码体制与密码分析密码体制（密码系统）：密码编码学是改变信息形式以隐蔽其真实含义的学科。具有这种功能的系统称为密码体制或密码系统(cryptographicsystem)。明文和密文：被隐蔽的信息称为明文(plaintext)，经过密码方法将明文变换成另一种隐蔽的形式称为密文(ciphertext)。加密变换与加密算法：实现明文到密文的变换过程称为加密变换(encryption)，这种变换的规则称为加密算法。解密变换与解密算法：合法接收者(receiver)将密文还原成明文的过程称为解密变换(decryption)，这种还原的规则称为解密算法。密钥：通常,加密算法和解密算法都是在一组信息的控制下进行的。控制加密算法或解密算法的信息分别称为加密密钥(key)或解密密钥。*密码体制与密码分析

信源M加密器解密器接收者mmc非法入侵者搭线信道（主动攻击）密码分析员（窃听者）搭线信道（被动攻击）密钥源密钥源密钥信道图1-5保密通信系统模型*密码体制与密码分析从原理上可分为两类单密钥体制双密钥体制序列密码（流密码）：按字符逐位加密。代数作业密码：多次迭代，置换。分组密码：将明文消息分组，逐组加密。主要特点是将加密和解密能力分开。*密码体制与密码分析主动攻击与被动攻击：如果敌手(opponent)通过某些渠道窃听或侦收到正在被发送的密文信息，然后试图用各种手段或方法去获取密钥或明文信息,那么,这种攻击方法称为被动攻击(passiveattack)。如果敌手通过更改被传送的密文信息，或将自已的扰乱信息插入到对方的通信信道之中以破坏合法接收者的正常解密，则这种攻击为主动攻击(activeattack)。*密码体制与密码分析密码分析：密码分析(cryptanalysis)是被动攻击,它是在不知道解密密钥及通信者所采用的加密体制的细节的条件下，试图通过密码分析达到获得机密消息的目的。密码分析在军事、外交、公安、商务、反间谍等领域中起着相当重要的作用。密码分析工具：(1)概率论和数理统计(2)线性代数和抽象代数(3)计算的复杂性理论(4)信息理论及其它一些特定的知识等。*密码体制与密码分析密码分析的类型

唯密文攻击(ciphertextonlyattack)已知明文攻击(knownplaintextattack)选择明文攻击(chosenplaintextattack)选择密文攻击(chosenciphertextattack)*第1章密码学概述密码学与信息安全密码体制与密码分析密码体制的安全性香农理论简介计算复杂性理论简介*密码体制的安全性计算安全性可证明安全性无条件安全性*小结密码学的基本概念和相关符号加密体制的分类密码分析的工具密码分析的类型密码安全性准则*应用密码学第2章古典密码学17回顾什么是密码体制？密码体制的分类。密码分析的分类。*2.1语言的统计特性研究保密性和密码破译方法的实质：就是研究明文信息在密文信息中有多大程度的泄漏。下面假设讨论的语言是某种语言的文字：设字母表为

X={x0，x1，…，xm-1}

为了方便起见，字母表也用0－（m-1）之间的数字来表示，此时字母表为

Zm={0，1，…，m－1}*2.1语言的统计特性例如，英文字母表可以表示为

X={a，b，c，…，x，y，z}或者

Zm={0，1，2，…，24，25}

明文是由Zm中的元素和固定的结个规则确定的。因此具有语言的统计特性。例如：字母q后总是跟着字母u。*2.1语言的统计特性语言的一阶统计特性称P={p0，p1，…，pm-1}为语言的一阶统计特性。其中，pi（0≦i≦m-1）代表字母i在该语言中出现的概率。例2.1英文字母表X={a，b，c，…，x，y，z}，由独立试验产生明文单码，Beker在1982年统计的样本总数为100362，得到单码的概率分布见表2.1。

*表2.1英文字母的概率分布字母概率字母概率字母概率A0.08167J0.00153S0.06327B0.01492K0.00772T0.09056C0.02782L0.04025U0.02758D0.04253M0.02405V0.00978E0.12702N0.06749W0.02360F0.02280O0.07567X0.00150G0.02015P0.01929Y0.01974H0.06094Q0.00095Z0.00074I0.06966R0.05497*2.1语言的统计特性英文字母出现的概率大小排列：

ETAOINSHRDLCUMWFGYPBVKJXQZ

按字母出现的概率分类：表2.2英文字母分类表1234567极大概率字母集：E大概率字母集：TAO较大概率子母集：INSHR平均概率字母集：DL较低概率字母集：CMWFGYPBU低概率字母集：VK极低概率字母集：JXQX*2.1语言的统计特性语言的一阶特性至少在以下两个方面没有反映出英文的语言特性：(1)双字母出现的概率例如QE出现的概率。按照一阶特性计算QE出现的概率为

p（QE）=0.0095×0.12702≈1.21×10-4

但是在英文课文中QE根本不会出现。(2)四字母SEND和SEDN在一阶统计特性下出现的概率相等，这也不符合实际。*2.1语言的统计特性双字母出现的频数表示为：

N(i，j)i,j=0,1,2,(m-1)

双字母出现的概率p(xi,xj)近似地可以表示为

p(xi,xj)=N(i，j)/(N－1)例2.2由独立试验产生双字母表。表2.3是Beker在1982年的统计结果。（教材39页）。利用此表计算p(SEND)=p(SE)×p(ND)≈0.7919

p(SEDN)=p(SE)×p(DN)≈0.08146

p(QE)=0*2.1语言的统计特性同理，三字母出现的概率可以近似地表示为

p(xi,xj,xk)=N(I,j,k)/(N－2)注意：在实际的通信中除了字母外还有数字，标点符号等，他们的统计特性也要考虑进去。另外数据格式，报头信息对于密码体制的安全有重要意义，，在密码分析中起着非常重要的作用。为什么是N－2？*2.2单表代替密码补充（1）变换集合X到自身的一个映射称为集合X的一个变换。对照映射的概念可以定义出满射变换，单射变换，双射变换。（2）置换有限集合X上的双射变换称为一个n次置换，通常用以下符号表示

=（3）群2…n

…

*2.2单表代替密码设集合G是一个非空集合，·是它的一个代数运算，如果满足条件：（1）结合律成立，即对G中任意元素a，b，c都有(a·b)·c=a·(b·c)（2）有左单位元。即存在元素e∈G，对G中的每个元素a都有

e·a=a（3）每个元素都存在逆元。即对于任意a∈G，存在a-1∈G，使a-1·a=e

则称G对代数运算·作成一个群。若交换律成立，则称G为可交换群或Abel群。*2.2单表代替密码（4）对称群假设所采用语言的字母表含有q个字母,即集合上置换的全体记为,则是上的对称群。定义2.1设是一列置换，是一列明文，其中,。变换Ek将n-明文组加密成n-密文组,即*2.2单表代替密码称上述加密方式为代替(substitution)加密。当时,称为单表代替(monalphabeticsubstitute)加密。否则,称其为多表代替(polyalphabeticsubstitute)加密。称为代替加密密表。下面学习两种代替密码*2.2.1移位代替密码以下将q个字母的字母表与Z模q中数作一一对应,利用每个字母对应的数字代替该字母。例如,将英文字母表作如下对应:abc…yz123…2526这样,可以用0表示a,用1表示b.....。移位代替密码是最简单的一种代替密码。其加密变换为：，0≤m,c＜q

显然,移位代替密码的密钥空间中元素的个数为q,其中k=0是恒等变换。试着写出解密变换的公式*2.2.1移位代替密码例2.3凯撒密码(CaesarCipher)是对英文字母表进行移位代替的密码,其中q=26。例如,选择密钥k=3,则有下述代替表:明:abcdefghijklmnopqrstuvwxyz密:DEFGHIJKLMNOPQRSTUVWXYZABC

设明文m=helloeverybody试计算其密文。

解密时,只要用密钥k=23的加密密表对密文c进行加密运算就可恢复出原明文。这种密码是将明文字母表中字母位置下标与密钥k进行模q加法运算的结果作为密文字母位置下标,相应的字母即为密文字母,因此又称其为加法代替密码。

*2.2乘法代替密码

乘法代替密码的加密变换为：，0≤c

＜q

。这种密码又叫采样密码(decimationcipher)，这是因为其密文字母表是将明文字母表按下标每隔k位取出一个字母排列而成(字母表首尾相接)。显然,当gcd(k,q)=1,即k与q互素时明文字母与密文字母才是一一对应的。若q为素数,则有q-2个可用密钥。否则就只有

φ(q)-1个可用密钥。这里φ(q)是欧拉函数,它表示小于q且与q互素的正整数的个数。（举例说明）

*2.2乘法代替密码例2.4英文字母表q=26,选k=9,则有乘法代替密码的明文密文字母对应表:012345678910111213141516171819202122232425

明:abcdefghijklmnopqrstuvwxyz

密:AJSBKTCLUDMVENWFOXGPYHQZIR

若明文m=multiplicativecipher

密文c=？*2.2.3仿射代替密码

将移位代替密码和乘法代替密码结合起来就构成仿射代替密码。其加密变换为其中以表示仿射代替密码的密钥。当k0=0时,就得到乘法代替密码,当k1=1时就得到移位代替密码。q=26时,可用的密钥数为26×12-1=311个。

解密变换为*2.2.3仿射代替密码例2.5

的仿射代替密码的代替表为:c=m×7+3，m=cipher

求c=?

试计算解密变换的代替表.*2.2.4密钥短语密码

可以通过下述方法对例2.2.1的加法代替密码进行改造,得到一种密钥可灵活变化的密码。选一个英文短语,称其为密钥字(keyword)或密钥短语(keyphrase)，如HAPPYNEWYEAR,按顺序去掉重复字母得HAPYNEWR。将它依次写在明文字母表之下,而后再将明文字母表中未在短语中出现过的字母依次写在此短语之后,就可构造出一个代替表,如下所示:

明:abcdefghijklmnopqrstuvwxyz

密:HAPYNEWRBCDFGIJKLMOQSTUVXZ*小结语言的表示方法及统计特性映射、置换、群、对称群移位代替、乘法代替、仿射代替、密钥短语作业：2.2、2.3、2.4*第三讲多表代替密码39复习影射置换群代替密码几种常见的代替密码移位代替密码乘法代替密码仿射代替密码密钥短语密码*多表代替密码什么是多表代替密码？在上述公式中满足什么条件？*本节内容单表代替密码能被破解的原因一次一密密码维吉尼亚密码博福特密码滚动密钥密码弗纳姆密码转轮密码M-209密码*单表代替密码能被破解的原因明文字母和密文字母之间存在一一对应即一个给定的明文字母总是用同一个密文字母代替自然语言的各种基本特性都转移到密文之中与明文字母相比，除了字母名称外，所有语言特性都没有变化*一次一密密码在公式中若密钥K是非周期序列，则对每一个明文字母都采用不同的代替表进行加密，称之为一次一密密码。

这是一种在理论上唯一不可破的密码。这种密码对于明文的特点可实现完全隐蔽,但由于需要的密钥量和明文信息的长度相同而难于广泛使用。为了减少密钥量,在实际应用中多采用周期多表代替密码，即代替表个数有限且重复地使用,此时代替表序列

d=1和d为无穷大时分别是什么密码*维吉尼亚密码历史上最有名的周期多表代替密码是由法国密码学家BlaisedeVigenere设计的。d个移位(加法)代替表由d个字母构成的序列决定，ki(i=1,2...,d)是确定加密明文第i+td个字母(t=0，1，2,…)的代替表的移位数,即维吉尼亚密码的解密变换为：

*维吉尼亚密码例题2.7令q=26,m=polyalphabeticcipher,密钥字K=RADIO分析：周期d=5,则有k

1703814

明文m=polyalphabetIccIpher

密钥K=RADIORADIORADIORADIO

怎样计算？*博福特密码加密：解密：

以为密钥的代替表是密文字母表为英文字母表逆序排列进行循环右移次形成的。例如,若ki=3(相当于字母D),则明文和密文的对应关系如下:明文:abcdefghijklmnopqrstuvwxyz密文:DCBAZYXWVUTSRQPONMLKJIHGFE*滚动密钥密码

对于周期多表代替密码，保密性将随周期d加大而增加。当d的长度和明文一样长时就变成了滚动密钥密码。如果其中所采用的密钥不重复就是一次一密体制。一般，密钥可取一本书或一篇报告作为密钥源,可由书名,章节号及标题来限定密钥起始位置。*弗纳姆密码当字母表字母数q=2时的滚动密钥密码就变成弗纳姆密码。它将英文字母编成五单元波多电码。波多电码见表2.4.1所示。选择随机二元数字序列作为密钥,以表示。明文字母变成二元向量后也可以表示成二元序列加密：解密：

例如：m=hello，k=00100，111000，10101，01010，11011

求：c=？*转轮密码第一次世界大战以后,人们开始研究用机械操作方式来设计极大周期的多表代替密码，这就是转轮密码(rotorcipher)体制。转轮密码机(rotormachine)是由一组布线轮和转动轴组成的可以实现长周期的多表代替密码机。它是机械密码时期最杰出的一种密码机，曾广泛应用于军事通信中。德军的Enigma密码机美军的Hagelin密码机（其中Hagelinc-48即M-209）日本的紫密和蓝密密码机*转轮密码

转轮密码由一组(N个)串联起来的布线轮组成。用一根可以转动的轴把N个园盘串接起来，使得相邻两个园盘上的接点能够接触就构成了一个简易的转轮密码机。其中转动轴是可以转动的，而且每个园盘在转动轴上也是可以转动的。有N个园盘的转轮密码体制的密钥由下面两方面组成:

(1)N个园盘实现的代替表pi(i=1,2,...,N)(2)每个园盘的起点(i=1,2,....,N)。

如果一个转轮密码体制只是各园盘的合成组成，则此转轮密码体制只相当于单表代替密码体制。*M-209密码机印字轮圆盘凸片鼓状滚筒销钉*M-209密码机每个园盘的外缘上分别刻有26,25,23,21,19,17个字母,每个字母下面都有一根销钉(或称为针)，每个销钉可向园盘的左侧或右侧凸出来，向右凸出时为有效位置,向左凸出时为无效位置。在使用密码机之前，需要将各园盘上的每根销钉置好位（向右或向左）。如果我们用0表示销钉置无效位，用1表示销钉置有效位，则第一个园盘上的销钉位置可以用长为26的0，1序列表示，第二个园盘上的销钉位置可以用长为25的0，1序列表示，……第六个园盘上的销钉位置可以用长为17的0，1序列表示，如表2.6.2所示。

*M-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根杆中的每一根对应六个园盘上凸片的一种配置。

*M-209密码机*M-209密码机凸片鼓状滚筒的每根杆上的凸片的配置（如表2.6.1所示）和每个园盘上销钉的配置（如表2.6.2所示）称为M-209的基本密钥。基本密钥在较长一段时间内（例如半年、一年等）不会改变。加密：c≡25+k–m(mod26)解密：m≡25+k–m(mod26)

其中k是凸片滚筒在一次完整旋转中选中的杆数。*M-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。如此下去,得到的密文是:WHDFCDPCDRFZQNRWVYFUXYESSRKHWJBI*****M-209密码机**小结数论知识单表代替多表代替密码机*应用密码学第四讲分组密码体制（一）*应用密码学*第三章分组密码体制复习：1、密码体制的分类。

2、什么是分组密码？*应用密码学*§1节分组密码概述分组密码是将明文消息编码表示后的序列划分成长为的组，各组（长为n的矢量）分别在密钥的控制下，变换成输出数字系列（长为m的矢量），其加密函数，和分别是n维和m维矢量空间，为密钥空间如图3-1所示。加密算法明文x解密算法明文x密文图3-1分组密码框架*应用密码学*在相同的密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以，只需研究对任意一组明文数字的的变换规则。通常取m=n。若则为有数据扩展的分组密码；若则为有数据压缩的分组密码。在二元的情况下，和均为二元数字序列，他们的每个分量，。本节主要讨论二元的情况。一、代换若明文和密文分组都是n比特，则：每个明文分组有个不同的取值。明文到密文的可逆变换（又称代换）个数为个。例如：n=4时，可产生16个不同的状态，其中每一个输入状态通过代换映射成一个输出状态，代换如图3-2所示。*应用密码学*4比特输入0123

4567

891011

1213141501234567891011121314154比特输出图3-2代换结构加密映射和解密映射也可以用代换表来定义，如表3-1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文间的任何可逆映射。*应用密码学*明文密文0000111000010100001011010011000101000010010111110110101101111000密文明文0000111000010011001001000011100001000001010111000110101001111111明文密文1000001110011010101001101011110011000101110110011110000011110111密文明文1000011110011101101010011011011011001011110100101110000011110101表3-1图3-2对应的代换表从安全角度讲分组长度n要足够大，而且从明文到密文可有任意的可逆代换，那么明文的统计特性将被隐藏而使攻击不能凑效。从实现的角度讲分组长度很大的可逆代换结构是不实际的。以表3-1为例，该表定义了n=4时从明文到密文的一个可逆映射，*应用密码学*其中，第2列是决定该可逆映射的密钥，该例中密钥需要64bit。一般地，对比特的代换结构，密钥的大小是比特。比如，密钥大小应是，变得难以处理。实际应用中，常将分成较小的段，例如可选其中，和都是正整数，将设计个变量的代换变为设计个较小的代换，而每个子代换只有个输入变量。一般都不大，称每个子代换为代换盒，简称S盒。二、扩散和混淆扩散：扩散就是将明文中的统计信息散布到密文中去，实现方式是使明文的每一位影响密文的多位的值，即密文中的密文中的每一位均受明文中的多位影响。例如对英文消息的加密：*应用密码学*是求字母对应的序号，是求序号对应的字母，是密钥。经过这样的代换后每一字母出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。在分组密码中扩散的目的是使明文和密文之间的统计关系变得尽可能的复杂，使敌手无法得到密钥。混淆：混淆是使密文和密钥之间的关系变得尽可能的复杂，使敌手无法得到密钥。使用复杂的代换算法可获得预期的混淆效果。扩散和混淆成功实现了分组密码的本质属性，因而成为设计现代分组密码的基础。*应用密码学*三、Feistel密码结构Feistel提出了利用乘积密码可获得简单的代换密码。乘积密码是指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于基本密码系统产生的结果。Feistel还提出了实现代换和置换的方法。1、Feistel加密结构加密算法的输入是分组长度为的明文和一个密钥。将每组明文分成左右两半和，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第轮迭代的输入为前一轮输出的函数：其中是第轮用的子密钥，由加密密钥得到。一般地，各轮密钥互不相同而且与也不相同。每轮的轮函数的结构都相同，但以不同的子密钥作为参数。如图3-3所示。*应用密码学*FF密文明文F图3-3Feistel网络示意图*应用密码学*Feistel网络的实现与以下参数和特性有关：①

分组大小 分组越大越安全，但加密速度就越慢。分组密码设计中最为常用的分组大小是64比特。

②

密钥大小 密钥越长安全性越高，但加密速度就越慢。通常128位。

③

轮数 单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型的轮数取为16。

④子密钥产生算法 该算法的复杂性越大，则密码分析的困难性就越大。⑤

轮函数 轮函数的复杂性越大，密码分析的难度就越大。在设计Feistel网络时，还有以下两个方面需要考虑：①

快速的软件实现。②

算法容易分析。算法能无疑义地解释清楚，利于分析算法抵抗攻击的能力，有助于设计高强度的算法。*应用密码学*2、Feistel的解密结构Feistel的解密过程和加密过程是一样的，算法使用密文作为输入，但使用子密钥的次序和加密过程相反，即第一轮使用，第二轮使用，，最后一轮使用。加密算法每轮的左右两半用和来表示，解密算法每轮的左右两半用和表示。加密过程的第轮的输出是（表示链接），解密过程的第轮的输入是。Feistel加密和解密过程见图3-4。*应用密码学*图3-4Feistel加解密结构

输入（明文）FFFF输出（密文）输入（密文）FFFF

输出（明文）*应用密码学*下证解密过程第1轮的输出等于加密过程第16轮的输入左右两半的交换值。在加密过程中：，在解密过程中：所以解密过程的第1轮的输出为，等于加密过程中第16轮输入左右两半交换后的结果。一般地，加密过程的第轮有，所以，可以用归纳法证解密过程中有：*应用密码学*§2节数据加密标准1975年3月17日首次公布1977年1月15日被正式批准为美国联邦信息处理标准，即FIP-46，同年7月15日生效。1997DESCHALL小组通过Internet搜索了个密钥，找出了DES密钥，恢复出了明文。1998美国EFF宣布，他们用一台20万美元的计算机改装的专用解密机用56小时破解了56比特密钥的DES。2000年新的加密标准AES已经产生。DES历史回顾：*应用密码学*一、DES描述置换选择2第2轮第1轮初始置换逆初始置换左右交换第16轮置换选择2置换选择2左循环移位左循环移位左循环移位置换选择164比特明文64比特密文56比特密钥图3-5DES加密算法框图*应用密码学*58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157表3-2DES的置换表（a）初始置换IP（b）逆初始置换IP408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757251、初始置换*应用密码学*32123454567898910111213121314151617161718192021202122232425242526272829282930313211672021291228171152326518311028241432273919133062211425（c）选择扩展运算E（D）置换运算P把32比特扩展成48比特*应用密码学*2、轮结构置换(p)置换(E)XORS盒XOR左移位左移位置换选择2图3-6DES算法的轮结构*应用密码学*R(32比特)K(48比特)48比特E+P32比特图3-7函数F(R,K)的计算过程，*应用密码学*144131215118310612590701574142131106121195384114813621115129731050151282491751131410061301234568791011121314150213列行表3-3DES的S盒的定义对于每一个S盒，其中的6比特输入中，第1和第6个比特形成一个2位二进制数，该二进制数决定S盒的行号。中间4个比特表示的二进制数决定列号。S盒中的元素转换成二进制后作为输出。例如：的输入为011001，01：即第1行1100：即第12列第1行，12列对应的数为9，即1001，所以的输出为1001。*应用密码学*3、密钥的产生57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124表3-4DES密钥编排用表（a）置换选择11417112415328156211023191242681672720132415231374755304051453348444939563453464250362932（b）置换选择2(PC-2)56比特的密钥首先经过一个置换选择1，然后分成左右两半，分别记作和。，，PC-2表示循环左移，当时移1位，其它轮移两位。*应用密码学*4、解密解密算法和加密算法相同，只是使用子密钥的顺序相反。参见图3-4。二、二重DES，EE(a)加密(b)解密图3-8二重DESDD*应用密码学*分析：假设对任意的两个密钥和，若能找出另一个密钥使得则二重DES和多重DES都没有意义。好在这种假设已经在1992年被证明不成立。中途相遇攻击如果有那么如果已知一个明文密文对（P，C），首先用个所有可能的密钥加密，将加密结果存入一张表并对表按X排序，然后用个所有可能的密钥对P对C解密，在上述表中找与C的解密结果相匹配的项，如果找到则记下相应的和。*应用密码学*再用一新的明文密文对检验一下即可确定和。对已知的明文P，二重DES能产生个可能的密文，而二重DES所用的密钥长度为112比特，所以选择密钥有个可能，于是对于给定的一个明文加密成密文，有种可能，再经过给定的明密文对的检验，密钥的误报率为，所以实施中途相遇攻击时，成功找到密钥的概率为PCCC种可能每一种映射有种可能的密钥。*应用密码学*三、两个密钥的三重DES解密图3-9两个密钥的3重DES*应用密码学*四、三个密钥的三重DES解密。*应用密码学*小结：1、分组密码的基本思想。2、代换、扩散、混淆和Feistel结构的基本思想。3、DES算法基本原理。4、多重DES。#本次课结束#*应用密码学*应用密码学

第五讲AES算法93复习DES算法分组长度密钥长度f函数S盒轮变换密钥调度

*本节内容AES（高级数据加密标准）算法描述密码分析RC6算法（自学）RC5算法描述RC6算法描述*AES算法1997年9月12日，为了替代即将退役的DES，美国国家标准与技术研究所（NIST）在《联邦纪事》上发表了征集AES算法的公告。1999年3月22日，公布了5个候选算法：MARS,RC6,Rijndael,SERPENT,Twofish。2000年10月2日，由比利时密码学家JoanDaemen和VincentRijmen提交的Rijndael算法被确定为AES。以下称Rijndael算法为AES算法。2001年11月26日被采纳为一个标准。*AES算法描述Rijndael分组加密算法的前身是Square分组加密算法，轮变换结构与其基本相同。为了应征AES候选算法，对Square分组加密算法进行了改进。由原来的密钥和分组长均为128比特改为分组和密钥长均可变，可以满足不同的加密需求。具体参数如下：①分组长度、密钥长度和加密层数均可变。②分组长度和密钥长度支持128、192、256比特。③分组和密钥长度可以独立改变，并由此决定加密层数。*为了后面论述方便，进行如下定义：(一)设计准则Rijndael加密算法按照如下原则进行设计：⒈抗所有已知的攻击⒉在多个平台上速度要快和编码紧凑⒊设计简单(二)状态、密钥与轮数定义：状态（State）：中间密码结果称为状态Nb=明文分组的4-字节字数（32比特）Nk=密钥的4-字节字数（32比特）Nr=加密的轮数*明文分组（密钥）长度为128比特时，Nb=Nk=4明文分组（密钥）长度为196比特时，Nb=Nk=6明文分组（密钥）长度为256比特时，Nb=Nk=8现以Nb=6和Nk＝4为例进行图示说明。a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35Nb=6时状态放置示意图

k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33Nk＝4时密钥放置示意图

*分组长度、密钥长度都可以在128bit、192比特和256比特间变化，但是不同的组合需要不同的加密轮数。分组长度与轮数的关系：NrNb

=4Nb

=6Nb

=8Nk

=4101214Nk

=6121214Nk=8141414*AES的总体描述：①给定一个明文x，将State初始化为x，并进行AddRoundKey操作，将RoundKey与State异或。②对前Nr-1轮中的每一轮，用S盒进行一次代换操作，称为SubBytes；对State作一个置换ShiftRows，再对State作一次操作MixColumns，然后进行RoundKey操作。③依次进行SubBytes，ShiftRows和AddRoundKey操作。④将State定义为明文。*加密开始时，首先将State定义明文字节x0，x1,…x15S00S01S02S03S10S11S12S13S20S21S22S23S30S31S32S33x00x01x02x03x10x11x12x13x20x1x22x23x30x31x32x33AESSubBytes操作所使用的S盒是{0，1}8上的一个置换，见下表。每一个字节都用两个16进制的数字表示。*0123456789abcdef0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973060814fdc222a908846eeb814de5e0bdbAe0323a0a4906245cc2d3ac629195e479Be7c8376d8dd54ea96c56f4ea657aae08cBa78252e1ca6b4c6e8dd741f4bbd8b8ad703eb5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fb054bb16*SuBytes算法

ExternalFieldInv,BinaryToField,FieldToBinaryz

BinaryToField(a7a6a5a4a3a2a1a0)if

z

0

then

z

FieldInv(z)(a7a6a5a4a3a2a1a0)

FieldToBinary(z)(c7c6c5c4c3c2c1c0)

(01100011)//在下面的循环中，所有下标都要经过模8约简

fori

0to7

dobi

(ai+ai+4+ai+5+ai+6+ai+7+ci)mod2return(b7b6b5b4b3b2b1b0)*FieldInv：表示求一个域元素的乘法逆BinaryToField：把一个字节变成一个域元素FieldToBinary：把一个域元素变成一个字节例题：设算法的输入是16进制的53，在二进制下是01010011表示为域元素为：x6+x4+x+1它的乘法逆元（在有限域F28中）：x7+x6+x3+x在二进制下，我们有：

(a7a6a5a4a3a2a1a0)

（11001010）*下面我们计算

b0=a0+a4+a5+a6+a7+c0mod2=0+0+0+1+1+1mod2=1b1=a1+a5+a6+a7+a0+c1mod2=1+0+1+1+0+1mod2=0

….

结果是：（b7b6b5b4b3b2b1b0）=(11101101)

以16进制表示就是ED。上面的结果可以通过查S盒代换表来验证。行号5，列号3，对应ED。*行变换改图的右移字节数是以Nb=4为例。更一般的情况见下页。*第0行保持不变，第1～3行分别右循环移动移动C1～C3字节。其中C1～C3的大小与Nb大小有关。NbC1C2C3412361238134*列混合通过线性变换将列变换到列。算法描述（MixColumn(State)）。作上的多项式运算，即作

(modx4+1)相当于作和上的线性变换。可用上矩阵运算描述为*Mixcolumn(c)ExternalFieldMult,BinaryToField,FieldToBinaryfori

0to3

doti

BinaryToField(Si,c)u0

FieldMult(x,t0)

FieldMult(x+1,t1)

t2

t3u1

FieldMult(x,t1)

FieldMult(x+1,t2)

t3

t0u2

FieldMult(x,t2)

FieldMult(x+1,t3)

t0

t1u3

FieldMult(x,t3)

FieldMult(x+1,t0)

t1

t2fori

0to3

doSi,c

FieldToBinary(ui)//FieldMult表示域元素求积。*密钥编排①密钥比特的总数等于分组长度乘轮数加1.②将密码密钥扩展成一个扩展密钥。③轮密钥是按下述方式从扩展密钥中取出的：第一个轮密钥由第一个Nb字组成，第二个轮密钥由接下来的Nb组成，由此继续下去。下面讨论密钥扩展算法。*密钥扩展算法设将扩展密钥以4-字节字为单位放到数组W[Nb*(Nr+1)]中，则第一Nk字包括密码密钥。其他所有字则由较小脚标的字递归生成。密钥扩展与Nk的取值有关；分为Nk≥6和Nk≤6两个版本当Nk=Nb=4时，Nr=10，我们需要11个轮密钥，每个轮密钥由16个字节4个字组成，共需44个字。*Nk≤6时的密钥扩展算法KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(imodNk==0)temp=SubByte(RotByte(temp))XorRcon[i/Nk];W[i]=W[i-Nk]Xortemp;}//SubByte表示将SubByte作用于其输入的每个字节。

//RotByte表示将一个4-字节字左移循环一个字节。*Nk>6的密钥扩展算法

KeyExpansion(byteKey[4*Nk]wordW[Nb*(Nr+1)]{for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(imodNk==0)temp=SubByte(RotByte(temp))XorRcon[i/Nk];elseif(imodNk==4)temp=SubByte[temp];W[i]=W[i-Nk]Xortemp;}*轮常数各轮使用独立的轮常数消除轮变换和轮之间的对称性。

Rcon[1]=01000000,Rcon[2]=02000000,Rcon[3]=04000000,Rcon[4]=08000000,Rcon[5]=10000000,Rcon[6]=20000000,Rcon[7]=40000000,Rcon[8]=80000000,Rcon[9]=1B000000,Rcon[10]=36000000,*AES解密算法

为了解密只需要将所有的操作逆序进行，并逆序使用密钥编排即可。其中ShiftRow、SubBytes、MixCollumns均用它的逆操作代替。*应用密码学第六讲分组密码工作模式*应用密码学*回顾：1、分组密码的基本概念。2、DES加密算法。Es-盒置换48bit(48bit)*应用密码学*

分组密码的运行模式电子本ECB（electroniccodebook）密码反馈CFB（cipherfeedback）密码分组链接CBC（cipherblockchaining）输出反馈OFB（outputfeedback）美国NSB在[FIPSPUS74和81]中定义了DES的4种运行模式。----这些模式也可以用于其它分组密码。下面以DES算法为例来介绍这四种模式。*应用密码学*一、电子本ECB模式图3-10ECB模式示意图*应用密码学*电子本ECB模式的特点：一次对64比特的分组加密，且每次加密密钥都相同；每一个明文分组都有一个密文分组与之对应----可以认为有一个非常大的电码本，对任意可能的明文分组，电码本中都有一个对应的密文；最后一个分组长度不够64比特，则要填充；相同的明文分组产生相同的密文分组；适用于短数据的加密；*应用密码学*二、密码分组链接（CBC）模式DES加密DES加密第1次第2次(a)加密DES加密第N次DES加密DES加密DES加密(b)解密图3-11CBC模式示意图*应用密码学*解密时每个密文分组被解密后，再与前一个密文分组分组异或。设：下面证明这种解密结构的确能够获得明文。[证毕]*应用密码学*CBC的特点每次加密使用相同的密钥；重复的明文分组产生不同的密文分组；需要一个初始向量和第一个明文分组异或；--初始向量需要像密钥一样保密，因为，用表示64比特分组的第个比特，那么算法的输入是当前明文分组与前一次密文分组的异或；*应用密码学*由异或特性知撇号表示比特补。如果敌手能够欺骗接收方使用不同的初始向量，则敌手能够在明文的第一个分组中插入自己选择的比特值。CBC模式对加密长于64比特的消息非常合适。CBC模式除了能够获得保密性外，还能够用于认证*应用密码学*三、密码反馈（CFB）模式DES是分组长为64的分组密码，但利用CFB或OFB模式可将DES转换为流密码。流密码不需要填充，且运行是实时的。弃

bit

选bit(a)加密bitbitDES加密bitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bit*应用密码学*(b)解密图3-12CFB模式示意图bitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bit*应用密码学*解密时仍然使用加密算法，这是因为：设是的个最高有效位，那么所以当时：所以*应用密码学*密码反馈（CFB）模式的特点：每个分组使用相同的密钥；与CFB模式一样明文被链接在一起，密文是前面所有明文分组的函数；每次实际被加密的分组长为j，一般是8；CFB模式除了加密外，还用于认证。*应用密码学*四、输出反馈（OFB）模式(a)加密bitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bit*应用密码学*(b)解密图3-12OFB模式示意图bitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bitbitbitDES加密弃

bit

选bit*应用密码学*OFB的特点传输过程中的比特错误不会被传播；？？比CFB更易受到对消息流的篡改攻击。？？每个分组都使用相同的密钥；将加密算法输出的最高j位反馈到移位寄存器；*应用密码学*IDEA算法一、设计原理明文：64比特，密文：64比特，密钥：128比特1、密码强度算法的强度主要通过有效的混淆和扩散来实现。混淆的3种运算（两个16比特输入，一个16比特输出）逐比特异或，表示为模即（65536）整数加法，表示为

，其输入和输出作为16位无符号位来处理。模（即65537）整数乘法，表示为，其输入，输出除16位全为0作为处理外，都作为16位无符号数处理。。*应用密码学*例如：000000000000000010000000000000001000000000000001这是因为这3种运算的任意两种都不满足分配率，例如

这3种运算的任意两种都不满足结合率，例如

这3中运算结合起来使用可对算法的输入提供复杂的变换，从而使得对IDEA的密码分析比仅使用异或运算的DES更安全。*应用密码学*XYXYXYXY000000000101000210000311101000101101101210101311210000210101210210210311311000311101311210311311表3-6IDEA中的3种运算（2比特数）

模模？*应用密码学*

图3-14MA结构2、实现软件软件采用16比特子段处理，可通过使用容易编程的加法、移位等运算实现3种运算。硬件由于加解密相似，差别仅为密钥的使用方式，因此可使用同一器件实现。算法的模块结构可方便VLSI的实现。扩散由乘加（MA）结构实现，如图3-14所示。该结构的输入是两个16比特的子段和两个16比特的子密钥，输出也是两个16比特的子段。这一结构在算法中重复使用了8次。

*应用密码学*补充：集成电路IC，集成电路

IC(InterrgratedCircuit)，是将晶体管、电阻、电容、二极管等电子组件整合装至一芯片(chip)上，由于集成电路的体积极小，使电子运动的距离大幅缩小，因此速度极快且可靠性高，集成电路的种类一般是以内含晶体管等电子组件的