第2讲 密码技术

第2讲密码技术2.1密码学概述密码学是一门古老的科学。自古以来，密码主要用于军事、政治、外交等重要部门，因而密码学的研究工作本身也是秘密进行的。密码学的知识和经验主要掌握在军事、政治、外交等保密机关，不便公开发表。然而随着计算机科学技术、通信技术、微电子技术的发展，计算机和通信网络的应用进入了人们的日常生活和工作中，出现了电子政务、电子商务、电子金融等必须确保信息安全的系统，使得民间和商界对信息安全保密的需求大大增加。总而言之，在密码学形成和发展的历程中，科学技术的发展和战争的刺激起着积极的推动作用。回顾密码学的历史，应用的无穷需求是推动密码技术文明和进步的直接动力。在古代，埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上可以说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求。这其中比较著名的是大约公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。严格上说，这只是对信息的隐藏，而不是真正意义上的加密。自从有了文字以来，人们为了某种需要总是想方设法隐藏某些信息，以起到保证信息安全的目的。这些古代加密方法体现了后来发展起来的密码学的若干要素，但只能限制在一定范围内使用。古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，加密方法逐渐复杂。虽然从近代密码学的观点来看，许多古典密码是不安全的，极易破译，但我们不应当忘掉古典密码在历史上发挥的巨大作用。古典密码的代表性密码体制主要有：单表代替密码、多表代替密码及转轮密码。Caser密码是一种典型的单表加密体制；Vigenere密码是典型的多表代替密码；而著名的Enigma密码就是第二次世界大战中使用的转轮密码。密码技术形成一门新的学科是在20世纪70年代，这是受计算机科学蓬勃发展和推动的结果。密码学的理论基础之一是1949年ClaudeShannon发表的“保密系统的通信理论”，这篇文章发表了30年后才显示出它的价值。1976年W.Diffie和M.Hellman发表了“密码学的新方向”一文，提出了适应网络保密通信的公钥密码思想，开辟了公开密钥密码学的新领域，掀起了公钥密码研究的序幕。各种公钥密码体制被提出，特别是1978年RSA公钥密码体制的出现，在密码学史上是一个里程碑同年，美国国家标准局正式公布实施了美国的数据加密标准，宣布了近代密码学的开始。2001年美国联邦政府颁布高级加密标准。随着其他技术的发展，一些具有潜在密码应用价值的技术也逐渐得到了密码学家极大的重视并加以应用，出现了一些新的密码技术，如混沌密码、量子密码等。这些新的密码技术正在逐步地走向实用化。2.1.1密码体制研究各种加密方案的科学称为密码编码学，而研究密码破译的科学称为密码分析学。密码学作为数学的一个分支，是密码编码学和密码分析学的统称，其基本思想是对信息进行一系列的处理，使未受权者不能获得其中的真实含义。一个密码系统，也称为密码体制，有五个基本组成部分。明文：是加密输入的原始信息，通常用m表示。全体明文的集合称为明文空间，通常用M表示。密文：是明文经加密变换后的结果，通常用c表示。全体密文的集合称为密文空间，通常用C表示。密钥：是参与信息变换的参数，通常用k表示。全体密钥的集合称为密钥空间，通常用K表示。加密算法：是将明文变换为密文的变换函数，即发送者加密消息时所采用的一组规则，通常用E表示。解密算法：是将密文变换为明文的变换函数，即接收者解密消息时所采用的一组规则，通常用D表示。加密：是将明文M用加密算法E在加密密钥Ke的控制下变成密文C过程，表示为C=EKe(M)。解密：是将密文C用解密算法D在解密密钥Kd的控制下恢复为明文M的过程，表示为M=DKd(C)，并且要求M=DKd(Eke(M))，即用加密算法得到的密文用一定的解密算法总是能够恢复成为原始的明文。对称密码体制：当加密密钥Ke与解密密钥Kd是同一把密钥，或者能够相互较容易地推导出来时，该密码体制被称为对称密码体制。非对称密码体制：当加密密钥Ke与解密密钥Kd不是一把密钥，且解密密钥不能根据加密密钥计算出来（至少在假定合理的长时间内）时，该密码体制被称为非对称密码体制。在密码学中通常假定加密和解密算法是公开的，密码系统的安全性只系于密钥的安全性，这就要求加密算法本身要非常安全。如果提供了无穷的计算资源，依然无法被攻破，则称这种密码体制是无条件安全的。除了一次一密之外，无条件安全是不存在的，因此密码系统用户所要做的就是尽量满足以下条件：（1）破译密码的成本超过密文信息的价值。（2）破译密码的时间超过密文信息有用的生命周期。如果满足上述两个条件之一，则密码系统可认为实际上是安全的。2.1.2密码分类加密技术除了隐写术以外可以分为古典密码和现代密码两大类。古典密码一般是以单个字母为作用对象的加密法，具有久远的历史；而现代密码则是以明文的二元表示作为作用对象，具备更多的实际应用。现将常用密码算法按照古典密码与现代密码归纳。加密法：古典密码、现代密码古典密码：替代密码(简单替代、多明码替代、多字母替代、多表替代)和换位密码现代密码：序列密码（RC4、A5），分组密码（DES、3DES、AES），公开密钥密码(RSA、EIGamal、ECC)2.2古典密码常用的古典密码可以分为替代密码和换位密码两大类。替代密码是发送者将明文中的每一个字符用另外一个字符来替换，生成密文发送，接收者对密文进行逆替换恢复出明文。换位密码是将明文中的字母不变而位置改变的密码，也称为置换密码2.2.1替代密码在古典密码学中，替代密码以下四种类型：简单替代密码多明码替代密码多字母替代密码多表替代密码其中，最常用的古典密码是简单替代密码和多表替代密码1.简单替代密码简单替代密码又称为单表替代密码或单字母密码，是指一个明文字符用相应的唯一一个密文字符替代的密码。如打乱字母的排列次序构成与明文对应的密码表，或者采用密钥词组来推导密码表。移位密码是简单替代密码中的一种，其替代规则是明文字母被字母表中排在该字母后面的第K个字母所替代，即明文字母表向左循环移位K位，Z的字母后面是A。当K=3时，就是最早的替代密码——恺撒密码。移位密码算法可以表示如下：设明文字母为m,则加密算法c=E(m)=(m+k)mod26，解密算法m=D(c)=(c-k)mod26,其中M={A,B,C,…,Z},C={A,B,C…,Z},K={0,1,2,…,25}。例2.1已知移位密码的密钥K=5,明文M=CLASSROOM，求密文C=？移位密码仅有25个可能的密钥，用强行攻击密码分析直接对所有25个可能的密钥进行尝试即能破解，因此非常不安全。如果允许字母能够任意替代则可以使密钥空间变大，消除强行攻击密码分析的可能性，如采用密钥词组单字母密码。在密钥词组的单字母密码替代算法中，密文字母序列为先按序写下密钥词组，去除该序列中已出现的字母，再依次写下字母表中剩余的字母构成密码表。例2.2已知密钥词组的单字母密码替代算法的密钥K=CLASSISOVER,明文M=BOOKSTOR,求密文C=?密钥词组的单字母密码虽然比移位密码更安全一些，但由于它和移位密码一样，都是明文字母与密文字母一一对应的，因此，利用语言的规律性，采用频率分析的方法仍能对密文进行破解。为了对抗频率分析，可以对单个字母提供多种替代，即一个明文字母可以对应多个密文字母，如果分配给每个字母的替代字母数正比于该字母的相对频率，则单字母频率信息会完全被淹没，如多表替代密码。2.多表替代密码多表替代密码是由多个简单替代密码组成的密码算法。Vigenere密码是一种典型的多表替代密码，其密码表是以字母表移位为基础，把26个英文字母进行循环移位，排列在一起，形成26*26的方阵。Vigenere密码算法表示如下：设密钥K=k0k1k2…kd，明文M=m0m1m2…mn加密变换：ci=(mi+ki)mod26,i=0,1,2,…,n解密变换：mi=(ci-ki)mod26,i=0,1,2,…,n例2.3已知Vigenere密码算法中密钥K=SCREEN,明文M=COMPUTER，求密文C=?2.2.2换位密码将明文中的字母不变而位置改变的密码称为换位密码，也称为置换密码。如，把明文中字母逆序来写，然后以固定长度的字母组发送或记录。列换位法是最常用的换位密码，其算法是以一个矩阵按行写出明文字母，再按列读出字母序列即为密文串。例2.4已知列换位法密钥K=SINGLE,明文M=ABOUTFUNCTIONDISCOVERVERY,求密文C=?2.3分组密码现代密码学中所出现的密码体制可分为两大类：对称加密体制和非对称加密体制。对称加密体制中相应采用的就是对称算法。在大多数对称算法中，加密密钥和解密密钥是相同的。从基本工作原理来看，古典加密算法最基本的替代和换位工作原理，仍是现代对称加密算法最重要的核心技术。对称算法可分为两类：序列密码和分组密码，其中绝大多数、基于网络的对称密码应用，使用的是分组密码。与序列密码每次加密处理数据流的一位或一个字节不同，分组密码处理的单位是一组明文，即将明文消息编码后的数字序列划分成长为L位的组m,各个长为L的分组分别在密钥k(密钥长为t)的控制下变换成与明文组等长的一组密文输出文字序列c。分组密码算法实际上就是在密钥的控制下，通过某个置换来实现对明文分组的加密变换。为了保证密码算法的安全强度，对密码算法的要求如下：(1)分组长度足够长；(2)密钥量足够多；(3)密码变换足够复杂2.3.1DES美国国家标准局（NBS）于1973年向社会公开征集一种用于政府机构和商业部门的加密算法，经过评测和一段时间的试用，美国政府于1977年颁布了数据加密标准（DES）。DES是分组密码的典型代表，也是第一个被公布出来的标准算法，曾被美国国家标准局（现为国家标准与技术研究所NIST）确定为联邦信息处理标准，使用广泛，特别是在金融领域，曾是对称密码体制事实上的世界标准。DES是一种分组密码，明文、密文和密钥的分组长度都是64位，并且是面向二进制的密码算法。DES处理的明文分组长度为64位，密文分组长度也是64位，使用的密钥长度为56位(实际上函数要求一个64位的密钥作为输入，但其中用到的只有56位，另外8位可以用作奇偶校验位或者完全随着设置)。DES是对合运算，它的解密过程和加密相似，解密时使用与加密同样的算法，不过子密钥的使用次序则要与加密相反。DES的整个体制是公开的，系统的安全性完全靠密钥保密。DES算法的加密过程经过了三个阶段：首先，64位的明文在一个初始置换IP后，比特重排产生了经过置换的输入，明文组被分成右半部分和左半部分，每部分32位，以L0和R0表示；第二阶段是对同一个函数进行16轮迭代，称为乘积变换或函数f。这个函数将数据和密钥结合起来，本身既包含换位又包含替代函数，输出为64位，在左边和右边两个部分经过变换后得到预输出。Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki),i=1,2,L,16最后阶段，预输出通过一个逆初始置换IP-1算法就生成了64位的密文结果。相对应的DES的解密过程由于DES的运算是对合运算，所以解密和加密可共同一个运算，只是子密钥的使用的顺序不同。解密过程可用如下的数学公式表示：Ri-1=LiLi-1=Ri⊕f(Li,Ki),i=1,2,L,16DES在总体上应该说是极其成功的，但在安全上也有其不足之处。(1)密钥太短：IBM原来的Lucifer算法的密钥长度是128位，而DES采用的是56位，这显然太短了。1998年7月17日美国EFF宣布，他们用一台价值25万美元的改装计算机，只用了56个小时就穷举出一个DES密钥。1999年EFF将该穷举速度提高到24小时。(2)存在互补对称性：将密钥的每一位取反，用原来的密钥加密已知明文得到密文分组，那么用此密钥的补密钥加密