SHA1算法实现及详解

SHA1算法实现及详解

0X1 SHA1算法详解

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

整个算法的核心是一个包含4轮循环的模块，每轮循环由20个步骤组成。

如下图：

其中Yq代表原始消息， CVq代表初始化的链接变量，最终我们要的密文就是CYq+1

1. 附加填充位

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

2. 初始化链接变量

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

A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476, E = 0xC3D2SEO靠我E1F0

3. 非线性函数f函数

f t ( x , y , z ) = { C h ( x , y , z ) = ( x ⋀ y ) ⨁ ( ┐ x ⋀ z ) , 0 ≤ t ≤ 19 P a r SEO靠我i t y ( x , y , z ) = x ⨁ y ⨁ z , 0 ≤ t ≤ 19 M a j ( x , y , z ) = ( x ⋀ y ) ⨁ ( x ⋀ z ) ⨁ ( y ⋀ z )SEO靠我 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)SEO靠我 = (x \bigwedge y) \bigoplus ( \urcorner x \bigwedge z),& 0 \leq t \leq 19 \\ Parity(x, y ,z) =x \biSEO靠我goplus y\bigoplus z,& 0 \leq t \leq 19 \\ Maj(x, y ,z) = (x \bigwedge y) \bigoplus(x \bigwedge z) \bSEO靠我igoplus(y \bigwedge z) & 0 \leq t \leq 19 \\ Parity(x, y ,z) =x \bigoplus y\bigoplus z,& 0 \leq t \lSEO靠我eq 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)⨁(SEO靠我x⋀z)⨁(y⋀z)Parity(x,y,z)=x⨁y⨁z,​0≤t≤190≤t≤190≤t≤190≤t≤19​

4. K值的获取

步数Krr = 1 (0 <= t <= 19)0x5A827999r SEO靠我= 2 (20 <= t <= 39)0x6ED9EBA1r = 3 (40 <= t <= 59)0x8F1BBCDCr = 4 (60 <= t <= 79)0xCA62C1D6

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

5. W值的获取

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

注意是循环左移n比特

W一共分为80组，其中从W[0]到WSEO靠我[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 SEO靠我− 14 ) ⨁ W ( t − 16 ) , 16 ≤ t ≤ 79 \begin{cases} W_t = M_t^{(i)} & 0 \leq t \leq 15 \\ W_t =ROTL^1(SEO靠我W_{(t-3)}\bigoplus W_{(t-8)}\bigoplus W_{(t-14)}\bigoplus W_{(t-16)},& 16 \leq t \leq 79 \end{cases}SEO靠我 {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 ) +SEO靠我 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 SEO靠我= (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=(ROTSEO靠我L5(A)+ft(B,C,D)+E+Wt+Kr)mod232B=AC=ROTL30(B)mod232D=CE=D

其中t是步数，0 <= t <= 79，r为轮数， 0 <= r <= 4.

0X2源代码SEO靠我

#include <stdio.h> #include <stdlib.h> #include <string.h> #pragma warning(dSEO靠我isable:4996)//初始化链接变量 unsigned int A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x103SEO靠我25476, E = 0xC3D2E1F0; //第一次迭代的链接变量unsigned int K[4] = { 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62CSEO靠我1D6 }; //循环中用到的常量 unsigned int A0 = 0x67452301, B0 = 0xEFCDAB89, C0 = 0x98BADCFE, D0 = 0x103SEO靠我25476, E0 = 0xC3D2E1F0;// 字节转换，将四个字节转换为一个整型 int CharToWord(unsigned char *context, int i) SEO靠我 {return (((int)context[i] & 0x000000ff) << 24) | (((int)context[i + 1] & 0x000000ff) << 16) | SEO靠我(((int)context[i + 2] & 0x000000ff) << 8) | ((int)context[i + 3] & 0x000000ff); }// 填充补位获得原始SEO靠我明文 void SHA1_fill(unsigned char *plaintext, unsigned int *group, int length) {printfSEO靠我("补位后获得的明文：\n");int temp = length / 32, len = length;while (len > 0){if (len = len / 32){for (int j SEO靠我= 0; j < temp; j++){group[j] = CharToWord(plaintext, 4 * j);printf("%08X\n", group[j]);}}else{plaintSEO靠我ext[length / 8] = 0x80;group[temp] = CharToWord(plaintext, temp * 4);printf("%08X\n", group[temp]);bSEO靠我reak;}}group[15] = length;for (int i = temp + 1; i < 16; i++)printf("%08X\n", group[i]);} //SEO靠我 f函数 unsigned int f(int B, int C, int D, int t) {return (t >= 0 && t <= 19) ? ((B&C)SEO靠我 | (~B&D)) : ((t >= 20 && t <= 39) ? (B ^ C ^ D) : ((t >= 40 && t <= 59) ? ((B&C) | (B&D) | (C&D)) :SEO靠我 ((t >= 60 && t <= 79) ? B ^ C ^ D : 0))); } //获得Kr unsigned int GetK(int r)SEO靠我 {/*if (r >= 0&& r <= 19){return K[0];}else if (r >= 20 && r <= 39){return K[1];}else if (r SEO靠我>= 40 && r <= 59){return K[2];}else if (r >= 60 && r <= 79){return K[3];}*/return (r >= 0 && r <= 19SEO靠我) ? K[0] : ((r >= 20 && r <= 39) ? K[1] : ((r >= 40 && r <= 59) ? K[2] : ((r >= 60 && r <= 79) ? K[3SEO靠我] : 0))); }//获得 Wt void GetW(unsigned int w[]) {/*for (int i = 16; i < 80; iSEO靠我++)w[i] = ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) << 1) | ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^SEO靠我 w[i - 16]) >> 31);*/for (int i = 16; i < 80; w[i++] = ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]SEO靠我) << 1) | ((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]) >> 31)); } // 步函数 vSEO靠我oid StepFunction(unsigned int w[], int t) {unsigned int temp = ((A << 5) | (A >> 27)) + f(B,SEO靠我 C, D, t) + E + w[t] + GetK(t);E = D, D = C, C = ((B << 30) | (B >> 2)), B = A, A = temp; } SEO靠我 // 获得密文 void GetCipher(unsigned int * cipher) {cipher[0] = A0 + A;cipher[1] SEO靠我= B0 + B;cipher[2] = C0 + C;cipher[3] = D0 + D;cipher[4] = E0 + E; }void SHA1(unsigned char SEO靠我*context,unsigned int * cipher) {int len = strlen((char*)context) * 8;unsigned int group[80]SEO靠我 = { 0 };SHA1_fill(context, group, len);GetW(group);for (int t = 0; t < 80; t++){StepFunction(group,SEO靠我 t);}GetCipher(cipher);} int main() {unsigned char m[56];unsigned int c[5] = { 0 };pSEO靠我rintf("请输入长度小于56且不包含空格的明文：");scanf("%s", m);SHA1(m,c);/*密文输出*/printf("密文为：");for (int j = 0; j <= 4;SEO靠我 j++) printf("%08X", c[j]);printf("\n");system("pause");return 0; }