sha1算法

SHA-1简介

安全散列算法SHA (Secure Hash Algorithm)是美国国家标准和技术局发布的国家标准FIPS PUB 180-1，一般称为SHA-1。其对长度不超过264二进制位的消息产生160位的消息摘要输出，按512比特块处理其输入。

SHA是一种数据加密算法，该算法经过加密专家多年来的发展和改进已日益完善，现在已成为公认的最安全的散列算法之一，并被广泛使用。

该算法的思想是接收一段明文，然后以一种不可逆的方式将它转换成一段（通常更小）密文，也可以简单的理解为取一串输入码（称为预映射或信息），并把它们转化为长度较短、位数固定的输出序列即散列值（也称为信息摘要或信息认证代码）的过程。散列函数值可以说时对明文的一种“指纹”或是“摘要”所以对散列值的数字签名就可以视为对此明文的数字签名。

消息摘要

定义：
消息摘要（Message Digest）又称为数字摘要(Digital Digest)。它是一个唯一对应一个消息或文本的固定长度的值，它由一个单向Hash加密函数对消息进行作用而产生。如果消息在途中改变了，则接收者通过对收到消息的新产生的摘要与原摘要比较，就可知道消息是否被改变了。因此消息摘要保证了消息的完整性。
消息摘要采用单向Hash函数将需加密的明文"摘要"成一串128bit的密文，这一串密文亦称为数字指纹(Finger Print)，它有固定的长度，且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。这样这串摘要便可成为验证明文是否是"真身"的"指纹"了。

SHA1哈希算法流程

对于任意长度的明文，SHA1首先对其进行分组，使得每一组的长度为512位，然后对这些明文分组反复重复处理。
每个明文分组的摘要生成过程如下：

（1）将512位的明文分组划分为16个子明文分组，每个子明文分组为32位。
（2）申请5个32位的链接变量，记为A、B、C、D、E。
（3） 16份子明文分组扩展为80份。
（4） 80份子明文分组进行4轮运算。
（5）链接变量与初始链接变量进行求和运算。
（6）链接变量作为下一个明文分组的输入重复进行以上操作。
（7）最后，5个链接变量里面的数据就是SHA1摘要。

具体实现过程

在进行散列值计算之前，先要对需要加密的数据进行预处理。这一预处理由三部分组成：消息填充、分割已填充消息(将填充后的消息等分成m位处理块)、为散列值计算设置初始化值。

1）消息填充
假设原始消息(M)的长度是L位。首先，在消息最后加一位“1”，接着在这位“1”后面补k个“0”，使得L+1+k(即补位后的消息长度)满足对512取模后余数是448。然后，添加最后的64位二进制数据，这64位二进制数据就是原始L位消息(M)长度的二进制表示。
alt text
经过补位后如下：

（2）分割已填充消息
经过消息填充后，还必须将数据划分成m位一组的N块的数据块来提供给下面的散列值计算过程。对于SHA-1加密算法，填充过的消息被分割成N(M(1),M(2),…，M(N))块，每块512位。(其长度正好为512位的整数倍，然后按512位的长度进行分组（block）)然后每组512位的输入块可以表示成16个32位的字，分别记为：M0(i),M1(i),…，M15(i)。
（3）设置初始散列值
初始散列值由下面5个32位的字组成，其16进制表示如下：
A=0x67452301，B=0xEFCDAB89，C=0x98BADCFE，D=0x10325476,E=0xC3D2E1F0。

（4）16份子明文分组扩展为80份
将这16份子明文分组扩充到80份子明文分组，我们记为W[k]（k= 0, 1,……79），扩充的方法如下。
$Wt = Mt , 当0≤t≤15$
$Wt = (Wt-3⊕Wt-8⊕ Wt-14⊕Wt-16) <<< 1, 当16≤t≤79$
alt text
5）SHA1的4轮运算
SHA1有4轮运算，每一轮包括20个步骤，一共80步(对应扩展后的80个W[t])，当第1轮运算中的第1步骤开始处理时，A、B、C、D、E五个链接变量中的值先赋值到另外5个记录单元A′，B′，C′，D′，E′中。这5个值将保留，用于在第4轮的最后一个步骤完成之后与链接变量A，B，C，D，E进行求和操作。
SHA1的4轮运算，共80个步骤使用同一个操作程序，如下：