散列函数与数字签名

散列函数与数字签名第1页，课件共48页，创作于2023年2月2023/7/24第五章散列函数与数字签名5.1概述5.2消息摘要5.3消息认证5.4数字签名5.5小结2第2页，课件共48页，创作于2023年2月5.1概述——消息摘要消息摘要（消息的数字指纹）是数字签名体系中实现信息完整性保障的技术。消息摘要的工作原理：将消息作为Hash函数的输入数据，生成定长的输出数据（即消息摘要），并将其作为消息的附加信息。Hash函数有两个基本特性：输入数据的任何细微变化将导致输出数据的巨大改变难以进行逆运算利用这两个特性，消息接收方根据消息摘要能验证收到的消息在传输过程中是否发生了改变，从而验证了消息的完整性和有效性。2023/7/243第3页，课件共48页，创作于2023年2月5.1概述——公开密钥技术公开密钥技术是数字签名体系中进行身份认证和保障不可抵赖性的主要技术。在公钥加密技术中，利用发送者A的私钥加密的信息只有用发送者A的公钥才能解密。在A的私钥没有泄露的情况下，如果一个经某私钥加密的信息能被A的公钥解密，那么就说明该私钥属于A，从而可以确定该信息是由A发出的。（A无法抵赖）同理，别人也无法冒充A发送信息，因为他没有A的私钥。2023/7/244第4页，课件共48页，创作于2023年2月2023/7/245.1概述——数字签名信息完整性和不可抵赖性是信息安全的两个基本要素。数字签名技术通过结合消息摘要技术和公开密钥技术，保证了不可靠网络中传输的信息的完整性和抗否认性。数字签名的大致步骤发送方利用Hash函数对待发消息M进行摘要处理，生成一个固定长度的消息摘要H(M)。用自己的私钥对该消息摘要（即一个hash值）进行加密，形成发送方的一个数字签名。（这个数字签名作为消息的附件随消息一起发送到接收方。）接收方利用数字签名中的消息摘要对消息的完整性进行判断，利用发送方的公钥对发送方进行身份认证和保证抗否认性。5图5.1数字签名过程第5页，课件共48页，创作于2023年2月5.2消息摘要5.2.1Hash函数的概念和原理5.2.2MD5算法5.2.3SHA-1算法5.2.4MD5和SHA-1算法的比较5.2.5HMAC算法2023/7/246第6页，课件共48页，创作于2023年2月2023/7/245.2消息摘要——概述在通信过程中，信息的完整性是信息安全保证的重要指标。信息完整性是指信息在存储和传输过程中不被非法篡改、破坏、增删，能真实无误地到达目的地的特性。消息摘要是保证信息完整性的基本技术之一，Hash函数则是消息摘要技术的核心内容。目前最典型的两个Hash算法：MD5算法和SHA-1算法。7第7页，课件共48页，创作于2023年2月2023/7/245.2.1Hash函数的概念Hash函数的定义把可变长度的输入数据转换成固定长度的输出数据的一种函数。这个定长的输出数据称为输入数据的消息摘要，也称为散列值、哈希值或数字指纹。Hash函数具有单向性指从输入数据很容易计算其Hash值，但通过Hash值想找到其对应的输入数据是很困难的。也就是说，要找到一个输入数据使其Hash值等于一个特定值是很困难的。一个好的Hash函数也是无碰撞的即很难产生两个输入数据，使它们的Hash值相同。8第8页，课件共48页，创作于2023年2月5.2.1Hash函数的性质一个典型的Hash函数应具有下列特性：单向性：已知Hash函数的输出c=hash(m)，要求它的输入m是困难的。快速性：已知输入m，计算hash(m)是容易的。抗碰撞性：已知hash(m1)=c1，构造m2使hash(m2)=c1是困难的。雪崩性：c=hash(m)，c的每一比特都与m的每一比特有关，具有高度敏感性。输入数据没有长度限制：对输入任何长度的数据能够生成该输入消息固定长度的输出。2023/7/249第9页，课件共48页，创作于2023年2月5.2.1Hash函数的例子一个最简单的Hash函数的例子将输入数据M分成n个等长的分组Mi(1≤i≤n)，然后对每个分组按位进行异或运算，得到的结果便为其消息摘要。2023/7/2410图5.2简单的Hash函数示例第10页，课件共48页，创作于2023年2月2023/7/245.2.1Hash函数的攻击方法Hash函数的安全性取决于其抗各种攻击的能力。攻击者的目标通常是找到两个不同消息映射为同一值。一般假定攻击者知道Hash算法。攻击Hash函数有两种基本方法，都属于选择明文攻击。穷举攻击法(ExhaustiveAttack)生日攻击(BirthdayAttack)穷举攻击法给定H=h(M)，其中H为初值，攻击者在所有可能的M中寻求有利于攻击者的M’，使h(M’)=h(M)，由于限定了目标h(M)来寻找M’，这种攻击又称为目标攻击法。11第11页，课件共48页，创作于2023年2月2023/7/245.2.1Hash函数的生日攻击法生日攻击法可用于攻击任何Hash算法，它只依赖于消息摘要的长度，即Hash值的长度。生日攻击基于生日悖论。在一个教室中，找一个与某人生日相同的概率不小于0.5时，所需学生为183人。在一个教室中，至少有两个学生的生日在同一天的概率不小于0.5的学生人数仅为23人。对于n比特Hash值的生日攻击，当进行2n/2次的选择明文攻击下成功的概率将超过0.63。12第12页，课件共48页，创作于2023年2月2023/7/245.2.1Hash函数的生日攻击法生日攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够的长。一个40比特长的消息摘要是很不安全的，因为仅仅用220(大约一百万)次随机Hash可至少以1/2的概率找到一个碰撞。为了抵抗生日攻击，通常建议消息摘要的长度至少应选取为128比特，此时生日攻击需要约264次Hash。统计结果表明：当hash值的长度为128比特时，则任意两个报文M1和M2具有相同hash值的概率接近于零。安全Hash标准的输出长度选为160比特。13第13页，课件共48页，创作于2023年2月2023/7/24Hash函数的单向性和抗碰撞性使Hash函数适用于加密与认证机制。UNIX系统一直使用Hash函数进行口令认证，系统并不直接存储用户的登录口令明文，而是存储其Hash值。用户登录时，系统对其输入的口令进行Hash值计算，如果结果与系统中存储的Hash值匹配，则允许该用户登录系统。这种机制还实现了对用户口令的保密，因为即使攻击者进入系统窃取了用户口令的Hash值，他也无法通过其计算出用户口令。Hash函数的雪崩性则使其适用于数据完整性的保障机制中。145.2.1Hash函数的应用第14页，课件共48页，创作于2023年2月5.2.1Hash函数的分类Hash函数按其是否有密钥控制分为两大类一类有密钥控制称为密码Hash函数。密码Hash函数的Hash值不但与输入数据有关，还与密钥有关，因此具有认证功能。一类没有密钥控制称为一般Hash函数，一般Hash函数的Hash值只与输入数据有关，因此不具备认证功能，只用于检测输入数据的完整性，一般与公钥加密技术结合使用。典型的Hash算法有MD5和SHA等。2023/7/2415第15页，课件共48页，创作于2023年2月2023/7/245.2.2MD5算法简介

