您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第四讲-Hash函数及应用
1上讲的主要内容公钥密码体制的简介基于RSA的公钥密码算法数字证书的简介公钥密码体制的优缺点第四讲Hash函数及应用主讲人:谷利泽Email:glzisc@bupt.edu.cnTel:010-622840093本讲的要点掌握Hash函数的性质了解SHA-1算法的实现过程理解数字签名的基本思想理解消息认证的基本思想4引言在一个开放通信网络的环境中,信息面临的攻击包括窃听、伪造、修改、插入、删除、否认等。因此,需要提供用来验证消息完整性的一种机制或服务---消息认证。这种服务的主要功能包括:确保收到的消息确实和发送的一样;确保消息的来源真实有效;注:对称密码体制和公钥密码体制都可提供这种服务,但用于消息认证的最常见的密码技术是基于哈希函数的消息认证码。5认证码和检错码现代密码学中的消息认证码与通信学的消息检错码有密切的联系,并由其演变而来。检错码是检测由于通信的缺陷而导致消息发生错误的方法;认证码是用来检查因恶意或有目的等而致使消息发生变化的技术。6哈希(Hash)函数的简介也称散列函数、杂凑函数等,是一种单向密码体制,即它是一个从明文到密文的不可逆映射,即只有加密过程,不存在解密过程。同时,Hash函数可以将“任意”长度的输入经过变换以后得到固定长度的输出。Hash函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或数据块的“数据指纹”(也称消息摘要或散列值),因此在数据完整性和数字签名等领域有广泛的应用的,哈希函数在现代密码学中起着重要作用。7哈希函数的表示对不同长度的输入消息,产生固定长度的输出。这个固定长度的输出称为原输入消息的“散列”或“消息摘要”(MessageDigest)。公式表示形式:h=H(M)M:任意长度的消息H:哈希(Hash)函数或杂凑函数或散列函数h:固定长度的哈希值8哈希算法的性质(特点)输入:消息,任意有限长度。输出:哈希值,固定长度。容易计算:对干任意给定的消息,容易计算其哈希值。单向性:对于给定的哈希值h,要找到M使得H(M)=h在计算上是不可行的。9哈希算法的性质(安全性)抗弱碰撞性:对于给定的消息M1,要发现另一个消息M2,满足H(M1)=H(M2)在计算上是不可行的。抗强碰撞性:找任意一对不同的消息M1,M2,使H(M1)=H(M2)在计算上是不可行的。雪崩效应:当一个输入位发生变化时,输出位将有一半会发生变化。10哈希函数的一般结构fM0bIV=CV0nfM1bnCV1n„fML-1bnCVL-1n输入分组分组数链接变量哈希值长度初始值压缩函数输入分组的长度11哈希函数的核心技术设计无碰撞的压缩函数f,而攻击者对算法的攻击重点是压缩函数f的内部结构,由于压缩函数f和分组密码一样是由若干轮处理过程组成,所以对压缩函数f的攻击需通过对各轮之间的位模式的分析来进行,分析过程常常需要先找出压缩函数f的碰撞。由于是压缩函数,其碰撞是不可避免的。因此,在设计压缩函数f时就应保证找出其碰撞在计算上是不可行的。常用的散列函数:MD5;SHA系列;12SHA的简介美国国家标准技术研究所NIST于1993年开发的另一个散列算法称为SHA。两年之后,这个算法被修改为了今天广泛使用的形式。修改后的版本是SHA-1,是数字签名标准中要求使用的算法。SHA接受任何有限长度的输入消息,并产生长度为160比特的Hash值(MD5仅仅生成128位的摘要),因此抗穷举性更好。SHA-1设计时基于和MD4相同原理,它有5个参与运算的32位寄存器字,消息分组和填充方式与MD5相同,主循环也同样是4轮,但每轮进行20次操作,非线性运算、移位和加法运算也与MD5类似,但非线性函数、加法常数和循环左移操作的设计有一些区别。13SHA-1的结构消息M填充使分组恰好512位„M1M2Mt初始值fff„哈希值14SHA-1哈希值的生成过程消息NbitsL512bits消息长度L(mod264)HSHA-1160HSHA-1CV1160HSHA-1CVi160HSHA-1CVL-1160512哈希值填充(0to511bits)512512512M0512bitsM1512bitsMi512bitsML-1512bits„„100…0„„IV16015SHA-1对单个512位分组的处理过程f1,Kt,W[0…19]20步f2,Kt,W[20…39]20步f3,Kt,W[40…59]20步f4,Kt,W[60…79]20步hi(160比特)+++++模232加hi-1(160比特)Mi512比特ABCDEABCDEABCDEABCDE初始值:A=0x67452301B=0xefcdab89C=0x98badcfeD=0x10325476E=0xc3d2e1f016SHA-1生成字Wt的方法Mi(512bit)w0,w2,w3,w8wt-16,wt-14,wt-8,wt-3„W16WtW0W15„„++S1S1Wt=S1(Wt-16+Wt-14+Wt-8+Wt-3)(t=16,17,…,79)循环左移一位w63,w65,w71,w76„W79+S1„17SHA-1的基本操作A=E+ft(B,C,D)+S5(A)+Wt+Kt;B=A;C=S30(B);D=C;E=D;ABCDEABCDEfS30++++S5WtKtKt=0x5a827999(t=0,…,19)Kt=0x6ed9ebal(t=20,…,39)Kt=0x8f1bbcdc(t=40,…,59)Kt=0xca62c1d6(t=60,…,79)ft(X,Y,Z)=(X∧Y)∨(~X∧Z)(t=0,…,19)ft(X,Y,Z)=X⊕Y⊕Z(t=20,…,39)ft(X,Y,Z)=(X∧Y)∨(X∧Z)∨(Y∧Z)(t=40,…,59)ft(X,Y,Z)=X⊕Y⊕Z(t=60,…,79)Kt的4个取值2、3、5、10的平方根,然后再乘以230,最后取结果的整数部分。18哈希函数的应用数字签名消息认证口令的安全性文件的完整性密码协议的应用譬如可信计算、文件病毒的检验、网页防篡改、黑白名单等许多应用。譬如零知识证明、比特承诺、投掷硬币、电子商务的安全协议等许多应用。19数字签名的简介数字签名体制是以电子签名形式存储消息的方法,所签名的消息能够在通信网络中传输。在当今数字化的信息世界里,数字化文档的认证性、完整性和不可否认性是实现信息化的基本要求,也决定信息化的普及和推广。数字签名是满足上述要求的主要手段之一,也是现代密码学的主要研究内容之一。数字签名是日常生活中手写签名的电子对应物。20数字签名与手写签名的不同签名:手写签名是被签文件的物理组成部分;数字签名是连接到被签消息上的数字串。传输方式:数字签名和所签名的消息能够在通信网络中传输。手写签名使用传统的安全方式传输。验证:手写签名是通过将它与真实的签名进行比较来验证;而数字签名是利用已经公开的验证算法来验证。数字签名的复制是有效的;而手写签名的复制品是无效的。手书签字是模拟的,且因人而异。数字签字是0和1的数字串,因消息而异。21数字签名的含义所谓数字签名(DigitalSignature),也称电子签名,是指附加在某一电子文档中的一组特定的符号或代码,它是利用数学方法和密码算法对该电子文档进行关键信息提取并进行加密而形成的,用于标识签发者的身份以及签发者对电子文档的认可,并能被接收者用来验证该电子文档在传输过程中是否被篡改或伪造。22数字签名的安全要求签名是可以被验证的;接受者能够核实签名者对消息的签名。签名是不可伪造的;除了签名者,任何人(包括接受者)不能伪造消息的签名。签名是不可重用的;同一消息不同时刻其签名是有区别的。签名是不可抵赖的;签名者事后不能抵赖对消息的签名,出现争议时,第三方可解决争端;23数字签名方案的组成数字签名方案是由五元组组成的,即{P,S,K,Sig,Ver}。P:明文空间;S:签名空间;K:密钥空间;Sign:签名算法;Ver:验证算法;24数字签名的过程系统初始化过程:生成数字签名方案用到的所有参数。签名生成过程用户利用给定的算法对消息产生签名s=Sign(m)。签名验证过程验证者利用公开的验证方法对给定消息的签名进行验证,得出签名的有效性。Ver(s,m)=0或1。25数字签名的基本原理签名者A验证者BHash函数哈希值消息签名Hash函数哈希值签名有效签名无效签名算法A的私钥消息签名验证算法A的公钥公开信道消息26RSA数字签名方案(初始化)1。选取两个大素数p和q,两个数长度接近,1024位2。计算n=p*q,ψ(n)=(p-1)(q-1)3.随机选取整数e(1eψ(n)),满足gcd(e,ψ(n))=14.计算d,满足d*e=1(modψ(n))。注:n公开,p和q保密。e为公钥,d为私钥。27RSA数字签名方案(签名和验证)签名算法1.利用一个安全的Hash函数h来产生消息摘要h(m)。2.用签名算法计算签名s=Sigk(m)=h(m)dmodn。验证算法1.首先利用一个安全的Hash函数h计算消息摘要h(m)。2.用检验等式h(m)modn=semodn是否成立,若相等签名有效,否则,签名无效。28RSA数字签名方案(正确性)由于s=h(m)dmodnd*e=1(modψ(n))所以semodn=h(m)edmodn=h(m)kψ(n)+1modn=h(m)*h(m)kψ(n)modn=h(m)*(h(m)ψ(n))kmodn=h(m)29RSA数字签名方案(举例)初始化:假设A选取p=13,q=11,e=13,则有n=pq=143,φ(n)=(p-1)(q-1)=12×10=120。求解ed=13d≡1(mod120)得d=37。因此A的公钥为(n=143,e=13);私钥为d=37。签名过程:假定消息m的Hash值h(m)=16,则计算m签名s=h(m)dmodn=1637mod143=3。验证过程:接受者B收到签名后,计算semodn=313mod143=16,h(m)modn=16mod143=16,等式h(m)modn=semodn成立,因此,B验证此签名有效。30哈希函数的应用数字签名消息认证口令的安全性文件的完整性密码协议的应用31消息认证的概述网络系统安全一般要考虑两个方面:一方面,加密保护传送的信息,使其可以抵抗被动攻击;另一方面,就是要能防止对手对系统进行主动攻击,如伪造、篡改信息等。认证是对抗主动攻击的主要手段,它对于开放的网络中的各种信息系统的安全性有重要作用。认证可分为实体认证和消息认证。32消息认证的目的验证信息的来源是真实的,而不是伪造的,此为消息源认证。验证消息的完整性,即验证信息在传送或存储过程中是否被篡改。33消息认证码消息认证码(MAC,MessagesAuthenticationCodes),是与密钥相关的的单向散列函数,也称为消息鉴别码或是消息校验和。MAC与单向散列函数一样,但是还包括一个密钥。不同的密钥会产生不同的散列函数,这样就能在验证发送者的消息没有经过篡改的同时,验证是由哪一个发送者发送的。34消息认证的实现过程Hash函数哈希值消息认证码Hash函数哈希值认证有效认证无效消息认证码公开信道消息对称密钥K对称密钥K相等YN35HMAC的简介利用对称分组密码体制(如DES、AES)的密码分组链接模式(CBC)一直是构造MAC的最常见的方法。近几年,人们越来越感兴趣于利用哈希函数来设计MAC,这是因为像MD5、SHA-1这样的哈希函数,其软件执行速度比诸如DES这样的对称分组密码要快。然而,诸如SHA-1这样的哈希函数并不是专门为MAC而设计的,由于哈希函数不依赖于密钥,所以它不能直接用于MAC。目前,已经提出了许多方案将密钥加到现有的哈希函数中。HMAC是最受支持的方案,并且在Internet协议中(如SSL)中有应用。36HMAC的有效实现方案预计算对每条消息计算K+ipadS1fIVK+opadfIVM0M1ML-1„b位b位b位哈希函数n位填充至b位n位S0n位fn位HMAC(K,M)左边经填充0后的K,
本文标题:第四讲-Hash函数及应用
链接地址:https://www.777doc.com/doc-4229237 .html