分布式系统课件：Chapter 9 Security

Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DISTRIBUTED SYSTEMSPrinciples and ParadigmsSecond EditionANDREW S.TANENBAUMMAARTEN VAN STEENChapter 9SecurityTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5分布式系统中的安全安全通道身份认证消息完整性机密性授权-访问控制加密-核心技术Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Security Threats,Policies,and MechanismsTypes of security threats to consider:InterceptionInterruption（DoS.）ModificationFabricationTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Security Threats,Policies,and MechanismsSecurity Policy:对系统中的实体允许或禁止采用的行为所给出的明确声明或规定.（实体包括：用户、数据和机器等）Security Mechanism:Encryption（使攻击者不能理解）Authentication（确认身份）Delegate right(授权)Auditing（进行追踪）Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:The Globus Security Architecture(1)Globus是一个支持大规模分布式计算的系统，也称是一个支持大规模分布式计算的系统，也称计算网格其安全策略描述如下：计算网格其安全策略描述如下：1.The environment consists of multiple administrative domains.（每个域有自己的局部安全策略）（每个域有自己的局部安全策略）2.Local operations are subject to a local domain security policy only.3.Global operations require the initiator to be known in each domain where the operation is carried out.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:The Globus Security Architecture(2)4.Operations between entities in different domains require mutual authentication.5.Global authentication replaces local authentication.6.Controlling access to resources is subject to local security only.7.Users can delegate rights to processes.8.A group of processes in the same domain can share credentials(共享凭证共享凭证).Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:The Globus Security Architecture(2)Globus Globus安全策略允许设计者集中开发一个全面的安全解决安全策略允许设计者集中开发一个全面的安全解决方案，考虑多个网域的安全威胁。假设方案，考虑多个网域的安全威胁。假设每个域执行其自身每个域执行其自身的安全策略的安全策略，重要的设计问题是：，重要的设计问题是：远程网域远程网域内用户的表示方法；内用户的表示方法；向用户向用户/代表分配一个代表分配一个远程网域远程网域中的资源；中的资源；引入两种代理：引入两种代理：User ProxyUser Proxy：在有限的时间内代表用户进行操作；：在有限的时间内代表用户进行操作；Resource ProxyResource Proxy：将一个资源上的全局操作转换为遵：将一个资源上的全局操作转换为遵循特定网域安全策略的局部操作。循特定网域安全策略的局部操作。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:The Globus Security Architecture(2)GlobusGlobus安全结构由安全结构由用户用户、用户代理用户代理、资源代理资源代理和一般和一般进程进程组成，组成，定义了定义了4 4个不同协议：个不同协议：1 1、用户、用户创建代理创建代理和向该代理和向该代理委派权限委派权限的方法；的方法；2 2、用户、用户代理代理对远程域中资源提出对远程域中资源提出分配请求分配请求的方式；的方式；3 3、由远程域内中的一个、由远程域内中的一个进程进程进行的资源分配；进行的资源分配；4 4、使用户在远程域内中可知；、使用户在远程域内中可知；Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:The Globus Security Architecture(2)创建代理并委派权限创建代理并委派权限代理代理对远程域资源提出对远程域资源提出分配请求分配请求远程域中远程域中进程进程进行的资源分配进行的资源分配使使用户用户在远程域内中在远程域内中可知可知Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5设计问题设计设计安全的分布式系统的关键：如何安全的分布式系统的关键：如何使用安全使用安全机制实现安全策略机制实现安全策略，问题包括：，问题包括：控制点；控制点；安全机制的分层；安全机制的分层；安全机制的分布；安全机制的分布；简洁性；简洁性；Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Focus of Control有有3 3种方法：种方法：对被访对被访数据数据或或实体实体的保护；的保护；对对操作操作的限制；的限制；对对角色角色的授权；的授权；Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Focus of Control(1)Figure.Three approaches for protection against security threats.(a)Protection against invalid operationsTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Focus of Control(2)Figure.Three approaches for protection against security threats.(b)Protection against unauthorized invocations.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Focus of Control(3)Figure.Three approaches for protection against security threats.(c)Protection against unauthorized users.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Layering of Security Mechanisms(1)Figure.The logical organization of a distributed system into several layers.将将通用服务通用服务与与通信服务通信服务分离分离Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Example:SMDS(2)SMDS(Switched Multimegabit Data Service SMDS-交换多兆位数据服务)是由Bell开发的。SMDS在1990年作为连接FDDI网络到MAN(城域网)的一种基于电信的系统进行了发布。SMDS是一种基于信元的数据传输技术，其传输速率在T载波线路上可以高达155Mbps，在欧洲有广泛的应用。SMDS是一种无连接的传输系统，致力于降低开销，所以将差错检查留给了智能的终端设备，例如交换机和路由器。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Layering of Security Mechanisms(3)Figure.Several sites connected through a wide-area backbone service.安全可以通过SMDS路由器处的加密设备提供，或通过SSL，或安全RPCTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Distribution of Security MechanismsFigure.The principle of RISSC as applied to secure distributed systems.RISSC(reduced interfaces for secure system components)遵循了防止客户及其应用程序直接访问关键服务的原则。TCB(Trusted computing base)是一个系统中安全机制的集合，用于执行一个安全策略。一般根据安全性需求将服务分部在不同的机器以提高系统的安全性。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Cryptography Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5u几千年前人类就有了通信保密的思想和方法。如在代换密码几千年前人类就有了通信保密的思想和方法。如在代换密码(substitution cipher)substitution cipher)中，一个字母或一组字母被另一个字中，一个字母或一组字母被另一个字母或另一组字母所代替母或另一组字母所代替-隐藏明文隐藏明文(Caesar cipher)Caesar cipher)。u19491949年，信息论创始人年，信息论创始人C.E.ShannonC.E.Shannon论证了一般论证了一般经典经典加密方加密方法得到的密文几乎都是可破的，这引起了密码学危机。法得到的密文几乎都是可破的，这引起了密码学危机。u2020世纪世纪6060年代起，随着电子、计算机、结构代数和可计算性年代起，随着电子、计算机、结构代数和可计算性理论的发展，产生了数据加密标准理论的发展，产生了数据加密标准DESDES和公开密钥体制，它们和公开密钥体制，它们成为近代密码学发展史上两个重要的里程碑。成为近代密码学发展史上两个重要的里程碑。Cryptography Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5历 史古罗马：Caesar 密码 ABCDEFGHIGKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCCaesar was a great soldier密码本密文Fdhvdu zdv d juhdw vroglhu明文密文CAESAR 密码：c=(m+3)Mod 26Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5历 史美国南北战争CANYOUUNDERSTAND输入方向输出方向明文：Can you understand 密文：codtaueanurnynsd Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5历史转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，4 轮ENIGMA在1944年装备德国海军.英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5历 史图灵（Alan Mathison Turing）Alan Mathison Turing,19121954.英国数学家。一生对智能与机器之间的关系进行着不懈探索。1936年，24岁的图灵提出“图灵机”的设想。二战期间成功地破译了纳粹德国的密码，设计并制造了COLOSSUS,向现代计算机迈进了重要一步。1952年，图灵遭到警方拘捕，原因是同性恋。1954年6月8日，服毒自杀，年仅42岁。图灵去世12年后，美国计算机协会以他的名字命名了计算机领域的最高奖“图灵奖”。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5密码学的基本概念密码编码：密码编码：通过信息编码使信息保密密码分析：密码分析：用分析方法解密信息基本术语：基本术语：明文(plain text)，密文(cipher text)加密(encrypt,encryption),解密(decrypt,decryption)密码算法（Algorithm），密码（Cipher）；用来加密和解密的数学函数 c=E(m),m=D(c),D(E(m)=m密钥（Key）:算法中的一个变量 c=EKe(m),m=DKd(c),DKd(EKe(m)=mTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5一个简单的加密算法异或110101011000110011xxxxxxxxTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5一个简单的加密算法异或异或 密文：0 1 1 0 解密：密钥：0 1 0 1 明文：0 0 1 1已知明文、密文，怎样求得密钥？C=P KP=C K异或运算（不带进位加法）：明文:0 0 1 1 加密：密钥:0 1 0 1 密文：0 1 1 0K=C P只知道密文，如何求得密文和密钥？Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5密码学的基本概念（Cont.）密码学基本模型密码学基本模型解密：m=DK(c)发送方接收方EncryptionDecryption加密：c=EK(m)不安全信道密码分析（Cryptanalysis）plaintextciphertextplaintextKeyKeyTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5CryptographyFigure.Intruders and eavesdroppers in communication.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5 机密性机密性:提供只允许特定用户访问和阅读信息，提供只允许特定用户访问和阅读信息，任何非授权用户对信息都不可理解的服务。任何非授权用户对信息都不可理解的服务。完整性完整性:提供确保数据在存储和传输过程中不提供确保数据在存储和传输过程中不被未授权修改（窜改、删除、插入和重放等）的被未授权修改（窜改、删除、插入和重放等）的服务。服务。认认 证证:提供与数据和身份识别有关的服务。提供与数据和身份识别有关的服务。抗否认性抗否认性:提供阻止用户否认先前的言论或行提供阻止用户否认先前的言论或行为的服务。为的服务。Cryptography-作用Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5 机密性机密性:-通过通过数据加密数据加密实现实现.完整性完整性:-通过通过数据加密、数据散列数据加密、数据散列或或数字签数字签名名来实现来实现.认认 证证:-通过通过数据加密、数据散列数据加密、数据散列或或数字签数字签名名来实现来实现.抗否认性抗否认性:-通过通过对称加密对称加密或或非对称加密，非对称加密，以以及及数字签名数字签名等，并借助可信的注册机构或证书机等，并借助可信的注册机构或证书机构的辅助，提供这种服务构的辅助，提供这种服务.Cryptography-实现Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5密码算法的分类古典古典密码算法和密码算法和现代现代密码算法密码算法 算法和密钥是否分开算法和密钥是否分开?对称对称密钥密码和密钥密码和非对称非对称密钥密码密钥密码 加解密是否使用相同的密钥加解密是否使用相同的密钥?分组分组密码和密码和序列序列密码密码 操作的数据单元是否分块操作的数据单元是否分块?Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5古典密码和现代密码古典密码（受限密码）古典密码（受限密码）代替密码（代替密码（Substitution CipherSubstitution Cipher）；）；换位密码换位密码 (transposition Cipher)(transposition Cipher)；代替密码与换位密码的组合；代替密码与换位密码的组合；缺陷缺陷 密码体制的密码体制的安全性安全性在于保持算法本身的在于保持算法本身的保密性保密性 受限算法的缺陷受限算法的缺陷n 不适合大规模生产不适合大规模生产n 不适合较大的或者人员变动较大的组织不适合较大的或者人员变动较大的组织n 用户无法了解算法的安全性用户无法了解算法的安全性Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5古典密码和现代密码（Cont.）现代密码算法现代密码算法 把算法和密钥分开把算法和密钥分开 密码算法可以公开，密钥保密密码算法可以公开，密钥保密 密码系统的安全性在于保持密码系统的安全性在于保持密钥密钥的的保密性保密性发送方接收方mm加密E解密Dc=Ek(m)m=Ek(c)密码分析密钥分配（秘密信道）kkTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5对称密码算法和非对称密码算法n对称密钥密码算法（传统密码算法/秘钥密码算法）加密和解密使用相同的密钥 Ke=Kd；数学表示：数学表示：常用算法：DES,IDEA,Blowfish,RC2等；n优点：加密速度快，便于硬件实现和大规模生产；n缺点：密钥分配：必须通过保密的信道；无法用来签名和抗抵赖（没有第三方公证时）；P=DK（EK（P）Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5对称密码和非对称密码（Cont.）n非对称密码，又称公开密钥密码算法加密和解密使用不同的密钥（Kp,Ks)，把加密密钥公开，解密密钥保密：c=EKp(m),m=DKs(c)数学表示：常用算法：RSA,DSA,背包算法，ElGamal,椭圆曲线等；n优点：密钥分配：不必保持信道的保密性；密钥个数：n pair；可以用来签名和抗抵赖；n缺点：加密速度慢，不便于硬件实现和大规模生产；P=DKD（EKE（P）Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5分组密码和序列密码n分组密码（Block Cipher）一次加密或解密操作作用于一个数据块，比如64位；n序列密码（Stream Cipher）一次加密或解密操作作用于一位或者一个字节；Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5l 单向函数单向函数(One-way Function):已知已知x x，很容易计算，很容易计算f(x),f(x),但已知但已知f(x)f(x)，却难于计算出，却难于计算出x x。作用：作用：不能用作加密不能用作加密,可以用于鉴别，过程如下：可以用于鉴别，过程如下：n AliceAlice将她的口令送给计算机将她的口令送给计算机;n 计算机完成口令的单向函数计算计算机完成口令的单向函数计算;n 计算机把单向函数的运算结果和它以前存储计算机把单向函数的运算结果和它以前存储的值进行比较。的值进行比较。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5 单向散列（单向散列（Hash)Hash)函数函数把可变输入长度串（称预映射，把可变输入长度串（称预映射，pre_image)pre_image)转换成固定长转换成固定长度的输出串（称散列值）。度的输出串（称散列值）。特点：特点：u难于产生难于产生2 2个预映射的值，使它们的散列值个预映射的值，使它们的散列值相同相同;u散列函数是公开的，对处理过程不保密散列函数是公开的，对处理过程不保密;u平均而言，预映射的单个位的改变，将引起散列值中一半平均而言，预映射的单个位的改变，将引起散列值中一半以上位的改变；以上位的改变；u已知一个散列值，要找到预映射，使它的散列值等于已知已知一个散列值，要找到预映射，使它的散列值等于已知的散列值在计算上是不可行的；的散列值在计算上是不可行的；u一般情况下，应使用不带密钥的单向散列函数，以便任何一般情况下，应使用不带密钥的单向散列函数，以便任何人都能验证散列值。人都能验证散列值。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5说明：说明：消息鉴别码（消息鉴别码（Message Authentication Code,MAC),Message Authentication Code,MAC),它它是带有密钥的单向散列函数，散列值是预映射的值和密钥的是带有密钥的单向散列函数，散列值是预映射的值和密钥的函数。函数。预映射鉴别密钥单向散列函数散列值Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5CryptographyFigure.Notation used in this chapter.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5对称密钥算法简介u 加密和解密使用相同的密钥：KE=KDu 密钥必须使用秘密的信道分配；发送方接收方mm加密E解密Dc=Ek(m)m=Dk(c)密钥分配（秘密信道）kkTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5对称密钥算法简介(Cont.)常用对称密钥密码算法：DES(Data Encryption Standard)及其各种变形；IDEA(International Data Encryption Algorithm)；RC2,RC4,RC5；AES(Advanced Encryption Standard)；CAST-128；Blowfish；Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DES算法原理IBM 公司70年代初提出，80年代成为国家数据加密标准；DES是一种对称密钥算法，密钥长度有40位、56位、128位等.56bits 加上奇偶校验，通常写成64bits；也是一种分组加密算法，64 bits为一个分组；采用先代替后置换的方式;基本思想：混乱（Confusion）和扩散（Diffusion）使用标准的算术和逻辑运算 Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DES密码体制：它是应用密码体制：它是应用56位密钥，加密位密钥，加密64比特明文分组的比特明文分组的分组秘钥密码体制；分组秘钥密码体制；DES加密算法：加密算法：DES(m)=IP-1 T16 T15.T2 T1 IP(m)（一）初始置换：（一）初始置换：x0=L0R0=IP(x)；（二）（二）16次迭代：次迭代：xi-1=Li-1Ri-1，Li=Ri-1，Ri=Li-1 f(Ri-1,ki)i=1,2,16；（三）逆置换：（三）逆置换：x16=L16R16，y=IP-1(x16)。密钥生成器：密钥密钥生成器：密钥ki是由是由56位系统密钥位系统密钥k生成的生成的32位子密钥。位子密钥。函数函数f及及P/E/S盒：盒：f(Ri-1,ki)=P(S(E(Ri-1)ki)Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DES算法Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DES算法Round16 IP-1 Roud1 Roud2 Initial Permutation Plaintext64bitsciphertext64bitsPermuted Choice1 Left Circular ShiftLeft Circular ShiftLeft Circular ShiftPermuted Choice2 Permuted Choice2 Permuted Choice2 Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5初始换位（IP）初始换位（IP）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157M=m1m2,m62m63,m64M=m58m50,m23m15,m7IP(M)Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5一轮迭代Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5一轮迭代Li-1Ri-1LiRi-1Ri=Li-1 f(Ri-1,Ki)Ki(48bits)32 bits32 bits32 bitsE-盒置换 S-盒代替P-盒置换32 bitsf4832Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5扩展置换(E)将Ri从32位扩展到48位目的：输入的一位影响下一步的两个替换，使得输出对输入的依赖性传播得更快，密文的每一位都依赖于明文的每一位1 2 3 45 6 7 81 2 3 4 5 6 7 8324832 1 2 3 4 5 4 5 6 7 8 9 8 9.31 32 11 2 3 4 5 6 7 8 9 10 11 12 13 14 46 47 48Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5S盒置换将48比特压缩成32比特ES1S2S3S4S5S6Ri-1 (32 bits)Ki(48bits)48 bitsS7S8Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5末置换末置换4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572558504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157初始置换IP-1(IP(M)=MTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5Symmetric Cryptosystems密钥的生成Figure.Details of per-round key generation in DES.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5DES解密过程nDES解密过程与加密过程完全相似，只不过将16次迭代的子密钥顺序倒过来，即：m=DES-1(c)=IP-1 T1T2.T15 T16 IP(c)n可以证明：DES(DES-1(m)=mTanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5关于关于DES的讨论的讨论S S盒是唯一非线性组件；盒是唯一非线性组件；DESDES的密钥量太小：密钥量为的密钥量太小：密钥量为2 25656 ；19771977年：年：Diffie.HellmanDiffie.Hellman提出制造一个每秒测试提出制造一个每秒测试10106 6的的VLSIVLSI芯片，则一天就可以搜索完整个密钥空间，当时造价芯片，则一天就可以搜索完整个密钥空间，当时造价2 2千万千万美元；美元；CRYPTO93CRYPTO93：R.SessionR.Session，M.WienerM.Wiener提出并行密钥搜索芯片，提出并行密钥搜索芯片，每秒测试每秒测试5x1075x107个密钥，个密钥，57605760片这种芯片，造价片这种芯片，造价1010万美元，万美元，平均一天即可找到密钥。平均一天即可找到密钥。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5InternetInternet的超级计算能力：的超级计算能力：19971997年年1 1月月2828日，美国日，美国RSARSA数据数据安全公司在安全公司在InternetInternet上开展了一项上开展了一项“秘密密钥挑战秘密密钥挑战”的竞的竞赛，悬赏一万美元，破解一段赛，悬赏一万美元，破解一段DESDES密文。计划公布后，得到密文。计划公布后，得到了许多网络用户的强力相应。科罗拉州的程序员了许多网络用户的强力相应。科罗拉州的程序员R.VerserR.Verser设计了一个可以通过互联网分段运行的密钥搜索程序，组设计了一个可以通过互联网分段运行的密钥搜索程序，组织了一个称为织了一个称为DESCHALLDESCHALL的搜索行动，成千上万的的志愿者的搜索行动，成千上万的的志愿者加入到计划中。加入到计划中。关于关于DES的讨论的讨论Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5第第9696天，即竞赛公布后的第天，即竞赛公布后的第140140天，天，19971997年年6 6月月1717日晚上日晚上1010点点3939分，美国盐湖城分，美国盐湖城InetzInetz公司职员公司职员M.SandersM.Sanders成功地找到成功地找到了密钥，解密出明文：了密钥，解密出明文：The unknown Message isThe unknown Message is：“Stronge cryptography makes the word a safer Stronge cryptography makes the word a safer place”(place”(高强度密码技术使世界更安全高强度密码技术使世界更安全)。InternetInternet仅仅仅仅利用闲散资源，毫无代价就破译了利用闲散资源，毫无代价就破译了DESDES密码，这是对密码密码，这是对密码方法的挑战，是方法的挑战，是InternetInternet超级计算能力的显示超级计算能力的显示.Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5差分分析法：除去穷举搜索密钥外，还有其他形式的攻击差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著名的有方法，最著名的有Biham，Shamir的差分分析法。这是的差分分析法。这是一个选择明文攻击方法。虽然对一个选择明文攻击方法。虽然对16轮轮DES没有攻破，但是，没有攻破，但是，如果迭代的轮数降低，则它可成功地被攻破。例如，如果迭代的轮数降低，则它可成功地被攻破。例如，8轮轮DES在一个个人计算机上只需要在一个个人计算机上只需要2分钟即可被攻破。分钟即可被攻破。因此，现在基本上不用因此，现在基本上不用DES，而采用，而采用3重重DES。Tanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-51.1.设计公钥密码体制的基本原理设计公钥密码体制的基本原理 RSARSA来自来自Revest,ShanirRevest,Shanir和和Adieman3Adieman3个发明人名字缩写；个发明人名字缩写；在公钥密码中，解密密钥和加密密钥不同，从一个难于推在公钥密码中，解密密钥和加密密钥不同，从一个难于推出另一个，加密密钥是可以公开的；出另一个，加密密钥是可以公开的；基本思想：利用没有任何已知的方法能够有效的找到大数基本思想：利用没有任何已知的方法能够有效的找到大数的素因子。私钥和公钥都是的素因子。私钥和公钥都是2 2个非常大的素数，破译个非常大的素数，破译RSARSA相相当于寻找这两个素数；当于寻找这两个素数；Public-Key Cryptosystems:RSATanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-5陷门单向函数：陷门单向函数：f(x)满足单向函数，若给定某些满足单向函数，若给定某些辅助信辅助信息息时又容易计算单向函数时又容易计算单向函数 f 的逆的逆 f-1，则称，则称 f(x)是一个是一个陷陷门单向函数。门单向函数。关键是找一个陷门单向函数，关键是找一个陷门单向函数，这一这一辅助信息辅助信息就是秘密的就是秘密的解密密钥。解密密钥。Public-Key Cryptosystems:RSATanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-52.2.公钥密码体制公钥密码体制公钥密码体制称为双密钥密码体制双密钥密码体制或非对称密码体制非对称密码体制.单钥加密单钥加密中使用的密钥称为秘钥秘钥(Secret Key)。公开密钥加密公开密钥加密中使用的两个密钥分别称为公开密钥公开密钥(Public Key)和私有密钥私有密钥(Private Key)。公开密钥的应用：(1)加密和解密；(2)数字签名；(3)密钥交换。Public-Key Cryptosystems:RSATanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserved.0-13-239227-53.3.公开密钥密码系统原理公开密钥密码系统原理公开密钥算法用一个密钥进行加密，而用另一个不同但是相关的密钥进行解密：仅仅知道密码算法和加密密钥而要确定解密密钥，在计算上是不可能的；两个相关密钥中任何一个都可以用作加密而让另外一个解密。4.4.公钥密码体制的安全性公钥密码体制的安全性（计算安全性）在公钥密码算法中求陷门单向函数的逆的复杂性决定的。没有任何已知的方法能够有效的找到大数的素因子。Public-Key Cryptosystems:RSATanenbaum&Van Steen,Distributed Systems:Principles and Paradigms,2e,(c)2007 Prentice-Hall,Inc.All rights reserv