MD5(Message-DigestAlgorithm5)在90年代初由MIT的计算机科学实验室和RSADataSecurityInc发明，经MD2、MD3和MD4发展而来。MD5将任意长度的输入消息变换成一个128bit的大整数，并且它是一个不可逆的变换算法。MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。MD5还广泛用于加密技术上。比如在UNIX系统中用户的密码就是经MD5（或其它类似的算法）加密后存储在文件系统中。16第16页，课件共48页，创作于2023年2月2023/7/245.2.2MD5算法的工作原理17图5.3MD5算法处理过程第17页，课件共48页，创作于2023年2月5.2.2MD5算法的具体过程（1）信息填充对输入信息进行填充，使信息长度为512比特（分组长度）的整数倍。（2）初始化链接变量(ChainingVariable)4个32位整型参数A,B,C,D（3）循环处理以A,B,C,D作为输入参数，对填充后信息的每个分组进行四轮循环处理，每轮循环对分组进行16次操作。2023/7/2418第18页，课件共48页，创作于2023年2月2023/7/245.2.2MD5算法——信息填充信息填充在信息的后面填充一个1和若干个0，直到信息长度扩展至512n+448比特为止。然后在其后附加一个64比特的数据，此数据表示填充前信息的长度。此时信息的比特长度恰好是512的整数倍。填充后将消息被划分成若干个512位的分组，每一分组又被划分为16个32位子分组。这些分组即为算法后续循环处理的输入信息。19第19页，课件共48页，创作于2023年2月5.2.2MD5算法——初始化链接变量初始化链接变量MD5算法中有A、B、C、D四个变量，最初存放的4个32位整数被称作链接变量，链接变量初始化为如下值：A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210当设置好这四个链接变量后，就开始进入算法的循环处理。2023/7/2420第20页，课件共48页，创作于2023年2月5.2.2MD5算法——循环处理循环处理消息的每一个分组均经过4轮循环处理，处理前将缓冲区A、B、C、D的内容作为输入参数，处理后的结果再加入到A、B、C、D中去。2023/7/2421第21页，课件共48页，创作于2023年2月5.2.2MD5算法——循环处理每轮循环处理每轮循环对一个分组进行16次操作。每次操作对a,b,c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量、分组的一个子分组和一个常数。再将所得结果循环左移，并加上a,b,c或d中之一。最后用该结果取代a,b,c或d中之一。2023/7/2422第22页，课件共48页，创作于2023年2月2023/7/245.2.3SHA-1算法安全哈希算法SHA(SecurehashAlgorithm)由美国国家标准技术局NIST(NationalInstituteofStandardsTechnology)在MD4的基础上开发出来的。SHA于1993作为联邦消息处理标准(FIPSPUB180)公布。在1995年出版了改进版本FIPSPUB181，叫做SHA-1。SHA-1算法允许的最大输入报文的长度不超过264位，输出160比特的报文摘要。SHA算法同样以512位分组为单位进行处理。23第23页，课件共48页，创作于2023年2月5.2.3SHA-1算法的具体过程1.信息填充填充方法与MD5算法相同。2.初始化消息摘要(MD)缓存器使用由5个32位寄存器组成的160位缓存来存放中间结果和最终散列值。3.摘要处理处理核心是一个4个循环的压缩函数模块，其中每个循环由20个处理步骤组成。2023/7/2424第24页，课件共48页，创作于2023年2月2023/7/245.2.4MD5算法和SHA-1算法的比较MD5和SHA-1都属于MD4的改进版本，它们之间的比较如下表所示。25MD4SHA-1MD5Hash值128bit160bit128bit分组处理长512bit512bit512bit基本字长32bit32bit32bit步数48(3*16)80(4*20)64(4*16)消息长≤264bit≤264bit≤264bit基本逻辑函数特征3个简单非线性并且对称3个简单非线性并且对称4个简单非线性并且对称常数个数3464速度约为MD4的3/4约为MD4的1/7第25页，课件共48页，创作于2023年2月5.2.5HMAC算法2023/7/2426HMAC在SSL协议采用。HMAC算法步骤：（1）密钥变换：使密钥k与消息块l等长。（2）异或：ipad=0x3636…36…（3）消息级联（4）计算消息摘要（5）异或：opad=0x5A5A…5A…（6）消息级联（7）输出最终结果第26页，课件共48页，创作于2023年2月5.3消息认证5.3.1消息认证概述5.3.2采用Hash函数的消息认证5.3.3采用MAC的消息认证2023/7/2427第27页，课件共48页，创作于2023年2月2023/7/245.3.1消息认证概述消息认证的定义使消息接收者能验证收到的消息在传输过程中有没有被篡改、伪造和假冒，消息的完整性和有效性是否被破坏的过程。消息认证的两种模式采用Hash函数采用消息认证码MAC(MessageAuthenticationCode)区别：是否需要密钥的参与28第28页，课件共48页，创作于2023年2月2023/7/245.3.2采用Hash函数的消息认证消息认证方式一：明文29特点？第29页，课件共48页，创作于2023年2月5.3.2采用Hash函数的消息认证消息认证方式二：加密消息2023/7/2430特点？第30页，课件共48页，创作于2023年2月5.3.2采用Hash函数的消息认证消息认证方式三：加密全部2023/7/2431特点？第31页，课件共48页，创作于2023年2月5.3.3采用MAC的消息认证消息认证码MAC的概念消息认证码MAC是由可变长度的消息M和收发双方共享的密钥K产生的定长函数值MAC=f(K,M)

