Ch02 分组密码体制

1、1网络与信息安全网络与信息安全Ch02 分组密码体制2本章学习目的本章学习目的o掌握掌握密码学的基本概念密码学的基本概念n分组密码、流密码、对称密码、非对称密码分组密码、流密码、对称密码、非对称密码 o理解理解经典密码体制的原理经典密码体制的原理o理解理解分组密码原理分组密码原理o了解数据加密标准、高级加密标准了解数据加密标准、高级加密标准o了解流密码了解流密码 一一 密码学的基本概念密码学的基本概念31 1 基本概念基本概念 o加密技术的基本思想就是伪装信息，使非法接入者加密技术的基本思想就是伪装信息，使非法接入者无法理解信息的真正含义。无法理解信息的真正含义。o伪装伪装就是对信息进行一组可

2、逆的数学变换。我们称就是对信息进行一组可逆的数学变换。我们称伪装前的原始信息为伪装前的原始信息为明文明文,经伪装的信息为经伪装的信息为密文密文，伪，伪装的过程为装的过程为加密加密，用于解除伪装还原出原始信息的，用于解除伪装还原出原始信息的过程为过程为解密解密。o加密加密Encrypt 解密解密Decrypto密文密文ciphertext 明文明文plaintext,一般一般m表示表示o密钥密钥Key一一 密码学的基本概念密码学的基本概念41 1 基本概念基本概念 o用于对信息进行加密的一组数学变换称为用于对信息进行加密的一组数学变换称为加密加密算法算法。o用于对信息进行解决的数学变换就是用于对

3、信息进行解决的数学变换就是解密算法解密算法。o为了有效控制加密、解密算法的实现，在这些为了有效控制加密、解密算法的实现，在这些算法的实现过程中，需要有某些只被通信双方算法的实现过程中，需要有某些只被通信双方所掌握的专门的、关键的信息参与，这些信息所掌握的专门的、关键的信息参与，这些信息就称为就称为密钥密钥。用作加密的称。用作加密的称加密密钥加密密钥，用作解，用作解密的称作密的称作解密密钥解密密钥。一一 密码学的基本概念密码学的基本概念52 2 密码学与密码体制密码学与密码体制 o密码学两个分支：密码学两个分支：密码编码学密码编码学与与密码分析学密码分析学：n密码编码学主要研究对信息进行编码实现

4、信息密码编码学主要研究对信息进行编码实现信息保密性的科学，即保密性的科学，即加密算法加密算法n密码分析学是研究、分析、破译密码的科学，密码分析学是研究、分析、破译密码的科学，即如何从密文推出明文、密钥或即如何从密文推出明文、密钥或解密算法解密算法的学的学问问n这两种技术相互依存、相互支持、共同发展这两种技术相互依存、相互支持、共同发展一一 密码学的基本概念密码学的基本概念62 2 密码学与密码体制密码学与密码体制 o加密算法的三个发展阶段：加密算法的三个发展阶段：n经典密码体制经典密码体制n对称密钥密码（即：单钥密码体制）对称密钥密码（即：单钥密码体制）n公钥密钥密码（即：双钥密码体制）公钥密

5、钥密码（即：双钥密码体制）o这些算法按密钥管理的方式可以分为这些算法按密钥管理的方式可以分为对称对称算法算法与与非对称算法非对称算法两大类，即我们通常所两大类，即我们通常所说的说的对称密钥密码体制对称密钥密码体制和和非对称密钥密码非对称密钥密码体制体制。 一一 密码学的基本概念密码学的基本概念73 3 对称密码体制对称密码体制 o加密密钥和解密密钥相同，或实质上等同（即加密密钥和解密密钥相同，或实质上等同（即从一个可以推出另外一个），我们称其为从一个可以推出另外一个），我们称其为对称对称密钥密钥或或单钥密码体制单钥密码体制。o加密方式有两种：加密方式有两种：n对明文按字符逐位加密，称为流密码或

