密码算法设计与实现

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,安全程序设计方法密码算法设计与实现,1,问题,点加/解密，可生成一个新文件(有默认目录和名称，可更改)。,如果消息校验失败，则输出解密失败信息，不会生成新文件。,2,问题分析加密,我们用,EA、 DA和AA分别表示加密算法、解密算法和数据认证算法，则,加密,过程如图所示，,可表示为：,（1）校验值ICV = AA (,P, Ka, IV)；,（2）密文,C,= EA (,K, IV,P,| ICV),3,问题分析加密,(续),上图,中，IV一般为计数器，功能是抗重放攻击，对于相同的明文和密钥，每次可以加密成不同的密文。,数据认证算法AA的功能是检测密文是否被篡改，保证数据的,完整性,，即,消息的接收者能够验证在传送过程中消息没有被修改，入侵者不能用假消息代替合法消息。,认证密钥Ka与加密密钥,K,可相同，也可不相同。,4,问题分析解密,解密过程根据加密套件选择相应的解密算法，,如图,所示，可表示为：（1）,P,| ICV = DA (,K, IV,C,)；,（2）认证码MAC = AA (,P, Ka, IV)；,（3）MAC = ICV,？,5,密码算法选择,(1),加密算法(,流密码算法、分组密码算法,、公钥密码算法)实现保密性；,(2),数据认证算法,(,分组密码算法的认证模式、CRC 、单向Hash函数,、数字签名算法),保证完整性（消息真实性）。,6,密码算法具体选用,1分组密码算法：,AES、SHACAL2,、DES、IDEA、MISTY1、Camellia、RC6,2分组密码模式：,CBC+PXOR(或CRC)、ECB(或CTR或OFB)+CBC-MAC,、OCB、PMAC、RMAC、XCBC,3流密码算法和PRNG(与,CBC-MAC,结合)：,RC4、SEAL,、A5、ANSI X9.17(基于3DES)、G-SHA-1,4,CRC-32,5单向Hash函数（备用）：,SHA1、SHA256,、Whirlpool、RIPEMD160、SHA384、SHA512、HMAC、UMAC、T-T-MAC、MD5,7,1分组密码算法,1.0概述,1.1,DES(数据加密标准)算法,1.2IDEA(国际数据加密算法),1.3AES(Rijndael)算法,1.4NESSIE候选分组密码算法,8,1.0 分组密码算法概述,美国的第一代分组密码算法标准是DES算法，也是一个早期的国际标准；第二代标准是AES算法。欧洲的第一代分组密码算法标准是IDEA算法，新标准是日本人Eisaku Takeda设计的MISTY1算法、Shiho Moriai和Mitsuru Matsui设计的Camellia算法、以及法国人Helena Handschuh和David Naccache设计的SHACAL2算法。,日本在分组密码算法领域的研究非常活跃，向NESSIE提交了5个分组密码算法，是递交数量最多的国家。Camellia算法也是日本的分组密码算法标准，据说某些性能超过了AES 算法。第三代移动通信系统3GPP的标准加密算法KASUMI是MISTY1算法的变种。,巴西在分组密码算法领域的研究也比较活跃，向NESSIE提交了3个分组密码算法，其中，Paulo S. L. M. Barreto和比利时人Vincen t Rijmen合作设计的Khazad算法是入围欧洲决赛的算法。在美国和欧洲新标准征集过程中，俄罗斯、加拿大、澳大利亚和韩国也提交了几个分组密码算法。,国内科研人员提出了几个分组密码算法，性能还不错。,9,1.1DES算法有陷门？,DES,的半公开性：S盒的设计原理至今未公布，可能隐含有陷门（Hidden trapdoors）。,有趣的是，,DES算法是由IBM公司设计的；当时的美国国家标准局(NSA)修改了S-盒设计，以确保IBM没有在算法中嵌入陷门，因为NSA没有理由相信IBM的研究成果，而他们不能绝对确定DES算法没有陷门，如果有陷门，将是他们失职，所以只好修改S-盒；而人们又怀疑NSA在DES,算法中强加了弱点。,10,1.2 IDEA(国际数据加密算法),IDEA算法是欧洲的第一代分组密码算法标准，是由我国旅欧学者来学嘉和他的导师James Massey设计的，也是PGP的标准之一。该算法的设计原则是“来自于3个不同代数群的混合运算”，即异或、模2,16,加、模2,16,+1乘，这就使得IDEA算法易于软硬件实现。,在代数结构上，IDEA算法也不是一个群。该算法的软件实现速度是DES算法的2倍。Bruce Schneier认为，在早期的分组密码算法中，IDEA算法是最好和最安全的。,11,1.3,AES(Rijndael)算法,DES算法的安全强度越来越满足不了技术发展的需要。为此，美国NIST于1997年开始制定AES(高级加密标准)算法以满足新时代的信息安全需求。1999年，NIST宣布已从15个候选算法中选出5个较好的算法：MARS，RC6，Rijndael，Serpent，Twofish。2000年底，NIST最终确定采纳Rijndael算法作为AES算法。AES算法是由比利时的Joan Daemen和Vincent Rijmen设计的，经过全世界密码学者3年多的密集评估，被认为是安全的。由于评估过程公开，AES算法会有陷门的可能性很小。,12,1.3,AES(高级加密标准)算法设计思路,通常，分组密码算法的结构是Feistel结构，不过AES算法使用了一种称为宽轨迹策略(WTS)的方法。,该算法有,3条设计准则：抗所有已知的攻击；在多个平台上快速简洁地实现；设计简单。其分组长度为128位 (Rijndael算法本身的分组长度可以是128、192或256位)，密钥长度可以是128、192或256位，分别记为AES-128、AES-192和AES-256。对于AES-128，迭代轮数,r,=10+1；对于AES-192，,r,=12+1；对于AES-256，,r,= 14+1。AES,算法过程可分为轮密钥编排和加密过程两个独立的部分。,13,1.3,AES算法加密全过程,加密,全过程包括,：轮密钥编排(扩展)；,轮密钥异或，前(,r,-,1)轮迭代，一个结尾轮。即,Rijndael (State, CipherKey),KeyExpansion (CipherKey, ExpandedKey);,AddRoundKey (State, ExpandedKey);,for (i=1; i 1),poly,；,else crc = crc 1；,crcTab ,i, = crc,；,则CRC-32算法ICV = CRC-32 (,P,)过程为：,crc = 0xffffffff；,for,i,= 0 to len-1 crc = crcTab(crc,P,i) & 0xff(crc 8)&0x00ffffff；,ICV = crc0xffffffff；,45,5单向Hash函数,5.0 概述,5.1 早期的Hash函数,5.2 HMAC(带密钥的Hash函数),5.3 新一代Hash函数,5.4 国产Hash函数,46,5.0 单向Hash函数概述,散列(Hash)函数又称为杂凑函数，或音译为哈希函数。单向散列函数的早期国际标准有SHA-1(美)、RIPEMD-160 (欧)等算法，现在NIST又增加了三个标准算法(SHA-256，SHA-384，SHA-512)。带密钥的散列函数(HMAC)是MAC(消息认证码)算法的一种。HMAC的美国标准是HMAC-MD5和HMAC-SHA-1算法。欧洲的单向散列函数新标准是比利时人Paulo Barreto和Vincent Rijmen设计的Whirlpool算法；欧洲的MAC新标准是Ted Krovetz, John Black,Shai Halevi, Hugo Krawczyk和Phillip Rogaway合作设计的UMAC算法以及德国人Bert de Boer和Bart Van Rompay设计的Two-Track-MAC算法。,我国学者王小云等已相继破译了MD4、MD5、HAVAL-128、RIPEMD-128、SHA-0和SHA-1等散列函数，,被认为是密码学界近年来“最具实质性的研究进展”,。国内科研人员提出了一些单向散列函数和MAC算法。,47,5.1早期的Hash函数,单向散列函数的早期国际标准有SHA-1(美)、RIPEMD-160 (欧)等算法。,早期的单向散列函数中，欧洲的RIPEMD-128算法是MD4算法的一种变型；HAVAL算法是MD5算法的改进版本。,我国学者王小云等已成功攻破了MD4、MD5、HAVAL-128、RIPEMD-128，在数小时内就可以找到MD5的碰撞，被认为是密码学界近年来“最具实质性的研究进展”；“能在任何初始值下用240次Hash运算找出SHA-0的碰撞，并且有望以更低的复杂度完成对SHA-0的攻击”。随后，王小云等又攻破了SHA-1算法。,48,5.2HMAC(带密钥的Hash函数),定义HMAC需要一个散列函数,H,和一个密钥,K,。我们用,T,来表示数据的分组长度（假设散列函数的分组长度,T,= 64 B），用,m,来表示散列函数的输出长度（MD5中,m,= 16 B，SHA1中,m,= 20 B）。密钥长度可以是小于等于分组长度的任何正整数值。应用程序中使用的密钥长度若是比,T,大，则首先用使用散列函数,H,作用于它，然后用,H,输出的,m,长度字符串作为在HMAC中实际使用的密钥。一般情况下，推荐的最小密钥长度是,m,个字节（与,H,的输出数据长度相等）。,49,5.2 HMAC,（续）,令ipad为字节0x36重复,T,次，opad为字节0x5C重复,T,次。则输入数据text的HMAC值为,H,(,K,opad) |,H,(,K,ipad) | text,用于HMAC的密钥可以为任意长度（比,T,长的密钥将首先被,H,处理）。但当密钥长度小于,m,时的情况是非常令人担心的，因为这样将降低函数的安全强度。长度大于,m,的密钥是可以接受的，但是额外的长度并不能显著的提高函数的安全强度。,50,5.3 新一代Hash函数,（1）SHA2（FIPS PUB 180-2）算法,包括3个算法： SHA-256、SHA-384和SHA-512。,（2）NESSIE候选散列函数与MAC算法,NESSIE共收到1个散列函数（比利时人Paulo Barreto和Vincent Rijmen设计的Whirlpool算法）和2个MAC(德国人Bert de Boer与Bart Van Rompay设计的Two-Track-MAC算法，Ted Krovetz, John Black,Shai Halevi, Hugo Krawczyk与Phillip Rogaway设计的UMAC)算法，均被采纳为欧洲标准。,51,5.3 新一代Hash函数,(2)NESSIE候选Hash函数与MAC算法,Whirlpool算法,是一个输出长度,m,= 64 B，输入长度,L, 2,256,b的散列函数。其整体结构为Miyaguchi-Preneel结构，可以运行在8 b和64 b的处理器上，即不依赖于具体的工作平台。Whirlpool算法基于一个内部分组密码，密钥和分组长度为,T,= 64 B。轮函数和密钥编排都是根据宽轨迹策略设计的。,Two-Track-MAC算法,为迭代结构，基于带密钥的RIPEMD-160，密钥和输出MAC值都是20 B。不带密钥的RIPEMD-160在其压缩函数中采用了双轨迹结构。双轨迹的作用是交换上一个消息分组；采用反馈使两个轨迹不可逆。通过组合最后一次迭代后两个轨迹的值得到最后的MAC值。,UMAC算法,。该算法的核心是一个通用的散列函数。散列函数处理消息和密钥，产生一个固定长度的散列值，该值与伪随机函数的输出进行异或，得到消息的认证标签，即,AuthTag =,H,(Key1, Msg),F,(Key2, Nonce),其中，Nonce是个18 B的随机数。,52,5.4 国产Hash函数,(1)基于三重分组链接的散列函数(HTBC),(2)基于三重分组的并行散列函数(PHTB),HTBC算法的速度比SHA-1快5%左右；PHTB算法的串行速度比SHA-1慢一点，比MD5和SHA2快。PHTB算法有一定的特色，因为现有的无陷门单向散列函数都是迭代算法，而PHTB算法可并行处理。,53,5.4 国产Hash函数安全性,传统单向散列函数一般由压缩函数,f,迭代构成:,Y,i,=,f,（,P,i,Y,i,-,1,）。这是个Markov过程,其当前迭代值,Y,i,只与当前分组消息,P,i,和上一次的迭代值,Y,i,-1,有关。压缩函数,f,存在多对一映射,即存在两个不同的消息,其前,i,-,1组消息P*和P迭代结果相同,则对任意消息,Q,消息(,P,*|,Q,)和(,P,|,Q,)最终的散列值相同;也就是说,常用单向散列函数都是局部散列的,并非全局杂凑的。,HTBC和PHTB算法不存在这种确定的规律,因为其每组计算值,Y,i,都与整个消息,P,有关;也就是说,HTBC和PHTB是全局散列的。从这个角度而言,HTBC和PHTB的安全性比常用单向散列函数高。,对HTBC和PHTB算法进行的大量统计测试结果都满足要求。,54,作业,大作业：综合运用所学知识，设计、开发和实现一个文件加密软件系统。,上机作业：常用密码算法编程实现，并测试其速度。,1分组密码算法：AES、,SHACAL2、MISTY1、Camellia、RC6,。工作模式采用CBC+PXOR(或CRC-32)、ECB(或CTR或OFB)+CBC-MAC,3流密码算法和PRNG(与CBC-MAC结合)：RC4、SEAL,4CRC-32,5单向Hash函数：SHA1、SHA256、,Whirlpool、RIPEMD160,、SHA384、SHA512,55,习题,1、网络系统安全机制的简单模型一般可分为两步：,(1),(身份)认证与密钥交换,和(2),保密通信,。,2、身份认证可分为两类：(1),对称,认证（即常用的,口令,认证）；,(2),非对称,认证,（基于,数字签名,算法）。,、(1)流密码算法、分组密码算法和公钥密码算法用于,加解密(保密,),；(2),分组密码算法的认证模式、单向Hash函数和数字签名算法用于,消息,认证(数据校验、窜改检测),；,Hash函数和公钥密码算法还可用于,(身份)认证与密钥交换,。,、(1)身份认证算法为信息安全提供,不可否认(抗抵赖，身份真实),性；(2),加密算法,为信息安全提供,保密,性；(3),数据认证算法,为信息安全提供,完整(数据真实),性。,5、对称算法(含Hash函数和PRNG)的基本设计思想是,扩散,和,混乱,。,56,习题,（续）,6、非对称算法(公钥密码算法)的基本设计思想是,计算复杂性,和,陷门单向函数,。,7、对称加密算法的处理过程一般分为两步：,密钥编排,和,数据加密,。,8、产生流密码中的密钥流的一种主要工具是,移位寄存器,。,9、分组密码设计一般采用,SP,思想(,S盒,和,置换运算P,两种变换)(,S盒,实现混乱；,置换运算P,实现扩散)和,Feistel,结构。,10、AES和Whirlpool算法是根据,宽轨迹,策略设计的。,11、在实际应用的混合密码系统中，,公钥密码(非对称),算法用作身份认证和加密会话密钥，,对称,算法用于加密消息。,12、把公钥密码用于密钥分配解决了重要的,密钥管理,问题。,57,习题,（续）,13、为了节约时间，数字签名协议经常和,单向Hash函数,一起使用。并不对整个文件签名，只对文件的,Hash值,签名。,14、密码统计测试方法的原理一般是,假设检验,。,15、对密码算法,f,，如果每一位输出依赖于每一位输入，则称,f,具有,完备性,。,16、当密码算法,f,的任意一位输入改变时，如果平均有一半的输出位改变，则称,f,具有,雪崩效应,。,17、当密码算法,f,的任意一位输入改变时,如果每一位输出改变的概率为0.5,则称,f,满足,严格雪崩准则,。,18、频率测试的目的是检验算法,f,的输出是否服从,均匀,分布。,19、什么是PKI?,20、PKI 的主要建设内容有哪些？,21、完整的PKI应用系统应包括哪些部分？,58,谢谢！,59,