Hash函数与消息认证.ppt

Hash函数与消息认证 Hash函数概述 1.1 Hash函数定义 数据安全 机密性 完整性 认证性 密码技术主要保证数据的机密性 Hash函数能保证数据的完整性和认证性 1.1 Hash函数定义 Hash函数的作用 1 用于加密，如RAS-OAEP 2 用于数字签名。因为数字签名的长度至少要和签名的文件一样长，对文件的散列值而不是整个文件签名要有效得多。 3 检查数据的完整性。数据完整性有两种基本的场景。第一种场景是数据正在传输给另一个人，有噪声的通信信道向数据引入了错误。第二种场景是观察者在接收者接收到数据之前重新安排了传输方式。两种场景中，数据都遭到了破坏。 1.1 Hash函数定义 Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。 1.1 Hash函数定义 Hash函数的碰撞（collision） 设x、x’是两个不同的消息，如果 h(x)=h(x’) 则称x和x’是Hash函数h的一个（对）碰撞. 1.1 Hash函数定义 Hash函数的分类 单向Hash函数（one?way） 给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数. 弱抗碰撞Hash函数（weakly collision?free） 任给一个消息x，如果寻找另一个不同的消息x’，使得h(x) =h(x’)是计算上不可行的，则称h是弱抗碰撞Hash函数. 强抗碰撞Hash函数 （strongly collision?free） 如果寻找两个不同的消息x和x’，使得h(x)=h(x’)是计算上不可行的，则称h是强抗碰撞Hash函数. 1.1 Hash函数定义 安全Hash函数h应具有以下性质： 对任意的消息x，计算h(x)是容易的； h是单向的； h是弱抗碰撞的，或是强抗碰撞的。 1 Hash函数概述 1.2 Hash函数的安全性 抗碰撞性是最难满足的。2004年，山东大学密码学家王小云对流行的散列算法MD4 MD5 HAVAL-128和RIPEMN找到了许多碰撞的例子。Lenstra给出了如何生成X.509证书的例子，它们的散列值相同。这就意味着，在一个证书上有效的数字签名在另一个证书上同样有效，因此不可能确定到底哪一个是由认证授权机构合法签署的。 2005年，王小云预测找到SHA-1的碰撞的计算复杂度大概是268，这比生日攻击的平均计算量280要好得多。她在60轮的SHA-1简化版本中找到了碰撞。 这些结果表明，使用当前流行的散列函数前要再三考虑，有必要替换掉这些算法。 1.2 Hash函数的安全性 对Hash函数的攻击是指寻找一对碰撞消息的过程 生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？ k人生日都不同的概率是： 1.2 Hash函数的安全性 生日攻击法 生日悖论原理可以用于构造对Hash函数的攻击 设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。 1.2 Hash函数的安全性 生日攻击法 分别把消息m和M表示成r和R个变形的消息 1.2 Hash函数的安全性 生日攻击法 计算真消息m的变形与假消息M的变形发生碰撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是： 1.2 Hash函数的安全性 生日攻击法 1 Hash函数概述 1.3 Hash函数的迭代构造法 压缩函数（compression function） 1.3 Hash函数的迭代构造法 计算消息x的散列值h(x)的步骤 预处理: 用一个公开算法在消息x右方添加若干比特，得到比特串y，使 得y的长度为t的倍数。即有 y= x || pad(x) = y1 || y 2 || … || yr , 其中| yi|=t (i =1, 2,…, r)，pad(x)称为填充函数。典型的填充函数是先添加x长度| x|的值，再添加若干比特（例如0）。 迭代过程: 设H0=IV是一个长度为m的初始