散列函数与数字签名精.ppt
散列函数与数字签名散列函数与数字签名第1页，本讲稿共48页2023/2/14第五章第五章 散列函数与数字签名散列函数与数字签名l5.1 概述概述l5.2 消息摘要消息摘要l5.3 消息认证消息认证l5.4 数字签名数字签名l5.5 小结小结2第2页，本讲稿共48页5.1 概述概述消息摘要消息摘要l消息摘要消息摘要（消息的（消息的数字指数字指纹纹）是数字）是数字签签名体系中名体系中实现实现信息完整性信息完整性保障的技保障的技术术。l消息摘要的工作原理消息摘要的工作原理：将消息作：将消息作为为Hash函数函数的的输输入数入数据，生成定据，生成定长长的的输输出数据（即出数据（即消息摘要消息摘要），并将其作），并将其作为为消消息的附加信息。息的附加信息。lHash函数有两个基本特性：函数有两个基本特性：l输入数据的任何细微变化将导致输出数据的巨大改变l难以进行逆运算l利用利用这这两个特性，消息接收方根据两个特性，消息接收方根据消息摘要消息摘要能能验证验证收到收到的消息在的消息在传输过传输过程中是否程中是否发发生了改生了改变变，从而，从而验证验证了消息了消息的完整性和有效性。的完整性和有效性。2023/2/143第3页，本讲稿共48页5.1 概述概述公开密公开密钥钥技技术术l公开密公开密钥钥技技术术是数字是数字签签名体系中名体系中进进行行身份身份认证认证和保障和保障不不可抵可抵赖赖性性的主要技的主要技术术。l在公在公钥钥加密技加密技术术中，中，利用利用发发送者送者A的私的私钥钥加密的信息加密的信息只有用只有用发发送者送者A的公的公钥钥才能解密才能解密。l在在A的私的私钥钥没有泄露的情况下，如果一个没有泄露的情况下，如果一个经经某私某私钥钥加加密的信息能被密的信息能被A的公的公钥钥解密，那么就解密，那么就说说明明该该私私钥钥属属于于A，从而可以，从而可以确定确定该该信息是由信息是由A发发出的出的。（。（A无法抵无法抵赖赖）l同理，同理，别别人也无法冒充人也无法冒充A发发送信息，因送信息，因为为他没有他没有A的的私私钥钥。2023/2/144第4页，本讲稿共48页2023/2/145.1 概述概述数字数字签签名名l信息完整性信息完整性和和不可抵不可抵赖赖性性是信息安全的两个基本要素。是信息安全的两个基本要素。l数字数字签签名技名技术术通通过结过结合合消息摘要技消息摘要技术术和和公开密公开密钥钥技技术术，保，保证证了不了不可靠网可靠网络络中中传输传输的信息的完整性和抗否的信息的完整性和抗否认认性。性。l数字数字签签名的大致步名的大致步骤骤l发送方利用Hash函数对待发消息M进行摘要处理，生成一个固定长度的消息摘要H(M)。l用自己的私钥对该消息摘要（即一个hash值）进行加密，形成发送方的一个数字签名。（这个数字签名作为消息的附件随消息一起发送到接收方。）l接收方利用数字签名中的消息摘要对消息的完整性进行判断，利用发送方的公钥对发送方进行身份认证和保证抗否认性。5图5.1 数字签名过程第5页，本讲稿共48页5.2 消息摘要消息摘要l5.2.1 Hash函数的概念和原理函数的概念和原理l5.2.2 MD5算法算法l5.2.3 SHA-1算法算法l5.2.4 MD5和和SHA-1算法的比较算法的比较l5.2.5 HMAC算法算法2023/2/146第6页，本讲稿共48页2023/2/145.2 消息摘要消息摘要概述概述l在通信在通信过过程中，信息的程中，信息的完整性完整性是信息安全保是信息安全保证证的重要指的重要指标标。l信息完整性信息完整性是是指信息在存指信息在存储储和和传输过传输过程中不被程中不被非法非法篡篡改、破坏、增改、破坏、增删删，能真，能真实实无无误误地到达目地到达目的地的特性的地的特性。l消息摘要消息摘要是保是保证证信息完整性信息完整性的基本技的基本技术术之一，之一，Hash函数函数则则是消息摘要技是消息摘要技术术的核心内容。的核心内容。l目前最典型的两个目前最典型的两个Hash算法：算法：MD5算法算法和和SHA-1算法算法。7第7页，本讲稿共48页2023/2/145.2.1 Hash函数的概念函数的概念lHash函数的定函数的定义义l把可变长度的输入数据转换成固定长度的输出数据的一种函数。这个定长的输出数据称为输入数据的消息摘要，也称为散列值、哈希值或数字指纹。lHash函数具有函数具有单单向性向性l指从输入数据很容易计算其Hash值，但通过Hash值想找到其对应的输入数据是很困难的。l也就是说，要找到一个输入数据使其Hash值等于一个特定值是很困难的。l一个好的一个好的Hash函数也是函数也是无碰撞的无碰撞的l即很难产生两个输入数据，使它们的Hash值相同。8第8页，本讲稿共48页5.2.1 Hash函数的性函数的性质质l一个典型的一个典型的Hash函数函数应应具有下列特性：具有下列特性：l单向性：已知Hash函数的输出c=hash(m)，要求它的输入m是困难的。l快速性：已知输入m，计算hash(m)是容易的。l抗碰撞性：已知hash(m1)=c1，构造m2使hash(m2)=c1是困难的。l雪崩性：c=hash(m)，c的每一比特都与m的每一比特有关，具有高度敏感性。l输入数据没有长度限制：对输入任何长度的数据能够生成该输入消息固定长度的输出。2023/2/149第9页，本讲稿共48页5.2.1 Hash函数的例子函数的例子l一个最一个最简单简单的的Hash函数的例子函数的例子l将输入数据M分成n个等长的分组Mi(1in)，然后对每个分组按位进行异或运算，得到的结果便为其消息摘要。2023/2/1410图5.2 简单的Hash函数示例第10页，本讲稿共48页2023/2/145.2.1 Hash函数的攻函数的攻击击方法方法lHash函数的安全性函数的安全性取决于取决于其抗各种攻其抗各种攻击击的能力的能力。l攻攻击击者的目者的目标标通常是通常是找到两个不同消息映射找到两个不同消息映射为为同一同一值值。一般一般假定攻假定攻击击者知道者知道Hash算法。算法。l攻攻击击Hash函数有两种基本方法，都属于函数有两种基本方法，都属于选择选择明文攻明文攻击击。l穷举攻击法(Exhaustive Attack)l生日攻击(Birthday Attack)l穷举穷举攻攻击击法法l给定H=h(M)，其中H为初值，攻击者在所有可能的M中寻求有利于攻击者的M，使h(M)=h(M)，由于限定了目标h(M)来寻找M，这种攻击又称为目标攻击法。11第11页，本讲稿共48页2023/2/145.2.1 Hash函数的生日攻函数的生日攻击击法法l生日攻生日攻击击法法可用于攻可用于攻击击任何任何Hash算法，它只依算法，它只依赖赖于消于消息摘要的息摘要的长长度，即度，即Hash值值的的长长度。度。l生日攻生日攻击击基于基于生日悖生日悖论论。l在一个教室中，找一个与某人生日相同的概率不小于0.5时，所需学生为183人。l在一个教室中，至少有两个学生的生日在同一天的概率不小于0.5的学生人数仅为23人。l对对于于n比特比特Hash值值的生日攻的生日攻击击，当，当进进行行2n/2次的次的选择选择明文明文攻攻击击下成功的概率将超下成功的概率将超过过0.63。12第12页，本讲稿共48页2023/2/145.2.1 Hash函数的生日攻函数的生日攻击击法法l生日攻生日攻击击对对Hash函数提出了一个必要的安全条件，即函数提出了一个必要的安全条件，即消息摘要必消息摘要必须须足足够够的的长长。l一个一个40比特比特长长的消息摘要是很不安全的，因的消息摘要是很不安全的，因为仅仅为仅仅用用220(大大约约一百万一百万)次次随机随机Hash可至少以可至少以1/2的概率找的概率找到一个碰撞。到一个碰撞。l为为了抵抗生日攻了抵抗生日攻击击，通常建，通常建议议消息摘要的消息摘要的长长度至少度至少应选应选取取为为128比特比特，此，此时时生日攻生日攻击击需要需要约约264次次Hash。l统计结统计结果表明：当果表明：当hash值值的的长长度度为为128比特比特时时，则则任意任意两个两个报报文文M1和和M2具有相同具有相同hash值值的概率接近于零。的概率接近于零。l安全安全Hash标标准的准的输输出出长长度度选为选为160比特比特。13第13页，本讲稿共48页2023/2/14lHash函数的函数的单单向性向性和和抗碰撞性抗碰撞性使使Hash函数适用于函数适用于加密加密与与认证认证机制机制。lUNIX系统一直使用Hash函数进行口令认证，系统并不直接存储用户的登录口令明文，而是存储其Hash值。l用户登录时，系统对其输入的口令进行Hash值计算，如果结果与系统中存储的Hash值匹配，则允许该用户登录系统。l这种机制还实现了对用户口令的保密，因为即使攻击者进入系统窃取了用户口令的Hash值，他也无法通过其计算出用户口令。lHash函数函数的雪崩性的雪崩性则则使其适用于使其适用于数据完整性数据完整性的保障机的保障机制中。制中。145.2.1 Hash函数的函数的应应用用第14页，本讲稿共48页5.2.1 Hash函数的分函数的分类类lHash函数按其是否有密函数按其是否有密钥钥控制分控制分为为两大两大类类l一类有密钥控制称为密码Hash函数。密码Hash函数的Hash值不但与输入数据有关，还与密钥有关，因此具有认证功能。l一类没有密钥控制称为一般Hash函数，一般Hash函数的Hash值只与输入数据有关，因此不具备认证功能，只用于检测输入数据的完整性，一般与公钥加密技术结合使用。典型的Hash算法有MD5和SHA等。2023/2/1415第15页，本讲稿共48页2023/2/145.2.2 MD5算法算法简简介介l MD5(Message-Digest Algorithm 5)在在90年代初由年代初由MIT的的计计算机科学算机科学实验实验室和室和RSA Data Security Inc发发明，明，经经MD2、MD3和和MD4发发展而来。展而来。lMD5将将任意任意长长度的度的输输入消息入消息变换变换成一个成一个128bit的大整的大整数数，并且它是一个，并且它是一个不可逆不可逆的的变换变换算法。算法。lMD5的典型的典型应应用是用是对对一段信息（一段信息（Message）产产生信息摘生信息摘要（要（Message-Digest），以防止被），以防止被篡篡改改。lMD5还还广泛用于加密技广泛用于加密技术术上。比如在上。比如在UNIX系系统统中用中用户户的密的密码码就是就是经经MD5（或其它（或其它类类似的算法）加密后存似的算法）加密后存储储在在文件系文件系统统中。中。16第16页，本讲稿共48页2023/2/145.2.2 MD5算法的工作原理算法的工作原理17图5.3 MD5算法处理过程第17页，本讲稿共48页5.2.2 MD5算法的算法的具体过程具体过程l（1）信息填充）信息填充l对输入信息进行填充，使信息长度为512比特（分组长度）的整数倍。l（2）初始化）初始化链链接接变变量量(Chaining Variable)l4个32位整型参数A,B,C,Dl（3）循）循环处环处理理l以A,B,C,D作为输入参数，对填充后信息的每个分组进行四轮循环处理，每轮循环对分组进行16次操作。2023/2/1418第18页，本讲稿共48页2023/2/145.2.2 MD5算法算法信息填充信息填充l信息填充信息填充l在信息的后面填充一个1和若干个0，直到信息长度扩展至512n+448比特为止。l然后在其后附加一个64比特的数据，此数据表示填充前信息的长度。此时信息的比特长度恰好是512的整数倍。l填充后将消息被划分成若干个512位的分组，每一分组又被划分为16个32位子分组。这些分组即为算法后续循环处理的输入信息。19第19页，本讲稿共48页5.2.2 MD5算法算法初始化初始化链链接接变变量量l初始化初始化链链接接变变量量lMD5算法中有A、B、C、D四个变量，最初存放的4个32位整数被称作链接变量，链接变量初始化为如下值：lA=0 x01234567 lB=0 x89abcdef lC=0 xfedcba98 lD=0 x76543210l当设置好这四个链接变量后，就开始进入算法的循环处理。2023/2/1420第20页，本讲稿共48页5.2.2 MD5算法算法循循环处环处理理l循环处理循环处理l消息的每一个分组均经过4轮循环处理，处理前将缓冲区A、B、C、D的内容作为输入参数，处理后的结果再加入到A、B、C、D中去。2023/2/1421第21页，本讲稿共48页5.2.2 MD5算法算法循循环处环处理理l每每轮轮循循环处环处理理l每轮循环对一个分组进行16次操作。每次操作对a,b,c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量、分组的一个子分组和一个常数。再将所得结果循环左移，并加上a,b,c或d中之一。最后用该结果取代a,b,c或d中之一。2023/2/1422第22页，本讲稿共48页2023/2/145.2.3 SHA-1算法算法l安全哈希算法安全哈希算法SHA(Secure hash Algorithm)l由美国国家标准技术局NIST(National Institute of Standards Technology)在MD4的基础上开发出来的。lSHA于1993作为联邦消息处理标准(FIPS PUB 180)公布。在1995年出版了改进版本FIPS PUB 181，叫做SHA-1。lSHA-1算法允许的最大输入报文的长度不超过264位，输出160比特的报文摘要。lSHA算法同样以512位分组为单位进行处理。23第23页，本讲稿共48页5.2.3 SHA-1算法的具体算法的具体过过程程l1.信息填充信息填充l填充方法与MD5算法相同。l2.初始化消息摘要初始化消息摘要(MD)缓缓存器存器l使用由5个32位寄存器组成的160位缓存来存放中间结果和最终散列值。l3.摘要摘要处处理理l处理核心是一个4个循环的压缩函数模块，其中每个循环由20个处理步骤组成。2023/2/1424第24页，本讲稿共48页2023/2/145.2.4 MD5算法和算法和SHA-1算法的比算法的比较较lMD5和和SHA-1都属于都属于MD4的改的改进进版本，它版本，它们们之之间间的比的比较较如下如下表所示。表所示。25MD4SHA-1MD5Hash值128 bit160 bit128 bit分组处理长512 bit512 bit512 bit基本字长32 bit32 bit32 bit步数48(3*16)80(4*20)64(4*16)消息长264 bit264 bit264 bit基本逻辑函数特征3个简单非线性并且对称3个简单非线性并且对称4个简单非线性并且对称常数个数3464速度约为MD4的3/4约为MD4的1/7第25页，本讲稿共48页5.2.5 HMAC算法算法2023/2/1426HMACHMAC在在在在SSLSSL协议采用。协议采用。协议采用。协议采用。HMACHMAC算法步骤：算法步骤：算法步骤：算法步骤：（1 1）密钥变换：使密）密钥变换：使密）密钥变换：使密）密钥变换：使密钥钥钥钥k k与消息块与消息块与消息块与消息块l l等长。等长。等长。等长。（2 2）异或：）异或：）异或：）异或：ipad=0 x363636ipad=0 x363636（3 3）消息级联）消息级联）消息级联）消息级联（4 4）计算消息摘要）计算消息摘要）计算消息摘要）计算消息摘要（5 5）异或：）异或：）异或：）异或：opad=0 x5A5A5Aopad=0 x5A5A5A（6 6）消息级联）消息级联）消息级联）消息级联（7 7）输出最终结果）输出最终结果）输出最终结果）输出最终结果第26页，本讲稿共48页5.3 消息消息认证认证l5.3.1 消息认证概述消息认证概述l5.3.2 采用采用Hash函数的消息认证函数的消息认证l5.3.3 采用采用MAC的消息认证的消息认证2023/2/1427第27页，本讲稿共48页2023/2/145.3.1 消息消息认证认证概述概述l消息消息认证认证的定的定义义l使消息接收者能验证收到的消息在传输过程中有没有被篡改、伪造和假冒，消息的完整性和有效性是否被破坏的过程。l消息消息认证认证的两种模式的两种模式l采用Hash函数l采用消息认证码MAC(Message Authentication Code)l区别：是否需要密钥的参与28第28页，本讲稿共48页2023/2/145.3.2 采用采用Hash函数的消息函数的消息认证认证l消息消息认证认证方式一：明文方式一：明文29特点？第29页，本讲稿共48页5.3.2 采用采用Hash函数的消息函数的消息认证认证l消息消息认证认证方式二：加密消息方式二：加密消息2023/2/1430特点？第30页，本讲稿共48页5.3.2 采用采用Hash函数的消息函数的消息认证认证l消息消息认证认证方式三：加密全部方式三：加密全部2023/2/1431特点？第31页，本讲稿共48页5.3.3 采用采用MAC的消息的消息认证认证l消息消息认证码认证码MAC的概念的概念l消息认证码MAC是由可变长度的消息M和收发双方共享的密钥K产生的定长函数值MAC=f(K,M)。l举举例：基于例：基于DES的消息的消息认证码认证码lDES算法可用于生成消息认证码，可使用密文的后若干位作为消息认证码。lMAC函数类似于加密。它与加密的区别是MAC函数不可逆。由于认证函数的这个数学性质使得它比加密函数更不容易破解。2023/2/1432第32页，本讲稿共48页5.3.3 采用采用MAC的消息的消息认证认证l消息消息认证认证方式一：明文方式一：明文2023/2/1433第33页，本讲稿共48页5.3.3 采用采用MAC的消息的消息认证认证l消息消息认证认证方式二：加密消息方式二：加密消息2023/2/1434第34页，本讲稿共48页5.3.3 采用采用MAC的消息的消息认证认证l消息消息认证认证方式三：加密全部方式三：加密全部2023/2/1435第35页，本讲稿共48页5.4 数字数字签签名名l5.4.1 基本概念基本概念l5.4.2 RSA签名算法签名算法l5.4.3 DSA签名算法签名算法l5.4.4 多重数字签名多重数字签名l5.4.5 不可抵赖数字签名不可抵赖数字签名l5.4.6 数字盲签名数字盲签名2023/2/1436第36页，本讲稿共48页2023/2/145.4.1 基本概念基本概念l数字数字签签名的定名的定义义l首先，数字签名不是将手写的签名经过扫描仪扫描后输入电脑。l电子签名法：数据电文中以电子形式所含（所附）、用于识别签名人身份、并表明签名人认可其中内容的数据。l数字签名是一串数据，该数据仅能由签名人生成，并且该数据能够表明签名人的身份。l数字数字签签名的作用名的作用l确认信息发送者，提供身份认证和不可抵赖性。l与传统文件中的手写签名具有同等法律效力。37第37页，本讲稿共48页5.4.1 基本概念基本概念l数字签名无法用消息认证码代替数字签名无法用消息认证码代替l l假设假设假设假设AliceAlice和和和和BobBob正通过网络完成一笔交易，那么可能出现两种正通过网络完成一笔交易，那么可能出现两种正通过网络完成一笔交易，那么可能出现两种正通过网络完成一笔交易，那么可能出现两种欺骗：欺骗：欺骗：欺骗：l l（1 1）BobBob伪造一个消息并使用与伪造一个消息并使用与伪造一个消息并使用与伪造一个消息并使用与AliceAlice共享的密钥共享的密钥共享的密钥共享的密钥K K产生该消产生该消产生该消产生该消息的认证码，然后声称该消息来自于息的认证码，然后声称该消息来自于息的认证码，然后声称该消息来自于息的认证码，然后声称该消息来自于A A。但实际上。但实际上。但实际上。但实际上AliceAlice并未发送并未发送并未发送并未发送任何消息。任何消息。任何消息。任何消息。l l（2 2）既然）既然）既然）既然BobBob有可能伪造有可能伪造有可能伪造有可能伪造AliceAlice发来的消息，那么发来的消息，那么发来的消息，那么发来的消息，那么AliceAlice就就就就可以对自己发过的消息予以否认。可以对自己发过的消息予以否认。可以对自己发过的消息予以否认。可以对自己发过的消息予以否认。l l这两种欺骗在实际应用中都有可能发生。双方争执不下而对簿公堂，这两种欺骗在实际应用中都有可能发生。双方争执不下而对簿公堂，这两种欺骗在实际应用中都有可能发生。双方争执不下而对簿公堂，这两种欺骗在实际应用中都有可能发生。双方争执不下而对簿公堂，但如果没有更有效的机制避免这种争端，法庭根本无法作出仲裁。但如果没有更有效的机制避免这种争端，法庭根本无法作出仲裁。但如果没有更有效的机制避免这种争端，法庭根本无法作出仲裁。但如果没有更有效的机制避免这种争端，法庭根本无法作出仲裁。2023/2/1438第38页，本讲稿共48页5.4.1 基本概念基本概念l l数字签名必须具有以下特点数字签名必须具有以下特点l发送方必然产生自己独有的信息来签名以防止伪造和否认。l这种签名很容易产生。l对于接收方，应该很容易验证签名的真伪。l对于给定的x，找出y(yx)使得签名Sig(y)=Sig(x)在计算上是不可行的。l找出任意两个不同的输入x、y，使得Sig(y)=Sig(x)在计算上是不可行的。2023/2/1439第39页，本讲稿共48页2023/2/145.4.1 基本概念基本概念l数字数字签签名体制的名体制的组组成成l签名生成算法：对消息m的签名可记为Sig(m)=s。签名密钥是秘密的。l签名验证算法：对签名s的验证可记为Ver(s)=真，伪=0,1。验证密钥应当公开。l常用的数字常用的数字签签名体制名体制lRSA签名体制lDSA签名体制lElGamal签名体制lRabin签名体制40第40页，本讲稿共48页2023/2/145.4.1 基本概念基本概念l数字签名的分类数字签名的分类l直接数字签名：发送者直接把消息和签名发送给接收者，接收者直接利用发送者公钥验证签名。l基于仲裁的数字签名：发送者把消息和签名经由称做仲裁者的可信第三方发送给接收者。接收者不能直接地验证签名，签名的合法性是通过仲裁者来检验。41第41页，本讲稿共48页2023/2/145.4.1 基本概念基本概念l数字数字签签名与手写名与手写签签名的区名的区别别l签名绑定方式：手写签名与文件自然绑定；数字签名中签名和消息需要借助算法绑定。l签名伪造难易程度：手写签名相对不安全，比较容易被伪造；数字签名过程需用到签名者的私钥，签名难以伪造。l签名复制难易程度：手写签名难以拷贝，因为手写签名拷贝容易与原签名区别开来；数字签名容易被拷贝，因为有效数字签名的拷贝同样有效，这就需要在消息中包涵其它信息（时间戳）来阻止数字签名的重复使用。42第42页，本讲稿共48页2023/2/145.4.2 RSA签签名体制名体制43签名生成过程签名生成过程签名验证过程签名验证过程第43页，本讲稿共48页5.4.3 DSA签签名名算法算法2023/2/1444第44页，本讲稿共48页5.4.4 多重数字签名多重数字签名l应用场景应用场景l需要两个或多个人同时对一份文件进行签名。2023/2/1445第45页，本讲稿共48页5.4.5 不可抵赖数字签名不可抵赖数字签名l l应用场景应用场景l l在没有签名方的同意下，接收方不能把签名给第在没有签名方的同意下，接收方不能把签名给第三者看。三者看。l l算法思想算法思想l l（1 1）AliceAlice向向BobBob出示一个签名。出示一个签名。l l（2 2）BobBob产生一个随机数并送给产生一个随机数并送给AliceAlice。l l（3 3）AliceAlice利用随机数和其私钥进行计算，并将计利用随机数和其私钥进行计算，并将计算结果发送给算结果发送给BobBob。AliceAlice只能计算该签名是否有效。只能计算该签名是否有效。l l（4 4）BobBob确认这个结果。确认这个结果。2023/2/1446第46页，本讲稿共48页5.4.6 数字数字盲签名盲签名l应用场景应用场景l希望Bob对文件签名，但不希望他知道文件的（准确）内容。（采用“分割选择技术”）l算法原理算法原理2023/2/1447第47页，本讲稿共48页2023/2/14作作业业lP90：2，5，748第48页，本讲稿共48页
