02-网络信息安全技术-第2章

第2章密码技术基础,2.1密码技术的基本概念2.2古典加密技术2.3现代加密技术,2.1密码技术的基本概念,采用密码方法可以隐藏和保护需要保密的信息，使未授权者不能获得该信息。加密技术是对传输过程中的数据进行保护的重要方法，也是对存储在媒体上的数据内容加以保护的一种有效手段。加密已经成为实现网络安全的一种有效又必不可少的技术手段。传统加密体制的整个过程如图2.1所示。此图是加密/解密的一个基本原理图，需要加密的信息称为明文（Plaintext），这个明文信息由一个加密函数变换成密文(Ciphertext)，这个函数以一个密钥（Key）作为参数，所以可以用c=E（m，ke）来表达这个加密过程。,解密过程基本类似，用一个解密函数和解密密钥对密文进行变换，成为明文，即m=D（c，kd），所以有m=D（E（m，ke），kd）。如果ke=kd，那么这种加密体制称为单钥或对称密码体制(OneCD*2KeyorSymmetricCryptosystem)。如果kekd，那么这种加密体制称为双钥或非对称密码体制(Two-KeyorAsymmetricCryptosystem)。这是1976年由Diffie和Hellman等人所开创的新体制。密钥是密码体制安全的关键，它的产生和管理是密码技术中的重要研究课题。,图2.1传统加密体制的基本过程,一般加密/解密的函数（算法）是公开的，一个算法的强度（被称为破解的难度）除了依赖于算法本身以外，还往往与密钥长度有关。通常密钥越长，强度越高，这是因为密钥越长，被猜出的可能性越低。所以，保密性在于一个强度高的算法加上一个长度长的密钥。,2.2古典加密技术,2.2.1置换密码置换密码亦称换位密码。置换只不过是一个简单的换位。每个置换都可以用一个置换矩阵来Ek表示。每个置换都有一个与之对应的逆置换Dk。置换密码的特点是仅有一个发送方和接收方知道的加密置换（用于加密）及对应的逆置换（用于解密）。它是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。,令明文m=m1,m2,mL。令置换矩阵所决定的置换为，则加密置换,c=Ek(m)=(c1,c2,cL)=m(1),m(2),m(L),解密置换,例，置换密码。,最后一段长不足5，加添一个字母x。将各段的字母序号按下述置换矩阵进行换位：,得到密文如下:,STIEHEMSLPSTSOPEITLBSRPNATOIISIOPCNSHXRE,利用下述置换矩阵：,可将密文恢复为明文。,L=5时可能的置换矩阵总数为5！=120。一般为L!个。可以证明，在给定L下所有的置换矩阵构成一个L!对称群。,2.2.2代换密码令表示明文字母表，内有q个“字母”或“字符”。设其顺序号为：0,1,q-1，可以将映射为一个整数集Zq=0,1,2,q-1，在加密时常将明文信息划分为长为L的信息单元，称为明文组。以m表示，如m=(m0,m1,mL),miZq,令表示明文字母表，内有q个“字母”或“字符”。设其顺序号为：0,1,:,q-1，可以将映射为一个整数集Z-q=0,1,2,:,q-1，密文组为c=(c1,c2,cL-1),ciZq，代换密码的加密变换是由明文空间到密文空间的映射。,f:mc,m,c,假定函数f是一对一的映射，那么，给定密文c，有且仅有一个对应的明文组m，即对于f存在逆映射f-1，使f-1(c)=f-1f(m)=m加密变换通常是在密钥控制下进行的，即c=f(m,k)=Ek(m),1单表代换密码单表代换密码是对明文的所有字母都用同一个固定的明文字母表到密文字母表的映射，即f:ZqZq若明文为m=m0,m1,则相应的密文为c=c0,c1,.=f(m0),f(m1),1）位移代换密码位移代换密码是最简单的一种代换密码，其加密变换为Ek(i)=(i+k)jmodq0i,jq,0kq密钥空间元素个数为q，其中有一恒等变换，k=0，解密变换为D(j)=Eq-k(j)j+q-k(i+k)-kimodq例如，凯撒密码变换是对英文26个字母进行位移代换的密码，即将每一字母向前推移k位。若q=26，如选择密钥k=5，则有下述变换:明文：abcdefghijklmnopqrstuvwxyz密文：FGHIJKLMNOPQRSTUVWXYZABCDE,不同的k将得到不同的密文。于是对于明文：m=caesarcipherisashiftsubstitution经凯撒密码变换后得到的密文：cFDVHDUFLSKHULVDVKLIWVXEVWLWXWLRQ反向利用同一个对应表，就可以很容易地从密文：cE(m)FDVHDUFLSKHULVDVKLIWVXEVWLWXWLRQ中恢复出原来的明文：m=caesarcipherisashiftsubstitution,2)乘数密码乘数密码的加密变换为Ek(i)=ikjmodq0jq这种密码也称采样密码，是将明文字母表按序号每隔k位取出一个字母排列而成密文（字母表首尾相连）。显然，当(k,q)=1，即k与q互素时才是一一对应的。若q为素数，则有q-2个可用密钥。,例如，英文字母表q=26，选k=9，则由明文密文字母对应表明文：abcdefghijklmnopqrstuvwxyz密文：AJSBKTCLUDMVENWFOXGPYHQZIR于是对明文：Multiplicativercipher有密文：EYVPUFVUSAPUHKSUFLKX。,3)仿射密码将移位密码和乘数密码进行组合就可以得到更多的选择方式获得密钥。按Ek(i)=ik1+k0jmodqk1,k0Zq其中，(k1,q)=1,以k1,k0表示密钥。当k0=0时就得到乘数密码，当k1=1时就得到位移密码，q=26时可能的密钥数为2612-1=311个。,2多表代换密码多表代换密码是一系列（两个以上）代换表依次对明文信息的字母进行代换的加密方法。令明文字母表为Zq，令=(1,2,)为代换序列，明文字母序列为m=m1,m2,则相应的密文字母序列为c=Ek(m)=(m)=1(m),2(m),，若为非周期的无限序列，则相应的密码为非周期多表代换密码，否则，为周期多表代换密码。维吉尼亚是法国的密码专家，以他的名字命名的维吉尼亚密码加密算法是多表密码的典型代表。方法如下：,设密钥k=k1,k2,kn，明文m=m1,m2,mn，加密变换为,Ek(m)=c1,c2,cn,其中,cimi+kimodqi=1,2,n,例如，令q=26，明文m=polyalphabeticcipher，k=RADIO，即周期为5。首先将m分解成长为5的序列:polyalphabeticcipher每一段用密钥k=RADIO加密得密文：c=GOOGOCPKTPNTLKQZPKMF,表2.1是维吉尼亚代换方阵，利用它可进行加密和解密。利用密钥k=RADIO对明文polya加密得GOOGO,第一个G是在r行p列上，第二个O是在a行o列上，第三个O是在d行l列上，以此类推。解密时p是r行含G的列，同理o是a行含O的列。以此可以推出全部密文，从而恢复明文。,表2.1维吉尼亚密码代换方阵,表2.1维吉尼亚密码代换方阵,2.3现代加密技术,1.对称加密技术对称密码技术包括任何加密形式，其中同一个密钥既用于加密又用于解密所涉及的文本，被称为对称密码，这点也是对非对称密码而言的。下面介绍几种著名的对称密码技术。1)分组密码分组密码将定长的明文块转换成等长的密文，这一过程是在密钥的控制之下。使用逆向变换和同一个密钥来实现解密。对于当前的许多分组密码，分组大小是64位，但这种长度可能会增加。,明文信息通常要比特定的分组大小长得多，而且使用不同的技术或操作方式。这样的方式示例有：电子编码本（ECB）、密码分组链接（CBC）或密码反馈（CFB）。ECB使用同一个密钥简单地将每个明文块一个接一个地进行加密；在CBC方式中，每个明文块在加密前先与前一密文块进行“异或”运算，从而增加了复杂程度，可以使某些攻击更难以实施。“输出反馈”方式（OFB）类似CBC方式，但是进行“异或”的量是独立生成的。目前CBC受到广泛使用，例如在DES（qv）实现中。,迭代的分组密码是那些在加密过程有多次循环的密码，因此提高了安全性。在每个循环中，可以通过使用特殊的函数从初始密钥派生出的子密钥来应用适当的变换。该附加的计算需求必然会影响加密的速度，因此在安全性需要和执行速度之间存在着一种平衡。天下没有免费的午餐，密码术也是如此；与其它地方一样，应用适当方法的技巧中有一部分是源于对需要进行的权衡以及它们与需求平衡的关系如何的理解。分组密码包括DES、IDEA、SAFER、Blowfish和Skipjack最后一个是“美国国家安全局（NSA,USNationalSecurityAgency）”限制器芯片中使用的算法。,下面介绍具体的分组密码的实现。(1)DES数据加密算法（DEA,DataEncryptionAlgorithm）的数据加密标准（DES,DataEncryptionStandard）是规范的描述，它出自IBM的研究工作，并在1997年被美国政府正式采纳。它很可能是使用最广泛的密钥系统，特别是在保护金融数据的安全中，最初开发的DES是嵌入硬件中的。通常，自动取款机（ATM,AutomatedTellerMachine）都使用DES。,DES使用一个56位的密钥以及附加的8位奇偶校验位，产生最大64位的分组大小。这是一个迭代的分组密码，使用称为Feistel的技术，其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但最后一个循环不交换。DES使用16个循环。,设明文m是0和1组成的长度为64bit的符号串，密钥k也是64bit的0、1符号串，即m=m1,m2,m64(mi=0或1)k=k1,k2,k64(ki=0或1)其中，密钥k只有56bit有效，k8,k16,k24,k64是奇偶校验位，在算法中不起作用。加密过程为DES(m)=IP-1。T16。T15T2。T1。IP(m)IP是初始置换，IP-1是它的逆置换。,表2.2IP的初始置换及逆置换,DES的加密过程。将DES的加密过程用图2.2表示。初始化换位IP，是将输入的二进制明文块T变换成T0=IP(T),然后T0经过16次函数f的迭代，最后通过逆初始换位IP-1得到64位的二进制密文输出。两次相邻的迭代之间的关系是,Li=Ri-1Ri=Li-1f(Ri-1,ki),其中，表示按位做不进位的加法运算，即10=01=1,00=11=0,ki表示48位的子密钥。,图2.2DES加密过程,函数f(Ri-1,ki)的结构如图2.3所示。图2.3中E是位选择表（见表2.3），它将Ri-1扩展成48位二进制块E(Ri=1)然后对E(Ri=1)和ki进行操作，并将结果分成8个6bit二进制块B1,B2,B8，此处B1,B2,B8=kiE(Ri-1)，每个6位子块Bi都是选择（代换）函数Si的输入，其输出是一个4位的二进制块，把这些子块合并成32位二进制块后，用置换表P(如表2.4)将它变成P(S1(B1),S2(B2),S8(B8)这就是函数f(Ri-1,ki)的输出。每个Si将一个6位块Bi=b1,b2,b6转换成一个4位块(如表2.5），与b1,b6对应的整数确定表中的行号，与b2,b3,b4,b5相对应的整数确定表中的列号，Si(Bi)的值就是位于该行和该列的整数的4位二进制表示形式。,图2.3DES中间变换过程,表2.3位选择表,表2.4换位表,表2.5选择（替代)函数S,表2.5选择（替代)函数S,表2.5选择（替代)函数S,密钥ki是由初始密钥推导得到的，初始密钥k是一个64位的二进制块，其中8位是奇偶校验位，分别位于第8、16、64位。子密钥换位函数PC-1把这些奇偶校验去掉，并把剩下的56位进行换位，如表（2.3）。换位后的结果PC-1(k)被分成两半C和D，各有28位，令Ci和Di分别表示推导ki时所用的C和D的值，变换公式如下Ci=LS(Ci-1)Di=LS(Di-1),式中，LS是循环左移位变换，其中LS1,LS2,LS9,LS16是循环左移一位变换，其余的LSi是循环左移两位变换。C0,D0是C和D的初始值。最后，通过子密钥变换函数PC2（参见表2.5）得出,ki=PC-2(Ci,Di),解密算法和加密算法相同，但是它使用的子密钥顺序是相反的。第一次是用k16,第2次迭代用k15,最后一次用k1，这是因为最终换位IP-1是初始换位IP的逆变换且,Ri-1=LiLi-1=Rif(Li,ki),DES代换使得输出成为输入的非线性函数，换位扩展了输出对输入的依赖性。,(2)IDEA国际数据加密算法IDEA（InternationalDataEncryptionAlgorithm）是由两位研究员XuejiaLai和JamesL.Massey在苏黎世的ETH公司开发的，一家瑞士Ascomsystec公司拥有专利权。IDEA是作为迭代的分组密码实现的，使用128位的密钥和8个循环。这比DES提供了更多的安全性，但是在选择用于IDEA的密钥时，应该排除那些称为“弱密钥”的密钥。DES只有四个弱密钥和12个次弱密钥，而IDEA中的弱密钥数相当可观，有251个。但是，如果密钥的总数非常大，达到2128个，那么仍有277个密钥可供选择。,2)序列密码与分组密码相比，序列密码是非常快速的，尽管某些方式下工作的一些分组密码（如CFB或OFB中的DES）可以与序列密码一样有效地运作,但序列密码作用于由若干位组成的一些小型组，通常使用称为密钥流的一个位序列作为密钥对它们逐位应用“异或”运算。有些序列密码基于一种称做“线性反馈移位寄存器（LFSR,LinearFeedbackShiftRegister）”的机制，该机制生成一个二进制位序列。,2.非对称密码非对称密码术相对于对称密码术的最大区别就在于它的加密和解密不是使用同一个密钥和算法。在对称密码术中加密和解密都需要共享一个密钥，这可能是使用密码术的对称密码体制的主要弱点。在非对称密码术或公钥密码术中没有这样的问题。使用在数学上相关的两个密钥，并通过用其中一个密钥加密的明文只能用另一个密钥进行解密的方法来使用它们。通常，其中一个密钥由个人秘密持有，因此几乎没有必要共享密钥，从而避免了对安全性的威胁。第二个密钥，即所谓的公钥，需要让尽可能多的人知道。,非对称密码体制提供的安全性取决于难以解决的数学问题。例如，将大整数因式分解成质数。公钥系统使用这样两个密钥，一个是公钥，用来加密文本；另一个是安全持有的私钥，只能用此私钥来解密。也可以使用私钥加密某些信息，然后用公钥来解密，而公钥是大家都知道的，这样拿此公钥能够解密的人就知道此消息是来自持有私钥的人，从而达到了认证作用。对于认证的应用方式我们下面会给出几种常见的非对称密码加密算法。,1)Diffie-HellmanDiffie-Hellman协议允许两个用户通过某个不安全的交换机制来共享密钥，而不需要首先就某些秘密值达成协议。它有两个系统参数，每个参数都是公开的，其中一个是质数p，另一个通常称为生成元，是比p小的整数；这一生成元经过一定次数幂运算之后再对p取模，可以生成从1到p-1之间任何一个数。,在实际情况下，可能涉及以下过程：首先，每个人生成一个随机的私有值，即a和b。然后，每个人使用公共参数p和g以及它们特定私有值a或b通过一般公式gnmodp（其中n是相应的a或b）来派生公共值。然后，他们交换这些公共值。最后，一个人计算kab=(gb)amodp，另一个人计算kba=(ga)bmodp。当kab=kba=k时，即是共享的秘钥。,这一密钥交换协议容易受到伪装攻击，即所谓中间人（middleperson）攻击。如果A和B正在寻求交换密钥，则第三个人C可能介入每次交换。A认为初始的公共值正在发送到B，但事实上，它被C拦截，然后向B传送了一个别人的公共值，然后B给A的消息也遭受同样的攻击，而B以为它给A的消息直接送到了A。这导致A与C就一个共享秘钥达成协议而B与C就另一个共享秘钥达成协议。然后，C可以在中间拦截从A到B的消息，并使用A/C密钥解密，修改它们，再使用B/C密钥转发到B，B到A的过程与此相反，而A和B都没有意识到发生了什么。,为了防止这种情况，1992年Diffie和其他人一起开发了经认证的Diffie-Hellman密钥协议。在这个协议中，必须使用现有的私钥公钥对以及与公钥元素的相关数字证书，由数字证书验证交换的初始公共值。,2)RSARSA使用很大的质数来构造密钥对。每个密钥对共享两个质数的乘积，即模数，但是每个密钥对还具有特定的指数。RSA实验室对RSA密码体制的原理做了如下说明：“用两个很大的质数p和q，计算它们的乘积n=pq，n是模数。选择一个比n小的数e，它与(p-1)(q-1)互为质数，即除了1以外，e和(p-1)(q-1)没有其它的公因数。找到另一个数d，使(ed-1)能被(p-1)(q-1)整除。值e和d分别称为公共指数和私有指数。公钥是这一对数(n，e)；私钥是这一对数(n，d)。”,知道公钥可以得到获取私钥的途径，但是这取决于将模数因式分解成组成它的质数，这是很困难的，因为通过选择足够长的密钥，可以使其基本上不可能实现。需要考虑的是模数的长度。RSA实验室目前建议：对于普通公司使用的密钥大小为1024位，对于极其重要的资料，使用双倍大小，即2048位。对于日常使用，768位的密钥长度已经足够，因为当前技术无法破解它。,3.散列函数散列函数与公钥密码体制不同，但因为散列函数通常用于消息摘要，因此在这里将它们视为认证和数字签名的整个系统的一部分也是适宜的。1)MD4和MD5MD2、MD4和MD5是由RonRivest开发的用于数字签名应用程序的消息摘要算法，在数字签名应用程序中将消息压缩成摘要，然后由私钥加密。MD2是为8位计算机系统设计的，而MD4和MD5是为32位计算机系统开发的。MD4是在1990开发的，现在它被认为是不安全的。,RSA实验室将MD5描述为“系有安全带的MD4”，它虽然比MD4慢，但却被认为是安全的。与使用MD4时相同，会填补明文消息以确保其位的长度加上448可以被512整除。然后添加表示原始消息长度的64位二进制数，然后使用循环压缩函数在512位块中处理该消息，每块都要经过四轮各不相同的处理。我们给出MD5的算法描述，对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。,在MD5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。因此，信息的字节长度（bitslength）将被扩展至n512+448，即n64+56个字节（bytes），n为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在这个结果后面附加一个以64位二进制数表示的填充前信息长度。经过这两步的处理，现在的信息字节长度为n512+448+64=(n+1)512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。,MD5中有四个32位被称为链接变量（ChainingVariable）的整数参数，它们分别为：a=0 x01234567，b=0 x89abcdef，c=0 xfedcba98，d=0 x76543210。当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。将上面四个链接变量复制到另外四个变量中：a到a，b到b，c到c，d到d。主循环有四轮（MD4只有三轮），每轮循环都很相似。第一轮进行16次操作，每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。以下是每次操作中用到的四个非线性函数（每轮一个）。,f(x,y,z)=(xi(x,y,z)=y(x|(z)式中，&是与操作，|是或操作，是非操作，是异或操作。,这四个函数的说明：如果x、y和z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。f是一个逐位运算的函数。即，如果x为1，那么选择y位上的数据，否则选择z位上的数据。函数h是逐位奇偶操作符,压缩过程如图2.4所示。,图2.4,假设Tj表示消息的第j个子分组（从015），F(a,b,c,d,Tj,s,Xi)表示a=b+(a+(f(b,c,d)+Tj+Xi)G(a,b,c,d,Tj,s,Xi)表示a=b+(a+(g(b,c,d)+Tj+Xi)H(a,b,c,d,Tj,s,Xi)表示a=b+(a+(h(b,c,d)+Tj+Xi)I(a,b,c,d,Tj,s,Xi)表示a=b+(a+(i(b,c,d)+Tj+Xi),这四轮（64步）是：第一轮F(a,b,c,d,T0,7,0 xd76aa478)F(d,a,b,c,T1,12,0 xe8c7b756)F(c,d,a,b,T2,17,0 x242070db)F(b,c,d,a,T3,22,0 xc1bdceee)F(a,b,c,d,T4,7,0 xf57c0faf)F(d,a,b,c,T5,12,0 x4787c62a)F(c,d,a,b,T6,17,0 xa8304613),F(b,c,d,a,T7,22,0 xfd469501)F(a,b,c,d,T8,7,0 x698098d8)F(d,a,b,c,T9,12,0 x8b44f7af)F(c,d,a,b,T10,17,0 xffff5bb1)F(b,c,d,a,T11,22,0 x895cd7be)F(a,b,c,d,T12,7,0 x6b901122)F(d,a,b,c,T13,12,0 xfd987193)F(c,d,a,b,T14,17,0 xa679438e)F(b,c,d,a,T15,22,0 x49b40821),第二轮G(a,b,c,d,T1,5,0 xf61e2562)G(d,a,b,c,T6,9,0 xc040b340)G(c,d,a,b,T11,14,0 x265e5a51)G(b,c,d,a,T0,20,0 xe9b6c7aa)G(a,b,c,d,T5,5,0 xd62f105d)G(d,a,b,c,T10,9,0 x02441453)G(c,d,a,b,T15,14,0 xd8a1e681)G(b,c,d,a,T4,20,0 xe7d3fbc8),G(a,b,c,d,T9,5,0 x21e1cde6)G(d,a,b,c,T14,9,0 xc33707d6)G(c,d,a,b,T3,14,0 xf4d50d87)G(b,c,d,a,T8,20,0 x455a14ed)G(a,b,c,d,T13,5,0 xa9e3e905)G(d,a,b,c,T2,9,0 xfcefa3f8)G(c,d,a,b,T7,14,0 x676f02d9)G(b,c,d,a,T12,20,0 x8d2a4c8a),第三轮H(a,b,c,d,T5,4,0 xfffa3942)H(d,a,b,c,T8,11,0 x8771f681)H(c,d,a,b,T11,16,0 x6d9d6122)H(b,c,d,a,T14,23,0 xfde5380c)H(a,b,c,d,T1,4,0 xa4beea44)H(d,a,b,c,T4,11,0 x4bdecfa9)H(c,d,a,b,T7,16,0 xf6bb4b60)H(b,c,d,a,T10,23,0 xbebfbc70)H(a,b,c,d,T13,4,0 x289b7ec6),H(d,a,b,c,T0,11,0 xeaa127fa)H(c,d,a,b,T3,16,0 xd4ef3085)H(b,c,d,a