6、序列密码o序列密码是手工和机械密码时代的主流方式。n先对明文消息分组，再逐组加密，称为分组密码o分组密码将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。o最典型的就是1977年美国国家标准局颁布DES算法。一一 密码学的基本概念密码学的基本概念8单密钥密码的加、解密过程单密钥密码的加、解密过程 3 3 对称密码体制对称密码体制 一一 密码学的基本概念密码学的基本概念93 3 对称密码体制对称密码体制 o加密密钥和解密密钥相同，或实质上等同（即从一加密密钥和解密密钥相同，或实质上等同（即从一个可以推出另外一个），我们称其为个可以推出另外一个），我们称其为对称密钥对称

7、密钥或或单单钥密码体制钥密码体制。o单钥密码体制的单钥密码体制的优点优点：安全性高、加解密速度快：安全性高、加解密速度快o其其缺点缺点是：是：n进行保密通信之前，双方必须通过安全信道传送所用的密进行保密通信之前，双方必须通过安全信道传送所用的密钥。相距较远的用户，较大的代价，甚至难以实现。钥。相距较远的用户，较大的代价，甚至难以实现。n例如，在拥有众多用户的网络环境中使例如，在拥有众多用户的网络环境中使n个用户之间相互个用户之间相互进行保密通信，若使用同一个对称密钥，一旦密钥被破解，进行保密通信，若使用同一个对称密钥，一旦密钥被破解，整个系统就会崩溃；使用不同的对称密钥，则密钥的个数整个系统就

8、会崩溃；使用不同的对称密钥，则密钥的个数几乎与通信人数成正比几乎与通信人数成正比需要需要n*(n-1)个密钥个密钥。由此可。由此可见，若采用对称密钥，大系统的密钥管理几乎不可能实现。见，若采用对称密钥，大系统的密钥管理几乎不可能实现。一一 密码学的基本概念密码学的基本概念10保密通信系统模型保密通信系统模型 4 4 保密通信系统模型保密通信系统模型 一一 密码学的基本概念密码学的基本概念115 5 非对称密码体制非对称密码体制 o若加密密钥和解密密钥不相同，从其中一个难以推出另一个，则若加密密钥和解密密钥不相同，从其中一个难以推出另一个，则称为称为非对称密钥非对称密钥或或双钥密码体制双钥密码体

9、制。o采用双钥密码体制的主要特点是采用双钥密码体制的主要特点是将加密和解密功能分开将加密和解密功能分开，因而可，因而可以实现多个用户加密的消息只能由一个用户解读，或只能由一个以实现多个用户加密的消息只能由一个用户解读，或只能由一个用户加密消息而使多个用户可以解读。用户加密消息而使多个用户可以解读。o在使用双钥体制时，每个用户都有一对预先选定的密钥：一个是在使用双钥体制时，每个用户都有一对预先选定的密钥：一个是可以公开的可以公开的(公钥公钥)，以，以k1表示，另一个则是秘密的表示，另一个则是秘密的(私钥私钥)，以，以k2表示，公钥表示，公钥k1可以像电话号码一样进行注册公布，私钥是其可以像电话号

10、码一样进行注册公布，私钥是其拥有者自己保存。因此双钥体制又称作拥有者自己保存。因此双钥体制又称作公钥体制公钥体制(Public Key System) 。o最有名的双钥密码体制是最有名的双钥密码体制是1977年由年由Rivest、Shamir和和Adleman等三人提出的等三人提出的RSA密码算法。密码算法。一一 密码学的基本概念密码学的基本概念12双钥密码体制的通信模型双钥密码体制的通信模型 5 5 非对称密码体制非对称密码体制 一一 密码学的基本概念密码学的基本概念13双钥密码体制既可用于实现公共通信网的保密通信，也可用于认证系统双钥密码体制既可用于实现公共通信网的保密通信，也可用于认证系

