SC@SDUSC
本周将三大算法中最后一个未介绍的算法SHA的原理进行分析。本章就对最初的SHA-1算法原理进行简要分析。
一、SHA-1背景
SHA-1算法也称安全散列算法1，可以将一个最大2^（64）-1的数据生成一个160位的数据摘要。尽管SHA-1算法已经被认为不再安全，但仍有部分应用使用SHA-1算法验证文件。
二、类型定义
在介绍算法原理之前，有必要定义一些数据类型，有助于我们脱离具体编程语言分析这个算法。这里使用C++的定义方式。
typedef __UINT8_TYPE__ BYTE;typedef __UINT32_TYPE__ WORD;typedef __UINT64_TYPE__ DWORD;
上面定义了三个数据类型，分别是：
BYTE，字节，由8位二进制数组成，表示范围（0x0 - 0xFF）。
WORD，字，由32位二进制数组成，表示范围（0x0 - 0xFFFFFFFF）。
DWORD，双字，两个字组成，表示范围（0x0 - 0xFFFFFFFFFFFFFFFF）
三、算法分析
输入：不定长度的字节序列（最大为2^（64）-1位）。
输出：160位数据。
这里主要关注一下输出。SHA-1算法最终产生160位数据，这实际上由5个变量存储，每个变量存储32位信息，也就是说，这160为数据存储在5个WORD中（5* 32=160），这五个变量被定义为：A，B，C，D，E。他们都有初始值，分别为：
WORD A = 0x67452301;WORD B = 0xEFCDAB89;WORD C = 0x98BADCFE;WORD D = 0x10325476;WORD E = 0xC3D2E1F0;
SHA-1算法的过程就是利用输入的字节序列，不断更新这五个变量，最后将这五个变量按字节拼接，就得到160位的数据。具体过程如下：
1.预处理
SHA-1算法的基本运算单位是一个块（block），一个块的大小为512位，即64字节。输入的数据位数按512被不断分块。如果数据不能被512整除，也就是说最后一部分数据不能填满一块怎么办呢？实际上即便最后一部分填满512位，我们依旧要进行更进一步处理，除非最后一部分刚好等于448位，也就是56个字节。因为我们需要最后一块的最后64个字节填入整个数据的位数长度。所以我们输入的数据有以下两种情况：
1.数据位数长度对512取余刚好等于448。
2.数据位数长度对512取余不等于448。
对情况1：我们只需要在最后64位中填入输入数据的位数长度即可。
对情况2：这里相对情况1更为复杂，需要进行补位。
什么是补位呢？我们需要在数据最后补上一个1，然后全部补0直到数据长度对512取余等于448。例如我们数据为：10011010，长度为8位，补位后为：10011010 1000...0（中间空格为了区分补位数据）。补位完成后，最后填入的数据长度依旧是8，补位数据不计入数据长度。
2.生成子组
由于SHA-1算法的基本运算单位是一个块，所以我们只需对上面分完的这么多个块中讨论一个块即可。
对于给定的一个块，512位，我们需要再分成16个子组，每个子组32位。也就是一个WORD，记为w0,w1,...w15，我们需要这16个子组，再生成64个子组，记为w16,w17,...w79。生成算法如下：
3.80次核心循环
在循环开始之前，我们需要得到一组A，B，C，D，E五个变量的拷贝，记为a，b，c，d，e。
WORD a = A, b = B, c = C, d = D, e = E;
接下来我们需要执行一个80次的循环，每次循环都利用到a，b，c，d，e，以及一个子组。
第1个20次循环(0 < i < 19)：
WORD temp = (b & c) | ((~b) & d) + 0x5A827999;WORD temp2 = a << 5 | a >> 27;e = d;d = c;c = b << 30 | b >> 2;b = a;a = temp + temp2 + e + w[i];
第2个20次循环(20 < i < 39)：
WORD temp = (b ^ c ^ d) + 0x6ED9EBA1;WORD temp2 = a << 5 | a >> 27;e = d;d = c;c = b << 30 | b >> 2;b = a;a = temp + temp2 + e + w[i];
第3个20次循环(40 < i < 59)：
WORD temp = (b & c) | (b & d) | (c & d) + 0x8F1BBCDC;WORD temp2 = a << 5 | a >> 27;e = d;d = c;c = b << 30 | b >> 2;b = a;a = temp + temp2 + e + w[i]；
第4个20次循环(60 < i < 79)：
WORD temp = (b ^ c ^ d) + 0xCA62C1D6;WORD temp2 = a << 5 | a >> 27;e = d;d = c;c = b << 30 | b >> 2;b = a;a = temp + temp2 + e + w[i]；
执行完之后，这一块的运算已经完成，只需要更新A，B，C，D，E的值即可。
A += a;B += b;C += c;D += d;E += e;
之后即可进行下一块运算。
4.运算符和符号（补充）
下面的逻辑运算符都被运用于“字”（Word）
X ^ Y = X，Y逻辑与
X // Y = X，Y逻辑或
X XOR Y = X，Y逻辑异或
~X = X逻辑取反
X+Y定义如下：字X和Y代表两个整数x和y,其中0 <= x < 2^32且0 <= y < 2^32.令整数z = (x + y) mod 2^32.这时候0 <= z < 2^32.将z转换成字Z,那么就是Z = X + Y.
循环左移位操作符Sn(X)：X是一个字，n是一个整数，0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)
X<<n定义如下：抛弃最左边的n位数字，将各个位依次向左移动n位，然后用0填补右边的n位（最后结果还是32位）。
X>>n是抛弃右边的n位，将各个位依次向右移动n位，然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算。
四、总结
安全散列算法（secure hash algorithm， SHA）
给定一个字符串， SHA返回其散列值。比如一个hello，sha返回2cf24bd…很长的值
对于每个不同的字符串， SHA生成的散列值都不同。
比较文件内容是否相同
你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB
的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送
给朋友，而可计算它们的SHA散列值，再对结果进行比较。
检查密码
SHA还让你能在不知道原始字符串的情况下对其进行比较。例如，假设Gmail遭到攻击，攻击者窃取了所有的密码！你的密码暴露了吗？没有，因为Google存储的并非密码，而是密码的SHA散列值！你输入密码时， Google计算其散列值，并将结果同其数据库中的散列值进行比较。
SHA被广泛用于计算密码的散列值。**这种散列算法是单向的。**你可根据字符串计算出散列值。但你无法根据散列值推断出原始字符串。
SHA实际上是一系列算法： SHA-0、 SHA-1、 SHA-2和SHA-3。 目前SHA-0和SHA-1已被发现存在一些缺陷。如果你要使用SHA算法来计算密码的散列值，请使用SHA-2或SHA-3。当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。
提一下MD5消息摘要算法被广泛使用的密码散列函数，相比较SHA-1生成摘要的性能高一些，MD5的摘要的长度尽128bit，SHA-1摘要长度160bit。多出32bit意味着什么呢？不同明文的碰撞几率降低了2^32 = 324294967296倍。
为了适应不同的应用场景，从而对安全、性能、空间等因素做出权衡。比如说过我的需求仅仅是验证数据完整性，使用SHA-512显然是浪费了。另外，如果想要追求安全性，也可以考虑把多种摘要算法结合使用。比如下面这样：
明文： abcd
MD5摘要：e2fc714c4727ee9395f324cd2e7f331f
SHA-256摘要：88d4266fd4e6338d13b845fcf289579d209c897823b9217da3e161936f031589
合成摘要：e2fc714c4727ee93209c897823b9217da3e161936f031589
取MD摘要的前16和SHA-256摘要的后32位，拼成一个长度48位的合成摘要。这样除非知道拼接规则，否则外人是无从破解的。
参考资料：SHA-1算法详解和C++实现 - 哔哩哔哩
参考博客：SHA算法_aleo的博客-CSDN博客
