SHA1算法实现及详解

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)=\{\begin{array}{ll}Ch(x,y,z)=(x\bigwedge y)⨁(┐x\bigwedge z),& 0\le t\le 19\\ Parity(x,y,z)=x⨁y⨁z,& 0\le t\le 19\\ Maj(x,y,z)=(x\bigwedge y)⨁(x\bigwedge z)⨁(y\bigwedge z)& 0\le t\le 19\\ Parity(x,y,z)=x⨁y⨁z,& 0\le t\le 19\end{array}$$

4. K值的获取

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

5. W值的获取

$ROT{L}^n(x)表示对32位比特的变量循环左移n比特$
注意是循环左移n比特

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

$$\{\begin{array}{ll}{W}_t=M_t^{(i)}& 0\le t\le 15\\ W_t=ROT{L}^1(W_{(t-3)}⨁W_{(t-8)}⨁W_{(t-14)}⨁W_{(t-16)},& 16\le t\le 79\end{array}$$

6. 步函数

$$\begin{gathered} A=(ROT{L}^5(A)+f^t(B,C,D)+E+W^t+K^r)mod{2}^{32} \\ B=A \\ C=ROT{L}^{30}(B)mod{2}^{32} \\ D=C \\ E=D \end{gathered}$$
其中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;
}