常用算法之三详解 SHA1 实现（基于算法的官方原文档）及源码详细注释

清疚 2022-04-12 05:16 540阅读 0赞

# 写在前面 #

在之前的工作中，用到了**CRC16**、**MD5** 和 **SHA1** 算法，主要用来校验下发的文件。网上关于这些算法的文章铺天盖地，以下内容仅仅是自己在学习时候的一个记录，一些套话来自于互联网。下面先来看看 **SHA1**。  
   以下算法分析基于 ***RFC 3174***。

> 1.  Request For Comments (RFC），所有关于Internet 的正式标准都是以RFC(Request for Comment )文档出版。需要注意的是，还有大量的RFC文档都不是正式的标准，出版目的都是为了提供信息。
> 2.  由互联网协会（Internet Society，简称ISOC）赞助发行，会交到互联网工程工作小组（IETF）和互联网结构委员会（IAB）。文档可由网站 [https://www.ietf.org/][https_www.ietf.org] 下载。

# 什么是 SHA1 #

全称为 Secure Hash Algorithm 1（安全散列算法1）。是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦数据处理标准（FIPS）。1993年 发布 SHA0，1995年发布了SHA1。其设计原理相似于MIT教授 Ronald L. Rivest 所设计的密码学散列算法 MD4 和 MD5。  
  SHA1 可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。主要适用于数字签名标准 （Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。

> SHA实际上是一系列算法的统称，分别包括：SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>类别</th> 
>    <th>消息长度</th> 
>    <th>分组长度</th> 
>    <th>计算字长</th> 
>    <th>计算步骤</th> 
>    <th>消息摘要长度</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>SHA-1</td> 
>    <td>小于2^64位</td> 
>    <td>512</td> 
>    <td>32</td> 
>    <td>80</td> 
>    <td>160</td> 
>   </tr> 
>   <tr> 
>    <td>SHA-224</td> 
>    <td>小于2^64位</td> 
>    <td>512</td> 
>    <td>32</td> 
>    <td>64</td> 
>    <td>224</td> 
>   </tr> 
>   <tr> 
>    <td>SHA-256</td> 
>    <td>小于2^64位</td> 
>    <td>512</td> 
>    <td>32</td> 
>    <td>64</td> 
>    <td>256</td> 
>   </tr> 
>   <tr> 
>    <td>SHA-384</td> 
>    <td>小于2^128位</td> 
>    <td>1024</td> 
>    <td>64</td> 
>    <td>80</td> 
>    <td>384</td> 
>   </tr> 
>   <tr> 
>    <td>SHA-512</td> 
>    <td>小于2^128位</td> 
>    <td>1024</td> 
>    <td>64</td> 
>    <td>80</td> 
>    <td>512</td> 
>   </tr> 
>  </tbody> 
> </table>

# 安全性 #

2005年二月，王小云、殷益群及于红波发表了对完整版SHA-1的攻击，只需少于269的计算复杂度，就能找到一组碰撞。（利用生日攻击法找到碰撞需要280的计算复杂度。）  
  2017年2月23日，CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击，发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

# 实现原理 #

When amessage of any length < 2^64 bits is input, the SHA-1 produces a 160-bit output called a message digest. （SHA-1算法输入报文的最大长度不超过2^64位，产生的输出是一个160位的报文摘要。）根据算法文档，算法的实现主要由以下几部分来组成。

1.  RFC3174 中的第二部分，给出了一些术语，总结一下也就下面三点：
    
     *  SHA-1算法把输入消息当做 **比特位字符串** 来处理
     *  输入是按 512 位（16个字）的分组进行处理的
     *  **字** 等于32位字符串，可以表示为8个十六进制数字的序列。（A word equals a 32-bit string which may be represented as a sequence of 8 hex digits. ）
2.  RFC3174 中的第三部分，给出了一些对于 **字** 的基本运算，总结一下：
    
     *  按位逻辑字操作
        
         *  X AND Y = bitwise logical “and” of X and Y.
         *  X OR Y = bitwise logical “inclusive-or” of X and Y.
         *  X XOR Y = bitwise logical “exclusive-or” of X and Y.
         *  NOT X = bitwise logical “complement” of 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。
     *  循环左移位操作符 `S^n(X)`。X是一个字，n是一个整数，`0<=n<=32`。`S^n(X) = (X << n) OR (X >> 32-n)`。`X << n`定义如下：抛弃最左边的n位数字，将各个位依次向左移动n位，然后用0填补右边的n位（最后结果还是32位）。`X>>n`是抛弃右边的n位，将各个位依次向右移动n位，然后在左边的n位填0。因此可以叫S^n(X)位循环右移位运算。
3.  RFC3174 中的第四部分，介绍了 **消息填充** 。  
      前面说了，SHA-1算法是以512一包来处理消息的，但是很多情况下，消息长度并不是512的整数倍，这个时候就需要对原始消息进行填充。
    
    1.  补位  
        原始消息必须进行补位，以使其长度在对512取模以后的余数是448。也就是说，（补位后的消息长度）%512 = 448。即使长度已经满足对512取模后余数是448，补位也必须要进行。  
        补位是这样进行的：***先补一个1，然后再补0*** ，直到长度满足对512取模后余数是448。总而言之，补位是至少补一位，最多补512位。
    2.  补长度  
        就是将原始数据的长度补到已经进行了补位操作的消息后面。通常用两个字（64位）来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0。
4.  RFC3174 中的第五部分，给出了算法使用的各种函数和常量 。  
      在SHA-1中使用了一系列逻辑函数f（0），f（1），…，f（79）。 每个f（t），0 <= t <= 79，对三个32位字B，C，D进行操作，并产生一个32位字作为输出。 f（t; B，C，D）定义如下：
    
     *  f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
     *  f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
     *  f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
     *  f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79).
        
        在SHA-1中使用一系列常数字K（0），K（1），…，K（79）。定义如下：
     *  K(t) = 5A827999 ( 0 <= t <= 19)
     *  K(t) = 6ED9EBA1 (20 <= t <= 39)
     *  K(t) = 8F1BBCDC (40 <= t <= 59)
     *  K(t) = CA62C1D6 (60 <= t <= 79).
5.  RFC3174 中的第六部分，给出了算法具体实现方法 。  
    经过前面的准备，接下来就是计算信息摘要了。SHA1有4轮运算，每一轮包括20个步骤，一共80步，最终产生160位的信息摘要，这160位的摘要存放在5个32位的链接变量中。  
    在SHA1的4论运算中，虽然进行的就具体操作函数不同，但逻辑过程却是一致的。首先，定义5个变量，假设为H0、H1、H2、H3、H4，对其分别进行如下操作：  
    （A）将A左移5为与 函数的结果求和，再与对应的子明文分组、E以及计算常数求和后的结果赋予H0。  
    （B）将A的值赋予H1。  
    （C）将B左移30位，并赋予H2。  
    （D）将C的值赋予H3。  
    （E）将D的值赋予H4。  
    （F）最后将H0、H1、H2、H3、H4的值分别赋予A、B、C、D

# 源码 #

*  **SHA1.h**

#ifndef SHA1_H
    #define SHA1_H
    
    #ifdef __cplusplus
    extern "C" { 
    #endif
    
    #define SHA1HANDSOFF
    #define LITTLE_ENDIAN
    
    typedef struct
    { 
    	unsigned long state[5];			/* 160(5×32)比特的消息摘要（即SHA-1算法要得出的） */
    	unsigned long count[2];			/* 储存消息的长度（单位：比特） */
    	unsigned char buffer[64];		/* 512(64×8)比特（位）的消息块（由原始消息经处理得出） */
    } SHA1_CTX;
    
    
    void SHA1Init(SHA1_CTX *context);
    
    void SHA1Update(SHA1_CTX *context, unsigned char *data, unsigned int len);
    
    void SHA1Final(unsigned char digest[20], SHA1_CTX *context);
    
    #ifdef __cplusplus
    }
    #endif
    
    #endif

*  **SHA1.c**

#include <stdio.h>
    #include <string.h>
    #include "SHA1.h"
    
    typedef union { 
    	unsigned char c[64];
    	unsigned long l[16];
    } CHAR64LONG16;
    
    #define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
    
    /* blk0() and blk() perform the initial expand. */
    /* I got the idea of expanding during the round function from SSLeay */
    #ifdef LITTLE_ENDIAN
    	#define blk0(i) (block->l[i] = (rol(block->l[i], 24) & 0xFF00FF00) | (rol(block->l[i], 8) & 0x00FF00FF))
    #else
    	#define blk0(i) block->l[i]
    #endif
    
    #define blk(i) (block->l[i & 15] = rol(block->l[(i + 13) & 15] ^ block->l[(i + 8) & 15] ^ block->l[(i + 2) & 15] ^ block->l[i & 15], 1))
    
    /* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
    #define R0(v, w, x, y, z, i) \ z += ((w & (x ^ y)) ^ y) + blk0(i) + 0x5A827999 + rol(v, 5); \ w = rol(w, 30);
    
    #define R1(v, w, x, y, z, i) \ z += ((w & (x ^ y)) ^ y) + blk(i) + 0x5A827999 + rol(v, 5); \ w = rol(w, 30);
    
    #define R2(v, w, x, y, z, i) \ z += (w ^ x ^ y) + blk(i) + 0x6ED9EBA1 + rol(v, 5); \ w = rol(w, 30);
    
    #define R3(v, w, x, y, z, i) \ z += (((w | x) & y) | (w & x)) + blk(i) + 0x8F1BBCDC + rol(v, 5); \ w = rol(w, 30);
    
    #define R4(v, w, x, y, z, i) \ z += (w ^ x ^ y) + blk(i) + 0xCA62C1D6 + rol(v, 5); \ w = rol(w, 30);
    
    
    static void SHA1Transform(unsigned long state[5], unsigned char buffer[64]);
    
    
    /* Hash a single 512-bit block. This is the core of the algorithm. */
    static void SHA1Transform(unsigned long state[5], unsigned char buffer[64])
    { 
    	unsigned long a, b, c, d, e;
    	CHAR64LONG16 *block;
    
    #ifdef SHA1HANDSOFF
    	static unsigned char workspace[64];
    	block = (CHAR64LONG16 *)workspace;
    	memcpy(block, buffer, 64);
    #else
    	block = (CHAR64LONG16 *)buffer;
    #endif
    
    	/* Copy context-> state[] to working vars */
    	a = state[0];
    	b = state[1];
    	c = state[2];
    	d = state[3];
    	e = state[4];
    
    	/* 完成的就是RFC文档中的H0～H4赋值给ABCDE的操作。接下来就是80轮运算的代码。每20轮为一组，共分四组 */
    	/* 第一组比较特殊，使用了R0和R1两个宏函数，其原因前面已经介绍了。因为第0~15轮运算和16~79轮运算的时候消息块M(i)和字块W(i)的转换是不一样的。后面的20~39轮，40~59轮，60~79轮就是依次使用的R2，R3，R4来运算了 */
    	/* 4 rounds of 20 operations each. Loop unrolled. */
    	R0(a, b, c, d, e, 0);
    	R0(e, a, b, c, d, 1);
    	R0(d, e, a, b, c, 2);
    	R0(c, d, e, a, b, 3);
    
    	R0(b, c, d, e, a, 4);
    	R0(a, b, c, d, e, 5);
    	R0(e, a, b, c, d, 6);
    	R0(d, e, a, b, c, 7);
    
    	R0(c, d, e, a, b, 8);
    	R0(b, c, d, e, a, 9);
    	R0(a, b, c, d, e, 10);
    	R0(e, a, b, c, d, 11);
    
    	R0(d, e, a, b, c, 12);
    	R0(c, d, e, a, b, 13);
    	R0(b, c, d, e, a, 14);
    	R0(a, b, c, d, e, 15);
    
    	R1(e, a, b, c, d, 16);
    	R1(d, e, a, b, c, 17);
    	R1(c, d, e, a, b, 18);
    	R1(b, c, d, e, a, 19);
    
    	R2(a, b, c, d, e, 20);
    	R2(e, a, b, c, d, 21);
    	R2(d, e, a, b, c, 22);
    	R2(c, d, e, a, b, 23);
    
    	R2(b, c, d, e, a, 24);
    	R2(a, b, c, d, e, 25);
    	R2(e, a, b, c, d, 26);
    	R2(d, e, a, b, c, 27);
    
    	R2(c, d, e, a, b, 28);
    	R2(b, c, d, e, a, 29);
    	R2(a, b, c, d, e, 30);
    	R2(e, a, b, c, d, 31);
    
    	R2(d, e, a, b, c, 32);
    	R2(c, d, e, a, b, 33);
    	R2(b, c, d, e, a, 34);
    	R2(a, b, c, d, e, 35);
    
    	R2(e, a, b, c, d, 36);
    	R2(d, e, a, b, c, 37);
    	R2(c, d, e, a, b, 38);
    	R2(b, c, d, e, a, 39);
    
    	R3(a, b, c, d, e, 40);
    	R3(e, a, b, c, d, 41);
    	R3(d, e, a, b, c, 42);
    	R3(c, d, e, a, b, 43);
    
    	R3(b, c, d, e, a, 44);
    	R3(a, b, c, d, e, 45);
    	R3(e, a, b, c, d, 46);
    	R3(d, e, a, b, c, 47);
    
    	R3(c, d, e, a, b, 48);
    	R3(b, c, d, e, a, 49);
    	R3(a, b, c, d, e, 50);
    	R3(e, a, b, c, d, 51);
    
    	R3(d, e, a, b, c, 52);
    	R3(c, d, e, a, b, 53);
    	R3(b, c, d, e, a, 54);
    	R3(a, b, c, d, e, 55);
    
    	R3(e, a, b, c, d, 56);
    	R3(d, e, a, b, c, 57);
    	R3(c, d, e, a, b, 58);
    	R3(b, c, d, e, a, 59);
    
    	R4(a, b, c, d, e, 60);
    	R4(e, a, b, c, d, 61);
    	R4(d, e, a, b, c, 62);
    	R4(c, d, e, a, b, 63);
    
    	R4(b, c, d, e, a, 64);
    	R4(a, b, c, d, e, 65);
    	R4(e, a, b, c, d, 66);
    	R4(d, e, a, b, c, 67);
    
    	R4(c, d, e, a, b, 68);
    	R4(b, c, d, e, a, 69);
    	R4(a, b, c, d, e, 70);
    	R4(e, a, b, c, d, 71);
    
    	R4(d, e, a, b, c, 72);
    	R4(c, d, e, a, b, 73);
    	R4(b, c, d, e, a, 74);
    	R4(a, b, c, d, e, 75);
    
    	R4(e, a, b, c, d, 76);
    	R4(d, e, a, b, c, 77);
    	R4(c, d, e, a, b, 78);
    	R4(b, c, d, e, a, 79);
    
    	/* 完成的就是更新缓冲区H0～H4的内容。然后把a～e清空为0 */
    	/* Add the working vars back into context.state[] */
    	state[0] += a;
    	state[1] += b;
    	state[2] += c;
    	state[3] += d;
    	state[4] += e;
    	/* Wipe variables */
    	a = b = c = d = e = 0;
    }
    
    /* SHA1Init - Initialize new context */
    void SHA1Init(SHA1_CTX *context)
    { 
    	/* SHA1 initialization constants */
    	context->state[0] = 0x67452301;
    
    	context->state[1] = 0xEFCDAB89;
    
    	context->state[2] = 0x98BADCFE;
    
    	context->state[3] = 0x10325476;
    
    	context->state[4] = 0xC3D2E1F0;
    
    	context->count[0] = context->count[1] = 0;
    }
    
    /* Run your data through this. */
    void SHA1Update(SHA1_CTX *context, unsigned char *data, unsigned int len)
    { 
    	unsigned int i, j;
    
    	/* j>>3获得的就是字节数，j = (j >> 3) & 63得到的就是低6位的值，也就是代表64个字节（512位）长度的消息。，因为我们每次进行计算都是处理512位的消息数据。 */
    	j = (context->count[0] >> 3) & 63;
    
    	/* context->count[ ]存储的是消息的长度，超出context->count[0]的存储范围的部分存储在context->count[1]中。len<<3就是len*8的意思，因为len的单位是字节，而context->count[ ]存储的长度的单位是位，所以要乘以8。 if ((context->count[0] += len << 3) < j) 的意思就是说如果加上len*8个位，context->count[0]溢出了，那么就要：context->count[1]++；进位。 len<<3的单位是位，len>>29（len<<3 >>32）表示的就是len中要存储在context->count[1]中的部分。 */
    	if ((context->count[0] += len << 3) < (len << 3))
    		context->count[1]++;
    
    	context->count[1] += (len >> 29);
    
    	/* 如果j+len的长度大于63个字节，就分开处理，每64个字节处理一次，然后再处理后面的64个字节，重复这个过程；否则就直接将数据附加到buffer末尾 */
    	if ((j + len) > 63)
    	{ 
    		memcpy(&context->buffer[j], data, (i = 64 - j));		/* i=64-j，然后从data中复制i个字节的数据附加到context->buffer[j]末尾，也就是说给buffer凑成了64个字节 */
    		SHA1Transform(context->state, context->buffer);			/* 执行SHA1Transform()来开始一次消息摘要的计算 */
    		/* 每64个字节处理一次 */
    		for (; i + 63 < len; i += 64)
    		{ 
    			SHA1Transform(context->state, &data[i]);
    		}
    		j = 0;
    	}
    	else
    	{ 
    		i = 0;
    	}
    
    	/* 如果前面的if不成立，那么也就是说原始数据context->buffer加上新的数据data的长度还不足以凑成64个字节，所以直接附加上data就行了。相当于：memcpy(&context->buffer[j], &data[i], 0); 如果前面的if成立，那么j是等于0的，而 i 所指向的偏移位置是 (└ len/64┘×64,len)之间。 └ ┘表示向下取整。*/
    
    	memcpy(&context->buffer[j], &data[i], len - i);
    }
    
    /* Add padding and return the message digest. */
    void SHA1Final(unsigned char digest[20], SHA1_CTX *context)
    { 
    	unsigned long i, j;
    	unsigned char finalcount[8];
    
    	for (i = 0; i < 8; i++)
    	{ 
    		finalcount[i] = (unsigned char)((context->count[(i >= 4 ? 0 : 1)]
    										 >> ((3 - (i & 3)) * 8)) &
    										255); /* Endian independent */
    	}
    	/* 填充的时候是以字节为单位的，最少1个字节，最多64个字节。并且第一位要填充1，后面都填充0。所以拿到一个消息我们首先要给他填充一个字节的10 000 000.SHA1Update() 函数就是完成的数据填充（附加）操作 */
    	SHA1Update(context, (unsigned char *)"\200 ", 1);
    
    	/* 循环测试数据模512是否与448同余。不满足条件就填充全一个字节0。 */
    	/* 使用 while ((context->count[0] & 511) != 448) 貌似更合适。但是，504后三位全0,511后三位全1。context->count中存储的是消息的长度，它的单位是：位。前面我们提到了我们的数据是以字节来存储的，所以context->count[ ]中的数据肯定是8个倍数，所以后三位肯定是000。所以不管是000&000，还是000&111其结果都是0。 */
    	while ((context->count[0] & 504) != 448)
    	{ 
    		SHA1Update(context, (unsigned char *)"\0 ", 1);
    	}
    
    	/* 这将触发SHA1Transform()函数的调用，该函数的功能就是进行运算，得出160位的消息摘要（message digest）并储存在context-state[ ]中，它是整个SHA-1算法的核心 */
    	SHA1Update(context, finalcount, 8); /* Should cause a SHA1Transform() */
    
    	/* 最后的这步转换将消息摘要转换成单字节序列。用代码来解释就是：将context-state[5]中储存的20个字节（5×4字节）的消息摘要取出，将其存储在20个单字节的数组digest中。并且按大端序存储（与之前分析context->count[ ]到finalcount[ ]转换的思路相同） */
    	for (i = 0; i < 20; i++)
    	{ 
    		digest[i] = (unsigned char)
    
    			((context->state[i >> 2] >> ((3 - (i & 3)) * 8)) & 255);
    	}
    
    	/* Wipe variables */
    	i = j = 0;
    	memset(context->buffer, 0, 64);
    	memset(context->state, 0, 20);
    	memset(context->count, 0, 8);
    	memset(&finalcount, 0, 8);
    
    #ifdef SHA1HANDSOFF /* make SHA1Transform overwrite it 's own static vars */
    	SHA1Transform(context->state, context->buffer);
    #endif
    }

# 使用方式 #

在实际使用时，往往需要多次调用循环计算。因为要计算的内容可能很长，需要分包一次次计算。上面的源码就是考虑到该种问题而实现的！使用方式如下：

SHA1_CTX ctx;
    unsigned char hash[20];
    unsigned char abc[] = "abc";
    /* 计算前，先初始化 */
    SHA1Init(&ctx);
    /* 多次调用 SHA1Update 循环计算多个包数据（如果有的话） */
    SHA1Update(&ctx, abc, 3);
    /* 最后调用 SHA1Final 获取最终结果 */
    SHA1Final(hash, &ctx);

最终，在数组`hash`中存放的就是最终计算结果！

# 附件 #

1.  [SHA1 算法 官方文档 rfc3174][SHA1 _ _ rfc3174]

[https_www.ietf.org]: https://www.ietf.org/
[SHA1 _ _ rfc3174]: https://download.csdn.net/download/zcshoucsdn/10838162