《网络安全ii密码学基础》由会员分享，可在线阅读，更多相关《网络安全ii密码学基础（50页珍藏版）》请在金锄头文库上搜索。
1、第18章 网络安全II密码学基础-2,公钥密码体系 (public key cryptography) 公钥密码算法 RSA算法 其它公钥密码算法 报文认证和散列算法 数字签名,传统密码体系的两个难题,密钥分发问题 密钥的安全分发一直是传统密码体系的难题。一个普遍接受的方法是：A、B双方通过与第三方的加密通道传递，第三方可信吗？如果，密码算法再强又有什么意义！ 数字签名 密码学要在信息技术产业、网络安全上获得广泛应用，必须要具有数字签名的手段。,公钥密码体系,Diffie 和Hellman1976年发表“密码学的新方向”，提出公钥密码体系，是密码学的重大革命。 每个通信方都有一对密钥，一个公开
2、，称公钥(public key)，另一个保密，称私钥(private key), 它们数学上相关，但由公钥无法推知私钥。 公钥算法基于数学函数而不是替代和置换。 公钥密码体系又称非对称密钥密码体系，它使用两个密钥，这对于保密通信、密钥分配、身份认证等都有深远影响。,公钥密码体系(续),传输密文,明文,明文,加密算法,解密算法,张三的公钥,公钥密码系统模型加密,加密变换,解密变换,张三的私钥,公钥密码体系(续),特性： 两个相关密钥中任一个都可以用于加密，而用另一个解密。 知道加密算法和加密密钥，要确定解密密钥在计算上是不可能的。 应用： 加密：发送方用接收方的公钥加密消息传送。 数字签名：发送
3、者用自己的私钥加密消息传送。 交换传统密码的对称密钥。.,公钥密码体系(续),对于公钥密码常见的误解： 公钥密码在防范密码分析上比传统密码更安全。 实际上，任何密码的安全性都依赖于密钥长度和破译密码的计算工作量，在抗击密码分析上那个都不比对方更优越。 公钥密码技术使传统密码已过时。 由于公钥加密算法的速度很慢，两者各有所用。 与传统密码密钥分发相比公钥分发就非常简单。 实际上，这个过程既不更简单，也不更有效。,RSA算法概述,麻省理工学院的 Rivest，Shamir 和 Adleman 在1977年研制，1978年发表的 RSA 是最著名、最广泛采用的公钥密码算法。 RSA是第一个较完善的公
4、钥密码算法，它既能用于加密，也能用于数字签名。 在已提出的公钥密码算法中，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) 计算
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=
6、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
7、 = 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，素数必
8、须从足够大的集合中选取，p 和 q 必须是大素数。 还没有产生任意大素数的有用技术。通常的过程是随机选取一个所需数量级的奇数，并检验它是否素数。若不是，选取后续的随机数。,RSA的速度,已经制造出许多实现RSA加密的芯片。 硬件实现时，RSA大约比DES慢1000倍。 软件实现时，RSA大约比DES慢100倍。 这些数字会随技术发展而变化。 但RSA的速度将永远不会达到对称密钥密码算法的速度。 公钥密码和对称密钥密码各有所长，各有所用。,RSA的安全性,如果能从 n 分解出 p 和 q，就可以计算(n)，然后从 ed = 1 (mod (n) 就可以确定 d。因子分解攻击 是对 RSA 最显而
9、易见的攻击方法。 RSA 的安全性取决于对一个大数做因子分解的难度。但从数学上从未证明过需要分解 n 才能从密文 C 和公钥 e 计算出明文 M。 大数的因子分解是一个难题。但现在不像以前那么难.。1977年RSA的三位发明者在印 一密码，悬赏100美元破译，公钥是129位十进制数。1994年4月一个通过Internet合作小组8个月后破译。.,其它公钥密码算法,安全使用 RSA 所要求的密钥长度近年已增加到1024位, 这对使用 RSA 的应用增加了处理开销。 1985年N.Koblitz和Miller提出将椭圆曲线用于密码算法， 椭圆曲线密码系统 ECC (Elliptic Curve C
10、ryptography)的前景看好。 ECC 的主要优点是它似乎用位数少得多的密钥(160)取得和 RSA(1024) 相等的安全性，因此减少了处理开销，加密系统运算更快。 ECC 比 RSA 等算法都难于解释。,报文认证和散列算法,报文认证和报文认证码MAC (Message Authentication Code) (单向)散列函数 散列(hash)算法 HMAC,报文认证和报文认证码MAC,报文认证：证实收到的报文来自可信的源，且未被篡改。 报文认证码 MAC：使用密钥从报文产生一个短小的定长数据块，即所谓报文认证码 MAC，并将它附在报文中。 散列(hash)函数：将一个任意长的报文
11、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 collisi
12、on resistance)。,(单向)散列函数(续),性质2，3是单向性的重要特征。 性质5保证 H(x)能充分地代表 x，x 的微小变化都将导致 H(x)的变化。无法找到一个替代报文，其散列值与给定报文的散列值相同，防止伪造。 报文 M 用散列函数 H 计算出报文摘要 H(M) 后，再用私钥对这个短数据(128位512位)加密，这也是数字签名技术的实质。,(单向)散列函数(续),设计一个接收任意长度输入的函数不是容易的事，更不用说还要单向。 实际中，将任意长度报文分成定长报文块处理。 单向散列函数是建立在压缩函数的想法上。 压缩函数 f 的输入是报文块 Mi 和前一块的输出。hi = f
13、(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
14、 (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。 步
15、骤(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
16、 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,
