散列函数

 

散列（HASH）函数H也称哈希函数或杂凑函数等，是典型的多到一的函数，其输入为一可变长x（可以足够的长），输出一固定长的串h（一般为128位、160位，比输入的串短），该串h被称为输入x的Hash值（或称消息摘要Message Digest、指纹、密码校验和或消息完整性校验)，计作h=H(x)。为防止传输和存储的消息被有意或无意地篡改，采用散列函数对消息进行运算生成消息摘要，附在消息之后发出或与信息一起存储，它在报文防伪中具有重要应用。

消息摘要采用一种单向散列算法将一个消息进行换算。在消息摘要算法中，文件数据作为单向散列运算的输入，这个输入通过HASH函数产生一个散列值。如果改动了文件，散列值就会相应地改变，接收者即能检测到这种改动过的痕迹。从理论上来讲，攻击者不可能制造一个替用的消息来产生一个完全相同的消息摘要。Hash函数可用于数字签名、消息的完整性检测、消息的起源认证检测等。

散列函数是安全的是指它具有：

一致性：相同的输入产生相同的输出。

随机性：消息摘要外观是随机的，以防被猜出源消息。

唯一性：几乎不可能找到两个消息产生相同的消息摘要。

单向性：即如果给出输出，则很难确定出输入消息。

Hash函数H一般满足以下几个基本要求：

（1）输入x可以为任意长度；输出数据串长度固定；

（2）正向计算容易，即给定任何x，容易算出H(x)；反向计算困难，即给出一Hash值h，很难找出一特定输入x，使h=H(x)；

（3）抗冲突性（抗碰撞性），包括两个含义，一是给出一消息x，找出一消息y使H(x)=H(y)是计算上不可行的（弱抗冲突），二是找出任意两条消息x、y，使H(x)=H(y)也是计算上不可行的（强抗冲突）。

对Hash函数有两种穷举攻击。一是给定消息的Hash函数H(x)，破译者逐个生成其他文件y，以使H(x)=H(y)。二是攻击者寻找两个随机的消息：x，y，并使H(x)=H(y)。这就是所谓的冲突攻击。穷举攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于Hash值的长度。由以下的生日问题分析我们知道Hash值必须足够长，比如160位。

 

我们来看生日问题。在一个教室中最少应有多少学生才使得找一个学生与某人生日（该人也在教室）相同的概率不小于1/2？答案是254人。但至少有两个学生的生日在同一天的概率不小于1/2的答案出人意料地低，仅为23人。以下进行详细分析。

一个人与一个已知生日的人不是同生日的概率是364/365，假如教室有t个人，则其余的人与某人都不同生日的概率是(364/365)^t-1，所以至少有一个人与此人同生日的概率是1-(364/365)^t-1。

第一个人的生日为一个特定生日，第二个人不在该日生的概率是(1-1/365)，第三个人与前两位不同生日的概率是(1-2/365)，第t个人与前t-1个人不同生日的概率是(1-(t-1)/365)，所以t个人都不同生日的概率是(1-1/365) (1-2/365)…(1-(t-1)/365)，利用1-x » e^-x(当x很小)，概率约为e^{-t(t-1)/（2*365）}，而至少有两个人生日相同的概率是1-(1-1/365) (1-2/365)…(1-(t-1)/365)。经过计算，我们有：t » 1.17*365^1/2 »22.3，即随机选择23人，至少有2人生日相同的概率至少为1/2。

 

寻找特定生日的一个人类似于第一种攻击；而寻找两个随机的具有相同生日的两个人则是第二种攻击。第二种方法通常被称为生日攻击（Birthday Attack）。

生日攻击意味着HASH值的长度有一个下界，128位的消息摘要，在1.17*2⁶⁴个随机HASH值中至少有1/2的概率发生一个碰撞。所以，通常建议用160位或更长的消息摘要。

 

单向散列函数通常用于提供消息或文件的指纹。与人类的指纹类似，由于散列指纹是唯一的，因而提供了消息的完整性和认证。发送者A向接收者B发送消息M的基本过程是：

（1）发送者写一消息M，并作为单向散列函数H的输入。

（2）消息摘要H(M)连消息M一齐发送

（3）接受者分离消息和消息摘要，并利用消息生成消息摘要。

（4）比较两消息摘要，如果相同，则消息在传送期间没被更改。

A → B ：M || H(M)

虽然大部分情况下，HASH函数是不需要密钥的，但根据应用不同，可以给HASH函数加上密钥，用于保护HASH结果的完整性，如HMAC。

如果发送者使用带密钥的HASH函数来产生HASH值的话，由于攻击者不知道密钥（发送文件的时候一般不会把密钥附带在文件上），所以，即使攻击者产生了假冒的HASH结果，接收者利用密钥进行验证的时候，同样会发现文件遭到了修改，从而保证了传输文件的完整性。利用上述方法产生的HASH结果就成为消息校验码MAC。

通过以下方式使用散列函数常提供消息鉴别：

（1）使用对称加密方法对附加消息摘要的报文进行加密（提供保密与鉴别）。

A → B ：E_k(M || H(M))

（2）使用对称加密方法对消息摘要进行加密（提供鉴别）。

A → B ： M || E_k(H(M))

（3）使用发方的私有密钥对消息摘要进行加密（提供鉴别和数字签名）。

A → B ： M || E_ka(H(M))

（4）在（3）的基础上，使用对称加密方法进行加密（提供鉴别和数字签名、保密）

A → B ： E_k(M || E_ka(H(M)))

（5）假定双方共享一个秘密值S，使用散列函数提供鉴别。

A → B ：M || H(M||S)

（6）假定双方共享一个秘密值S，使用散列函数、对称加密方法提供鉴别、数字签名、保密。

A → B ：E_k(M || H(M) ||S)

消息摘要使用几种有着些许差别的算法。其中两种最普遍、最流行的消息摘要方式是：RSA一MD2和RSA一MD5。一个消息摘要是一个加密校验和，不像CRC是一个算术校验和。常用的散列函数有：消息摘要4（MD4）算法、消息摘要5（MD5）算法、安全散列函数（SHA）。

MD5算法是对杂凑压缩信息块按512位进行处理的，首先它对杂凑信息进行填充，使信息的长度等于512的倍数。填充方法是首先在压缩信息后填充以字节长的信息长度，然后再用首位为1，后面全为0的填充信息填充，使经过填充后的信息长度为512的倍数，然后对信息依次每次处理512位，每次进行4轮，每轮16步总共64步的信息变换处理，每次输出结果为128位，然后把前一次的输出作为下一次信息变换的输入初始值（第一次初始值算法已经固定），这样最后输出一个128位的杂凑结果。目前MD5被认为是最安全的杂凑算法之一，现已经在很多应用中被当成标准使用。