密码编码学与网络安全.ppt

名词解释 20 RSA算法（因素，因子）公钥，私钥的计算 20 AES分析，矩阵的变换 20 HMAC算法，结构，4种目标，实现，问答型，理解型 20 PGP（原理图）什么时候加密，怎么加密 20 密钥交换 理解原理，目的防止攻击，提出好方法？防范措施 20 流程图的解读 记号读懂 20,公钥加密的出现,1976年由Whitfield Diffie & Martin Hellman 在Stanford University所发明 加密密钥PK是公开的，称为公钥 解密密钥SK是保密的，称为私钥 公钥技术是二十世纪最伟大的思想之一 改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务,公钥编码模型-1,公钥编码模型-2,公钥加密的特点,公开密钥密码体制 能够有效计算公钥PK和私钥SK。 从已知的公钥PK不能推导出私钥SK。 发送方用公钥PK进行加密，而接收方用私钥SK进行解密,还原出明文，即： DSK(EPK(P) = P 两个密钥中的任何一个都能进行加密，而另一个则进行解密。,公钥算法应用：保密,公钥算法应用：鉴别,保密和鉴别,RSA,RSA方法由三位MIT科学家Rivest、Shamir和Adleman于1977年提出 最著名和使用最广泛的公钥加密方法 基于整数的有限幂次对素数的取模 使用大整数作为密钥 安全性依赖于大数的因子分解,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 。,RSA-加密与解密,1将明文划分为一个个数据块P，其中0Pn。 2C为P对应的密文。则： 加密： C= Pe (mod n) 解密： P= Cd (mod n),RSA-证明,解密： X = DSK(C) = Cd mod n = (Xe mod n)d mod n = Xed mod n 由于de 1 mod(n)，故 de = k(n) +1，则 Cd mod n = X k(n) +1 mod n = (X(n)k X mod n = X (根据欧拉定理的变化形式),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=Pe mod n = 65 mod 119 =41。 解密：P=Cd mod n = 4177 mod 119= 6。,RSA的计算技巧,模运算的性质计算Me mod n (a mod n) (b mod n) = (ab) mod n e= bkbk-1b0, 则e = 2i, 其中bi =1 Me = M2i =(Mbk)2 Mbk-1)2 Mbk-2)2 )2 Mbk)2 Mb1)2 Mb0 如：65 =6101=(6)2)2 . 6= 362 . 6 = 7776 . 6 = 46656 计算算法 d=1 For i=k to 0 do d=d2 mod n If bi=1 then d=(d*M) mod n,RSA的计算技巧,计算7560 mod 561 560=230h=0010 0011 0000b d=1, k=9, i=9, d=d2 mod 561=1, b9=1, d=(d*7) mod 561=7 i=8, d=d2 mod 561=49, b8=0 i=7, d=d2 mod 561=157, b7=0 i=6, d=d2 mod 561=526, b6=0 i=5, d=d2 mod 561=103, b5=1, d=(d*7) mod 561=160 i=4, d=d2 mod 561=355, b4=1, d=(d*7) mod 561=241 i=3, d=d2 mod 561=298, b3=0 i=2, d=d2 mod 561=166, b2=0 i=1, d=d2 mod 561=67, b1=0 i=0, d=d2 mod 561=1, b0=0,RSA-安全性,蛮力攻击 数学攻击 定时攻击,RSA-蛮力攻击,整数N的因子分解： 从2 开始试验每一个小于等于N 的素数 整数n的十进制位数 因子分解的运算次数 所需计算时间（次/微秒） 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年,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 具有相同大小且满足其他限制,RSA-定时攻击,mid-1990s 提出 利用运算过程中的时间变化 密钥中的0或1，时间不同 从化费时间推算出操作数的大小 对策 使用固定时间 随机延迟 运算盲化-取幂操作前将密文与一个随机数相乘,Summary,have considered: principles of public-key cryptography RSA algorithm, implementation, security,第5章 高级加密标准,5.1 AES评估准则 5.2 AES密码,Advance Encryption Standard,1997年NIST宣布征集AES算法。 与三重DES比，要快且至少一样安全； 分组128位，密钥128/192/256位； 设计简洁。 1998年确定第一轮15个候选者 1999年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofish。 2000年底Rijndael胜出。,Rijndael简介,加密、解密相似但不对称 不属于Feistel结构，属于重复结构 支持128/32=Nb数据块大小 支持128/192/256(/32=Nk)密钥长度 有较好的数学理论作为基础 结构简单、速度快,AES算法结构,AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层。 线性混合层：确保多轮之上的高度扩散。 非线性层：具有最优最差-情形非线性的S-盒的并行应用 密钥加层：轮密钥简单地异或到中间状态上。,AES算法结构,Ecryption Decryption,状态、密钥的表示,状态/密钥的矩阵表示 State Key,字节代替(Substitute Bytes )变换,字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个1616的矩阵。,example,行移位(Shift Row)变换,列混合Mix Column变换,代替操作，将状态的列看作有限域GF（28）上的4维向量并被有限域GF（28）上的一个固定可逆方阵A乘,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,轮密钥加（Add Round Key),一个简单地按位异或的操作,AES的密钥调度,长度选择 所有轮密钥比特的总数等于分组长度乘(轮数加1)。（如128比特的分组长度和10轮迭代，共需要1408比特的密钥）。 密钥扩展 将密码密钥扩展成一个扩展密钥。 轮密钥选取 轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始Nb个字组成，第二个轮密钥由接下来的Nb个字组成，如此继续下去。,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.,AES Key Expansion Example,Round constants RCj=2RCj-1, where multiplication is define over GF(28) 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,Rijndael算法的抵抗攻击能力,消除了DES中出现的弱密钥的可能 也消除了IDEA中发现的弱密钥 能有效抵抗目前已知的攻击算法 线性攻击 差分攻击,先进对称分组加密算法的特点,可变的密钥长度: RC5 混合的运算 IDEA 数据相关的圈数 RC5 密钥相关的圈数 CAST-128 密钥相关的S盒: Blowfish 冗长密钥调度算法： Blowfish 可变的F：CAST-128 可变长明文/密文块长度 可变圈数 每圈操作作用于全部数据,12.3 HMAC,由密码散列函数导出MAC 目的： 密码散列函数（如SHA-1）比加密算法（如DES）执行速度快。 容易获得密码散列函数的库代码 美国对散列函数没有限制，而对加密算法则有严格限制。,HMAC-设计目标,使用现成的散列函数 容易替换为更安全的散列函数 保持散列函数的原有性能 使用和处理密钥的方式简单 对鉴别机制有一个易懂的密码分析。,HMAC-结构,b-一个分组位数 n-散列码长度 K-密钥 K+-左边填0，总长为b。 ipad-将00110110重复b/8次。 opad-将01011010重复b/8次。 H-嵌入的散列函数 Yi-报文的第i个分组 L-报文的分组个数,第15章 电子邮件的安全性,15.1 PGP 15.2 S/MIME,互联网上电子邮件传递简图,用户代理: UNIX MH, Berkeley Mail, Elm和Mush 报文传输代理(MTA):UNIX sendmail RFC 821定义了SMTP协议 RFC 822定义了在两个MTA之间采用RFC821标准传输的函件报文格式,服务器,安全电子邮件,E-mail 是Internet上最大的应用,也是唯一的广泛跨平台、跨体系结构的分布式应用。 安全的电子邮件主要是解决身份鉴别和保密性的安全问题。涉及到的问题： 安全算法的选择 系统邮件的信息格式 如何实现认证和信任管理 邮件服务器的可靠性 应用实际例子：PGP、S/MIME、PEM、MOSS,15.1 PGP,PGP - Pretty Good Privacy 作者：Phil Zimmermann 提供可用于电子邮件和文件存储应用的保密与鉴别服务。,PGP发展特点,选择最好的可用加密算法作为系统的构造模块 将这些算法集成到一个通用的应用程序中，该程序独立于操作系统和处理器，并且基于一个使用方便的小命令集。 设计了程序、文档，并在Internet上公开。 一个商业公司（Network Associates)提供全兼容、低成本的商业版本。,PGP广泛应用的原因,免费、可用于多平台。DOS/Windows、Unix、Macintosh 选用算法的生命力和安全性公众认可 具有广泛的可用性 不由政府或标准化组织控制,PGP安全业务,数字签名 DSS/SHA或RSA/SHA SHA-散列函数，RSA/DSS-数字签名算法 完整性： RSA、MD5 消息加密 CAST-128或IDEA或3DES，用会话密钥进行加密 Diffie-Hellman的变种(ElGamal)或RSA来加密会话密钥,PGP安全业务,数据压缩 ZIP 用于存储和传输 邮件兼容 Radix 64 将邮件转换成ASCII字符串 数据分段 报文的分段和重新装配,PGP,PGP记号说明,Ks : session key KRa: 用户A的私钥 KUa: 用户A的公钥 EP : 公钥加密 DP : 公钥解密 EC : 常规加密 DC : 常规加密 H : 散列函数 | : 连接 Z : 用ZIP算法数据压缩 R64: 用radix64转换到ASCII格式,PGP :身份鉴别,发送方 产生消息M 用SHA-1对M生成一个160位的散列码H 用发送者的私钥对H加密，并与M连接 接收方 用发送者的公钥解密并恢复散列码H 对消息M生成一个新的散列码，与H比较。如果一致，则消息M被鉴别。,PGP :身份鉴别,说明： 1. RSA的强度保证了发送方的身份 2. SHA-1的强度保证了签名的有效性 3. DSS/SHA-1可选替代方案。 签名与消息可以分离 对消息进行单独的日志记录 可执行程序的签名记录，检查病毒 文档多方签名，可以避免嵌套签名,PGP :保密性,发送方 生成消息M并为该消息生成一个随机数作为会话密钥。 用会话密钥加密M 用接收者的公钥加密会话密钥并与消息M结合 接收方 用自己的私钥解密恢复会话密钥 用会话密钥解密恢复消息M,PGP :保密性,采用CAST-128(或IDEA或3DES)、64位CFB方式。 一次性密钥，单向分发，公钥算法保护。 对称加密算法和公钥加密算法的结合可以缩短加密时间 用公钥算法解决了会话密钥的分配问题 不需要专门的会话密钥交换协议 由于邮件系统的存储-转发的特性，用握手方式交换密钥不太可能 每个消息都有自己的一次性密钥，进一步增强了保密强度。所以，每个密钥只加密很小部分的明文内容 公开密钥算法的长度决定安全性RSA（7683072）、DSS（1024）,数据压缩,压缩的位置：发生在签名后、加密前。 压缩之前生成签名： （1）验证时无须压缩 （2）压缩算法的多样性 在加密前压缩： 压缩的报文更难分析 对邮件传输或存储都有节省空间的好处。,LZ77的压缩过程,E-mail兼容性,加密后是任意的8位字节，需要转换到ASCII格式。 Radix64将3字节输入转换到4个ASCII字符，并带CRC校验。 长度扩大33% 与压缩综合后，长度为： 1.33x0.5xM = 0.665xM,Radix-64变换,分段与重组,Email常常受限制于最大消息长度（一般限制在最大50000字节） 更长的消息要进行分段，每一段分别邮寄。 PGP自动分段并在接收时自动恢复。 签名只需一次，在第一段中。,PGP报文的传输和接收,加密密钥和密钥环,PGP使用四种类型的密钥：一次性会话常规密钥，公钥，私钥，基于口令短语的常规密钥。 需求： 1、需要一种生成不可预知的会话密钥的手段 2、需要某种手段来标识具体的密钥 一个用户拥有多个公钥/私钥对。（更换，分组） 3、每个PGP实体需要维护一个文件保存其公钥私钥对，和一个文件保存通信对方的公钥。,会话密钥的生成,以CAST-128为例。 128位的随机数是由CAST-128自己生成的。输入包括一个128位的密钥和两个64位的数据块作为加密的输入。使用CFB方式，CAST-128产生两个64位的加密数据块，这两个数据块的结合构成128位的会话密钥。（算法基于ANSI X12.17） 作为明文输入的两个64位数据块，是从一个128位的随机数流中导出的。这些数是基于用户的键盘输入的。键盘输入时间和内容用来产生随机流。因此，如果用户以他通常的步调敲击任意键，将会产生合理的随机性。,密钥标识符,一个用户有多个公钥/私钥对时，接收者如何知道发送者是用了哪个公钥来加密会话密钥？ 将公钥与消息一起传送。 将一个标识符与一个公钥关联。对一个用户来说做到一一对应。 定义Key ID 包括64个有效位：(KUa mod 264) Key ID同样也需要PGP数字签名。,发送消息的格式,一个消息包含三部分成员： 报文message component 签名signature (optional) 会话密钥session key component (optional),PGP消息的一般 格式（A to B),密钥环,我们已经看到Key ID对于PGP是如何关键。 两个key ID包含在任何PGP消息中，提供保密与鉴别功能。 需要一种系统化的方法存储和组织这些key以保证使用。 PGP在每一个节点上提供一对数据结构： 存储该节点拥有的公钥/私钥对； （私钥环） 存储本节点知道的其他用户的公钥；（公钥环）,私钥环说明,User ID：通常是用户的邮件地址。也可以是一个名字，或重用一个名字多次。 Private Key：使用CAST-128(或IDEA或3DES)加密过程如下： 用户选择一个口令短语用于加密私钥； 当系统用RSA生成一个新的公钥/私钥对时，要求用户输入口令短语。对该短语使用SHA-1生成一个160位的散列码后，销毁该短语。 系统用其中128位作为密钥用CAST-128加密私钥，然后销毁这个散列码，并将加密后的私钥存储到私钥环中。 当用户要访问私钥环中的私钥时，必须提供口令短语。PGP将检索出加密的私钥，生成散列码，解密私钥。,公钥环说明,User ID：公钥的拥有者。多个User ID可以对应一个公钥。 公钥环可以用User ID或Key ID索引。,PGP报文的生成,PGP报文的生成,签名： 从私钥环中得到私钥，利用use rid作为索引 PGP提示输入口令短语，恢复私钥 构造签名部分 加密： PGP产生一个会话密钥，并加密消息 PGP用接收者user id从公钥环中获取其公钥 构造消息的会话密钥部分,PGP报文的接收,PGP :接收方处理消息的过程,解密消息 PGP用消息的会话密钥部分中的Key ID作为索引，从私钥环中获取私钥 PGP提示输入口令短语，恢复私钥 PGP恢复会话密钥，并解密消息 验证消息 PGP用消息的签名部分中的Key ID作为索引，从公钥环中获取发送者的公钥 PGP恢复被传输过来的消息摘要 PGP对于接收到的消息作摘要，并与上一步的结果作比较,公钥管理问题,由于PGP重在广泛地在正式或非正式环境下应用，没有建立严格的公钥管理模式。 如果A的公钥环上有一个从BBS上获得B发布的公钥，但已被C替换，这是就存在两条通道。C可以向A发信并冒充B的签名，A以为是来自B；A与B的任何加密消息C都可以读取。 为了防止A的公钥环上包含错误的公钥，有若干种方法可用于降低这种风险。,公钥管理问题,1、物理上得到B的公钥。 2、通过电话验证公钥。 B将其公钥email给A，A可以用PGP对该公钥生成一个160位的SHA-1摘要，并以16进制显示。这一特点称作密钥的“指纹”。然后A打电