。举例：基于DES的消息认证码DES算法可用于生成消息认证码，可使用密文的后若干位作为消息认证码。MAC函数类似于加密。它与加密的区别是MAC函数不可逆。由于认证函数的这个数学性质使得它比加密函数更不容易破解。2023/7/2432第32页，课件共48页，创作于2023年2月5.3.3采用MAC的消息认证消息认证方式一：明文2023/7/2433第33页，课件共48页，创作于2023年2月5.3.3采用MAC的消息认证消息认证方式二：加密消息2023/7/2434第34页，课件共48页，创作于2023年2月5.3.3采用MAC的消息认证消息认证方式三：加密全部2023/7/2435第35页，课件共48页，创作于2023年2月5.4数字签名5.4.1基本概念5.4.2RSA签名算法5.4.3DSA签名算法5.4.4多重数字签名5.4.5不可抵赖数字签名5.4.6数字盲签名2023/7/2436第36页，课件共48页，创作于2023年2月2023/7/245.4.1基本概念数字签名的定义首先，数字签名不是将手写的签名经过扫描仪扫描后输入电脑。《电子签名法》：数据电文中以电子形式所含（所附）、用于识别签名人身份、并表明签名人认可其中内容的数据。数字签名是一串数据，该数据仅能由签名人生成，并且该数据能够表明签名人的身份。数字签名的作用确认信息发送者，提供身份认证和不可抵赖性。与传统文件中的手写签名具有同等法律效力。37第37页，课件共48页，创作于2023年2月5.4.1基本概念数字签名无法用消息认证码代替假设Alice和Bob正通过网络完成一笔交易，那么可能出现两种欺骗：

