SHA1算法实现及详解

0X1 SHA1算法详解

SHA1算法是Hash算法的一种。SHA1算法的最大输入长度小于2^64比特的消息，输入消息（明文）以512比特的分组为单位处理，输出160比特的消息摘要（密文）

整个算法的核心是一个包含4轮循环的模块，每轮循环由20个步骤组成。
如下图：
其中Yq代表原始消息， CVq代表初始化的链接变量，最终我们要的密文就是CYq+1

1. 附加填充位

消息必须进行填充，以使其长度在对512取模以后的余数是448。也就是说，（填充后的消息长度）%512 = 448。即使长度已经满足对512取模后余数是448，填充也必须要进行。填充的规则是填充一个“1”和若干个“0”使其长度模512和448同余。然后附加64比特的无符号整数，其值为原始消息的长度

2. 初始化链接变量

和MD5有些类似，将5个32比特的固定数赋值给5个32比特的寄存器（和汇编里面的寄存器不同，可以理解为变量）A、B、C、D、E作为第一次迭代的链接变量输入：
A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476, E = 0xC3D2E1F0

3. 非线性函数f函数

f t ( x , y , z ) = { C h ( x , y , z ) = ( x ⋀ y ) ⨁ ( ┐ x ⋀ z ) , 0 ≤ t ≤ 19 P a r i t y ( x , y , z ) = x ⨁ y ⨁ z , 0 ≤ t ≤ 19 M a j ( x , y , z ) = ( x ⋀ y ) ⨁ ( x ⋀ z ) ⨁ ( y ⋀ z ) 0 ≤ t ≤ 19 P a r i t y ( x , y , z ) = x ⨁ y ⨁ z , 0 ≤ t ≤ 19 f_t(x,y,z) =\begin{cases} Ch(x, y ,z) = (x \bigwedge y) \bigoplus ( \urcorner x \bigwedge z),& 0 \leq t \leq 19 \\ Parity(x, y ,z) =x \bigoplus y\bigoplus z,& 0 \leq t \leq 19 \\ Maj(x, y ,z) = (x \bigwedge y) \bigoplus(x \bigwedge z) \bigoplus(y \bigwedge z) & 0 \leq t \leq 19 \\ Parity(x, y ,z) =x \bigoplus y\bigoplus z,& 0 \leq t \leq 19 \end{cases} ft​(x,y,z)=⎩⎪⎪⎪⎨⎪⎪⎪⎧​Ch(x,y,z)=(x⋀y)⨁(┐x⋀z),Parity(x,y,z)=x⨁y⨁z,Maj(x,y,z)=(x⋀y)⨁(x⋀z)⨁(y⋀z)Parity(x,y,z)=x⨁y⨁z,​0≤t≤190≤t≤190≤t≤190≤t≤19​

4. K值的获取

步数	Kr
r = 1 (0 <= t <= 19)	0x5A827999
r = 2 (20 <= t <= 39)	0x6ED9EBA1
r = 3 (40 <= t <= 59)	0x8F1BBCDC
r = 4 (60 <= t <= 79)	0xCA62C1D6

当然你也可以自己计算，四个值的获取分别是2、3、5和10的平方根，然后乘以2^30 = 1 073 741 824最后取乘积的整数部分。

5. W值的获取

R O T L n ( x ) 表 示 对 32 位 比 特 的 变 量 循 环 左 移 n 比 特 ROTL^n(x)表示对32位比特的变量循环左移n比特 ROTLn(x)表示对32位比特的变量循环左移n比特
注意是循环左移n比特

W一共分为80组，其中从W[0]到W[15]为获得的原始消息均分为16组。

{ W t = M t ( i ) 0 ≤ t ≤ 15 W t = R O T L 1 ( W ( t − 3 ) ⨁ W ( t − 8 ) ⨁ W ( t − 14 ) ⨁ W ( t − 16 ) , 16 ≤ t ≤ 79 \begin{cases} W_t = M_t^{(i)} & 0 \leq t \leq 15 \\ W_t =ROTL^1(W_{(t-3)}\bigoplus W_{(t-8)}\bigoplus W_{(t-14)}\bigoplus W_{(t-16)},& 16 \leq t \leq 79 \end{cases} {Wt​=Mt(i)​Wt​=ROTL1(W(t−3)​⨁W(t−8)​⨁W(t−14)​⨁W(t−16)​,​0≤t≤1516≤t≤79​

6. 步函数

A = ( R O T L 5 ( A ) + f t ( B , C , D ) + E + W t + K r ) m o d 2 32 B = A C = R O T L 30 ( B ) m o d 2 32 D = C E = D A = (ROTL^5(A) + f^t(B,C,D) + E + W^t + K^r)mod 2^{32}\\B=A\\C= ROTL^{30}(B)mod2^{32}\\D=C\\E=D A=(ROTL5(A)+ft(B,C,D)+E+Wt+Kr)mod232B=AC=ROTL30(B)mod232D=CE=D
其中t是步数，0 <= t <= 79，r为轮数， 0 <= r <= 4.

0X2源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)

//初始化链接变量
unsigned int A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476, E = 0xC3D2E1F0;        //第一次迭代的链接变量

unsigned int K[4] = { 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6 };                              //循环中用到的常量
unsigned int A0 = 0x67452301, B0 = 0xEFCDAB89, C0 = 0x98BADCFE, D0 = 0x10325476, E0 = 0xC3D2E1F0;

// 字节转换，将四个字节转换为一个整型
int CharToWord(unsigned char *context, int i)
{
	return (((int)context[i] & 0x000000ff) << 24) | (((int)context[i + 1] & 0x000000ff) << 16) | (((int)context[i + 2] & 0x000000ff) << 8) | ((int)context[i + 3] & 0x000000ff);
}

// 填充补位获得原始明文
void SHA1_fill(unsigned char *plaintext, unsigned int *group, int length)
{
	printf("补位后获得的明文：\n");
	
	int temp = length / 32, len = length;
	while (len > 0)
	{
		if (len = len / 32)
		{
			for (int j = 0; j < temp; j++)
			{
				group[j] = CharToWord(plaintext, 4 * j);
				printf("%08X\n", group[j]);
			}
		}
		else
		{
			plaintext[length / 8] = 0x80;
			group[temp] = CharToWord(plaintext, temp * 4);
			printf("%08X\n", group[temp]);
			break;
		}
	}
	group[15] = length;
	for (int i = temp + 1; i < 16; i++)
		printf("%08X\n", group[i]);
	
}
// f函数
unsigned int f(int B, int C, int D, int t)
{
	return (t >= 0 && t <= 19) ? ((B&C) | (~B&D)) : ((t >= 20 && t <= 39) ? (B ^ C ^ D) : ((t >= 40 && t <= 59) ? ((B&C) | (B&D) | (C&D)) : ((t >= 60 && t <= 79) ? B ^ C ^ D : 0)));
}
//获得Kr
unsigned int GetK(int r)
{
	/*
	if (r >= 0&& r <= 19)
	{
		return K[0];
	}else if (r >= 20 && r <= 39)
	{
		return K[1];
	}else if (r >= 40 && r <= 59)
	{
		return K[2];
	}else if (r >= 60 && r <= 79)
	{
		return K[3];
	}
	*/
	return (r >= 0 && r <= 19) ? K[0] : ((r >= 20 && r <= 39) ? K[1] : ((r >= 40 && r <= 59) ? K[2] : ((r >= 60 && r <= 79) ? K[3] : 0)));
}

//获得 Wt
void GetW(unsigned int w[])
{
	/*
	for (int i = 16; i < 80; i++)
		w[i] = ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) << 1) | ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) >> 31);
	*/
	for (int i = 16; i < 80; w[i++] = ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) << 1) | ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) >> 31));
}
// 步函数
void StepFunction(unsigned int w[], int t)
{
	unsigned int temp = ((A << 5) | (A >> 27)) + f(B, C, D, t) + E + w[t] + GetK(t);
	E = D, D = C, C = ((B << 30) | (B >> 2)), B = A, A = temp;
}
// 获得密文
void GetCipher(unsigned int * cipher)
{
	cipher[0] = A0 + A;
	cipher[1] = B0 + B;
	cipher[2] = C0 + C;
	cipher[3] = D0 + D;
	cipher[4] = E0 + E;
}

void SHA1(unsigned char *context,unsigned int * cipher)
{
	int len = strlen((char*)context) * 8;
	unsigned int group[80] = { 0 };

	SHA1_fill(context, group, len);
	GetW(group);
	for (int t = 0; t < 80; t++)
	{
		StepFunction(group, t);
	}


	GetCipher(cipher);

}
int main()
{
	unsigned char m[56];
	unsigned int c[5] = { 0 };
	printf("请输入长度小于56且不包含空格的明文：");
	scanf("%s", m);
	SHA1(m,c);
	/*密文输出*/
	printf("密文为：");
	for (int j = 0; j <= 4; j++) printf("%08X", c[j]);
	printf("\n");
	system("pause");
	return 0;
}