散列函数与数字签名.ppt

信息安全概论 电子科技大学出版社2007年8月 2020 1 3 1 2020 1 3 第五章散列函数与数字签名 5 1概述5 2消息摘要5 3消息认证5 4数字签名5 5小结 2 5 1概述 消息摘要 消息摘要 消息的数字指纹 是数字签名体系中实现信息完整性保障的技术 消息摘要的工作原理 将消息作为Hash函数的输入数据 生成定长的输出数据 即消息摘要 并将其作为消息的附加信息 Hash函数有两个基本特性 输入数据的任何细微变化将导致输出数据的巨大改变难以进行逆运算利用这两个特性 消息接收方根据消息摘要能验证收到的消息在传输过程中是否发生了改变 从而验证了消息的完整性和有效性 2020 1 3 3 5 1概述 公开密钥技术 公开密钥技术是数字签名体系中进行身份认证和保障不可抵赖性的主要技术 在公钥加密技术中 利用发送者A的私钥加密的信息只有用发送者A的公钥才能解密 在A的私钥没有泄露的情况下 如果一个经某私钥加密的信息能被A的公钥解密 那么就说明该私钥属于A 从而可以确定该信息是由A发出的 A无法抵赖 同理 别人也无法冒充A发送信息 因为他没有A的私钥 2020 1 3 4 2020 1 3 5 1概述 数字签名 信息完整性和不可抵赖性是信息安全的两个基本要素 数字签名技术通过结合消息摘要技术和公开密钥技术 保证了不可靠网络中传输的信息的完整性和抗否认性 数字签名的大致步骤发送方利用Hash函数对待发消息M进行摘要处理 生成一个固定长度的消息摘要H M 用自己的私钥对该消息摘要 即一个hash值 进行加密 形成发送方的一个数字签名 这个数字签名作为消息的附件随消息一起发送到接收方 接收方利用数字签名中的消息摘要对消息的完整性进行判断 利用发送方的公钥对发送方进行身份认证和保证抗否认性 5 图5 1数字签名过程 5 2消息摘要 5 2 1Hash函数的概念和原理5 2 2MD5算法5 2 3SHA 1算法5 2 4MD5和SHA 1算法的比较5 2 5HMAC算法 2020 1 3 6 2020 1 3 5 2消息摘要 概述 在通信过程中 信息的完整性是信息安全保证的重要指标 信息完整性是指信息在存储和传输过程中不被非法篡改 破坏 增删 能真实无误地到达目的地的特性 消息摘要是保证信息完整性的基本技术之一 Hash函数则是消息摘要技术的核心内容 目前最典型的两个Hash算法 MD5算法和SHA 1算法 7 2020 1 3 5 2 1Hash函数的概念 Hash函数的定义把可变长度的输入数据转换成固定长度的输出数据的一种函数 这个定长的输出数据称为输入数据的消息摘要 也称为散列值 哈希值或数字指纹 Hash函数具有单向性指从输入数据很容易计算其Hash值 但通过Hash值想找到其对应的输入数据是很困难的 也就是说 要找到一个输入数据使其Hash值等于一个特定值是很困难的 一个好的Hash函数也是无碰撞的即很难产生两个输入数据 使它们的Hash值相同 8 5 2 1Hash函数的性质 一个典型的Hash函数应具有下列特性 单向性 已知Hash函数的输出c hash m 要求它的输入m是困难的 快速性 已知输入m 计算hash m 是容易的 抗碰撞性 已知hash m1 c1 构造m2使hash m2 c1是困难的 雪崩性 c hash m c的每一比特都与m的每一比特有关 具有高度敏感性 输入数据没有长度限制 对输入任何长度的数据能够生成该输入消息固定长度的输出 2020 1 3 9 5 2 1Hash函数的例子 一个最简单的Hash函数的例子将输入数据M分成n个等长的分组Mi 1 i n 然后对每个分组按位进行异或运算 得到的结果便为其消息摘要 2020 1 3 10 图5 2简单的Hash函数示例 2020 1 3 5 2 1Hash函数的攻击方法 Hash函数的安全性取决于其抗各种攻击的能力 攻击者的目标通常是找到两个不同消息映射为同一值 一般假定攻击者知道Hash算法 攻击Hash函数有两种基本方法 都属于选择明文攻击 穷举攻击法 ExhaustiveAttack 生日攻击 BirthdayAttack 穷举攻击法给定H h M 其中H为初值 攻击者在所有可能的M中寻求有利于攻击者的M 使h M h M 由于限定了目标h M 来寻找M 这种攻击又称为目标攻击法 11 2020 1 3 5 2 1Hash函数的生日攻击法 生日攻击法可用于攻击任何Hash算法 它只依赖于消息摘要的长度 即Hash值的长度 生日攻击基于生日悖论 在一个教室中 找一个与某人生日相同的概率不小于0 5时 所需学生为183人 在一个教室中 至少有两个学生的生日在同一天的概率不小于0 5的学生人数仅为23人 对于n比特Hash值的生日攻击 当进行2n 2次的选择明文攻击下成功的概率将超过0 63 12 2020 1 3 5 2 1Hash函数的生日攻击法 生日攻击对Hash函数提出了一个必要的安全条件 即消息摘要必须足够的长 一个40比特长的消息摘要是很不安全的 因为仅仅用220 大约一百万 次随机Hash可至少以1 2的概率找到一个碰撞 为了抵抗生日攻击 通常建议消息摘要的长度至少应选取为128比特 此时生日攻击需要约264次Hash 统计结果表明 当hash值的长度为128比特时 则任意两个报文M1和M2具有相同hash值的概率接近于零 安全Hash标准的输出长度选为160比特 13 2020 1 3 Hash函数的单向性和抗碰撞性使Hash函数适用于加密与认证机制 UNIX系统一直使用Hash函数进行口令认证 系统并不直接存储用户的登录口令明文 而是存储其Hash值 用户登录时 系统对其输入的口令进行Hash值计算 如果结果与系统中存储的Hash值匹配 则允许该用户登录系统 这种机制还实现了对用户口令的保密 因为即使攻击者进入系统窃取了用户口令的Hash值 他也无法通过其计算出用户口令 Hash函数的雪崩性则使其适用于数据完整性的保障机制中 14 5 2 1Hash函数的应用 5 2 1Hash函数的分类 Hash函数按其是否有密钥控制分为两大类一类有密钥控制称为密码Hash函数 密码Hash函数的Hash值不但与输入数据有关 还与密钥有关 因此具有认证功能 一类没有密钥控制称为一般Hash函数 一般Hash函数的Hash值只与输入数据有关 因此不具备认证功能 只用于检测输入数据的完整性 一般与公钥加密技术结合使用 典型的Hash算法有MD5和SHA等 2020 1 3 15 2020 1 3 5 2 2MD5算法简介 MD5 Message DigestAlgorithm5 在90年代初由MIT的计算机科学实验室和RSADataSecurityInc发明 经MD2 MD3和MD4发展而来 MD5将任意长度的输入消息变换成一个128bit的大整数 并且它是一个不可逆的变换算法 MD5的典型应用是对一段信息 Message 产生信息摘要 Message Digest 以防止被篡改 MD5还广泛用于加密技术上 比如在UNIX系统中用户的密码就是经MD5 或其它类似的算法 加密后存储在文件系统中 16 2020 1 3 5 2 2MD5算法的工作原理 17 图5 3MD5算法处理过程 5 2 2MD5算法的具体过程 1 信息填充对输入信息进行填充 使信息长度为512比特 分组长度 的整数倍 2 初始化链接变量 ChainingVariable 4个32位整型参数A B C D 3 循环处理以A B C D作为输入参数 对填充后信息的每个分组进行四轮循环处理 每轮循环对分组进行16次操作 2020 1 3 18 2020 1 3 5 2 2MD5算法 信息填充 信息填充在信息的后面填充一个1和若干个0 直到信息长度扩展至512n 448比特为止 然后在其后附加一个64比特的数据 此数据表示填充前信息的长度 此时信息的比特长度恰好是512的整数倍 填充后将消息被划分成若干个512位的分组 每一分组又被划分为16个32位子分组 这些分组即为算法后续循环处理的输入信息 19 5 2 2MD5算法 初始化链接变量 初始化链接变量MD5算法中有A B C D四个变量 最初存放的4个32位整数被称作链接变量 链接变量初始化为如下值 A 0 x01234567B 0 x89abcdefC 0 xfedcba98D 0 x76543210当设置好这四个链接变量后 就开始进入算法的循环处理 2020 1 3 20 5 2 2MD5算法 循环处理 循环处理消息的每一个分组均经过4轮循环处理 处理前将缓冲区A B C D的内容作为输入参数 处理后的结果再加入到A B C D中去 2020 1 3 21 5 2 2MD5算法 循环处理 每轮循环处理每轮循环对一个分组进行16次操作 每次操作对a b c和d中的其中三个作一次非线性函数运算 然后将所得结果加上第四个变量 分组的一个子分组和一个常数 再将所得结果循环左移 并加上a b c或d中之一 最后用该结果取代a b c或d中之一 2020 1 3 22 2020 1 3 5 2 3SHA 1算法 安全哈希算法SHA SecurehashAlgorithm 由美国国家标准技术局NIST NationalInstituteofStandardsTechnology 在MD4的基础上开发出来的 SHA于1993作为联邦消息处理标准 FIPSPUB180 公布 在1995年出版了改进版本FIPSPUB181 叫做SHA 1 SHA 1算法允许的最大输入报文的长度不超过264位 输出160比特的报文摘要 SHA算法同样以512位分组为单位进行处理 23 5 2 3SHA 1算法的具体过程 1 信息填充填充方法与MD5算法相同 2 初始化消息摘要 MD 缓存器使用由5个32位寄存器组成的160位缓存来存放中间结果和最终散列值 3 摘要处理处理核心是一个4个循环的压缩函数模块 其中每个循环由20个处理步骤组成 2020 1 3 24 2020 1 3 5 2 4MD5算法和SHA 1算法的比较 MD5和SHA 1都属于MD4的改进版本 它们之间的比较如下表所示 25 5 2 5HMAC算法 2020 1 3 26 HMAC在SSL协议采用 HMAC算法步骤 1 密钥变换 使密钥k与消息块l等长 2 异或 ipad 0 x3636 36 3 消息级联 4 计算消息摘要 5 异或 opad 0 x5A5A 5A 6 消息级联 7 输出最终结果 5 3消息认证 5 3 1消息认证概述5 3 2采用Hash函数的消息认证5 3 3采用MAC的消息认证 2020 1 3 27 2020 1 3 5 3 1消息认证概述 消息认证的定义使消息接收者能验证收到的消息在传输过程中有没有被篡改 伪造和假冒 消息的完整性和有效性是否被破坏的过程 消息认证的两种模式采用Hash函数采用消息认证码MAC MessageAuthenticationCode 区别 是否需要密钥的参与 28 2020 1 3 5 3 2采用Hash函数的消息认证 消息认证方式一 明文 29 特点 5 3 2采用Hash函数的消息认证 消息认证方式二 加密消息 2020 1 3 30 特点 5 3 2采用Hash函数的消息认证 消息认证方式三 加密全部 2020 1 3 31 特点 5 3 3采用MAC的消息认证 消息认证码MAC的概念消息认证码MAC是由可变长度的消息M和收发双方共享的密钥K产生的定长函数值MAC f K M 举例 基于DES的消息认证码DES算法可用于生成消息认证码 可使用密文的后若干位作为消息认证码 MAC函数类似于加密 它与加密的区别是MAC函数不可逆 由于认证函数的这个数学性质使得它比加密函数更不容易破解 2020 1 3 32 5 3 3采用MAC的消息认证 消息认证方式一 明文 2020 1 3 33 5 3 3采用MAC的消息认证 消息认证方式二 加密消息 2020 1 3 34 5 3 3采用MAC的消息认证 消息认证方式三 加密全部 2020 1 3 35 5 4数字签名 5 4 1基本概念5 4 2RSA签名算法5 4 3DSA签名算法5 4 4多重数字签名5 4 5不可抵赖数字签名5 4 6数字盲签名 2020 1 3 36 2020 1 3 5 4 1基本概念 数字签名的定义首先 数字签名不是将手写的签名经过扫描仪扫描后输入电脑 电子签名法 数据电文中以电子形式所含 所附 用于识别签名人身份 并表明签名人认可其中内容的数据 数字签名是一串数据 该数据仅能由签名人生成 并且该数据能够表明签名人的身份 数字签名的作用确认信息发送者 提供身份认证和不可抵赖性 与传统文件中的手写签名具有同等法律效力 37 5 4 1基本概念 数字签名无法用消息认证码代替假设Alice和Bob正通过网络完成一笔交易 那么可能出现两种欺骗 1 Bob伪造一个消息并使用与Alice共享的密钥K产生该消息的认证码 然后声称该消息来自于A 但实际上Alice并未发送任何消息 2 既然Bob有可能伪造Alice发来的消息 那么Alice就可以对自己发过的消息予以否认 这两种欺骗在实际应用中都有可能发生 双方争执不下而对簿公堂 但如果没有更有效的机制避免这种争端 法庭根本无法作出仲裁 2020 1 3 38 5 4 1基本概念 数字签名必须具有以下特点 发送方必然产生自己独有的信息来签名以防止伪造和否认 这种签名很容易产生 对于接收方 应该很容易验证签名的真伪 对于给定的x 找出y y x 使得签名Sig y Sig x 在计算上是不可行的 找出任意两个不同的输入x y 使得Sig y Sig x 在计算上是不可行的 2020 1 3 39 2020 1 3 5 4 1基本概念 数字签名体制的组成签名生成算法 对消息m的签名可记为Sig m s 签名密钥是秘密的 签名验证算法 对签名s的验证可记为Ver s 真 伪 0 1 验证密钥应当公开 常用的数字签名体制RSA签名体制DSA签名体制ElGamal签名体制Rabin签名体制 40 2020 1 3 5 4 1基本概念 数字签名的分类直接数字签名 发送者直接把消息和签名发送给接收者 接收者直接利用发送者公钥