《网络安全与保密》课件第3章

第3章单向散列函数3.1MD5算法3.2安全散列函数(SHA)3.3消息认证码(MAC)参考文献思考题

在很多情况下，我们需要鉴别和认证用户。如用户登录计算机(或自动柜员机等)时，计算机往往需要知道用户是谁，确认是某个用户而不是其他人在冒充，传统的方法是用口令来解决这个问题。用户在登录计算机前输入其口令，由计算机确认口令正确后用户才可登录计算机。用户和计算机均知道口令。用户每次登录均需输入口令。由于计算机需要知道口令，这就需要把口令保存在计算机中。这为入侵计算机偷取口令提供了可能。为此，我们不直接保存口令本身，而保存口令的散列值(口令的某种表示形式)。

当用户输入口令后，计算机先计算口令的散列值并与保存在计算机中的散列值进行比较，以此来鉴别用户。由于用来计算散列值的单向函数具有单向性，即根据散列值不可能逆向恢复出口令，从而即使获得了由口令产生的散列值表也无法知道用户的口令。

上面提到的散列值是由单向散列函数产生的。所谓的单向散列函数(哈希函数、杂凑函数，hashfunction)是将任意长度的消息M映射成一个固定长度散列值h的函数

h = H(M)

其中，h的长度为m。

散列函数要具有单向性，则必须满足如下特性：

(1)给定M，很容易计算h。

(2)给定h，根据H(M) = h反推M很难。

(3)给定M，要找到另一消息M′ 并满足H(M) = H(M′)很难。

在某些应用中，单向散列函数还需要满足抗碰撞(collision)的条件：要找到两个随机的消息M和M′，使H(M) = H(M′)满足很难。

在实际中，单向散列函数是建立在压缩函数的想法之上，如图3-1所示。图3-1HASH函数工作模式

给定一任意长度的消息输入，单向函数输出长为m的散列值。压缩函数的输入是消息分组和前一分组的输出(对第一个压缩函数，其输入为消息分组1和初始化向量IV)；输出是到该点的所有分组的散列，即分组Mi的散列为

hi = f(Mi，hi-1)

该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入。最后一分组的散列就是整个消息的散列。

单向散列函数还经常用于消息认证(防篡改)、数字签名。本章将介绍几种常用的单向散列函数。

3.1MD5算法

3.1.1算法MD表示消息摘要(MessageDigest)。MD5是MD4的改进版，算法对输入的任意长度消息产生128位散列值(或消息摘要)。MD5算法可由图3-2表示。由图3-2可知，MD5算法包括以下5个步骤。图3-2MD5算法

1．附加填充位

首先填充消息使其长度为一个比512的倍数小64位的数。填充方法是：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1～512。

2．附加长度

将原消息长度的64位表示附加在填充后的消息后面。当原消息长度达大于264时，用(消息长度mod264)填充。这时消息长度恰好是512的整数倍。令M[01…N-1]为填充后消息的各个字(每字M[i]为32位)，N是16的倍数。

3．初始化MD缓冲区

初始化用于计算消息摘要的128位缓冲区。这个缓冲区由4个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)：

4．按512位的分组处理输入消息

这一步为MD5的主循环，包括四轮，如图3-3所示。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。图3-3单个512比特分组的MD5主循环处理

图3-3中，四轮的操作类似，每一轮进行16次操作。每一轮的操作过程如图3-4所示。图3-4MD5某一轮的执行过程

四轮操作的不同之处在于每轮使用的非线性函数不同，在第一轮操作之前首先把A、B、C、D复制到另外的变量a、b、c、d中。这四个非线性函数分别为(其输入输出均为32位字)

其中，∧表示按位与；表示按位或；～表示按位反；⊕表示按位异或。

此外，由图3-4可知，这一步中还用到了一个有64个元素的表T[1…64]，T[i] = 232 × abs(sin(i))，i的单位为弧度。

根据以上描述，将这一步骤的处理过程归纳如下：

5．输出

由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。

以上就是对MD5算法的描述。MD5算法的运算均为基本运算，比较容易实现且速度很快。

3.1.2举例

在本章的参考文献[1]中，给出了实现MD5的C源代码。我们以求字符串“abc”的MD5散列值为例来说明上面描述的过程。“abc”的二进制表示为011000010110001001100011。

(1)填充消息：消息长l=24，先填充1位‘1’，然后填充423位‘0’，再用消息长，24，即0x0000000000000018填充。则

(2)初始化：

(3)主循环：利用2.1.1中描述的过程对字块1(本例只有一个字块)进行处理。变量a、b、c、d每一次计算后的中间值可根据参考文献[1]提供的C源代码得到，这里不详细列出。

(4)输出：消息摘要=900150983cd24fb0d6963f7d28e17f72

3.2安全散列函数(SHA)

