第7章加密编码

1普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著第7章加密编码加密编码的基础知识数据加密标准DES国际数据加密算法（IDEA〕公开密钥加密法通信网络中的加密信息安全和确认技术2普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.1加密编码的基础知识人们希望把重要信息通过某种变换转换成秘密形式的信息。转换方法可以分为两大类：隐写术，隐蔽信息载体——信号的存在，古代常用。编码术，将载荷信息的信号进行各种变换使它们不为非授权者所理解。在利用现代通讯工具的条件下，隐写术受到很大限制，但编码术却以计算机为工具取得了很大的发展。3普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.1.1加密编码中的基本概念真实数据称为明文M对真实数据施加变化的过程称为加密EK加密后输出的数据称为密文C从密文恢复出明文的过程称为解密DK完成加密和解密的算法称为密码体制。变换过程中使用的参数叫密钥K。加密时使用的密钥与解密时使用的密钥可以相同（单密钥），也可以不同（双密钥）4普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著安全性如果求解一个问题需要一定量的计算，但环境所能提供的实际资源却无法实现它，则称这种问题是计算上不可能的；如果一个密码体制的破译是计算上不可能的，则称该密码体制是计算上安全的。5普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著保密性即使截获了一段密文C，甚至知道了与它对应的明文M，破译者要从中系统地求出解密变换仍然是计算上不可能的。破译者要由截获的密文C系统地求出明文M是计算上不可能的。保密性只要求对变换DK（解密密钥）加以保密，只要不影响DK的保密，变换EK可以公布于众。EKDKMCM6普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著真实性对于给定的C，即使密码分析员知道对应于它的明文M，要系统地求出加密变换EK仍然是计算上不可能的。密码分析员要系统地找到密文C’，使DK（C’）是明文空间上有意义的明文，这在计算上是不可能的。EKDKMCM真实性只要求变换EK（加密密钥）保密，变换DK可公布于众。7普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著密码体制（1）对称（单密钥）体制：加密密钥和解密密钥相同或者很容易相互推导出。由于我们假定加密方法是众所周知的，所以这就意味着变换EK和DK很容易互相推导。因此，如果对EK和DK都保密，则保密性和真实性就都有了保障。但这种体制中EK和DK只要暴露其中一个，另一个也就暴露了。所以，对称密码体制必须同时满足保密性和真实性的全部要求。用于加密私人文件。8普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著非对称（双密钥）密码体制：加密密钥和解密密钥中至少有一个在计算上不可能被另一个导出。因此，在变换EK或DK中有一个可公开而不影响另一个的保密。通过保护两个不同的变换分别获得保密性和真实性。保护DK获得保密性，保护EK获得真实性。公开密钥体制即是这种。接收者通过保密自己的解密密钥来保障他接收信息的保密性，但不能保证真实性，因为任何知道他的加密密钥的人都可以将虚假消息发给他。发送者通过保密自己的解密密钥来保障他发送信息的真实性。但任何知道他的加密密钥的人都可以破译消息，保密性不能保证。用于数字签名。密码体制（2）9普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著EBDBMCM保障保密性保障真实性MCMDAEADAEBDBEAMC’CC’M保密性真实性保密性与真实性10普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著密码分类根据加密明文数据时的加密单位的不同，分为分组密码和序列密码两大类。分组密码：设M为密码消息，将M分成等长的连续区组M1,M2,…，分组的长度一般是几个字符，并且用同一密钥K为各区组加密，即序列密码：若将M分成连续的字符或位m1,m2,…，并用密钥序列K＝K1K2…的第i个元素给mi加密，即常用分组密码。12()()()kkkCEMEMEM1212()()()kkkCEMEmEm11普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.1.2加密编码中的熵概念密码学和信息论一样，都是把信源看成是符号（文字、语言等）的集合，并且它按一定的概率产生离散符号序列。在第二章中介绍的多余度的概念也可用在密码学中，用来衡量破译某一种密码体制的难易程度。多余度越小，破译的难度就越大。可见对明文先压缩其多余度，然后再加密，可提高密文的保密度。12普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著安全性在截获密文后，明文在多大程度上仍然无法确定。即如果无论截获了多长的密文都得不到任何有关明文的信息，那么就说这种密码体制是绝对安全的。所有实际密码体制的密文总是会暴露某些有关明文的信息。被截获的密文越长，明文的不确定性就越小，最后会变为零。这时，就有了足够的信息唯一地决定明文，于是这种密码体制也就在理论上可破译了。理论上可破译，并不能说明这些密码体制不安全，因为把明文计算出来的时空需求也许会超过实际上可供使用的资源。在计算上是安全的。13普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著熵概念密码系统的安全问题与噪声信道问题进行类比。噪声相当于加密变换，接收的失真消息相当于密文，破译者则可类比于噪声信道中的计算者。随机变量的不确定性可以通过给予附加信息而减少。正如前面介绍过条件熵一定小于无条件熵。例如，令X是32位二进制整数并且所有值的出现概率都相等，则X的熵H(X)＝32比特。假设已经知道X是偶数，那么熵就减少了一位，因为X的最低位肯定是零。14普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著疑义度对于给定密文，密钥的疑义度可表示为对于给定密文，明文的疑义度可表示为2(/)()(/)log(/)jijijjiHKCpcpkcpkc2(/)()(/)log(/)jijijjiHMCpcpmcpmc15普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著破译者的任务是从截获的密文中提取有关明文的信息或从密文中提取有关密钥的信息I(M；C)＝H(M)－H(M/C)I(K；C)＝H(K)－H(K/C)H(M/C)和H(K/C)越大，破译者从密文能够提取出有关明文和密钥的信息就越小。对于合法的接收者，在已知密钥和密文条件下提取明文信息：H(M/C,K)＝0I(M；CK)＝H(M)－H(M/C,K)＝H(M)疑义度16普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著因为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值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难。()KCEM疑义度17普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著又因为H(K)H(K/C)H(M/C)，则上式说明，保密系统的密钥量越少，密钥熵H(K)就越小，其密文中含有的关于明文的信息量I(M;C)就越大。至于破译者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。(;)()(/)()()IMCHMHMCHMHK疑义度18普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.2数据加密标准DES——私密密钥加密法1977年7月美国国家标准局公布了采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DESDataEncryptionStandard）。DES密码是一种采用传统加密方法的区组密码，它的算法是对称的，既可用于加密又可用于解密。19普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.2.1换位和替代密码换位密码：对数据中的字符或更小的单位（如位）重新组织，但并不改变它们本身。替代密码：改变数据中的字符，但不改变它们之间的相对位置。20普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著P盒015150014140013130012120输011110输010100入0990出0880数0770数0660据0551据0440033002201110输入第i位输出第j位151413121110987654321741210152111914638135换位盒(P盒)21普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著S盒n=32n=82n=80001112213314415516677输入输出000001010011100101110111101010100111000110011001替代盒（S盒）22普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著0PsPsPsP0010000输0sss0输01入01出0sss1数01数00据0sss0据00010sss110P盒和S盒的结合使用23普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.2.2DES密码算法DES密码就是在上述换位和替代密码的基础上发展的。将输入明文序列分成区组，每组64比特。64比特的密钥源循环移位产生16个子密钥1264Kkkk24普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著64646416次64486464输入初始置换IP密码运算逆置换输出子密钥密钥源图7-6DES算法25普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著643232L0R0K1＋fL1＝R0R1＝L0＋f(R0，K1)K2＋fL2＝R1R2＝L1＋f(R1，K2)Kn＋fL15＝R14R15＝L14＋f(R14，K15)K16＋fL16＝R15R16＝L15＋f(R15，K16)64图7-7密码运算26普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著Ri-1(32)密钥(64)E密钥表48比特Ki(48)＋S1S2S3…S8P32比特图7-8密码计算函数f(R，K)27普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著密钥64置换选择12828C0D0左移左移C1D148置换选择2K1左移左移CnDn48置换选择2Kn左移左移C16D1648置换选择2K16密钥表计算28普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著7.2.3DES密码的安全性DES的出现在密码学史上是一个创举。以前的任何设计者对于密码体制及其设计细节都是严加保密的。而DES算法则公开发表，任人测试、研究和分析，无须通过许可就可制作DES的芯片和以DES为基础的保密设备。DES的安全性完全依赖于所用的密钥。29普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著弱密钥DES算法中每次迭代所用的子密钥都相同，即K1＝K2＝…＝K16，如11…1，此时DESk(DESk(x))＝x，DESk－1(DESk－1(x))＝x即以k对x加密两次或解密两次都恢复出明文。其加密运算和解密运算没有区别。而对一般密钥只满足DESk－1(DESk(x))＝DESk(DESk－1(x))＝x30普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著半弱密钥给定的密钥k，相应的16个子密钥只有两种图样，且每种都出现8次。如1010…10半弱密钥的特点是成对地出现，且具有下述性质：若k1和k2为一对互逆的半弱密钥，x为明文组，则有DESk1(DESk2(x))＝DESk2(DESk1(x))＝x称k1和k2是互为对合的。31普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著问题DES