密码编码学与网络安全

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,名词解释 20RSA算法（因素，因子）公钥，私钥的计算 20AES分析，矩阵的变换 20HMAC算法，结构，4种目标，实现，问答型，理解型 20PGP（原理图）什么时候加密，怎么加密 20密钥交换 理解原理，目的防止攻击，提出好方法？防范措施 20流程图的解读 记号读懂 20,1,公钥加密的出现,1976年由Whitfield Diffie & Martin Hellman 在Stanford University所发明,加密密钥P,K,是公开的，称为公钥,解密密钥S,K,是保密的，称为私钥,公钥技术是二十世纪最伟大的思想之一,改变了密钥分发的方式,可以广泛用于数字签名和身份认证服务,2,公钥编码模型-1,3,公钥编码模型-2,4,公钥加密的特点,公开密钥密码体制,能够,有效计算,公钥PK和私钥SK。,从已知的公钥PK,不能推导,出私钥SK。,发送方用公钥PK进行加密，而接收方用私钥SK进行解密,还原出明文，即：,D,SK,(E,PK,(P) = P,两个密钥中的任何一个都能进行加密，而另一个则进行解密。,5,公钥算法应用：保密,6,公钥算法应用：鉴别,7,保密和鉴别,8,RSA,RSA,方法由三位,MIT,科学家,R,ivest,、,S,hamir,和,A,dleman于1977年,提出,最著名和使用最广泛的公钥加密方法,基于整数的有限幂次对素数的取模,使用大整数作为密钥,安全性依赖于大数的因子分解,9,RSA-,密钥选择,1,随机选择两个大素数,p,和,q,。,2,计算公开的模,n=p*q,。,3,计算欧拉函数,(n)=(p-1)*(q-1),。,4,随机选一整数,e,，,1e(n),，,(,（,n,）,e)=1,。即,（,n,）,和,e,互素,。,5,计算,d,，满足,ed mod (n) =,1,。,得到公钥和密钥，公钥为,(,e , n,),，密钥为,d,。,10,RSA-加密与解密,1,将明文划分为一个个数据块,P,，其中,0,Pn。,2C,为P对应的密文。则：,加密：,C= P,e,(mod n),解密：,P= C,d,(mod n),11,RSA-证明,解密：X = D,SK,(C) = C,d,mod n,= (X,e,mod n),d,mod n,= X,ed,mod n,由于de 1 mod(n)，故 de = k(n) +1，则,C,d,mod n = X,k(n) +1,mod n,= (X,(n),),k,X mod n,= X (,根据欧拉定理的变化形式,),12,RSA-举例,1选择p=7,q=17。,2计算n=p*q=119，(n）=(p-1)*(q-1)=96。,3选e=5，因为5和96互素。,4根据5d mod 96=1，得d=77。,5公钥为(5,117),密钥为77。,如：明文为P=6。,密文: C=P,e,mod n = 6,5,mod 119 =41。,解密：,P=C,d,mod n = 41,77,mod 119= 6。,13,RSA的计算技巧,模运算的性质计算M,e,mod n,(a mod n) (b mod n) = (ab) mod n,e= b,k,b,k-1,b,0, 则e = 2,i, 其中b,i,=1,M,e,= M,2,i,=(M,b,k,),2,M,b,k-1,),2,M,b,k-2,),2, ),2,M,b,k,),2,M,b,1,),2,M,b,0,如：6,5,=6,101,=(6),2,),2,.,6= 36,2,.,6 = 7776,.,6 =,46656,计算算法,d=1,For i=k to 0 do,d=d,2,mod n,If b,i,=1 then d=(d*M) mod n,14,RSA的计算技巧,计算7,560,mod 561,560=230h=0010 0011 0000b,d=1, k=9,i=9, d=d,2,mod 561=,1, b,9,=1, d=(d*7) mod 561=,7,i=8, d=d,2,mod 561=,49, b,8,=0,i=7, d=d,2,mod 561=,157, b,7,=0,i=6, d=d,2,mod 561=,526, b,6,=0,i=5, d=d,2,mod 561=,103, b,5,=1, d=(d*7) mod 561=,160,i=4, d=d,2,mod 561=,355, b,4,=1, d=(d*7) mod 561=,241,i=3, d=d,2,mod 561=,298, b,3,=0,i=2, d=d,2,mod 561=,166, b,2,=0,i=1, d=d,2,mod 561=,67, b,1,=0,i=0, d=d,2,mod 561=,1, b,0,=0,15,RSA-安全性,蛮力攻击,数学攻击,定时攻击,16,RSA-蛮力攻击,整数N的因子分解：,从2 开始试验每一个小于等于N 的素数,整数n的十进制位数 因子分解的运算次数 所需计算时间（次/微秒）,501.4x10,10,3.9,小时,759.0x10,12,104,天,1002.3x10,15,74,年,2001.2x10,23,3.8x10,9,年,3001.5x10,29,4.0x10,15,年,5001.3x10,39,4.2x10,25,年,17,RSA-数学攻击,三种形式:,因子分解,N=p.q,从而发现,(N),和,d,直接确定,(N),，然后找出 d,直接找出 d,关键是因子分解,改进不大,Aug-99,曾经使用,GNFS,攻击 130,decimal digits (512) bit,算法改进,从 “Quadratic Sieve” 到 “Generalized Number Field Sieve”,采用1024+,bit RSA,使攻击更困难,确保 p, q 具有相同大小且满足其他限制,18,RSA-定时攻击,mid-1990s 提出,利用运算过程中的时间变化,密钥中的0或1，时间不同,从化费时间推算出操作数的大小,对策,使用固定时间,随机延迟,运算盲化-取幂操作前将密文与一个随机数相乘,19,Summary,have considered:,principles of public-key cryptography,RSA algorithm, implementation, security,20,第5章 高级加密标准,5.1 AES评估准则,5.2 AES密码,21,Advance Encryption Standard,1997年NIST宣布征集AES算法。,与三重DES比，要快且至少一样安全；,分组128位，密钥128/192/256位；,设计简洁。,1998年确定第一轮15个候选者,1999年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofish。,2000年底Rijndael胜出。,22,Rijndael简介,加密、解密相似但不对称,不属于Feistel结构，属于重复结构,支持128/32=,N,b,数据块大小,支持128/192/256(/32=,N,k,)密钥长度,有较好的数学理论作为基础,结构简单、速度快,23,AES算法结构,AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层。,线性混合层：确保多轮之上的高度扩散。,非线性层：具有最优最差-情形非线性的S-盒的并行应用,密钥加层：轮密钥简单地异或到中间状态上。,24,AES算法结构,Ecryption,Decryption,25,状态、密钥的表示,状态/密钥的矩阵表示,State Key,S,00,S,01,S,02,S,03,S,10,S,11,S,12,S,13,S,20,S,21,S,22,S,23,S,30,S,31,S,32,S,33,k,00,k,01,k,02,k,03,k,10,k,11,k,12,k,13,k,20,k,21,k,22,k,23,k,30,k,31,k,32,k,33,26,字节代替(Substitute Bytes )变换,字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个16,16的矩阵。,27,example,28,行移位(Shift Row)变换,29,列混合Mix Column变换,代替操作，将状态的列看作有限域GF（2,8,）上的4维向量并被有限域GF（2,8,）上的一个固定可逆方阵A乘,30,MixColumns Transformation,(0287),(036E),46,A6=47,0287=(0000 1110), (0001 1011)=(0001 0101),036E=6E,02 6E=(0110 1110), (1101 1100) = (1011 0010),0001 0101, 1011 0010, 0100 0110,1010 0110 = 0100 0111 = 47,31,轮密钥加（Add Round Key),一个简单地按位异或的操作,32,AES的密钥调度,长度选择,所有轮密钥比特的总数等于分组长度乘(轮数加1)。（如128比特的分组长度和10轮迭代，共需要1408比特的密钥）。,密钥扩展,将密码密钥扩展成一个扩展密钥。,轮密钥选取,轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始N,b,个字组成，第二个轮密钥由接下来的N,b,个字组成，如此继续下去。,33,AES Key Expansion,g function,One-byte circular left shift on a word.,A byte substitution using S-box,XOR with a round constant, Rconj, in which the three rightmost bytes are always 0, the left byte is define in the next page.,34,AES Key Expansion Example,Round constants,RCj=2,RCj-1, where multiplication is define over GF(2,8,),Round 8 example,EA D2 73 21,B5 8D BA D2 31 2B F5 60,7F 8D 29 2F,Calculate the round key for round 9,j,1,2,3,4,5,6,7,8,9,10,RCj,01,02,04,08,10,20,40,80,1B,36,i,temp,After,RotWord,After,SubByte,Rcon,(9),After,XOR,wi-4,XOR,temp,36,7F8D292F,8D292F7F,5DA515D2,1B000000,46A515D2,EAD27321,AC7766F3,35,Rijndael算法的抵抗攻击能力,消除了DES中出现的弱密钥的可能,也消除了IDEA中发现的弱密钥,能有效抵抗目前已知的攻击算法,线性攻击,差分攻击,36,先进对称分组加密算法的特点,可变的密钥长度: RC5,混合的运算 IDEA,数据相关的圈数 RC5,密钥相关的圈数 CAST-128,密钥相关的S盒: Blowfish,冗长密钥调度算法： Blowfish,可变的F：CAST-128,可变长明文/密文块长度,可变圈数,每圈操作作用于全部数据,37,12.3 HMAC,由密码散列函数导出MAC,目的：,密码散列函数（如SHA-1）比加密算法（如DES）执行速度快。,容易获得密码散列函数的库代码,美国对散列函数没有限制，而对加密算法则有严格限制。,38,HMAC-设计目标,使用现成的散列函数,容易替换为更安全的散列函数,保持散列函数的原有性能,使用和处理密钥的方式简单,对鉴别机制有一个易懂的密码分析。,39,HMAC-结构,b,-一个分组位数,n,-散列码长度,K-密钥,K,+,-左边填0，总长为,b,。,ipad-将00110110重复,b,/8次。,opad-将01011010重复,b,/8次。,H-嵌入的散列函数,Y,i,-报文的第i个分组,L,-报文的分组个数,40,第15章 电子邮件的安全性,15.1 PGP,15.2 S/MIME,41,互联网上电子邮件传递简图,用户代理: UNIX MH, Berkeley Mail, Elm和Mush,报文传输代理(MTA):UNIX sendmail,RFC 821定义了SMTP协议,RFC 822定义了在两个MTA之间采用RFC821标准传输的函件报文格式,终端用户,终端用户,用户代理,用户代理,待发函件队列,报文传输代理,客户,报文传输代理,用户邮箱,发送者,接收者,TCP连接,TCP端口号25,服务器,42,安全电子邮件,E-mail,是Internet上最大的应用,也是唯一的广泛跨平台、跨体系结构的分布式应用。,安全的电子邮件主要是解决身份鉴别和保密性的安全问题。涉及到的问题：,安全算法的选择,系统邮件的信息格式,如何实现认证和信任管理,邮件服务器的可靠性,应用实际例子：PGP、S/MIME、PEM、MOSS,43,15.1 PGP,PGP - Pretty Good Privacy,作者：Phil Zimmermann,提供可用于电子邮件和文件存储应用的保密与鉴别服务。,44,PGP发展特点,选择最好的可用加密算法作为系统的构造模块,将这些算法集成到一个通用的应用程序中，该程序独立于操作系统和处理器，并且基于一个使用方便的小命令集。,设计了程序、文档，并在,Internet,上公开。,一个商业公司（,Network Associates),提供全兼容、低成本的商业版本。,45,PGP广泛应用的原因,免费、可用于多平台。DOS/Windows、Unix、Macintosh,选用算法的生命力和安全性公众认可,具有广泛的可用性,不由政府或标准化组织控制,46,PGP安全业务,数字签名,DSS/SHA或RSA/SHA,SHA-散列函数，RSA/DSS-数字签名算法,完整性：,RSA、MD5,消息加密,CAST-128或IDEA或3DES，用会话密钥进行加密,Diffie-Hellman的变种(ElGamal),或RSA来加密会话密钥,47,PGP安全业务,数据压缩,ZIP,用于存储和传输,邮件兼容,Radix 64,将邮件转换成ASCII字符串,数据分段,报文的分段和重新装配,48,PGP,49,PGP记号说明,Ks: session key,KRa: 用户A的私钥,KUa: 用户A的公钥,EP: 公钥加密,DP: 公钥解密,EC: 常规加密,DC: 常规加密,H:,散列函数,|: 连接,Z: 用ZIP算法数据压缩,R64: 用radix64转换到ASCII格式,50,PGP,:身份鉴别,发送方,产生消息M,用SHA-1对M生成一个160位的散列码H,用发送者的私钥对H加密，并与M连接,接收方,用发送者的公钥解密并恢复散列码H,对消息M生成一个新的散列码，与H比较。如果一致，则消息M被鉴别。,51,PGP,:身份鉴别,说明：,1. RSA的强度保证了发送方的身份,2. SHA-1的强度保证了签名的有效性,3. DSS/SHA-1,可选替代方案。,签名与消息可以分离,对消息进行单独的日志记录,可执行程序的签名记录，检查病毒,文档多方签名，可以避免嵌套签名,52,PGP,:,保密性,发送方,生成消息,M,并为该消息生成一个随机数作为会话密钥。,用会话密钥加密,M,用接收者的公钥加密会话密钥并与消息,M,结合,接收方,用自己的私钥解密恢复会话密钥,用会话密钥解密恢复消息,M,53,PGP,:保密性,采用,CAST-128(,或,IDEA,或,3DES),、,64,位,CFB,方式。,一次性密钥，单向分发，公钥算法保护。,对称加密算法和公钥加密算法的结合可以缩短加密时间,用公钥算法解决了会话密钥的分配问题,不需要专门的会话密钥交换协议,由于邮件系统的存储,-,转发的特性，用握手方式交换密钥不太可能,每个消息都有自己的一次性密钥，进一步增强了保密强度。所以，每个密钥只加密很小部分的明文内容,公开密钥算法的长度决定安全性,RSA,（,7683072,）、,DSS,（,1024,）,54,数据压缩,压缩的位置：发生在签名后、加密前。,压缩之前生成签名：,（1）验证时无须压缩,（2）压缩算法的多样性,在加密前压缩：,压缩的报文更难分析,对邮件传输或存储都有节省空间的好处。,55,LZ77的压缩过程,56,E-mail兼容性,加密后是任意的8位字节，需要转换到ASCII格式。,Radix64,将3字节输入转换到4个ASCII字符，并带CRC校验。,长度扩大33%,与压缩综合后，长度为：,1.33x0.5xM = 0.665xM,57,Radix-64变换,58,分段与重组,Email常常受限制于最大消息长度（一般限制在最大50000字节）,更长的消息要进行分段，每一段分别邮寄。,PGP自动分段并在接收时自动恢复。,签名只需一次，在第一段中。,59,PGP报文的传输和接收,60,加密密钥和密钥环,PGP,使用四种类型的密钥：一次性会话常规密钥，公钥，私钥，基于口令短语的常规密钥。,需求：,1、需要一种生成不可预知的会话密钥的手段,2、需要某种手段来标识具体的密钥,一个用户拥有多个公钥/私钥对。（更换，分组）,3、每个PGP实体需要维护一个文件保存其公钥私钥对，和一个文件保存通信对方的公钥。,61,会话密钥的生成,以CAST-128为例。,128位的随机数是由CAST-128自己生成的。输入包括一个128位的密钥和两个64位的数据块作为加密的输入。使用CFB方式，CAST-128产生两个64位的加密数据块，这两个数据块的结合构成128位的会话密钥。（算法基于ANSI X12.17）,作为明文输入的两个64位数据块，是从一个128位的随机数流中导出的。这些数是基于用户的键盘输入的。键盘输入时间和内容用来产生随机流。因此，如果用户以他通常的步调敲击任意键，将会产生合理的随机性。,62,密钥标识符,一个用户有多个公钥/私钥对时，接收者如何知道发送者是用了哪个公钥来加密会话密钥？,将公钥与消息一起传送。,将一个标识符与一个公钥关联。对一个用户来说做到一一对应。,定义Key ID 包括64个有效位：(KUa mod 2,64,),Key ID,同样也需要PGP数字签名。,63,发送消息的格式,一个消息包含三部分成员：,报文message component,签名signature (optional),会话密钥session key component (optional),64,PGP,消息的一般,格式（A to B),65,密钥环,我们已经看到Key ID对于PGP是如何关键。,两个key ID包含在任何PGP消息中，提供保密与鉴别功能。,需要一种系统化的方法存储和组织这些key以保证使用。,PGP在每一个节点上提供一对数据结构：,存储该节点拥有的公钥/私钥对；（私钥环）,存储本节点知道的其他用户的公钥；（公钥环）,66,67,私钥环说明,User ID：通常是用户的邮件地址。也可以是一个名字，或重用一个名字多次。,Private Key：使用CAST-128(或IDEA或3DES)加密过程如下：,用户选择一个口令短语用于加密私钥；,当系统用RSA生成一个新的公钥/私钥对时，要求用户输入口令短语。对该短语使用SHA-1生成一个160位的散列码后，销毁该短语。,系统用其中128位作为密钥用CAST-128加密私钥，然后销毁这个散列码，并将加密后的私钥存储到私钥环中。,当用户要访问私钥环中的私钥时，必须提供口令短语。PGP将检索出加密的私钥，生成散列码，解密私钥。,68,公钥环说明,User ID：公钥的拥有者。多个User ID可以对应一个公钥。,公钥环可以用User ID或Key ID索引。,69,PGP报文的生成,70,PGP报文的生成,签名：,从私钥环中得到私钥，利用use rid作为索引,PGP提示输入口令短语，恢复私钥,构造签名部分,加密：,PGP产生一个会话密钥，并加密消息,PGP用接收者user id从公钥环中获取其公钥,构造消息的会话密钥部分,71,PGP报文的接收,72,PGP,:接收方处理消息的过程,解密消息,PGP用消息的会话密钥部分中的Key ID作为索引，从私钥环中获取私钥,PGP提示输入口令短语，恢复私钥,PGP恢复会话密钥，并解密消息,验证消息,PGP用消息的签名部分中的Key ID作为索引，从公钥环中获取发送者的公钥,PGP恢复被传输过来的消息摘要,PGP对于接收到的消息作摘要，并与上一步的结果作比较,73,公钥管理问题,由于PGP重在广泛地在正式或非正式环境下应用，没有建立严格的公钥管理模式。,如果A的公钥环上有一个从BBS上获得B发布的公钥，但已被C替换，这是就存在两条通道。C可以向A发信并冒充B的签名，A以为是来自B；A与B的任何加密消息C都可以读取。,为了防止A的公钥环上包含错误的公钥，有若干种方法可用于降低这种风险。,74,公钥管理问题,1、物理上得到B的公钥。,2、通过电话验证公钥。,B将其公钥email给A，A可以用PGP对该公钥生成一个160位的SHA-1摘要，并以16进制显示。这一特点称作密钥的“指纹”。然后A打电话给B，让B在电话中对证“指纹”。如果双方一致，则该公钥被认可。,3、从双方都信任的个体D处获得B的公钥。,D是介绍人，生成一个签名的证书。其中包含B的公钥，密钥生成时间。D对该证书生成一个SHA-1摘要，用其私钥加密这个摘要，并将其附加在证书后。因为只有D能够产生这个签名，没有人可以生成一个错误的公钥并假装是D签名的。这个签名的证书可以由B或D直接发给A，也可以贴到公告牌上。,4、从一个信任的CA中心得到B的公钥。,75,公钥的作废,密钥暴露或定时更新导致需要公钥报废功能,通常的报废方法是由主人签发一个密钥报废证书。这个证书具有与通常签名证书相同的形式，但包含一个指示符表明这个证书是要作废该公钥的使用。注意到必须使用所对应的私钥来签名一个密钥报废证书，其主人应尽可能越广越快散布这个证书，以使得潜在的有关人员更新他们的公钥环。,注意：对手也可以发出这个证书，然而，这将导致他自己也被否决。因此，这样比起恶意使用偷来的私钥来看似乎会减少漏洞。,76,10.2 Diffie-Hellman算法,实际上并非是数据加密算法，而是密钥,交换,算法。,有效性依赖于计算离散对数的难度,如果,q,是一个素数，,a,是,q,的一个原根，那么：,a,mod,q,，,a,2,mod,q,，,a,p-1,mod,q,是各不相同的整数并且以某种排列方式组成了从1到,q,-1的所有整数,77,Diffie-Hellman算法,1A和B选择一个素数,q,和一个整数,，其中,是,q,的一个原根，,q,和,可公开。,2用户A选择一个随机数,X,a,(保密)，计算公开密钥,Y,a,=,Xa,mod,q,，将,Y,a,发送给B。,3用户B选择一个随机数,X,b,(保密)，计算公开密钥,Y,b,=,Xb,mod,q,，将,Y,b,发送给A。,4用户A计算会话密钥K=(,Y,b,),Xa,mod,q,。用户B计算会话密钥K=(,Y,a,),Xb,mod,q,。,78,Diffie-Hellman密钥交换,79,Diffie-Hellman算法-安全性,由于,X,a,和,X,b,是保密的,在密钥交换过程中第三方可用的材料为：,q、Y,a,和,Y,b,，,破解者必须计算离散对数来确定密钥，即从,Y,b,来推导出,X,b,。,虽然计算一个整数的指数模相对容易，但计算离散对数却很困难。,80,