3.2.1算法SHA是美国NIST和NSA共同设计的安全散列算法(SecureHashAlgorithm)，用于数字签名标准DSS(DigitalSignatureStandard)。SHA的修改版SHA-1于1995年作为美国联邦信息处理标准公告(FIPSPUB180-1)发布[2]。SHA-1产生消息摘要的过程类似MD5，如图3-5所示。SHA-1的输入为长度小于264位的消息，输出为160位的消息摘要。具体过程如下。图3-5SHA-1算法

1．填充消息

首先将消息填充为512位的整数倍，填充方法和MD5完全相同：先填充一个1，然后填充一定数量的0使其长度比512的倍数少64位；接下来用原消息长度的64位表示填充。这样，消息长度就成为512的整数倍。以M0、M1、…、Mn表示填充后消息的各个字块(每字块为16个32位字)。

2．初始化缓冲区

在运算过程中，SHA要用到两个缓冲区，两个缓冲区均有5个32位的寄存器。第一个缓冲区标记为A、B、C、D、E；第二个缓冲区标记为H0、H1、H2、H3、H4。此外，运算过程中还用到一个标记为W0、W1、…、W79的80个32位字序列和一个单字的缓冲区TEMP。在运算之前，初始化{Hj}：

3．按512位的分组处理输入消息

SHA运算主循环包括4轮，每轮20次操作。SHA用到一个逻辑函数序列f0、f1、…、f79。每个逻辑函数的输入为3个32位字，输出为一个32位字。定义如下(B、C、D均为32位字)：

其中运算符的定义与3.1节中MD5运算中的相同。

SHA运算中还用到了常数字序列K0、K1、…、K79，其值为：

SHA算法按如下步骤处理每个字块Mi：

4．输出

在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。

3.2.2SHA-1与MD5的比较

SHA-1与MD5的比较如表3-1所示。

3.2.3举例

我们以求字符串“abc”的SHA-1散列值为例来说明上面描述的过程。“abc”的二进制表示为011000010110001001100011。

(1)填充消息：消息长l = 24，先填充1位‘1’，然后填充423位‘0’，再用消息长24即0x0000000000000018填充。

(2)初始化：

(3)主循环：处理消息字块1(本例中只有1个字块)，分成16个字：

然后根据3.2.1节中描述的过程计算，其中循环“fort=0to79”中，各步A、B、C、D、E的值如下：

3.3消息认证码(MAC)

与密钥相关的单向散列函数通常称为MAC，即消息认证码MAC = CK(M)其中，M为可变长的消息；K为通信双方共享的密钥，C为单向函数。

MAC可为拥有共享密钥的双方在通信中验证消息的完整性；也可被单个用户用来验证他的文件是否被改动。如图3-6所示。图3-6MAC应用于消息认证

HMAC全称为keyed-hashmessageauthenticationcode，它用一个秘密密钥来产生和验证MAC[3]。

为了论述的方便，首先给出HMAC中用到的参数和符号如下。

B：计算消息摘要时输入块的字节长度(如对于SHA-1，B=64)。

H：散列函数如SHA-1、MD5等。

ipad：将数值0x36重复B次。

opad：将数值0x5c重复B次。

K：共享密钥。

K0：在密钥K的左边附加0使其为B字节的密钥。

L：消息摘要的字节长度(如对于SHA-1，L=20)。

t：MAC的字节数。

TEXT：要计算HMAC的数据。数据长度为n字节，n的最大值依赖于采用的hash函数。

X||Y：将字串连接起来，即把字串Y附加在字串X后面。

异或。

密钥K的长度应大于或等于L/2。当使用长度大于B的密钥时，先用H对密钥求得散列值，然后用得到的L字节结果作为真正的密钥。

利用HMAC函数计算数据text的MAC过程如图3-7所示。图3-7HMAC

由图可知，HMAC执行的是如下操作：

HMAC算法可以和任何密码散列函数结合使用，而且对HMAC实现作很小的修改就可用一个散列函数H代替原来的散列函数H′。

参考文献

[1]RRivest.TheMD5Message-DigestAlgorithm.RFC1321，April1992[2]NationalInstituteofStandardsandTechnology，FIPSPUB180-1.SecureHashStandard.U.S.DepartmentofCommerce，April1995

[3]NationalInstituteofStandardsandTechnology，FIPSPUB#HMAC.TheKeyed-HashMessageAuthenticationCode(HMAC).U.S.DepartmentofCommerce，DRAFT，2001

[4]MihirBellare，RanCanetti，HugoKrawczyk.MessageAuthenticationusingHashFunctions－TheHMACConstruction.RSALaboratoriesCryptoBytes，Vol.2，No.1，Spring1996

思考题

[1]概述MD4和MD5各自的优缺点。[2]假定a1a2a3a4是一个32比特字中