第八讲 密码学函数.ppt

第八讲 密码学hash函数 Message Authentication 消息认证概念 认证函数 认证函数分类 认证函数：Hash函数 认证函数：Hash函数（续） 根据是否使用密钥 带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列值称作MAC(消息认证码 )。 不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时，散列值称作MDC(消息检测码 )。 认证函数：Hash函数（续） 认证函数：Hash函数（续） 认证函数：Hash函数（续） 认证函数：Hash函数（续） 认证函数：Hash函数（续） 认证函数：Hash函数（续） 杂凑函数应满足的条件 函数的输入可以是任意长 函数的输出是固定长 已知x,求H(x)较为容易 已知h，求H(x)＝h的在计算上不可行，即单向杂凑函数. 已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。满足这一性质，则称其为弱单向杂凑函数。 找出任意两个不同的x,y，是H(x)=H(y)在计算上不可行，满足这一性质，称为强单向杂凑函数. Hash函数的安全性 对Hash函数的攻击是指寻找一对碰撞消息的过程 生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？ k人生日都不同的概率是： Hash函数的安全性 生日攻击法 生日悖论原理可以用于构造对Hash函数的攻击 设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。 Hash函数的安全性 生日攻击法 分别把消息m和M表示成r和R个变形的消息 Hash函数的安全性 生日攻击法 计算真消息m的变形与假消息M的变形发生碰撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是： Hash函数的安全性 生日攻击法 中间相遇攻击（in-the-middle attack） 用于攻击一类具有特殊结构的Hash函数 分析Hash函数运算的中间值相等的概率 讨论一类利用加密变换构造的Hash函数 设加密体制为： 中间相遇攻击（in-the-middle attack） 用于攻击一类具有特殊结构的Hash函数 分析Hash函数运算的中间值相等的概率 讨论一类利用加密变换构造的Hash函数 Hash函数的安全性 Hash函数的安全性 迭代型杂凑函数的一般结构 Hash函数的迭代构造法 压缩函数（compression function） 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的初始比特串，重复使用压缩函数f，依次计算 Hi= f (Hi?1|| yi) (i =1, 2,…, r). 输出变换: 设g: {0,1}m?{0,1}t是一个公开函数，令 h(x)=g(Hr). hash函数通用模型 由Merkle于1989年提出 几乎被所有hash算法采用 具体做法: 把原始消息M分成一些固定长度的块Yi 最后一块padding并使其包含消息M的长度 设定初始值CV0 压缩函数f, CVi=f(CVi-1,Yi-1) 最后一个CVi为hash值 算法描述 MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。 ③ 对MD缓冲区初始化算法使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A，B，C，D），每个寄存器都以littleendian方式存储数据，其初值取为（以存储方式）AB=89ABCDEF， C=FEDCBA98，D实际上为