网络安全II密码学基础.ppt

第18章 网络安全II密码学基础-2,公钥密码体系 (public key cryptography) 公钥密码算法 RSA算法 其它公钥密码算法 报文认证和散列算法 数字签名,传统密码体系的两个难题,密钥分发问题 密钥的安全分发一直是传统密码体系的难题。一个普遍接受的方法是：A、B双方通过与第三方的加密通道传递，第三方可信吗？如果，密码算法再强又有什么意义！ 数字签名 密码学要在信息技术产业、网络安全上获得广泛应用，必须要具有数字签名的手段。,公钥密码体系,Diffie 和Hellman1976年发表“密码学的新方向”，提出公钥密码体系，是密码学的重大革命。 每个通信方都有一对密钥，一个公开，称公钥(public key)，另一个保密，称私钥(private key), 它们数学上相关，但由公钥无法推知私钥。 公钥算法基于数学函数而不是替代和置换。 公钥密码体系又称非对称密钥密码体系，它使用两个密钥，这对于保密通信、密钥分配、身份认证等都有深远影响。,公钥密码体系(续),传输密文,明文,明文,加密算法,解密算法,张三的公钥,公钥密码系统模型加密,加密变换,解密变换,张三的私钥,公钥密码体系(续),特性： 两个相关密钥中任一个都可以用于加密，而用另一个解密。 知道加密算法和加密密钥，要确定解密密钥在计算上是不可能的。 应用： 加密：发送方用接收方的公钥加密消息传送。 数字签名：发送者用自己的私钥加密消息传送。 交换传统密码的对称密钥。.,公钥密码体系(续),对于公钥密码常见的误解： 公钥密码在防范密码分析上比传统密码更安全。 实际上，任何密码的安全性都依赖于密钥长度和破译密码的计算工作量，在抗击密码分析上那个都不比对方更优越。 公钥密码技术使传统密码已过时。 由于公钥加密算法的速度很慢，两者各有所用。 与传统密码密钥分发相比公钥分发就非常简单。 实际上，这个过程既不更简单，也不更有效。,RSA算法概述,麻省理工学院的 Rivest，Shamir 和 Adleman 在1977年研制，1978年发表的 RSA 是最著名、最广泛采用的公钥密码算法。 RSA是第一个较完善的公钥密码算法，它既能用于加密，也能用于数字签名。 在已提出的公钥密码算法中，RSA是最容易理解和实现的，也是最流行的。 RSA已经受了多年深入的密码分析。密码分析者既不能证明、也不能否定RSA的安全性。这正好说明RSA有可信度。,RSA算法,密钥生成 (1) 选择大的素数 p, q； ( p, q 保密 ) (2) 计算 n = pq； ( n 公开) (3) 计算欧拉函数(pq) =(p)(q) = (p-1)(q-1) (根据Euler 函数定义,(n)是小于 n 且与 n 互素的正整数个数) (n)保密 ) (4) 选择 d(n), 满足 gcd(n), d)=1；(d保密) (5) 计算 e, 满足 ed=1 (mod (n)； (e公开) 公钥 = (e, n)，私钥 = (d, n)。,RSA算法(续),用公钥加密 明文：M n (如果 M 大，可分块处理) 密文：C = M e (mod n) 用私钥解密 密文：C 明文：M = C d (mod n),RSA算法例子,密钥生成： 选择两个素数 p = 47, q = 71。 计算 n = p q = 4771 = 3337。 计算(n) = (p-1) (q-1) = 3220。 选择一个d, d (n)且与(n)互素, 取d = 1019。 计算e, 使de =1 (mod 3220), e = 79。101979=80501=253220+1。 公开e 和 n，保密d, p, q。 加密：明文=688，密文=68879 (mod 3337) = 1570。,RSA算法例子(续),加密：明文 M = 688 232 687 966 668 3 首先将 M 分成小块，在本例中按三位数字分块就可。 第一块用公钥加密：68879 (mod 3337) = 1570。 对其余块进行同样运算，产生密文： C = 1570 2756 2091 2276 2423 158 解密：用私钥 1019 进行相同的指数运算。如 15701019 (mod 3337) = 688。.,RSA算法原理,RSA的加密和解密 密文：C = Me mod n 明文：M = Cd mod n = (Me)d mod n = Med mod n 公钥(e, n)，私钥(d, n)， ed = 1 (mod (n)。 需要关系： Med mod n = M mod n Euler 定理的推论：给定素数 p 和 q，整数 n 和 m，n = pq 且0mn，对任意整数 k，下式成立： mk(n)+1 = m mod n,RSA算法密钥的计算,密钥的计算： 确定两个大素数 p 和 q, 选择 d 或 e, 计算另一个。 记住：选择大的 d。. p 和 q 是保密的，但 n = pq 是公开的，为防止通过穷举攻击发现 p 和 q，素数必须从足够大的集合中选取，p 和 q 必须是大素数。 还没有产生任意大素数的有用技术。通常的过程是随机选取一个所需数量级的奇数，并检验它是否素数。若不是，选取后续的随机数。,RSA的速度,已经制造出许多实现RSA加密的芯片。 硬件实现时，RSA大约比DES慢1000倍。 软件实现时，RSA大约比DES慢100倍。 这些数字会随技术发展而变化。 但RSA的速度将永远不会达到对称密钥密码算法的速度。 公钥密码和对称密钥密码各有所长，各有所用。,RSA的安全性,如果能从 n 分解出 p 和 q，就可以计算(n)，然后从 ed = 1 (mod (n) 就可以确定 d。因子分解攻击 是对 RSA 最显而易见的攻击方法。 RSA 的安全性取决于对一个大数做因子分解的难度。但从数学上从未证明过需要分解 n 才能从密文 C 和公钥 e 计算出明文 M。 大数的因子分解是一个难题。但现在不像以前那么难.。1977年RSA的三位发明者在印 一密码，悬赏100美元破译，公钥是129位十进制数。1994年4月一个通过Internet合作小组8个月后破译。.,其它公钥密码算法,安全使用 RSA 所要求的密钥长度近年已增加到1024位, 这对使用 RSA 的应用增加了处理开销。 1985年N.Koblitz和Miller提出将椭圆曲线用于密码算法， 椭圆曲线密码系统 ECC (Elliptic Curve Cryptography)的前景看好。 ECC 的主要优点是它似乎用位数少得多的密钥(160)取得和 RSA(1024) 相等的安全性，因此减少了处理开销，加密系统运算更快。 ECC 比 RSA 等算法都难于解释。,报文认证和散列算法,报文认证和报文认证码MAC (Message Authentication Code) (单向)散列函数 散列(hash)算法 HMAC,报文认证和报文认证码MAC,报文认证：证实收到的报文来自可信的源，且未被篡改。 报文认证码 MAC：使用密钥从报文产生一个短小的定长数据块，即所谓报文认证码 MAC，并将它附在报文中。 散列(hash)函数：将一个任意长的报文 M 映射为 定长的散列值 H(M)，也称为报文摘要(message digest)。 散列与加密合并为一个整体函数，实际上就是一个MAC。,(单向)散列函数,为用于报文认证，散列函数 H 应该具备的性质： 1. 输入为任意长度报文，输出为固定长度散列值。 2. 任意给定 x，计算 H(x) 很容易。 3. 任意给定 H(x)，计算 x 很难，即单向性。 4. 对任何给定 x，寻找 y x 使 H(y) = H(x) 很难。称弱抗冲突(weak collision resistance)。 5. 寻找任何 (x，y) 对，使 H(x) = H(y) 很难。称强抗冲突(strong collision resistance)。,(单向)散列函数(续),性质2，3是单向性的重要特征。 性质5保证 H(x)能充分地代表 x，x 的微小变化都将导致 H(x)的变化。无法找到一个替代报文，其散列值与给定报文的散列值相同，防止伪造。 报文 M 用散列函数 H 计算出报文摘要 H(M) 后，再用私钥对这个短数据(128位512位)加密，这也是数字签名技术的实质。,(单向)散列函数(续),设计一个接收任意长度输入的函数不是容易的事，更不用说还要单向。 实际中，将任意长度报文分成定长报文块处理。 单向散列函数是建立在压缩函数的想法上。 压缩函数 f 的输入是报文块 Mi 和前一块的输出。hi = f (Mi, hi-1)。该散列值和下一报文块一起作为压缩函数的下一轮输入。最后一个报文块的散列就成为整个报文的散列。,散列函数的一般结构,f,f,f,Y0,Y1,YL-1,CV1,CVL-1,CVL,IV=CV0,n,n,n,n,n,b,b,b,IV = 初值 CV= 链接变量 Yi = 第 i 个输入块 f = 压缩算法,L = 输入的块数 n = 散列码长度 b = 输入块长,散列算法,大多数重要散列算法遵循以上结构。. 报文摘要算法 MD5 (Message Digest 5) MD5是麻省理工学院的 Ron Rivest 提出，被广泛使用。它产生128位散列值。 安全散列算法 SHA-1 (Secure Hash Algorithm-1) SHA是由美国国家标准和技术局NIST提出，1993年公布，1995年发布了修订版，称SHA-1。它产生160位散列值。,报文摘要算法MD5过程,报文,填充,长度值,Y0,HMD5,Y1,HMD5,IV,128,CV1,128,512位,512位,.,Yq,HMD5,CVq,128,512位,.,YL-1,HMD5,CVL-1,128,512位,摘要,128位,L512位,(1),(2),(3),(4),(5),报文摘要算法MD5过程(续),步骤(1)：填充报文到448 (mod 512)位，即512的整数倍减64位。填充位=1000。 步骤(2)：附加64位长度值。若原始报文长K位，则长度值=K mod 264。这两步产生L512位的扩展报文，表示成512位的块序列Y0, , YL-1。 步骤(3)：初始化缓存。使用一个128位的缓存存放散列函数的中间值CVq及最终结果，该缓存可表示为4个32位的寄存器(A, B, C, D)，它们的初值，即IV为：(十六进制表示)。,报文摘要算法MD5过程(续),A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 这些值的低位字节放在低地址字节上。存储为： 字A：01 23 45 67 字B：89 AB CD EF 字C：FE DC BA 98 字D：76 54 32 10 步骤(4)：处理512位(16字)的报文块序列Y0, , YL-1，算法的核心是模块HMD5。 步骤(5)：所有L个512位的报文块处理完成后，第L阶段产生的输出就是128位报文摘要。,MD5的压缩函数HMD5,HMD5是一个包含四轮的压缩函数。四轮有相似的结构，每一轮进行16步操作。但每轮使用不同的逻辑函数F, G, H, I 和表 T 不同的1/4部分。 表T通过正弦函数构建。Ti的值是232|sin(i)|的整数部分，i的单位是弧度。0 |sin(i)| 1，因此Ti均能用32位表示。表T提供了一个“随机化”的32位数集。 HMD5的每轮以Yq和缓存ABCD为输入，更新缓存内容。第四轮的缓存输出与第一轮的输入CVq的4个字分别以模232相加得CVq+1。,HMD5的处理过程,F, T116, Xi, 16个步骤,G, T1732, X2(i), 16个步骤,H, T3348, X3(i), 16个步骤,I, T4964, X4(i), 16个步骤,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,CVq,+,+,+,+,Yq,CVq+1,512位,HMD5中每轮的单步,HMD5中每轮由对缓存ABCD的16 步操作组成。每1步操作为： ( a + g(b, c, d) + Xk + Ti ) s ) + b，其中 a, b, c, d = 缓存ABCD中4个32位字 g = 逻辑函数F, G, H, I 之一(非线性) s = 32位数循环左移 s 位 Xk = 报文块Yq 的第 k 个字，k =0, , 15 Ti = 表 T 中第 i 个字 + = 模 232 加法,HMD5中每轮的单步(续),c,d,+,g,b,a,+,+, s,+,c,d,b,a,Xk,Ti,HMD5中每轮的单步(续),HMD5中每轮的单步(续),每轮使用四个逻辑函数中的一个。符号“”，“”，“”，“”分别表示“与”，“或”，“非”和“异或”，都是逐位的逻辑操作。 32位字的数组X015保存当前待处理的512位报文块的值。在一轮中的每一步，这16个字的每个只被使用一次；这些字的使用顺序在各轮中不同。第一轮中字按原顺序使用。以后各轮 k：2(i)=(1+5i) mod 16； 3(i)=(5+3i) mod 16； 4(i)=7i mod 16。 在第二轮中，Xk的使用顺序 k=1,6,11,0,5,。,HMD5中每轮的单步(续),在每一轮中的每一步，表 T 中64个32位字的每一个只被使用一次。 每轮中的单步轮流使用4个不同的循环左移量，且在各轮中使用的不同。 第一、二、三、四轮中使用的左移位数分别是： s = 7, 12, 17, 22，s = 5, 9, 14, 20， s = 4, 11, 16, 23，s = 6, 10, 15, 21。 所有这些复杂操作的意义在于使两个512位报文块产生相同输出非常困难。,MD5的安全性,对 MD5的攻击有针对单轮的，使用密码分析在合理的时间内找出能产生相同摘要的两个报文。 提出的攻击还有针对 MD5的压缩函数，即对单个512位输入块，寻找另一报文块产生相同的128位输出。 目前，似乎还没有提出对一个使用 MD5初值(IV) 的完整报文和包含四轮 MD5的攻击。但. 由于认为 MD5易受攻击，需要具有更长散列码和更能抵御已知密码分析攻击的散列函数。,其它散列算法SHA-1,安全散列算法 SHA 由 NIST 在1993年公布，在1995年发布了它的修订版，称为SHA-1。 SHA-1算法输入报文最大长度不超过264位，也按512位的块进行处理，输出160位报文摘要。 报文总体处理过程与MD5相似。缓存是5个32位寄存器ABCDE，算法核心是包含四轮的模块，每轮由20步组成。 SHA-1摘要160位，使用穷举攻击，产生一个报文使其摘要等于给定摘要，需2160数量级操作。对SHA-1还没有已知的密码分析攻击.。,HMAC,虽然可以利用对称块密码来构建报文认证码MAC，但近年的研究转向由散列码导出MAC。因为： 散列函数 (如MD5和SHA-1) 的软件执行速度比对称块密码 (如DES) 快。 容易获得散列函数的代码库。 美国或其它国家对散列函数没有出口限制，而对块密码，即便用作MAC也是限制的。 散列函数不能直接用于MAC，因它不包含密钥。将密钥与散列函数结合的最重要算法是HMAC。,HMAC算法,+,Si,Y0,Y1,YL-1,散列函数,K+,ipad,So,+,K+,opad,散列函数,. . .,IV(n位),b位,b位,b位,H(Si | M),b位,填充到 b 位,n位,n位,IV(n位),HMACK (M),HMAC算法(续),H = 嵌入的散列函数(如MD5，SHA-1等)。 M = HMAC输入报文(包括散列函数所需填充)。 Yi = M中第 i 块，0 i L-1。 L = M中的块数。 b = 一块的位数。 n = 散列函数产生的散列码长度。 K = 密钥；若密钥长度b, 输入散列函数产生 n 位的密钥；推荐密钥长度 n。 K+ = 在 K 的左边填充0，使总长度等于 b。,HMAC算法(续),ipad = 00110110 重复 b/8 次 opad = 01011010 重复 b/8 次 HMACK = H (K+ opad) | H (K+ ipad) | M 算法说明： 1. 对密钥 K的左端填充0，生成 b 位的串 K+ (例如，若 K的长度是160位, b=512, 则填充44个0字节)。 2. 将 K+与 ipad 按位异或，产生一个b 位块 Si 。 3. 将报文 M 附加到 Si 后。,HMAC算法(续),4. 使用 H 计算第3步产生的数据流的散列值。 5. 将 K+与 opad 按位异或，产生一个 b位块 So 。 6. 将第4步产生的散列值附加到 So 后。 7. 使用 H 计算第6步产生的数据流的散列值。 注意，与 ipad 异或的结果是使 K 中一半的位值反转。与 opad 异或的效果也一样，只是反转的位不同。从效果上看，Si 和So 通过散列函数中的压缩函数将从 K 产生两个伪随机密钥。,HMAC的安全性,HMAC将散列函数看作一个“黑盒”。 HMAC的安全性依赖于嵌入的散列函数的密码分析强度。 如果嵌入的散列函数已不够安全，可以简单地用更安全的散列函数来替换。 由于还有密钥K, HMAC采用MD5而不是SHA-1作为嵌入散列函数目前是完全可以接受的。,数字签名,数字签名对于报文的安全来说应该有三方面功能： 完整性：数字签名确保报文没有被篡改； 真实性：数字签名确保报文是由签名者所发出； 不可否认性：数字签名者对所发的报文不能否认。 利用公钥密码系统可以构造这样的数字签名。对于由A发出的报文 M，A可以用自己的私钥 DA加密该报文，记作MDA，这可以做数字签名。 问题?,数字签名(续),公钥算法加密一个大报文需要大量处理时间。 对数字签名的大部分应用，报文本身无需加密，只要确保报文的完整性、真实性、不可否认性。 散列函数将一个报文映射为一个短得多的、固定长度散列码，即“报文摘要”。 报文摘要RSA私钥加密可以达到数字签名目的。ISO9796是使用RSA的国际数字签名标准。 NIST在1991年公布数字签名标准 DSS，采用散列算法SHA和NSA研制的数字签名算法 DSA。,数字签名方案1散列+RSA,M,散列 函数,M,加密 RSA,散列 函数,解密 RSA,比较,私钥,公钥,数字签名标准DSS(散列+DSA),M,散列 函数,s,M,签名 算法,发方私钥,全局公钥,随机数k,r,散列 函数,签名 验证,发方公钥,全局公钥,比较,数字签名算法DSA,DSA是基于数学上计算离散对数的难度。 算法首先构造全局公钥(p, q, g)，它包括三个分量：160 位的素数 q