1、1协商大素数p，本原根g选择随机数XA、XB计算YA=gXA，YB=gXB (mod p)Alice计算K= (YB ) XA(mod p); Bob计算K = (YA ) XB(mod p), K = K =g XA XB(mod p)协商大素数q，本原根选择随机数XAAlice计算YA= XA (mod q); PU= q, , YA SU= XAK = K =g XA XB(mod P)Bob随机选择k，K= YakC1= k, C2=KMAliceK=C1XAM=C2K-12pHash函数的应用p两个简单的Hash函数p需求和安全性p基于CBC的Hash函数p安全Hash算法(SHA)
2、pSHA-3Hash实例第三部分第三部分：数据完整性算法：数据完整性算法3Hash实例网络通信的攻击威胁网络通信的攻击威胁p 泄露泄露p 流量分析流量分析p 伪装伪装p 内容篡改内容篡改p 顺序修改顺序修改p 时间修改时间修改p 发送方发送方否认否认p 接收接收方否认方否认消息认证数字签名不属于机密性范畴,属于数据完整性范畴4Hash实例p散列函数散列函数（ Hash Functions)：一个散列函数以作为，并产生一个定长的散列码一个定长的散列码，有时也称消息摘要消息摘要，作为输出输出。p消息消息认证认证（Message Authentication)：是一个证实证实来自可信的源点来自可信的
3、源点且未被未被篡改篡改的过程。p数字签名数字签名（Digital Signature）是一种防止防止或抵赖抵赖的鉴别技术。5Hash实例p散列函数散列函数（ Hash Functions)：一个散列函数以作为，并产生一个定长的散列码一个定长的散列码，有时也称消息摘要消息摘要，作为输出输出。单向性：单向性：对于预先指定的Hash值，找到对应的数据块在计算上不可行抗碰撞性：抗碰撞性：找到两个不同数据块，对应相同的Hash值在计算上不可行6Hash实例p 消息消息认证认证（Message Authentication)：是一个证实证实来自可信的源点来自可信的源点且未被篡改未被篡改的过程。p 实现方式
4、：发送者根据待发送消息产生一组Hash值，将消息与Hash值一同发送；接收者作同样算法验证结果是否一致。消息认证消息认证HashHash的应用：的应用：7Hash实例p 实现方式：发送者根据待发送消息产生一组Hash值，将消息与Hash值一同发送；接收者作同样算法验证结果是否一致。消息认证消息认证HashHash的应用：的应用：中间人攻击加密4种方案啊8Hash实例方案方案(a)消息认证消息认证HashHash的应用：的应用：kAB :EMH (M ) 提 供 鉴 别 加 密 保 护 H ( M ) 提 供 保 密 仅 A 和 B 共 享 密 钥 k 回顾：流密码、一次一密的篡改攻击9Hash
5、实例方案方案(b)消息认证消息认证HashHash的应用：的应用：用于无须保密性的应用10Hash实例方案方案(c)消息认证消息认证HashHash的应用：的应用：不需要加密算法11Hash实例方案方案(d)消息认证消息认证HashHash的应用：的应用：不需要加密算法12Hash实例消息认证消息认证HashHash的应用：的应用：13Hash实例消息认证消息认证HashHash的应用：的应用：密钥Hash消息认证码(MAC)消息认证的过程：消息认证的过程：1. 将密钥与消息快一同输入将密钥与消息快一同输入Hash函数，得到函数，得到MAC2. 将将MAC与消息一同发送或存储与消息一同发送或存
6、储3. 需要需要验证时重新计算验证时重新计算MAC看是否一致看是否一致说明：说明： 攻击攻击者不知道密钥，篡改消息后无法生成者不知道密钥，篡改消息后无法生成新的新的MAC 由于有密钥才能生成由于有密钥才能生成MAC，验证方也就知道发送者是谁，验证方也就知道发送者是谁了了14Hash实例消息认证消息认证HashHash的应用：的应用：数字签名的操作与数字签名的操作与MAC类似：类似：1. 签名：使用用户私钥加密消息的签名：使用用户私钥加密消息的Hash值值2. 验证：任何知道该用户公钥的都可以进行验证验证：任何知道该用户公钥的都可以进行验证数字签名数字签名15Hash实例消息认证消息认证Hash
7、Hash的应用：的应用：数字签名的操作与数字签名的操作与MAC类似：类似：1. 签名：使用用户私钥加密消息的签名：使用用户私钥加密消息的Hash值值2. 验证：任何知道该用户公钥的都可以进行验证验证：任何知道该用户公钥的都可以进行验证数字签名数字签名16Hash实例消息认证消息认证HashHash的应用：的应用：数字签名数字签名17Hash实例消息认证消息认证HashHash的应用：的应用：1. 生成单向口令：生成单向口令：存储口令的Hash值而不是口令本身，即使被黑客访问口令文件，也不会泄露2. 入侵入侵检测和病毒检测：检测和病毒检测：将文件的Hash值存储在安全系统中，通过重新计算Hash
8、值判断文件是否被修改3. 构建伪随机函数或伪随机数发生器构建伪随机函数或伪随机数发生器4. 构建构建抗量子计算的公钥密码系统抗量子计算的公钥密码系统数字签名数字签名其他应用其他应用18Hash实例两个简单的两个简单的HashHash函数：函数：消息: 0 1 1 0, 0 1 0 0 0 0 1 1, 0 1 0 1Hash: 0 1 0 1, 0 0 0 1大多数文本文件最高位是0的概率大128位Hash有效性为2-11219Hash实例两个简单的两个简单的HashHash函数：函数：消息: 0 1 1 0, 0 1 0 0 0 0 1 1, 0 1 0 1改进：改进：1. Hash初始值为
9、初始值为02. 对每个对每个n位分组位分组 当前Hash循环左移一位 将该分组与移位后的Hash异或Hash1: 0 1 1 0, 0 1 0 0左移: 1 1 0 0, 1 0 0 02组消息: 0 0 1 1, 0 1 0 1Hash2: 1 1 1 1, 1 1 0 120Hash实例两个简单的两个简单的HashHash函数：函数：改进：改进：1.Hash初始值为初始值为02.对每个对每个n位分组位分组 当前Hash循环左移一位 将该分组与移位后的Hash异或p 若仅加密若仅加密Hash值值(图图11.3b和和11.4a)该方法无法保证数据完整性。该方法无法保证数据完整性。p 攻击者可以
10、选定某消息攻击者可以选定某消息然后在该消息后附加一个然后在该消息后附加一个n位分组位分组得到相同得到相同Hash值值p 即使即使CBC方式加密后方式加密后(11.3a的模式的模式)也不安也不安全全21Hash函数Hash实例碰撞对于h=H(x)，称x为h的原像。考虑b位消息M的n位Hash函数，平均每个Hash值都对应2b-n个原像。Hash函数的安全性要求函数的安全性要求1. 输入长度可变：H可用于任何尺寸的消息M2. 输出长度固定：产生固定长度的输出 h3. 效率：对任何消息x ,计算h=H(x)是容易的4. 抗原像攻击(单向性)：给定 h ，计算满足H(x)=h的x在计算上是不可行的5.
11、 抗第二原像攻击(抗弱碰撞性)：给定x，计算满足H(y)=H(x)的y在计算上是不可行的6. 抗(强)碰撞性：找到任何满足 H(y)=H(x)的偶对（ x,y ），在计算上是不可行的。 7. 伪随机性：H满足伪随机性测试标准22Hash函数Hash实例Hash函数的安全性要求函数的安全性要求1.输入长度可变：H可用于任何尺寸的消息M2.输出长度固定：产生固定长度的输出 h3.效率：对任何消息x ,计算h=H(x)是容易的4.抗原像攻击(单向性)：给定 h ，计算满足H(x)=h的x在计算上是不可行的5.抗第二原像攻击(抗弱碰撞性)：给定x，计算满足H(y)=H(x)的y在计算上是不可行的6.抗
12、(强)碰撞性：找到任何满足 H(y)=H(x)的偶对（ x,y ），在计算上是不可行的。 7.伪随机性：H满足伪随机性测试标准p 满足15，弱Hash函数；满足16，强Hash函数p 强Hash函数在签名中可以防止替换签名内容的攻击23Hash函数Hash实例Hash函数的安全性要求函数的安全性要求p 不满足单向性的危害在Hash函数的用法11.3(e)中, 秘密值S本身并不发送, 如果散列函数不是单向的,攻击者截获到M和H(M|S). 然后通过某种逆变换获得M|S, 因而攻击者就可以得到S.p 不满足抗弱碰撞性的危害攻击者以一个有效签名(x,y)开始，此处y= sigk(h(x)。首先他计算
13、Z=h(x)，并企图找到一个x满足h(x)=h(x)。若他做到这一点，则(x,y)也将为有效签名。p 不满足抗强碰撞性的危害攻击者首先找到两个消息x=x,满足h(x)=h(x),然后Oscar把x 给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x,y)是一个有效的伪造。24Hash函数Hash实例Hash函数的安全性要求函数的安全性要求抗原像攻击(单向性)：给定 h ，计算满足H(x)=h的x在计算上是不可行的抗第二原像攻击(抗弱碰撞性)：给定x，计算满足H(y)=H(x)的y在计算上是不可行的抗(强)碰撞性：找到任何满足 H(y)=H(x)的偶对（ x,y ），在计算上是不可行的。
14、 25Hash函数Hash实例不同应用中对不同应用中对Hash函数的安全性要求函数的安全性要求满足满足15或或16条件的条件的Hash函数会收到什么样的威胁呢？函数会收到什么样的威胁呢？26Hash函数Hash实例穷举攻击穷举攻击p 原像攻击原像攻击和和第二原像攻击第二原像攻击：对于：对于m位的位的Hash值，攻击者平值，攻击者平均要试均要试2m-1次次p 碰撞攻击碰撞攻击：大约：大约2m/2次次 生日攻击生日攻击p 生日攻击生日攻击p 攻击者的主要攻击目标是找到一对或更多对碰撞消息。p 攻击Hash算法和计算碰撞消息的方法。1.一般的方法，攻击任何类型的Hash算法，比如“生日攻击”；2.特
15、殊的方法，只能用于攻击某些特殊的Hash算法。27Hash函数Hash实例生日生日攻击攻击问题：问题：我们班上有我们班上有57个人个人，那么其中两个人生日相同的，那么其中两个人生日相同的概率概率是多少？是多少？注意：注意：生日生日相同指的是两个人的出生月份和日期相同，不考相同指的是两个人的出生月份和日期相同，不考虑虑年份；另外，忽略闰年。年份；另外，忽略闰年。直接考虑有直接考虑有n个人，当个人，当n=366时，时，p=1；当当n86.4%；n=57时，时，99%28Hash函数Hash实例生日攻击生日攻击p 假定假定使用使用64位的散列码位的散列码,是否安全是否安全?p 如果采用传输加密的散列
16、码和不加密的报文如果采用传输加密的散列码和不加密的报文M,对手需要对手需要找到找到M ,使得使得H(M )=H(M),以便使用替代报文来欺骗接收以便使用替代报文来欺骗接收者者.p 一种基于生日悖论的攻击可能做到这一点一种基于生日悖论的攻击可能做到这一点.29Hash函数Hash实例生日攻击生日攻击p 一一种基于生日悖论的攻击可能做到这一点种基于生日悖论的攻击可能做到这一点.p 具体方法如下：具体方法如下：1. 发送发送方方A签名：签名：A用私钥对用私钥对m位位Hash加密，附在消息后加密，附在消息后2. 攻击攻击者可以产生（合法）消息的者可以产生（合法）消息的2m/2种变形，计算种变形，计算H
17、ash3. 攻击攻击者想伪造一个消息者想伪造一个消息y，并获得，并获得A的签名的签名4. 攻击攻击者产生者产生y的变形，并比较是否与的变形，并比较是否与2中某个中某个Hash相同相同5. 假设找到假设找到x=y，攻击者将，攻击者将x发给发给A，之后用，之后用y替换替换p 所所需的计算代价仅为需的计算代价仅为2m/2 ，64位位Hash仅需要仅需要23230Hash函数Hash实例生日攻击生日攻击p 一一种基于生日悖论的攻击可能做到这一点种基于生日悖论的攻击可能做到这一点.p 具体方法如下：具体方法如下：1. 发送发送方方A签名：签名：A用私钥对用私钥对m位位Hash加密，附在消息后加密，附在消
18、息后2. 攻击攻击者可以产生（合法）消息的者可以产生（合法）消息的2m/2种变形，计算种变形，计算Hash3. 攻击攻击者想伪造一个消息者想伪造一个消息y，并获得，并获得A的签名的签名4. 攻击攻击者产生者产生y的变形，并比较是否与的变形，并比较是否与2中某个中某个Hash相同相同5. 假设找到假设找到x=y，攻击者将，攻击者将x发给发给A，之后用，之后用y替换替换p 所所需的计算代价仅为需的计算代价仅为2m/2 ，64位位Hash仅需要仅需要23231Hash函数Hash实例密码分析密码分析Hash函数的通用结构：函数的通用结构：由由Merkle于于1989年提出年提出Ron Rivest于
19、于1990年提出年提出MD4几乎被所有几乎被所有hash函数使用函数使用attacks focus on collisions in function f具体做法具体做法:把原始消息M分成一些固定长度的块Yi最后一块padding并使其包含消息M长度设定初始值CV0压缩函数f, CVi=f(CVi-1,Yi-1)最后一个CVi为hash值32Hash函数Hash实例安全性举例：基于安全性举例：基于CBC的的Hash函数函数无密钥的分组密码链接方法，将消息无密钥的分组密码链接方法，将消息M分为大小固定的组：分为大小固定的组：M1，M2，MN假如使用假如使用DES生成生成64位位Hash值，易受生
20、日攻击影响，非常脆值，易受生日攻击影响，非常脆弱。弱。应用应用于签名时更为明显。于签名时更为明显。33Hash函数Hash实例安全性举例：基于安全性举例：基于CBC的的Hash函数函数基于基于CBC的的Hash用于签名时用于签名时攻击攻击者可以利用者可以利用“中间相遇攻击中间相遇攻击”pMD5即即Message-Digest Algorithm 5，用于确保信息传输完，用于确保信息传输完整一致。是计算机广泛使用的散列算法之一（又译整一致。是计算机广泛使用的散列算法之一（又译摘要算摘要算法法、哈希算法），主流编程语言普遍已有、哈希算法），主流编程语言普遍已有MD5实现。实现。p将将数据数据（如汉
21、字）运算为另一固定长度值，是散列算法的（如汉字）运算为另一固定长度值，是散列算法的基础原理，基础原理，MD5的前身有的前身有MD2、MD3和和MD4。p产生产生128-bit的的hash值值p直到现在仍是被广泛使用的直到现在仍是被广泛使用的hash算法算法p最近已受到穷举攻击和密码分析攻击p2004，美密会，王小云，快速寻找MD5碰撞（几分钟）Hash函数安全性MD5消息摘要算法消息摘要算法p MD5算法应用算法应用p 其典型应用是对一段其典型应用是对一段Message（字节串）产生（字节串）产生Fingerprint（指纹（指纹），以防止被篡改），以防止被篡改。p 比如，在UNIX下有很多软
22、件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构为： MD5 (httpd-2.2.0.tar.bz2) = 402b90a2e47205f94b3b1d91e1a8c459，p 这就是httpd-2.2.0.tar.bz2文件的数字签名。p 如果在以后传播这个文件的过程中，无论文件的内容发生了任何如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改，如形式的改变（包括人为修改，如Repack进木马病毒，或者下载进木马病毒，或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新过程中线路不稳定引起的传输错
23、误等），只要你对这个文件重新计算计算MD5时就会发现信息摘要不相同，由此可以确定你得到的只时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件是一个不正确的文件。p MD5还广泛用于加密和解密技术上。还广泛用于加密和解密技术上。p 例如在UNIX系统中用户的密码就是以MD5（或其它类似算法）经加密后存储在文件系统中。Hash函数安全性MD5算法描述算法描述 - step 1p 信息填充信息填充：1. 在MD5算法中，首先需要对信息进行填充，使。因此，信息的字节长度（Bits Length）将被扩展至N*512+448，即N*64+56个字节（Bytes），N为一个正整数。填充的方
24、法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。2. 然后，在这个结果后面表示的填充前填充前信息长度信息长度。p 经过这两步的处理，现在的信息字节长度=N*512+448+64=(N+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。Hash函数安全性SHA-512过程类似:1024,896SHA-512: 12837Hash函数安全性MD5描述描述step 2p 初始化初始化MD缓存缓存p MD为为128bit，用于存放散列函数的中间及最终结果，用于存放散列函数的中间及最终结果p MD可表示为可表示为4个个32bi
25、t的寄存器的寄存器(A,B,C,D)，初始化如下：，初始化如下：Hash函数安全性SHA-512: 512位输出SHA-512: 8个64位寄存器MD5描述描述step 3.压缩压缩：4个循环的压缩算法个循环的压缩算法1.以以16个字（个字（512bits）为分组处理消息）为分组处理消息2.把最后的缓冲值作为把最后的缓冲值作为hash输出值（输出值（128比特）比特）Hash函数安全性2022-1-20西安电子科技大学计算机学院40Hash函数安全性41Hash函数安全性p 而而SHA是是FIPS(联邦信息处理标准联邦信息处理标准)所认证的五种安全所认证的五种安全散列算法散列算法。p SHA家
26、族的五个算法，分别是家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和，和SHA-512，由，由美国国家安全局美国国家安全局(NSA)所设计，并由所设计，并由美美国国家标准与技术研究院国国家标准与技术研究院(NIST)发布；是美国的政府标准。后四发布；是美国的政府标准。后四者有时并称为者有时并称为SHA-2。p SHA-1在许多安全协定中广为使用，包括在许多安全协定中广为使用，包括TLS和和SSL、PGP、SSH、S/MIME和和IPsec，曾被视为是，曾被视为是MD5的后继者。但的后继者。但SHA-1的安全的安全性如今被密码学家严重质疑；虽然至今尚未出现对性
27、如今被密码学家严重质疑；虽然至今尚未出现对SHA-2有效的有效的攻击，它的算法跟攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展基本上仍然相似；因此有些人开始发展其他替代的散列算法其他替代的散列算法。Hash函数安全性SHA VersionsSHA-1SHA-224SHA-256 SHA-384SHA-512 Message digest size160224256384512Message size 264 264 264 2128 2128 Block size51251251210241024Word size3232326464Number of steps80646480
28、80Hash函数安全性SHA-512 OverviewHash函数安全性SHA-512 Compression Function heart of the algorithm processing message in 1024-bit blocks consists of 80 rounds updating a 512-bit buffer using a 64-bit value Wt derived from the current message block and a round constant based on cube root of first 80 prime numbe
29、rsHash函数安全性（1）消息）消息填填充充Hash函数安全性（2）SHA-512 Round FunctionHash函数安全性Hash函数安全性（3） Message Digest InitializationHash函数安全性前8个素数平方根的小数部分Hash函数安全性前80个素数平立根的小数部分（4）W产产生生Hash函数安全性Hash函数安全性53消息认证数字签名口令保护入侵检测伪随机数MD5、SHA-512、SHA-3输入变长输入变长输出固定输出固定抗原像抗原像攻击攻击抗弱碰撞抗弱碰撞抗强碰撞抗强碰撞伪随机检测穷举攻击碰撞：生日攻击密码分析Hash结构压缩函数f100|原始长度数据SHA-3：10*、10*1压缩函数fSHA-3的海绵函数：吸水、挤压