11、统中对消息进行数字签名，同时实现信息保密性和对消息的认证，在明文中对消息进行数字签名，同时实现信息保密性和对消息的认证，在明文消息空间和密文消息空间等价，且加密、解密运算次序可换，即消息空间和密文消息空间等价，且加密、解密运算次序可换，即E Eklkl(D(Dk2k2(m)=D(m)=Dk2k2(E(Ek1k1(m)=m(m)=m。 双钥保密和认证体制双钥保密和认证体制 6 6 双密钥双密钥+ +认证系统认证系统 一一 密码学的基本概念密码学的基本概念14实际网络多采用实际网络多采用双钥和单钥密码双钥和单钥密码相结合的混合加密体制，即使用单相结合的混合加密体制，即使用单钥密码进行钥密码进行加解

12、密明文或密文加解密明文或密文，采用双钥密码实现，采用双钥密码实现密钥传送密钥传送。这样。这样既解决了密钥管理的困难，又解决了加、解密速度的问题。既解决了密钥管理的困难，又解决了加、解密速度的问题。 7 7 混合加密系统混合加密系统 一一 密码学的基本概念密码学的基本概念158 8 密码学的作用密码学的作用 o密码学主要的应用形式有密码学主要的应用形式有数字签名、身份认证、消息认证（也数字签名、身份认证、消息认证（也称数字指纹）、数字水印称数字指纹）、数字水印等几种，这几种应用的关键是密钥的等几种，这几种应用的关键是密钥的传送，网络中一般采用混合加密体制来实现。密码学的应用主传送，网络中一般采用

13、混合加密体制来实现。密码学的应用主要体现了以下几个方面的功能。要体现了以下几个方面的功能。n（1）维持机密性）维持机密性o传输中的公共信道和存储的计算机系统容易受到被动攻击传输中的公共信道和存储的计算机系统容易受到被动攻击（如截取、偷窃、拷贝信息）和主动攻击（如删除、更改、（如截取、偷窃、拷贝信息）和主动攻击（如删除、更改、插入等操作）。加密关键信息，让人看不懂而无从攻击。插入等操作）。加密关键信息，让人看不懂而无从攻击。n（2）可用性）可用性o由于网上的通信双方互不见面，必须在相互通信时（交换敏由于网上的通信双方互不见面，必须在相互通信时（交换敏感信息时）确认对方的真实身份，即消息的接收者应

14、该能够感信息时）确认对方的真实身份，即消息的接收者应该能够确认消息的来源，入侵者不可能伪装成他人。确认消息的来源，入侵者不可能伪装成他人。一一 密码学的基本概念密码学的基本概念168 8 密码学的作用密码学的作用 n（3）保证完整性）保证完整性o接收者能够验证在传送过程中是否被篡改；入侵者不接收者能够验证在传送过程中是否被篡改；入侵者不可能用假消息代替合法消息。可能用假消息代替合法消息。n（4）抗抵赖）抗抵赖(不可否认性不可否认性)o在网上开展业务的各方在进行数据传输时，必须带有在网上开展业务的各方在进行数据传输时，必须带有自身特有的、无法被别人复制的信息，以保证发生纠自身特有的、无法被别人复

15、制的信息，以保证发生纠纷时有所对证，发送者事后不可能否认他发送的消息。纷时有所对证，发送者事后不可能否认他发送的消息。 一一 密码学的基本概念密码学的基本概念179 9 密码分析学密码分析学 一一 密码学的基本概念密码学的基本概念o密码编码学：对信息进行编码实现隐蔽信息的一门学问。o密码分析学：分析破译密码的学问。两者相互对立、促进。o1、常用的密码分析攻击有四类、常用的密码分析攻击有四类 ：n前提：前提：加密算法：公开加密算法：公开 。 攻击目标：获得密钥攻击目标：获得密钥Kn唯密文攻击（ciphertext only attacks）。o已知：截获部分密文n已知明文攻击（know plai

16、ntext attacks）。o已知：截获部分密文；若干明文密文对。n选择明文攻击（chosen plaintext attacks）。o已知：截获部分密文；自主选择的明文密文对。n选择密文攻击o暂时接近密码机，可选择密文串，并构造出相应的明文。189 9 密码分析学密码分析学 一一 密码学的基本概念密码学的基本概念o2、算法的安全性、算法的安全性 o密码算法具有不同的安全等级 :以下情况可能是安全的n破译算法的代价大于加密数据的价值 n破译算法所需的时间大于加密数据保密的时间 n用单密钥加密的数据量小于破译算法需要的数据量 oShannon理论：仅当密钥至少和明文一样长时才无条件安全。o如果

17、不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的；只有一次一密乱码本，才是无条件安全的。o所有其它的密码系统在唯密文攻击中都是可破的 （蛮力攻击 ）。191 1 经典密码体制经典密码体制 二二 经典密码体制的基本原理经典密码体制的基本原理o单表代换密码n密钥移位固定o多表代换密码n密钥移位周期固定o多字母代换密码n明文分组变换201 1 单表代换密码单表代换密码 二二 经典密码体制的基本原理经典密码体制的基本原理o单表代换密码：对所有的明文字母都用一个固定的代换进行加密 ，因而称为单表代换密码。加密过程中是从明文字母表到密文字母表的一一映射。例：恺撒（Caes

18、ar)密码。n明文a b c d e f g h I j k l m n o p q r s t u v w x y zn密文X N Y A HP OGZQWB T S F L RC VMU E K J D Io解决函数是一个逆置换，即解密算法：nABC DE F G HI J K L MN O PQRS T U VW XYZnd l r y v o h e z x w p t b g f j q n m u s k a c Io例：MGZVY ZLGHC MHJMY XSSFM NHAHY CDLMHAo解：thisc ipher textc annot bedec ryptedo含义：Th

19、is ciphertext can not be decrypted211 1 单表代换密码单表代换密码 二二 经典密码体制的基本原理经典密码体制的基本原理o英语26个字母中，各字母出现的频率不同而稳定，经过大量统计，可以给出了各字母出现的频率值。英文明文字母按出现概率大小分组表：o1 e 0.1o2 t a o i n s h r 0.05-0.1o3 d l 0.03-0.05o4 c u m w f g y p b 0.01-0.03o5 v k j x q z 0.01221 1 单表代换密码单表代换密码 二二 经典密码体制的基本原理经典密码体制的基本原理o字母、三字母组合是分析单表密

20、码的有力手段 。o英语单词以e、s、t、d双结尾的超过一半；以t、a、s、w 为起始字母的约为一半。o某些常用用法也会提供有价值的线索，如信的开头写Dear ；源程序的某一位置是版权声明；电子资金传送报头格式。 o单表密码的弱点：明文和密文字母之间的一一代替关系。这使得明文中的一些固有特性和规律（比如语言的各种统计特性）必然反映到密文中去。232 2 多表代换密码多表代换密码 二二 经典密码体制的基本原理经典密码体制的基本原理o多表代换密码多表代换密码：由多个单字母密码构成，每个密钥加密对应位置的明文。 例：维吉尼亚密码。o维吉尼亚（维吉尼亚（Vigenere）密码：）密码：典型的多表密码，即

21、一个明文字母可表示为多个密文字母。o例如：明文为System，密钥为dog，a,b,cx,y,z分别用0,1,223,24,25来表示，加密过程如下：o明文：S y s t e mo密钥：d o g d o go密文：V m g w r so在这个例子中，明文事每三个字母中的第一、第二、第三个字母分别移动（mod 26）3个，14个和6个位置。243 3 多字母代换密码多字母代换密码二二 经典密码体制的基本原理经典密码体制的基本原理o多字母代替密码：明文字符串按固定长度被分组，然后成组加密。如：o明文：wearediscoveredsaveyourselfabco首先将明文分成6个字母长的明文

22、组：o分组：weared iscove redsav eyours elfabco将每6字母长的明文组按密钥k重新排列如下：oAEWDRE CVIEOS DARVSE ORESUY FBECALo密文： AEWDRECVIEOSDARVSEORESUYFBECAL1 2 3 4 5 63 5 1 6 4 2k251 1 分组密码基本含义分组密码基本含义三三 分组密码原理分组密码原理o分组密码系统对不同的组采用同样的密钥K进行加、解密。n设密文组为y=y1y2ym，n则对明文组x=x1x2xm,o用密钥k加密可得到:ny=ek(x1) ek(x2) ek(xm).262 2 分组密码设计原理分组

23、密码设计原理三三 分组密码原理分组密码原理o进一步分析：n分组密码将明文消息编码表示后的明文数字序列x0、x1、x2、,划分成长度为n的组:nX=(x0,x1,x2, xn-1),可看到长度为n的矢量n每组分别在密钥k=(k0,k1,k2, km-1)的控制下变换成等长的密文序列nY=(y0,y1,y2, yn-1),也可看到成n维矢量n加密函数是E：VnKVn,是n维矢量空间，K为密钥空间。n过程如下图所示272 2 分组密码设计原理分组密码设计原理三三 分组密码原理分组密码原理明文明文(x0,xn-1)y=(y0,yn-1)密钥密钥k=(k0,km-1)密钥密钥k=(k0,km-1)加密算

24、法密文密文解密算法明文明文(x0,xn-1)y=ek(x0) ek(x2) ek(xn-1)分组密码模型分组密码模型283 3 分组密码设计的一般原则分组密码设计的一般原则三三 分组密码原理分组密码原理o分组长度应足够大，使得不同明文分组的个数2n足够大，以防止明文被穷举法攻击。o密钥空间应足够大，尽可能消除弱密钥，从而使所有密钥同等概率，以防穷举密钥攻击。o由密钥确定的算法要足够复杂，充分实现明文与密钥的扩散和混淆。o软件实现的要求：尽量使用适合编程的子块和简单的算法。o硬件实现的要求：加密和解密应具有相似性，即加密和解决过程的不同应仅仅在于密钥的使用方式上，以便采用同样的器件来实现加密和解

25、密，以节省费用和体积。尽可能采用标准的组件结构，以便能在超大规模集成电路中实现。294 4 分组密码的一般结构分组密码的一般结构三三 分组密码原理分组密码原理o一般有两种：nFeistel网络结构o由Feistel发明，被DES采用nSP网络结构o可逆函数S，置换作用P，是一种重要的结构oAES标准采用此结构301 DES1 DES加密标准加密标准四四 数据加密标准数据加密标准o发明人：IBM公司W. Tuchman 和 C. Meyer 1971-72年研制。o产生：美国商业部的国家标准局NBS1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。IBM的LUCIFE

26、R的改进方案被采纳。o标准化：于1976年11月被美国政府采用，DES随后被美国国家标准局和美国国家标准协会(American National Standard Institute， ANSI) 承认。1977年1月以数据加密标准DES（Data Encryption Standard）的名称正式向社会公布。于1977年7月15日生效。oDES的发展：如衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等。311 DES1 DES加密标准加密标准四四 数据加密标准数据加密标准o破解：发明人在1977年，人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密，而且需

27、要12个小时的破解才能得到结果。 o1997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。o1997年1月，用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天 ；1998年7月， “第2-2届DES挑战赛（DES Challenge II-2）” 把破解DES的时间缩短到了只需56个小时； “第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5小时 。322 DES2 DES算法框图算法框图四四 数据加密标准数据加密标准输入64位比特明文数据初始变换IP初始逆变换IP-1在密钥控制下16轮迭代交换

28、左右32比特输出64位比特密文数据333 DES3 DES的问题讨论的问题讨论四四 数据加密标准数据加密标准oDES算法中，除S盒外，所有计算都是线性的。有人质疑S盒可能存在陷门，但至今没发现。o担心实际56比特的密钥长度不足以抵抗穷举攻击，因为密钥量只有2561017个。事实也如此，1997年即被破解。343 DES3 DES的问题讨论的问题讨论四四 数据加密标准数据加密标准oDES算法中，除S盒外，所有计算都是线性的。有人质疑S盒可能存在陷门，但至今没发现。o担心实际56比特的密钥长度不足以抵抗穷举攻击，因为密钥量只有2561017个。事实也如此，1997年即被破解。354 DES4 DE

29、S的变形的变形四四 数据加密标准数据加密标准o双重DESn已知明文P和两个密钥K1和K2，密文为C=EK2(EK1(P),解决过程做逆运算：P=DK1(DK2(C)n问题：o是否存在K3,使得EK2(EK1(P)=EK3(P)? o直到1992年，这个结论才被证明是不成立的。o中途攻击n已知明文、密文对（P,C）,是可能找到K1和K2的；o三重DESn为解决中途攻击而设计，密钥长度2112.361 1 高级加密标准高级加密标准五五 高级加密标准高级加密标准oNIST(国家标准技术研究所)1997年9月12日发出征集高级加密标准的通知 。n1998年8月首次选出15个候选者，1999年3月遴选出5个，包括：E2、MARS、RC6、Rijndael、Twofish。n2000年10月2日，美国商务部部长宣布比利时的Rijndael算法成为新的AES。o选择的基本条件：公开；分组单钥，分组长度128；密钥可为128，192，256；可软硬件实现。o优劣标