（1）Bob伪造一个消息并使用与Alice共享的密钥K产生该消息的认证码，然后声称该消息来自于A。但实际上Alice并未发送任何消息。（2）既然Bob有可能伪造Alice发来的消息，那么Alice就可以对自己发过的消息予以否认。这两种欺骗在实际应用中都有可能发生。双方争执不下而对簿公堂，但如果没有更有效的机制避免这种争端，法庭根本无法作出仲裁。2023/7/2438第38页，课件共48页，创作于2023年2月5.4.1基本概念数字签名必须具有以下特点①发送方必然产生自己独有的信息来签名以防止伪造和否认。②这种签名很容易产生。③对于接收方，应该很容易验证签名的真伪。④对于给定的x，找出y(y≠x)使得签名Sig(y)=Sig(x)在计算上是不可行的。⑤找出任意两个不同的输入x、y，使得Sig(y)=Sig(x)在计算上是不可行的。2023/7/2439第39页，课件共48页，创作于2023年2月2023/7/245.4.1基本概念数字签名体制的组成签名生成算法：对消息m的签名可记为Sig(m)=s。签名密钥是秘密的。签名验证算法：对签名s的验证可记为Ver(s)={真，伪}={0,1}。验证密钥应当公开。常用的数字签名体制RSA签名体制DSA签名体制ElGamal签名体制Rabin签名体制40第40页，课件共48页，创作于2023年2月2023/7/245.4.1基本概念数字签名的分类直接数字签名：发送者直接把消息和签名发送给接收者，接收者直接利用发送者公钥验证签名。基于仲裁的数字签名：发送者把消息和签名经由称做