SHA1算法详解和C实现

　　背景介绍
　　SHA-1算法也称安全散列算法1，可以将一个最大2^{64}-1的数据生成一个160位的数据摘要。尽管SHA-1算法已经被认为不再安全，但仍有部分应用使用SHA-1算法验证文件。 算法原理类型定义
　　在介绍算法原理之前，有必要定义一些数据类型，有助于我们脱离具体编程语言分析这个算法。我这里使用C++的定义方式，不会C++也没有问题，我会解释代码的意义。 typedef __UINT8_TYPE__ BYTE; typedef __UINT32_TYPE__ WORD; typedef __UINT64_TYPE__ DWORD;
　　上面定义了三个数据类型，分别是： BYTE  ，字节，由8位二进制数组成，表示范围（0x0 - 0xFF）。 WORD  ，字，由32位二进制数组成，表示范围（0x0 - 0xFFFFFFFF）。 DWORD  ，双字，两个字组成，表示范围（0x0 - 0xFFFFFFFFFFFFFFFF） 算法剖析
　　（以下算法分析均建立在大端存储的基础之上，关于大端存储与小端存储对算法的影响，请见C++实现部分关于大端存储与小端存储的具体实现。）
　　输入： 不定长度的字节序列（最大为2^{64}-1位）。
　　输出： 160位数据摘要。
　　输入不必多说，这里说一下输出。SHA-1算法最终产生160位数据摘要，这实际上由5个变量存储，每个变量存储32位信息，也就是说，这160为数据摘要存储在5个 WORD  中（5	imes 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个字节填入整个数据的位数长度。所以我们输入的数据有以下两种情况： 数据位数长度对512取余刚好等于448。 数据位数长度对512取余不等于448。
　　对情况1：我们只需要在最后64位中填入输入数据的位数长度即可。
　　对情况2：这里相对情况1更为复杂，需要进行 补位 。
　　什么是补位呢？我们需要在数据最后补上一个1，然后全部补0直到数据长度对512取余等于448。例如我们数据为： 10011010  ，长度为8位，补位后为： 10011010 1000...0  ，中间空格为了区分补位数据。补位完成后，最后填入的数据长度依旧是8，补位数据不计入数据长度。 2. 生成子组
　　由于SHA-1算法的基本运算单位是一个块，所以我们只需对上面分完的这么多个块中讨论一个即可。
　　对于给定的一个块，512位，我们需要再分成16个子组，每个子组32位。也就是一个 WORD  ，记为w_0, w_1, ..., w_{15}，我们需要这16个子组，再生成64个子组，记为w_{16},w_{17},...,w_{79}。生成算法如下：
　　$
　　w_{i} = w_{i-3}oplus w_{i-8}oplus w_{i-14}oplus w_{i-16}
　　$
　　其中i in {16, ..., 79}，oplus表示异或，在C++中对应运算符为 ^  。 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;
　　之后即可进行下一块运算。 C++实现大小端问题
　　值得注意的是，SHA-1算法建立在大端存储的基础上，包括填入数据长度时，最后64个字节也是按照大端存储来分配的。但是如果机器是小端存储，这边就会出问题，问题出现的地方在：循环位移运算、加法运算。所以如果是小端存储的机器，必须保证在实际内存上数据的排列按SHA-1算法要求，那么我们必须在取出数据和存入数据时反转数据。 大文件分批次读取计算的问题
　　关于大文件无法一次性读入内存时，SHA-1算法支持分批次读入，这是由于SHA-1算法计算基础单位是一个块决定的，所以读入大文件时，需要一个变量记住不断累计的文件长度，并且读入数据满一个块时立即计算并清空块缓冲区，等待下一组数据读入。 具体实现
　　关于C++的具体实现部分我已经在Github上开源，项目为GitHub - andsssf/justsha1: just implement sha1 algorithm，欢迎各位点个star。