余艳玮现代密码学与应用Hash函数和数据完整性.pptVIP

2008-10-12 111  现代密码学与应用 ——Hash函数和数据完整性 参考书籍 《Handbook of Applied Cryptography》: Chapter 9 《Applied Cryptography: Protocols, algorithms, and source code in C》：Chapter 18 《经典密码学与现代密码学》：第9章 大纲 一、 Hash函数概述 二、 MD5算法 三、 SHA算法 四、MAC (Message Authentication Codes) 五、数据完整性和消息认证 一、Hash函数概述 Hash函数 单向函数 函数f(x):A→B，若满足下面两个条件，则称为单向函数 对于任意x∈A，计算y=f(x)是容易的，其中 y ∈B。 （实用性） 对于y∈B，求满足y=f(x)的x(x∈A)在计算上是不可行的。 （安全性） 安全的Hash函数 设H：将A*映射到An，H满足： H是单向函数。 将任意长度的输入映射为固定长度的输出 已知 x, 找 x*∈A*，使H (x)= H (x*)在计算上是不可能的。 （抗弱碰撞性） 找一对 x 和 x* ，x ≠ x* ，使H (x)= H (x*) 在计算上也是不可能的。 （抗强碰撞性） H称为安全的Hash函数。 Hash函数的分类 根据安全水平： 弱无碰撞：散列函数H称为是弱无碰撞的，是指对给定消息x，在计算上几乎找不到异于x的x*，使H (x)= H (x*) 。 ? 强无碰撞：散列函数H被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x 、x* ，使得H (x)= H (x*) 。 根据是否使用密钥 带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时Hash值称作MAC(Message Authentication Codes)。 不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时Hash值称作MDC(Modification Detection Codes)。 Hash函数的用途 Hash值也称为报文摘要 有极强的错误检测能力：消息的完整性检测 为MAC时，可用于消息认证 ? 可辅助数字签名 可用于必威体育官网网址 其他： 知识证明 密钥推导 伪随机数生成 数字签名 Hash函数的安全性 一般假定对手知道Hash算法，采用选择明文攻击法。 Hash函数的安全性取决于其抗击各种攻击的能力，对手的目标是找到两个不同的消息映射为同一Hash值。 假设Hash函数将一个t比特的输入，映射到一个n比特的输出上，则： 有2t-n个输入对应同一个输出 两个随机选择的输入，产生同一个输出的概率为2-n (与ｔ无关) 对Hash函数的基本攻击方法 穷举攻击法： 给定H=H(H0, M)，其中H0为初值。攻击者在所有可能的M中寻求有利于攻击者的M’，使H(H0, M’)=H(H0, M)。 由于限定了目标H(H0, M)来寻找H(H0, M’)，这种攻击法称为目标攻击。 若对算法的初值H0不限定，使其H(H0, M)等于H(H0, M’)，则称这种攻击法为自由起始目标攻击。 生日攻击 这种攻击法不涉及Hash算法的结构，可用于攻击任何Hash算法。 （弱碰撞问题）H有n个输出，H(x)是一个特定的输出。如果对H随机取k个输入，至少存在一个y使得H(y)=H(x)成立的概率为0.5时，k有多大？ H(y)=H(x)的概率为1/n，不等的概率为1-1/n. k个随机输入后，每个hash值都不等于H(x)的概率为[1-1/n]k. k个随机输入中至少有一个hash值等于H(x)的概率为1- [1-1/n]k≈k/n=0.5，可推得：k=n/2。 MDC的构造 基于分组密码的Hash函数 (9.4.1节) 定制的Hash函数（迭代型） (9.4.2节) MD4,MD5,SHA-1 基于模运算的Hash函数 (9.4.3节) MASH-1 基于分组密码的Hash函数 EK( X)表示一种分组加密算法，K是密钥，X是加密算法的输入。 消息分组为M1,…, M i,… H0=I为初始值。 B. Preneel总结的下述12种基本方式构造的分组迭代Hash函数。 Hi=EHi-1(Mi)?Mi Hi=EHi-1(Mi)?Mi?Hi-1 Hi=EHi-1 (Mi?Hi-1)?Mi Hi=EHi-1(Mi?Hi-1)?Mi?Hi-1 Hi=EMi(Hi-1)?Hi-1 Hi=EMi(Mi?Hi-1)?Mi?Hi-1 Hi=EMi(Hi-1)?Mi?Hi-1 Hi=EMi(Mi?Hi-1)?Hi-1 Hi=EMi?Hi-1(Mi)?Mi Hi=EMi?Hi-1(H