密码学ppt课件

17.1 密码学的基础知识密码学的基础知识人们希望把重要信息通过某种变换转换成秘人们希望把重要信息通过某种变换转换成秘密形式的信息。转换方法可以分为两大类：密形式的信息。转换方法可以分为两大类：n n隐写术隐写术隐写术隐写术，隐蔽信息载体，隐蔽信息载体信号的存在，古代常用。信号的存在，古代常用。n n编码术编码术编码术编码术，将载荷信息的信号进行各种变换使它们不为，将载荷信息的信号进行各种变换使它们不为非授权者所理解。非授权者所理解。在利用现代通讯工具的条件下，隐写术受到在利用现代通讯工具的条件下，隐写术受到很大限制，但编码术却以计算机为工具取得了很很大限制，但编码术却以计算机为工具取得了很大的发展。大的发展。17.1 密码学的基础知识 人们希望12普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.1.1 密码学中的基本概念密码学中的基本概念 n n真实数据称为真实数据称为明文明文明文明文MM n n对真实数据施加变化的过程称为对真实数据施加变化的过程称为加密加密加密加密E EKK n n加密后输出的数据称为加密后输出的数据称为密文密文密文密文C C n n从密文恢复出明文的过程称为从密文恢复出明文的过程称为解密解密解密解密D DKKn n完成加密和解密的算法称为完成加密和解密的算法称为密码体制密码体制密码体制密码体制。n n变换过程中使用的参数叫变换过程中使用的参数叫密钥密钥密钥密钥KK。n n加密时使用的密钥与解密时使用的密钥可以相同加密时使用的密钥与解密时使用的密钥可以相同（单密钥），也可以不同（双密钥）（单密钥），也可以不同（双密钥）2普通高等教育“十五”国家级规划教材信息论与编码 曹雪23普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著安全性安全性n n如果求解一个问题需要一定量的计算，但环境所能提供的实际资源却无法实现它，则称这种问题是计算上不可能的计算上不可能的；n n如果一个密码体制的破译是计算上不可能的，则称该密码体制是计算上安全计算上安全的的。3普通高等教育“十五”国家级规划教材信息论与编码 曹雪34普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著保密性n n即使截获了一段密文即使截获了一段密文C C，甚至知道了与它对应，甚至知道了与它对应的明文的明文MM，破译者要从中系统地求出解密变换，破译者要从中系统地求出解密变换仍然是计算上不可能的。仍然是计算上不可能的。n n破破译译者者要要由由截截获获的的密密文文C C系系统统地地求求出出明明文文MM是是计算上不可能的。计算上不可能的。保密性只要求对变换DK（解密密钥）加以保密，只要不影响DK的保密，变换EK可以公布于众。EKDKMCM4普通高等教育“十五”国家级规划教材信息论与编码 曹雪45普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著真实性n n对于给定的对于给定的C C，即使密码分析员知道对应于它，即使密码分析员知道对应于它的明文的明文MM，要系统地求出加密变换，要系统地求出加密变换E EK K仍然是计仍然是计算上不可能的。算上不可能的。n n密码分析员要系统地找到密文密码分析员要系统地找到密文C C，使，使D DK K（C C）是明文空间上有意义的明文，这在计算上是不是明文空间上有意义的明文，这在计算上是不可能的。可能的。EKDKMCM真实性只要求变换EK K（加密密钥）保密，变换D DK K可公布于众。5普通高等教育“十五”国家级规划教材信息论与编码 曹雪56普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著密码体制（密码体制（1）n n对对对对称称称称（单单单单密密密密钥钥钥钥）体体体体制制制制：加加密密密密钥钥和和解解密密密密钥钥相相同或者很容易相互推导出。同或者很容易相互推导出。由由于于我我们们假假定定加加密密方方法法是是众众所所周周知知的的，所所以以这这就就意意味味着着变变换换E EK K和和D DK K很很容容易易互互相相推推导导。因因此此，如如果果对对E EK K和和D DK K都都保保密密，则则保保密密性性和和真真实实性性就就都都有有了了保保障障。但但这这种种体体制制中中E EK K和和D DK K只只要要暴暴露露其其中中一一个个，另另一一个个也也就就暴暴露露了了。所所以以，对对称称密密码码体体制制必必须须同同时时满满足足保保密密性性和和真真实实性性的的全全部部要要求求。用于加密私人文件。用于加密私人文件。6普通高等教育“十五”国家级规划教材信息论与编码 曹雪67普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n n非非非非对对对对称称称称（双双双双密密密密钥钥钥钥）密密密密码码码码体体体体制制制制：加加密密密密钥钥和和解解密密密密钥钥中中至至少少有有一一个个在在计计算算上上不不可可能能被被另另一一个个导导出出。因因此此，在在变换变换E EK K或或D DK K中有一个可公开而不影响另一个的保密。中有一个可公开而不影响另一个的保密。通通过过保保护护两两个个不不同同的的变变换换分分别别获获得得保保密密性性和和真真实实性性。保保护护D DK K获获得得保保密密性性，保保护护E EK K获获得得真真实实性性。公公开开密密钥钥体体制制即即是是这这种种。接接收收者者通通过过保保密密自自己己的的解解密密密密钥钥来来保保障障他他接接收收信信息息的的保保密密性性，但但不不能能保保证证真真实实性性，因因为为任任何何知知道道他他的的加加密密密密钥钥的的人人都都可可以以将将虚虚假假消消息息发发给给他他。发发送送者者通通过过保保密密自自己己的的解解密密密密钥钥来来保保障障他他发发送送信信息息的的真真实实性性。但但任任何何知知道道他他的的加加密密密密钥钥的的人人都都可可以以破破译译消消息息，保密性不能保证。用于数字签名。保密性不能保证。用于数字签名。密码体制（密码体制（2）7普通高等教育“十五”国家级规划教材信息论与编码 曹雪78普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著EBDBMCM保障保密性保障真实性MCMDAEADAEBDBEAMCCCM保密性真实性保密性与真实性保密性与真实性8普通高等教育“十五”国家级规划教材信息论与编码 曹雪89普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著密码分类密码分类n n根根据据加加密密明明文文数数据据时时的的加加密密单单位位的的不不同同，分分为为分分分分组密码组密码组密码组密码和和序列密码序列密码序列密码序列密码两大类。两大类。n n分分分分组组组组密密密密码码码码：设设MM为为密密码码消消息息，将将MM分分成成等等长长的的连连续续区区组组MM1 1,MM2 2,，分分组组的的长长度度一一般般是是几几个个字字符符，并且用同一密钥并且用同一密钥K K为各区组加密，即为各区组加密，即n n序序序序列列列列密密密密码码码码：若若将将MM分分成成连连续续的的字字符符或或位位m m1 1,m m2 2,，并并用用密密钥钥序序列列K KK K1 1K K2 2的的第第i i个个元元素素给给m mi i加加密密，即即n n常用分组密码。常用分组密码。9普通高等教育“十五”国家级规划教材信息论与编码 曹雪910普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.1.2 加密编码中的熵概念加密编码中的熵概念 密码学和信息论一样，都是把信源看成是符号（文字、语言等）的集合，并且它按一定的概率产生离散符号序列。在第二章中介绍的多余度的概念也可用在密码学中，用来衡量破译某一种密码体制的难易程度。多余度越小，破译的难度就越大。可见对明文先压缩其多余度，然后再加密，可提高密文的保密度。10普通高等教育“十五”国家级规划教材信息论与编码 曹1011普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著安全性安全性n n在截获密文后，明文在多大程度上仍然无法确在截获密文后，明文在多大程度上仍然无法确定。即如果无论截获了多长的密文都得不到任定。即如果无论截获了多长的密文都得不到任何有关明文的信息，那么就说这种密码体制是何有关明文的信息，那么就说这种密码体制是绝对安全绝对安全的。的。n n所有实际密码体制的密文总是会暴露某些有关所有实际密码体制的密文总是会暴露某些有关明文的信息。被截获的密文越长，明文的不确明文的信息。被截获的密文越长，明文的不确定性就越小，最后会变为零。这时，就有了足定性就越小，最后会变为零。这时，就有了足够的信息唯一地决定明文，于是这种密码体制够的信息唯一地决定明文，于是这种密码体制也就在也就在理论上可破译理论上可破译了。了。n n理论上可破译，并不能说明这些密码体制不安理论上可破译，并不能说明这些密码体制不安全，因为把明文计算出来的时空需求也许会超全，因为把明文计算出来的时空需求也许会超过实际上可供使用的资源。在过实际上可供使用的资源。在计算上是安全计算上是安全的。的。11普通高等教育“十五”国家级规划教材信息论与编码 曹1112普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著熵概念熵概念n n密码系统的安全问题与噪声信道问题进行类比。密码系统的安全问题与噪声信道问题进行类比。噪声相当于加密变换，接收的失真消息相当于密噪声相当于加密变换，接收的失真消息相当于密文，破译者则可类比于噪声信道中的计算者。文，破译者则可类比于噪声信道中的计算者。n n随机变量的不确定性可以通过给予附加信息而减随机变量的不确定性可以通过给予附加信息而减少。正如前面介绍过条件熵一定小于无条件熵。少。正如前面介绍过条件熵一定小于无条件熵。例如，令例如，令X X是是3232位二进制整数并且所有值的出现位二进制整数并且所有值的出现概率都相等，则概率都相等，则X X的熵的熵H(X)H(X)3232比特。假设已经比特。假设已经知道知道X X是偶数，那么熵就减少了一位，因为是偶数，那么熵就减少了一位，因为X X的最的最低位肯定是零。低位肯定是零。12普通高等教育“十五”国家级规划教材信息论与编码 曹1213普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著疑义度疑义度 n n对于给定密文，密钥的疑义度可表示为n n对于给定密文，明文的疑义度可表示为13普通高等教育“十五”国家级规划教材信息论与编码 曹1314普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n n破破译译者者的的任任务务是是从从截截获获的的密密文文中中提提取取有有关关明明文文的的信息或从密文中提取有关密钥的信息信息或从密文中提取有关密钥的信息n nI(MI(M；C)C)H(M)H(M)H(M/C)H(M/C)n nI(KI(K；C)C)H(K)H(K)H(K/C)H(K/C)n nH(M/C)H(M/C)和和H(K/C)H(K/C)越越大大，破破译译者者从从密密文文能能够够提提取取出出有关明文和密钥的信息就越小。有关明文和密钥的信息就越小。n n对对于于合合法法的的接接收收者者，在在已已知知密密钥钥和和密密文文条条件件下下提提取明文信息：取明文信息：H(M/C,K)H(M/C,K)0 0 I(MI(M；CK)CK)H(M)H(M)H(M/C,K)H(M/C,K)H(M)H(M)疑义度疑义度 14普通高等教育“十五”国家级规划教材信息论与编码 曹1415普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著因为H(K/C)H(M/K,C)H(M/C)H(K/M,C)（M和K交换）H(M/C)（熵值H(K/M,C)总是大于等于零）H(M/C,K)0，上式得H(K/C)H(M/C)即已知密文后，密钥的疑义度总是大于等于明文的疑义度。我们可以这样来理解，由于可能存在多种密钥把一个明文消息M加密成相同的密文消息C，即满足的K值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难。疑义度疑义度 15普通高等教育“十五”国家级规划教材信息论与编码 曹1516普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著又因为H(K)H(K/C)H(M/C)，则上式说明，保密系统的密钥量越少，密钥熵H(K)就越小，其密文中含有的关于明文的信息量I(M;C)就越大。至于破译者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。疑义度疑义度 16普通高等教育“十五”国家级规划教材信息论与编码 曹1617普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.2 数据加密标准数据加密标准DES 1977年7月美国国家标准局公布了采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DESDataEncryptionStandard）。DES密码是一种采用传统加密方法的区组密码，它的算法是对称的，既可用于加密又可用于解密。17普通高等教育“十五”国家级规划教材信息论与编码 曹1718普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.2.1 换位和替代密码换位和替代密码 n n换位密码：对数据中的字符或更小的单位（如位）重新组织，但并不改变它们本身。n n替代密码：改变数据中的字符，但不改变它们之间的相对位置。18普通高等教育“十五”国家级规划教材信息论与编码 曹1819普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著P盒015150014140013130012120输011110输010100入0990出0880数0770数0660据0551据0440033002201110输入第i位输出第j位151413121110987654321741210152111914638135换位盒(P盒)19普通高等教育“十五”国家级规划教材信息论与编码 曹1920普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著S盒n=32n=82n=80001112213314415516677输入输出000001010011100101110111101010100111000110011001替代盒（S盒）20普通高等教育“十五”国家级规划教材信息论与编码 曹2021普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著0PsPsPsP0010000输0sss0输01入01出0sss1数01数00据0sss0据00010sss110P盒和S盒的结合使用21普通高等教育“十五”国家级规划教材信息论与编码 曹2122普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.2.2 DES密码算法密码算法 n nDES密码就是在上述换位和替代密码的基础上发展的。n n将输入明文序列分成区组，每组64比特。n n64比特的密钥源循环移位产生16个子密钥22普通高等教育“十五”国家级规划教材信息论与编码 曹2223普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著23普通高等教育“十五”国家级规划教材信息论与编码 曹2324普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著图7-7密码运算24普通高等教育“十五”国家级规划教材信息论与编码 曹2425普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著25普通高等教育“十五”国家级规划教材信息论与编码 曹2526普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著密钥表计算26普通高等教育“十五”国家级规划教材信息论与编码 曹2627普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.2.3 DES密码的安全性密码的安全性 DES的出现在密码学史上是一个创举。以前的任何设计者对于密码体制及其设计细节都是严加保密的。而DES算法则公开发表，任人测试、研究和分析，无须通过许可就可制作DES的芯片和以DES为基础的保密设备。DES的安全性完全依赖于所用的密钥。27普通高等教育“十五”国家级规划教材信息论与编码 曹2728普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著弱密钥n nDESDES算算法法中中每每次次迭迭代代所所用用的的子子密密钥钥都都相相同同，即即 K K1 1K K2 2K K1616，如，如111111，此此时时DESDESk k(DES(DESk k(x x)x x，DESDESk k1 1(DES(DESk k1 1(x x)x x即即以以k k对对x x加加密密两两次次或或解解密密两两次次都都恢恢复复出出明明文。其加密运算和解密运算没有区别。文。其加密运算和解密运算没有区别。n n而对一般密钥只满足而对一般密钥只满足DESDESk k1 1(DES(DESk k(x x)DESDESk k(DES(DESk k1 1(x x)x x28普通高等教育“十五”国家级规划教材信息论与编码 曹2829普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著半弱密钥n n给定的密钥k，相应的16个子密钥只有两种图样，且每种都出现8次。如101010n n半弱密钥的特点是成对地出现，且具有下述性质：若k1和k2为一对互逆的半弱密钥，x为明文组，则有DESk1(DESk2(x)DESk2(DESk1(x)x称k1和k2是互为对合的。29普通高等教育“十五”国家级规划教材信息论与编码 曹2930普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著问题问题n nDES的密钥短了些n n选择长的密钥会使成本提高、运行速度降低。n n新算法很可能要采用128比特密钥。n n实现DES算法的产品有：n n设计专用设计专用LSILSI器件或芯片；器件或芯片；n n用现成的微处理器实现；用现成的微处理器实现；n n只限于实现只限于实现DESDES算法；算法；n n可运行各种工作模式。可运行各种工作模式。30普通高等教育“十五”国家级规划教材信息论与编码 曹3031普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.2.4 DES密码的改进密码的改进尽管DES算法十分复杂，但它基本上还是采用64比特字符的单字母表替换密码。当同样的64比特明文块进入编码器后，得到的是同样的64比特的密文块。破译者可利用这个性质来破译DES。改进方法：密码块链接、密码反馈方式31普通高等教育“十五”国家级规划教材信息论与编码 曹3132普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著密码块链接密码块链接M1M2M3M4C1C2C3C4V#密钥DDDD解密箱加密箱密钥EEEEV#异或C1C2C3C4M1M2M3M4(a)(b)32普通高等教育“十五”国家级规划教材信息论与编码 曹3233普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著64位移位寄存器64位移位寄存器C2C3C4C5C6C7C8C9C2C3C4C5C6C7C8C9648密钥E加密箱C10密钥E加密箱C10选择最左字节选择最左字节8M10#C10C10#M108(a)(b)密码反馈方式密码反馈方式33普通高等教育“十五”国家级规划教材信息论与编码 曹3334普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.3 国际数据加密算法（国际数据加密算法（IDEA）n n尽管一次加密的尽管一次加密的DESDES仍然广泛应用于保密中，仍然广泛应用于保密中，但专家们对但专家们对DESDES不安全的原因作了大量的分析，不安全的原因作了大量的分析，认为这种方法刚被发明时是很适用的，而现在认为这种方法刚被发明时是很适用的，而现在已不再能满足需要。人们开始寻求更安全的块已不再能满足需要。人们开始寻求更安全的块密码，曾提出了许多算法，其中最令人感兴趣密码，曾提出了许多算法，其中最令人感兴趣最重要的就是最重要的就是IDEAIDEA（IntrenationalDataIntrenationalDataEncryptionAlgorithmEncryptionAlgorithm），即国际数据加密算法。），即国际数据加密算法。n nIDEAIDEA由瑞士的两名科学家于由瑞士的两名科学家于19901990年提出，最早年提出，最早称作称作PESPES（ProposedEncryptionStandardProposedEncryptionStandard），后），后改称为改称为IDEAIDEA。34普通高等教育“十五”国家级规划教材信息论与编码 曹3435普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.3.1 算法原理算法原理 n n采用下述几种基本运算：采用下述几种基本运算：（1 1）逐位逐位mod2mod2和，记作和，记作；（2 2）mod2mod21616（即（即6553665536）整数加，记作）整数加，记作；（3 3）mod(2mod(216161)1)（即（即6553765537）整数乘，记作）整数乘，记作；（4 4）三三个个运运算算中中任任意意两两个个运运算算不不满满足足分分配配律律。例例如如：a a (b cb c)(a ba b)()(a ca c)（5 5）三三个个运运算算中中任任意意两两个个运运算算间间不不满满足足结结合合律律。例例如：如：a a (b b c c)(a ba b)c c 35普通高等教育“十五”国家级规划教材信息论与编码 曹3536普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著实现时需考虑实现时需考虑 （1 1）基基基基本本本本构构构构件件件件乘乘乘乘/加加加加单单单单元元元元：实实现现1616比比特特为为字字长长的的非非线线性性S S盒盒，如如图图所所示示。它它是是IDEAIDEA实实现现中中的的关关键键非非线线性性构构件件。通通过过8 8轮轮迭迭代代，能能够够完完成成更更好好的的扩扩散散和和混混淆淆。研研究究表表明明，为为实实现现完完善善混混淆淆至至少少需要需要4 4轮迭代。轮迭代。（2 2）硬硬硬硬件件件件：加加密密、解解密密运运算算相相似似，差差别别是是密密钥钥时时间间表表，类类似似于于DESDES，具具有有对对合合性性，可可用用同同一一器器件件实实现现。由由于于采采用用规规则的模块结构，易于设计则的模块结构，易于设计ASICASIC实现。实现。（3 3）软软软软件件件件：采采用用子子段段结结构构：以以1616比比特特为为字字长长进进行行处处理理。采采用用简简单单运运算算，三三种种运算易于编程实现加、移位等。运算易于编程实现加、移位等。F116F216K5K6G116G21636普通高等教育“十五”国家级规划教材信息论与编码 曹3637普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.3.2 加密解密过程加密解密过程 n n输入和输出字长为输入和输出字长为6464比特，密钥长比特，密钥长128128比特，比特，8 8轮迭代体制。最后经过一个输出变换给出密文。轮迭代体制。最后经过一个输出变换给出密文。IDEAIDEA可用于各种标准工作模式。可用于各种标准工作模式。n n它由两部分组成：一个是对输入它由两部分组成：一个是对输入6464比特明文组比特明文组的的8 8轮迭代产生轮迭代产生6464比特密文输出；另一个是由比特密文输出；另一个是由输入的输入的128128比特会话密钥，产生比特会话密钥，产生8 8轮迭代所需的轮迭代所需的5252个子密钥，共个子密钥，共52165216比特。比特。37普通高等教育“十五”国家级规划教材信息论与编码 曹3738普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著64比特明文xx1x2x3x4K1迭代1K6w11w12w13w14K7迭代2K12 w21w22w23w24w71w72w73w74 K43迭代8K48 w81w82w83w84 K49输出变换K52 y11y12y13y14密文IDEAIDEA算法框图算法框图38普通高等教育“十五”国家级规划教材信息论与编码 曹3839普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著128比特密钥K子密钥生成器16K1K52x1x2x3x4K1K3K2K4乘加单元K5K6 w11w12w13w14图7-15 w1w2w3w4K49K51K50K52图7-16IDEA的输出变换39普通高等教育“十五”国家级规划教材信息论与编码 曹3940普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著K(128比特)K1K2K3K4K5K6K7K8K15K16K9K10K11K12K13K14K15K22K23K24K17K18K19K20K21K28K29K30K31K32K25K26K27K28K35K36K37K38K39K40K33K34K41K42K43K44K45K46K47K48K49K50K51K52图7-17IDEA的子密钥40普通高等教育“十五”国家级规划教材信息论与编码 曹4041普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.3.3 算法的安全性算法的安全性 如果采用穷搜索破译，要求进行如果采用穷搜索破译，要求进行2 212812810103838次次试探。若每秒可完成试探。若每秒可完成100100万次加密，需万次加密，需10101313年；年；若用若用10102424个个ASICASIC芯片阵需要一天。有关专家研芯片阵需要一天。有关专家研究表明，究表明，IDEAIDEA算法没有似算法没有似DESDES意义下的弱密钥，意义下的弱密钥，8 8轮迭代使得没有任何捷径破译，在差分和线性轮迭代使得没有任何捷径破译，在差分和线性攻击下是安全的。当然若将字长由攻击下是安全的。当然若将字长由1616比特增加比特增加到到3232比特，密钥相应长比特，密钥相应长256256比特，采用比特，采用2 23232模加，模加，2 232321 1模乘，则可进一步强化模乘，则可进一步强化IDEAIDEA。41普通高等教育“十五”国家级规划教材信息论与编码 曹4142普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.4 公开密钥加密法公开密钥加密法 n n前面介绍的秘密密钥加密法，算法公开，密钥是保密的（对称密钥）。n n如果要进行通信，必须在这之前把密钥通过非常可靠的方式分配给所有接收者，这在某些场合是很难做到的。n n因而提出了公开密钥加密法PKC（PublicKeyCryptography）42普通高等教育“十五”国家级规划教材信息论与编码 曹4243普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著密密 钥钥n n使用两个不同密钥（非对称密钥体制）；n n一个公开（公钥），另一个为用户专用（私钥）；n n通信双方无需事先交换密钥就可进行保密通信；n n要从公钥或密文分析出明文或私钥，在计算上是不可能的。43普通高等教育“十五”国家级规划教材信息论与编码 曹4344普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著应应 用用n n保密通信：多个用户将信息传给某用户，可用该用户的公钥加密，唯有该用户可用自己的私钥解读。n n数字签名：用自己的私钥加密信息，而以公钥作为解密密钥，用来确认发送者。44普通高等教育“十五”国家级规划教材信息论与编码 曹4445普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著PKC算法的关键算法的关键 加密函数加密函数yF(x)的的单向性 n n加密计算容易：对任意给定的x值，容易计算yF(x)的值；n n破译难：已知F和y，不可能求出对应的x值；n n用私钥容易解密：若知道F的某种特殊性质（窍门trapdoor），就容易计算出x值。45普通高等教育“十五”国家级规划教材信息论与编码 曹4546普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著构造和使用构造和使用n n使用者构造出单向函数F（公钥）和它的逆函数F1（私钥）。n n破译者：已知F和密文不能推导出F1或明文；n n接收者：用窍门信息（解密密钥Kd）简单地求解xF1Kd(y)。46普通高等教育“十五”国家级规划教材信息论与编码 曹4647普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.4.1 公开密钥密码体制公开密钥密码体制 保密通信保密通信 公开加密密钥秘密解密密钥B(e，n)B(d，n)A(e，n)A(d，n)B发到ABMfA(e，n)CAA接收BACfA(d，n)MA发到BAMfB(e，n)CBB接收ABCfB(d，n)M47普通高等教育“十五”国家级规划教材信息论与编码 曹4748普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.4.1 公开密钥密码体制公开密钥密码体制 数字签名数字签名 公开加密密钥秘密解密密钥B(e，n)B(d，n)A(e，n)A(d，n)B发到ABMfB(d，n)SfA(e，n)CAA收到BACfA(d，n)SfB(e，n)M48普通高等教育“十五”国家级规划教材信息论与编码 曹4849普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n nRSA由来n n理论基础n n密钥设计n n加密解密n n实现步骤7.4.2 RSA密码体制密码体制49普通高等教育“十五”国家级规划教材信息论与编码 曹4950普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著RSA密码体制（密码体制（1）n nRSARSA由来由来：RSARSA体制是根据体制是根据PKCPKC算法由美国麻算法由美国麻省理工学院（省理工学院（MITMIT）的研究小组提出的，该体）的研究小组提出的，该体制的名称是用了三位作者（制的名称是用了三位作者（RivestRivest，ShamirShamir和和AdlemanAdleman）英文名字的第一个字母拼合而成。）英文名字的第一个字母拼合而成。n n理论基础理论基础：利用数论利用数论正正：要求得到两个大素数（如大到：要求得到两个大素数（如大到100100位）的位）的乘积在计算机上很容易实现。乘积在计算机上很容易实现。逆逆：但要分解两个大素数的乘积在计算上几乎：但要分解两个大素数的乘积在计算上几乎不可能实现。不可能实现。50普通高等教育“十五”国家级规划教材信息论与编码 曹5051普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n n密钥设计：两个密钥：公钥（e，n）私钥（d，n）n n加密解密：加密时：解密时：RSA密码体制（密码体制（2）51普通高等教育“十五”国家级规划教材信息论与编码 曹5152普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n n实现步骤：n n选取两个很大的素数选取两个很大的素数p p和和q q，令模数，令模数 n n求求n n的欧拉函数的欧拉函数 并从并从2 2至至(n n)11中任选一个数作为加密指数中任选一个数作为加密指数e e；n n解同余方程解同余方程 求得解密指数求得解密指数d d；n n(e e，n n)即为公开密钥，即为公开密钥，(d d，n n)即为秘密密钥。即为秘密密钥。RSA密码体制（密码体制（3）52普通高等教育“十五”国家级规划教材信息论与编码 曹5253普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著例题保密通信例题保密通信例例例例7-1 7-1 在在RSARSA方方法法中中，令令p p3 3，q q1717，取取e e5 5，试计算解密密钥试计算解密密钥d d并加密并加密MM2 2。解：解：解：解：n npqpq5151 (n)(n)(p(p1)(q1)(q1)1)3232(5(5d d)mod32)mod321 1，可解得，可解得d d1313加密加密 y yx xe emodnmodn2 255mod51mod513232解密解密 y yd dmodnmodn32321313mod51mod512 2x x若需发送的报文内容是用英文或其他文字若需发送的报文内容是用英文或其他文字表示的，则可先将文字转换成等效的数字，再表示的，则可先将文字转换成等效的数字，再进行加密运算。进行加密运算。53普通高等教育“十五”国家级规划教材信息论与编码 曹5354普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著RSA公开密钥体制用于数字签名公开密钥体制用于数字签名n n发送者发送者A A用自己的秘密解密密钥用自己的秘密解密密钥(d(dA A，n nA A)计算签名；计算签名；n n用接收者用接收者B B的公开加密密钥的公开加密密钥(e(eB B，n nB B)再次加密：再次加密：n n接收者接收者B B用自己的秘密解密密钥用自己的秘密解密密钥(d(dB B，n nB B)解密：解密：n n查发送者查发送者A A的公开密钥的公开密钥(d(dA A，n nA A)计算，恢复出发送计算，恢复出发送者的签名，认证密文的来源。者的签名，认证密文的来源。(dA，nA)(eB，nB)(dB，nB)(eA，nA)MiSiSSiMi54普通高等教育“十五”国家级规划教材信息论与编码 曹5455普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著例题数字签名例题数字签名例例例例7-27-2 用用户户A A发发送送给给用用户户B B一一份份密密文文，用用户户A A用用首首字字母母B B0202来签署密文。用户来签署密文。用户A A知道下列三个密钥：知道下列三个密钥：ABAB公开密钥公开密钥(e e，n)(7n)(7，123)(13123)(13，51)51)秘密密钥秘密密钥(d d，n)(23n)(23，123)123)A A计算他的签名：计算他的签名：再次加密签名：再次加密签名：55普通高等教育“十五”国家级规划教材信息论与编码 曹5556普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著 接接收收者者B B必必须须恢恢复复出出0202B B认认证证他他接接收收的的密密文文。接接收收者者也也知道三个密钥：知道三个密钥：ABAB公开密钥公开密钥(e e，n)(7n)(7，123)(13123)(13，51)51)秘密密钥秘密密钥(d d，n)(5n)(5，51)51)B B用户用自己的秘密解密密钥一次解密：用户用自己的秘密解密密钥一次解密：再用再用A A用户的公开密钥解密：用户的公开密钥解密：B B用户可以确认：该签名是由用户可以确认：该签名是由A A发出发出用用A A公钥可解读；公钥可解读；该签名是发给自己的该签名是发给自己的用了用了B B的公钥。的公钥。例题数字签名（续）例题数字签名（续）56普通高等教育“十五”国家级规划教材信息论与编码 曹5657普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著安全性和速度安全性和速度n nn n要大，破译要大，破译512512比特（比特（154154位）位）RSARSA算法体制与算法体制与破译破译6464比特的单密钥体制相当；比特的单密钥体制相当；n n目前目前n n512512比特在短期内十分安全，但已有一定比特在短期内十分安全，但已有一定威胁，很快可能要采用威胁，很快可能要采用768768比特甚至比特甚至10241024比特；比特；n nRSARSA算法的硬件实现速度很慢，最快也只有算法的硬件实现速度很慢，最快也只有DESDES的的1/10001/1000，512512比特模下的比特模下的VLSIVLSI硬件实现只达硬件实现只达64kb/s64kb/s；软件实现的；软件实现的RSARSA的速度只有的速度只有DESDES的软件的软件实现的实现的1/1001/100。n n在速度上在速度上RSARSA无法与对称密钥体制相比，因而无法与对称密钥体制相比，因而RSARSA体制多用于密钥交换和认证。体制多用于密钥交换和认证。57普通高等教育“十五”国家级规划教材信息论与编码 曹5758普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著n n有时需要确认一段报文的出处，而报文本身不需加密。如用公开密钥算法加密整段报文，则加密时间长，而且报文传输和存储的开销也大。n n采用报文摘要(messagedigest)，即从一段报文中计算出较短的报文摘要，然后在报文摘要上签名，并将签名的摘要和报文一起发送。7.4.3 报文摘要报文摘要 58普通高等教育“十五”国家级规划教材信息论与编码 曹5859普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著报文摘要的特点报文摘要的特点n n该方案基于单向散列(Hash)函数的思想；n n给出报文P就易于计算出报文摘要MD(P)；n n只给出MD(P)，几乎无法找出P；n n无法生成两条具有同样报文摘要的报文；n n如果有人替换了报文P，当接收者计算MD(P)时就得不到相同的结果。59普通高等教育“十五”国家级规划教材信息论与编码 曹5960普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著添加1512比特报文长度Kmod264L512比特N32比特K比特报文1000512比特512比特512比特512比特Y0Y1YqYL-1512512512512ABCDHMD5HMD5HMD5HMD5128128128128128比特报文摘要采用MD5算法产生报文摘要60普通高等教育“十五”国家级规划教材信息论与编码 曹6061普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著MDq128Yq512ABCD32ABCDfF(ABCD，Yq，T1.16)ABCDABCDfG(ABCD，Yq，T17.32)ABCDABCDfH(ABCD，Yq，T33.48)ABCDABCDfI(ABCD，Yq，T49.64)MDq+1128处理512比特块的算法HMD561普通高等教育“十五”国家级规划教材信息论与编码 曹6162普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著ABCDg32XkTiCLSsABCLSsAg(BCD)XkTi16次62普通高等教育“十五”国家级规划教材信息论与编码 曹6263普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著表7-12基本函数的逻辑运算关系轮轮基本函数基本函数gg(B,C,D)fFF(B,C,D)fGG(B,C,D)fHH(B,C,D)fII(B,C,D)63普通高等教育“十五”国家级规划教材信息论与编码 曹6364普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著表7-13基本函数的真值表BCDFGHI0000111100110011010101010101001100100111011010011001110064普通高等教育“十五”国家级规划教材信息论与编码 曹6465普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著MD5的安全性的安全性求具有相同求具有相同HashHash值的两个消息在计算上是值的两个消息在计算上是不可行的。不可行的。MD5MD5的输出为的输出为128128比特，若采用比特，若采用纯纯强力攻击强力攻击寻找一个消息具有给定寻找一个消息具有给定HashHash值的计算值的计算困难性为困难性为2 2128128，用每秒可试验，用每秒可试验1,000,000,0001,000,000,000个消个消息的计算机需时息的计算机需时1.07101.07102222年。若采用年。若采用生日攻击生日攻击法法，寻找有相同，寻找有相同HashHash值的两个消息需要试验值的两个消息需要试验2 26464个消息，用每秒可试验个消息，用每秒可试验1,000,000,0001,000,000,000个消息的个消息的计算机需时计算机需时585585年。年。差分攻击差分攻击对对MD5MD5的安全性的安全性不构成威胁。不构成威胁。65普通高等教育“十五”国家级规划教材信息论与编码 曹6566普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著公开密码体制的优缺点公开密码体制的优缺点n n减少了密钥数量。在减少了密钥数量。在n n个用户的密码系统中，采用对个用户的密码系统中，采用对称密码体制，需要称密码体制，需要n(n-1)/2n(n-1)/2个密钥。采用公钥密码体个密钥。采用公钥密码体制，只需要制，只需要n n对密钥，而真正需要严加保管的只有用对密钥，而真正需要严加保管的只有用户自己的秘密密钥；户自己的秘密密钥；n n彻底消除了密钥在分送过程中被窃的可能性，大大彻底消除了密钥在分送过程中被窃的可能性，大大提高了密码体制的安全性。提高了密码体制的安全性。n n便于实现数字签名，完满地解决了对发方和收方的便于实现数字签名，完满地解决了对发方和收方的证实问题，彻底解决了发、收双方就传送内容可能证实问题，彻底解决了发、收双方就传送内容可能发生的争端，为在商业上广泛应用创造了条件。发生的争端，为在商业上广泛应用创造了条件。n n计算较复杂，加密和解密的工作速率远低于对称密计算较复杂，加密和解密的工作速率远低于对称密码体制。码体制。66普通高等教育“十五”国家级规划教材信息论与编码 曹6667普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.5 模拟信号加密模拟信号加密 模拟话音加密模拟话音加密 n n分类：模拟加密、数字加密分类：模拟加密、数字加密n n模拟话音的特性：时间、频率和幅度模拟话音的特性：时间、频率和幅度 n n模拟加密方法：时间置乱、频率置乱、幅度置乱；模拟加密方法：时间置乱、频率置乱、幅度置乱；一维置乱、二维置乱一维置乱、二维置乱 n n数字加密方法：比特置乱、比特掩盖数字加密方法：比特置乱、比特掩盖n n模拟加密简单，但保密度较差；模拟加密简单，但保密度较差；n n数字加密，要求取样率较高。数字加密，要求取样率较高。n n可结合使用。可结合使用。67普通高等教育“十五”国家级规划教材信息论与编码 曹6768普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.6 通信网络中的加密通信网络中的加密链路加密链路加密 数据数据节点密钥1密钥1密钥2密钥2节点节点明文68普通高等教育“十五”国家级规划教材信息论与编码 曹6869普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.6 通信网络中的加密通信网络中的加密节点加密节点节点节点加密数据加密数据数据（密钥1）（密钥2）数据密钥1密钥1密钥2密钥2（安全模块）（安全模块）（安全模块）数据数据69普通高等教育“十五”国家级规划教材信息论与编码 曹6970普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.6 通信网络中的加密通信网络中的加密端对端加密节点密钥1节点节点密钥1数据数据70普通高等教育“十五”国家级规划教材信息论与编码 曹7071普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.7 信息安全和确认技术信息安全和确认技术 n n信息资源共享的限制n n信息资源的保护71普通高等教育“十五”国家级规划教材信息论与编码 曹7172普通高等教育普通高等教育“十五十五”国家级规划教材信息论与编码国家级规划教材信息论与编码 曹雪虹等编著曹雪虹等编著7.7.1 信息安全的基本概念信息安全的基本概念 n n认证业务认证业务：提供某种方法来证实某一声明是正确：提供某种方法来证实某一声明是正确的。例口令的。例口令n n访问控制访问控制：控制非授权的访问。例防火墙。：控制非授权的访问。例防火墙。n n保密业务保密业务：对未授权者保护信息，例数据加密：对未授权者保护信息，例数据加密n n数据完整性业务数据完整性业务：对安全威胁所采取的一类防护：对安全威胁所采取的一类防护措施，措施，n n不可否认业务不可否认业务：提供无可辩驳的证据来证明曾经：提供无可辩驳的证据来证明曾经发生过的交换。采用数字签名技术。发生过的交换。采用数字签名技术。72普通高等教育“十五”国家级规划教材