哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　数字认证技术 ：第四讲数据完整性验证1 主要内容完整性验证概述Hash函数Hash函数通常构造MD5/SHA2基于困难问题的Hash构造长数据的Hash处理基于MAC的消息认证2 概述消息认证（Message Authentication）:验证消息没有被改变，即完整性认证问题：消息认证与原始数据的关系？不考虑数据保密性：与加密技术对比不允许改动数据：脆弱水印与消息认证码（纠错码）纠错码尽管在错误检测中非常有用，并不能可靠地验证数据完整性，这是因为 CRC 通常采用线性结构，非常容易地故意改变数据而维持 CRC 不变，安全性不足3 验证块与数据块的关系（重点）验证块与数据块的关系？令数据块长度为L，验证码长度为K假设从数据块到验证码的映射是随机的当L=K，验证重复率为：2L/2K=1当L=K+1，验证重复率为：2K+1/2K=2……验证重复率为：2L-K为无穷大，表示了具有相同验证码的消息数目碰撞概率： 2L-K/2L=1/2K 对任意1个数据，碰撞概率与待验证数据长度无关，只与验证码长度相关如何对于大数据的消息认证？如K=128比特这是平均情况的概率，最坏情况要≥1/2K 4 消息认证的定义消息认证的（功能与安全）定义：给定密钥k有效生成：计算Hk(M)=σ，传输(M, σ)有效验证：存在算法Vk (M, σ)=1，要求成功概率为Pr[Vk (M, σ)=1:Hk(M)=σ]=1困难伪造：发现M’ ,使得M’≠M（碰撞）,那么1/2K ≤ Pr[Vk (M’, σ)=1] ε5 消息认证函数是单向函数（重点）单向函数f()定义：计算容易：f(x)=y求逆困难：f -1(y)=x’ and f(x’)=yPr[f(f -1 (y))=y]ε通常定义“验证函数”和“认证块生成函数”为同一函数(实现方便)Pr[Vk (M, σ)=1Hk(M)=σ]=1Vk (M, σ)=1 = Hk(M)=σ发现M’≠M,那么 Pr[Hk(M’)=σ] εPr[Hk(H-1k(σ))=σ] ε6 完整性验证的数学基础单向函数Hash函数单向性：已知y，找出x，使得Hash(x)=y困难（强和弱）碰撞性:已知x，找到x’x，使得Hash(x’)=Hash(x)困难用于构造消息认证函数 单向置换单向性：已知y，找出x，使得Hash(x)=y困难唯一性（无碰撞性）：已知x，不可能找到x’x，使得Hash(x’)=Hash(x)用于构造加密算法7 消息认证分类数据完整性验证脆弱性水印消息认证无密钥消息认证（无攻击下使用）基于Hash算法的认证有密钥消息认证基于MAC算法的认证基于加密算法的认证单密钥认证（对称加密）双密钥认证（非对称加密）8 Hash函数9 3.1.1 基本概念Hash函数也称为杂凑函数或散列函数，其输入为一可变长度x，返回一固定长度串，该串被称为输入x的Hash值（消息摘要）因为Hash函数是多对一的函数，所以一定将某些不同的输入变化成相同的输出。这就要求给定一个Hash值，求其逆是比较难的，但给定的输入计算Hash值必须是很容易的，因此也称Hash函数为单向Hash函数。10 Hash定义密码学Hash函数是一个压缩函数Hashk:X-YHashk(x)=yHash函数的安全要求：单向性：已知y，找出x，使得Hashk(x)=y困难弱碰撞：已知x，找出x’≠x，使得Hashk(x’)= Hashk(x)困难强碰撞：找出任意x’≠x，使得Hashk(x’)= Hashk(x)困难困难性具有递增关系：强碰撞必然是弱碰撞，弱碰撞必然单向性11 生日攻击强碰撞：找出任意x’≠x，使得Hashk(x’)= Hashk(x)困难12 基本概念（续）Hash函数一般满足以下几个基本需求：（1）输入x可以为任意长度；（2）输出数据长度固定；（3）容易计算，给定任何x，容易计算出x的Hash值H(x)；（4）单向函数：即给出一个Hash值，很难反向计算出原始输入；（5）碰撞性：即难以找到两个不同的输入会得到相同的Hash输出值（在计算上是不可行的）。13 Hash函数分类一般Hash函数压缩函数，不满足安全性要求密码学Hash函数基于分组密码的Hash函数MD5，SHA1，SHA2，SHA3（ 2012/10/2，Keccak被选为NIST杂凑函式竞赛的胜利者）基于公钥密码的Hash函数SQRT14 Hash效率CPU ArchitectureFrequencyAlgorithmWord size (bits)Cycles/Byte x86MiB/s x86Cycles/Byte x86-64MiB/s x86-64Intel Ivy Bridge3.5?GHzSHA-25632-bit16.8019913.05256SHA-51264-bit43.66768.48394AMD Piledriver3.8?GHzSHA-25632-bit22.8715818.47196SHA-51264-bit88.364112.4329215 Hash函数的通常构造16 Hash函数的通常构造17 F函数F函数是一个经典的单向函数18 Hash构造的安全性通过对简单“单向函数”的迭代，实现了更加困难的Hash函数构造。19 MD5/Sha220 介绍21SHA-3 NIST在2015年8月定为标准 SHA1数据定义再进行分组压缩，每组512比特压缩比接近322 MD5/SHA1 Overview23 SHA1算法回忆压缩函数Compress(Zi-1,Mi)=Zi16组*32-bit=512-bit5组*32-bit=160-bit80轮，初始化，前16轮用输入数据，后64轮用前一轮计算结果：数据绞肉机24 SHA-1算法框图移位：线比特进行了非线性处理，效率低下，但结构简单25 非线 基于困难问题的Hash构造29 基于困难问题的Hash构造30 SQUASH2007年，Shamir给出了一个基于平方剩余问题的Hash构造：SQUASHs,N(x)=LSBm((x+s)2 mod N)LSBm()是最后m个比特。S为密钥，可为0。问题：计算开销？如何加快计算?快速Mod运算(x+s)2 =y1 2n+y0=y1+y0 mod 2n-1建议：21277-1安全性？N的分解，x不能太小。31 SqHash32 其他Hash函数构造基于平方剩余问题的Hash构造给定N=pq, 对任意x，sq(x)=x^2 mod N33 基于随机矩阵的Hash函数一个n*m随机矩阵，mn, z是短向量34 长数据的Hash处理35 压缩函数Hash函数的输出长度L由算法的类型决定，与输入消息大小无关，一般为128或者160位。常用的单向Hash算法有MDS、SHA-l等但在密码协议中，Hash函数的输入是定常K的，K≥L，我们称其为压缩函数通常，K/L=2-5问题： 如何使用固定压缩率的Hash函数实现无限长消息的Hash函数36 37 树状Hash：Merkel Tree38? 基于MAC的消息认证39 MAC定义40 MAC的认证过程MMac(M)41 MAC构造方法通过Hash函数构造HMAC，嵌套MAC通过加密算法构造CBC-MAC42 Hash函数构造MAC由Hash函数构造MAC优于采用对称加密算法Hash函数要快于加密算法，Why？Hash压缩比较高（Q：加密函数压缩比是多少？）不受国际海关控制通常的方法：MACkey(M)=Hash(keyM)即把密钥key作为Hash的初始向量IV一些攻击被发现（下页阐述）弥补这些安全问题，HMAC被开发43 对简单Hash构造MAC的攻击44 HMAC介绍opad和ipad:被用来为嵌套Hash提供两个不同密钥为什么是这么两个数？HMAC(K,x)=SHA( (K+opad) SHA( (K+ipad) x) )45 HMAC框图46 201547 48 CBC-MAC攻击201549