1、12024/3/192024/3/1912024/3/192024/3/1912024/3/192024/3/191 16.3.2 SHA-1散列算法散列算法NIST在1993年发布了一个哈希算法称为安全HASH算法，1995年修改，修改后的版本是SHA-1，这个版本是当前使用最广泛的哈希算法。SHA-1接受输输入消息入消息的最大长度为264-1 bits，生成生成160 bits的消息摘要的消息摘要。SHA-1算法操作首先对输入消息划分消息划分为512-bit块，若最后一个数据块不满足长度要求，按照一定规则进行填充填充为512-bit块。然后每个512-bit块重复使用分重复使用分块处块处理
2、函数理函数，最终输出160 bits哈希值。22024/3/192024/3/1922024/3/192024/3/19232024/3/192024/3/1932024/3/192024/3/193 1）SHA-1算法算法预处理预处理42024/3/192024/3/1942024/3/192024/3/19452024/3/192024/3/1952024/3/192024/3/1953/19/20245（1）消息由704位二进制组成。先划分第一个分组：704-512=192第二个分组填充：先填充一个“1”，填充“0”的个数位：448-1-192=255最后64个比特填充消息的二进制长度。
3、（2）消息由448位二进制组成。已经448bits了，又必须填充1，故填充后消息为2个分组。故先填充一个“1”，然后用“0”把第1个分组填满。再把第2个分组的前448比特然后用“0”填充，剩下最后64比特填充消息的二进制长度。62024/3/192024/3/1962024/3/192024/3/196如果消息长度为480bits呢？72024/3/192024/3/1972024/3/192024/3/1973/19/20247实际上，在编程的时候应当分为2种情况：（1）消息的最后分组小于448比特，即56个字节，这种情况的填充方式容易理解；（2）消息的最后分组长度大于等于448比特，这种情
4、况会增加一个分组。另外，按照现在计算机的编码方式，消息的长度总是8的整数倍。编程时，先分组再算消息摘要，还是读一组计算一组？文件很大呢？多线程？-内存映射文件的方式82024/3/192024/3/1982024/3/192024/3/19892024/3/192024/3/1992024/3/192024/3/199102024/3/192024/3/19102024/3/192024/3/1910数据扩展112024/3/192024/3/19112024/3/192024/3/1911122024/3/192024/3/19122024/3/192024/3/1912132024/3/1
5、92024/3/19132024/3/192024/3/19132）SHA-1算法算法512-bit分块处理过程分块处理过程SHA-1算法以512-bit分块为单位进行循环处理，处理过程为：第一个512-bit分块与160-bit初始IV变量作为输入，通过分块处理压缩函数，输出160bits数据块；然后，第二512-bit分块和第一个分块处理最后输出160-bit数据块作为输入，通过分块处理处理压缩函数，输出160bits数据块；依次，直到最后一个512-bit子块处理完成，最后输出160 bits数据块为输入原始消息的哈希值，如图所示142024/3/192024/3/19142024/3/
6、192024/3/1914152024/3/192024/3/19152024/3/192024/3/1915162024/3/192024/3/19162024/3/192024/3/1916（1）逻辑函数(?)分块处理中需要使用结构相似的四个基本逻辑函数：f1，f2，f3，f4，每个回合使用不同的逻辑函数，f1，f2，f3，f4逻辑函数的定义如下所示：172024/3/192024/3/19172024/3/192024/3/1917（4）压缩函数寄存器A、B、C、D，E数据通过压缩函数变换182024/3/192024/3/19182024/3/192024/3/1918回合回合步骤步骤
7、输入常数输入常数取值方式取值方式(整数整数)1Kt=5A827992Kt=6ED9EBA13Kt=8F1BBCDC4Kt=CA62C1D6192024/3/192024/3/19192024/3/192024/3/19193）SHA-1算法伪代码算法伪代码202024/3/192024/3/19202024/3/192024/3/1920212024/3/192024/3/19212024/3/192024/3/19214.5Fort=0to79T=ROTL5(A)+f1(B,C,D)+E+Wt+KtE=D；D=C；C=ROTL30(B)；B=A；A=TEnd；222024/3/192024/
8、3/19222024/3/192024/3/1922EndFor5.return哈希值(H0|H1|H2|H3|H4)备注：伪代码中+表示模加232024/3/192024/3/19232024/3/192024/3/19232024/3/192024/3/192323例例:对字符串对字符串”abc”，运用，运用SHA-1求散列值求散列值首先首先”abc”二进制表示为：二进制表示为：01100001 01100010 01100011，共，共24位长度位长度SHA-1算法：算法：第一步：第一步：按照按照SHA-1要求，填充数据要求，填充数据 5126424424（填充（填充1位位“1”，423
9、位位“0”，及，及 1000000)512位的输入数据为位的输入数据为(十六进制表示十六进制表示）：）：61626380 00000000，,00000018故故 W0=61626380,W1=W2=W14=00000000,W15=00000018第二步第二步：初始化初始化 A、B、C 与与 D 缓缓存器，如下：存器，如下：A：67 45 23 01 B：EF CD AB 89 C：98 BA DC FE D：10 32 54 76 E：C3 D2 E1 F0-实例实例242024/3/192024/3/19242024/3/192024/3/19242024/3/192024/3/1924
10、24第三步第三步：进入进入第一第一轮次运算轮次运算，执行执行 2020 回合回合：A A,B,C,D,E,B,C,D,E(E+fE+f1 1(t,B,C,D(t,B,C,D)+)+S S5 5(A)+W(A)+Wt t+K Kt t),A,S,A,S3030(B),C,D(B),C,D)求求A A,B,C,D,B,C,D的值。的值。SHA-1散列算法后面的与步骤散列算法后面的与步骤3类似计算。类似计算。由标准可知，若输入字符串由标准可知，若输入字符串”abc”，SHA-1算法算法160 bits哈希值为：哈希值为：a9993e36 4706816aba3e2571 7850c26c 9cd0d
11、89d252024/3/192024/3/19252024/3/192024/3/19256.3.3 SHA-256、SHA-384和和SHA-512*在2002年，相继对SHA系列算法进行扩展，提出SHA-256、SHA-384、SHA-512，并称为SHA-2。SHA-256与SHA-1算法一样，以512-bit分块为基本处理单位，每分块又划分为16个32-bit字进入哈希函数中处理操作。而SHA-384、SHA-512与SHA-1算法不同，是以1024-bit分块为基本处理单位，每分块是划分为16个64-bit字进入哈希函数中处理操作。262024/3/192024/3/19262024
12、/3/192024/3/1926-SHA-SHA参数比较：参数比较：参数比较：参数比较：272024/3/192024/3/19272024/3/192024/3/19276.3.4 SHA-3 算法算法自2007年，NIST发起了SHA-3竞赛以征集新的Hash算法以来，截止到 2010 年 10 月，第二轮遴选结束，共有五种算法进入最终轮遴选，入选的五个算法是：BLAKE、Grstl、JH、Keccak、Skein，到2012年，NIST最终选择Keccak算法作为SHA-3标准(即美国的FIPS PUB 202）。SHA-3为了与SHA-2完全兼容，SHA-3中也提出了4个Hash算法S
13、HA3-224,SHA3-256,SHA3-384,SHA3-512，可完全替换SHA-2。282024/3/192024/3/19282024/3/192024/3/1928Keccak算法是由 Guido Bertoni，Joan Daemen，Michal Peeters，以及Gilles Van Assche设计的。作为SHA家族最新的算法，其采用了不同于传统MD结构，而选择了海绵构造（sponge结构）。通过采用这种结构，常用于MD结构的攻击方法难以进行，增加了其算法安全性。292024/3/192024/3/19292024/3/192024/3/19292024/3/192024
14、/3/1929296.3.5 Hash散列算法的应用（略）散列算法的应用（略）Hash算算列列函函数数由由于于其其单单向向性性和和随随机机性性的的特特点点,主主要要运运用用于于提提供供数数据据完完整整性性(包包括括数数字字签签名名、以以及及与与数数字字签签名名联联系系起起来来的的数数字字指指纹纹的的应应用用)知知识识证证明明、密密钥钥推推导导、伪伪随随机机数生成等方面。数生成等方面。1生成程序或文档的生成程序或文档的“数字指纹数字指纹”-完整性验证完整性验证302024/3/192024/3/19302024/3/192024/3/19302024/3/192024/3/1930302用于安全
15、存储口令用于安全存储口令http:/ 散列算法的攻击现状（略）散列算法的攻击现状（略）散列函数主要用于数据完整性验证，确定消息是否被修改，因此对散列函数攻击因此对散列函数攻击的目标是生成这样的修改后的消息：的目标是生成这样的修改后的消息：其散列值与原有消息的散列值相等其散列值与原有消息的散列值相等。对散列函数的攻击可以分为如下几类：对散列函数的攻击可以分为如下几类：对散列函数的攻击可以分为如下几类：对散列函数的攻击可以分为如下几类：2024/3/192024/3/193131322024/3/192024/3/19322024/3/192024/3/19322024/3/192024/3/19
16、3232 目前，对散列函数的碰撞攻击最重要的平凡攻击是生日攻击。生日攻击的名字起源于所谓的生日悖论，严格来说，它它并并不不是是一一个个真真正正的的悖悖论论，只只是是一一个个令令人人吃吃惊的概率问题惊的概率问题。生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即HashHash值值值值的的的的长长长长度度度度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够的长。6.4.1 生日悖论问题生日悖论问题 生日悖论是这样一个问题：在在k k个个人人中中至至少少有有两两个个人人的的生生日日相相同同的的概概率率大大于于0.50.5时时，k k至少多大？至
17、少多大？绝大多数人回答这个问题时候会认为是一个很大的数，事实上是非常小的一个数。为了回答这一问题，下面我们给出计算方法：为了回答这一问题，下面我们给出计算方法：332024/3/192024/3/19332024/3/192024/3/19332024/3/192024/3/193333 （1）对于进入房间的第一个人来说，有365个不同的生日；（2）对于第二个进入房间时，有364个与第一个人不是同一天生日的可能，因此不匹配概率为364/365；（3）对于第三个人进入房间时，有363个与前两个人不是一天生日，因此现在不匹配的概率为：匹配概率为：匹配概率为：（4）但k个人进入房间时，不匹配概率的一
18、般公式为：匹配概率为：匹配概率为：342024/3/192024/3/19342024/3/192024/3/19342024/3/192024/3/193434 （5）当k=23时，概率为0.5073，即在23个人中至少有两个人生日相同的概率大于0.5。若k取100，则概率0.9999997，即获得如此大的概率。之所以称这一问题是悖论是因为当人数之所以称这一问题是悖论是因为当人数k给定时，得到的至少有两个人的生日相给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。同的概率比想象的要大得多。这是因为在这是因为在k个人中考虑的是任意两个人的生日是否相同，在个人中考虑的是任意两个人的生日
19、是否相同，在23个人中可能的情个人中可能的情况数为况数为 。将将生生日日悖悖论论推推广广：已知一个在1到n之间均匀分布的整数型随机变量，若该变量的k个取值中至少有两个取值相同的概率大于0.5，则k至少多大？352024/3/192024/3/19352024/3/192024/3/19352024/3/192024/3/1935356.4.2 生日攻击生日攻击 Yuval生日攻击实例生日攻击实例：假假设设用用户户A采采用用散散列列函函数数作作为为签签名名发发送送给给B，A能能够够利利用用Yuval生生日日攻攻击欺骗击欺骗B，具体过程如下：具体过程如下：(1)设设用用户户A预预先先准准备备了了两
20、两条条不不同同的的消消息息，例例如如一一份份合合同同的的两两种种不不同同版版本，一种是对本，一种是对B有利的合同，另外一种将使有利的合同，另外一种将使B破产的合同；破产的合同；362024/3/192024/3/19362024/3/192024/3/1936 (2)A对对这这两两种种不不同同版版本本的的合合同同每每一一份份都都作作一一些些细细微微的的改改变变(例例如如对对文文件件，A可可在在文文件件的的单单词词之之间间插插入入很很多多“空空格格-退退格格-空空格格”字字符符对对，然然后后将将其其中中的的某某些些字字符符对对替替换换为为“空空格格-退退格格-空空格格”就就得得到到一一个个变变形
21、形的的消消息息)，并分别计算散列值；并分别计算散列值；(4)A将对将对B有利的合同和散列值提交给有利的合同和散列值提交给B请求签字，然后返回给请求签字，然后返回给A372024/3/192024/3/19372024/3/192024/3/19372024/3/192024/3/193737 上述攻击中如果散列值的长为上述攻击中如果散列值的长为64比特，比特，则则A攻击成功所需的时间复杂度为攻击成功所需的时间复杂度为O(232)，那么那么64位的散列函数对付生日攻击显然太小。位的散列函数对付生日攻击显然太小。大多数的单向散列函数产生大多数的单向散列函数产生128位的散列（如位的散列（如MD5）
22、，），这样试图进行生日的这样试图进行生日的攻击的攻击者必须对攻击的攻击者必须对264个随机消息进行散列运算才能找到散列值相同的消息。个随机消息进行散列运算才能找到散列值相同的消息。目前目前NIST在其安全散列标准（在其安全散列标准（SHS）中用的是中用的是160位的散列值（如位的散列值（如SHA-1），），这样生日攻击就更难进行，需要对这样生日攻击就更难进行，需要对280个随机消息进行散列运算。个随机消息进行散列运算。382024/3/192024/3/19382024/3/192024/3/1938-hash-hash函数小结：函数小结：392024/3/192024/3/19392024/
23、3/192024/3/19396.5 消息认证消息认证6.5.1 消息认证的基本概念消息认证是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未重排、重放、延迟）。消息认证过程中检验内容应包括：（1）证实消息的源和宿；（2）消息内容是否曾受到偶然的或有意的篡改；（3）消息的序号和时间先后。402024/3/192024/3/19402024/3/192024/3/1940总之，消息认证使接收者能识别：消息的源，内容的真伪，时间性和信宿。这种认证只在相应通信的双方之间进行，而不允许第三者进行上述认证。认证不一
24、定是实时的，可用消息认证码MAC（MessageAuthenticationcode）对消息做认证。消息认证码是指消息被一密钥控制的公开函数作用后产生的，用作认证符的固定长度的数值，也称为密码校验和或者MAC值。消息认证码目的是确认完整性并进行认证技术。根据任意长度消息输出固定长度的数据，这点与Hash函数类似，但是与Hash函数不同，计算MAC值必须持有共享密钥，没有共享密钥的人无法计算MAC值。412024/3/192024/3/19412024/3/192024/3/1941与Hash函数一样，哪怕消息发送1 bit的变化，MAC值也会产生变化，消息认证码利用这一特性来达到确认完整性目的
25、。因此，消息认证码也可以理解为上一种与密钥相关联的单向Hash函数。消息认证码主要包括基于分组密码设计的MAC和基于Hash的MAC。1基于分组密码的MAC目前，大多数消息认证码都是基于分组密码，它们有相对较短比特长度或短密码（如基于DES-CBC的MAC是56 bits），MAC函数与加密算法类似，不同之处为MAC函数不必是可逆的，因此与加密算法相比更不易被攻破，提供足够安全。CBC-MAC算法是最常用的一种基于分组的MAC算法，如图所示。422024/3/192024/3/19422024/3/192024/3/1942基于分组密码的CBC-MAC算法，其初始变量 取值为零，然后把需要认证
26、的数据 进行分组，分组的长度由所选的分组密码算法所决定，若最后一组数据不够分组规定长度，则需要进行必要的填充，最简单填充方法在其后补零.注意虚线框432024/3/192024/3/19432024/3/192024/3/19432基于Hash的MAC为了提供数据认证和数据完整性保证，也常使用基于Hash的MAC算法产生MAC消息认证码。下面介绍一种基于MD5的MAC算法（MD5-MAC算法），如下图所示。MD5-MAC算法的是由MD5算法经过变换得到，记为MD5，它的性能与MD5接近，在软件实现中慢5%20%，具体算法如下：442024/3/192024/3/19442024/3/19202
27、4/3/1944452024/3/192024/3/19452024/3/192024/3/19453消息认证码的使用方式基于消息认证码的认证过程，前提条件是通信双方共享一密钥K。设Alice欲发送给Bob的消息是M，Alice首先计算MAC=CK(M)，其中CK()是密钥控制的公开函数，然后向Bob发送MMAC，B收到后做与A相同的计算，求得一新MAC，并与收到的MAC做比较，如图所示。462024/3/192024/3/19462024/3/192024/3/1946如果仅收发双方知道密钥K，且Bob计算得到的MAC与接收到的MAC一致，则这一系统就实现了以下功能：（1）接收方Alice相
28、信发送方Bob发来的消息未被篡改。（2）接收方Bob相信发送方Alice不是冒充的。上述过程中只提供认证性而未提供保密性。472024/3/192024/3/19472024/3/192024/3/1947为了提供认证同时提供消息保密性，可在MAC函数作用之后，进行一次加密，若采用对称密码算法，算法密钥也需被收发双方共享。上图中，上图中，M M与与MACMAC链接后再被整体加密，消息认证与明文相关消息认证链接后再被整体加密，消息认证与明文相关消息认证与机密性（与机密性（与明文相关与明文相关）482024/3/192024/3/19482024/3/192024/3/1948 上图中，上图中，M
29、 M先被加密再与先被加密再与MACMAC链接后发送，消息认证与密文相关（链接后发送，消息认证与密文相关（与密与密文相关文相关）492024/3/192024/3/19492024/3/192024/3/19496.5.2 HMACHMAC是由H.Krawezyk，M.Bellare，R.Canetti于1996年提出的一种基于Hash函数和密钥进行消息认证的方法，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以应用。HMAC所能提供的消息认证包括两方面内容：（1）消息完整性认证：能够证明消息内容在传送过程没有被修改。（2）信源身份认证：因为通信双方共享了认证的密钥，接
30、收方能够认证发送该数据的信源于所宣称的一致，即能够可靠的确认接收的消息与发送的一致。1.HMAC的设计目标（RFC2104中列举的）：（1）不必修改而直接使用现有Hash函数502024/3/192024/3/19502024/3/192024/3/1950(2)如果找到或者需要更快或更安全的Hash函数，应能很容易地替代原来嵌入的Hash函数；(3)应保持Hash函数原有的性能，不因用于HMAC而使其性能降低；(4)以简单方式使用和处理密钥；(5)如果已知嵌入的Hash函数的强度，易于分析HMAC用于认证时的密码强度。2.HMAC算法描述：HMAC算法计算前需要进行预定义和预处理，如右图所示
31、。512024/3/192024/3/19512024/3/192024/3/1951522024/3/192024/3/19522024/3/192024/3/1952532024/3/192024/3/19532024/3/192024/3/1953542024/3/192024/3/19542024/3/192024/3/19546.5.3 MAC的应用（略）的应用（略）消息认证码（MAC），HMAC算法被广泛应用于因特网安全协(SSL/TLS、SSH、IPsec、3GPP、WiMax)以及金融部门的信贷交易。MAC是带秘密密钥Hash函数，它可以防止数据被未经授权的篡改。下面以HMAC
32、-SHA1算法为例，简单介绍一下HMAC消息认证算法在IP电话记费上的应用（如左下图所示）。当用户使用IP电话，只须直接拨入所叫的电话号码即可，智能终端则自动拨向IP服务商，待响应后,服务器返回一个随机值给智能终端，并在会话中记录这个随机值，客户端将该随机值作为密钥，用户密码进行HMAC运算；然后将终端序列号、主叫电话号码、认证码一同发给服务商（智能终端序列号相当于公钥，服务器发送的随机值相当于用户的密钥），智能终端对密钥进行HMAC协议的MAC运算自动生成认证码；服务器接收数据码流，根据终端序列号确定用户的基本信息，再通过数据库中存储的认证码与接收到认证码的比较，确认用户的合法身份。如身份无误，则接通话路，计时收费。552024/3/192024/3/19552024/3/192024/3/1955562024/3/192024/3/19562024/3/192024/3/1956
