- Hash函数介绍
Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
消息是任意有限长度，哈希值是固定长度。
Hash的概念起源于1956年，Dumey用它来解决symbol table question(符号表问题)。使得数据表的插入、删除、查询操作可以在平均常数时间完成。
- Hash函数的特点
单向性（抗原像）：对干任意给定的消息，计算其哈希值容易。但是，对于给定的哈希值h，要找到M使得H(M)＝h在计算上是不可行的。
抗弱碰撞（抗二次原像）：对于给定的消息M1，要发现另一个消息M2，满足H( M1 )＝H(M2)在计算上是不可行的。
抗强碰撞：找任意一对不同的消息M1，M2 ，使H(M1)＝H(M2 )在计算上是不可行的。
- SHA-1哈希算法介绍
SHA (Secure Hash Algorithm，译作安全散列算法) 是美国国家安全局 (NSA) 设计，美国国家标准与技术研究院(NIST) 发布的一系列密码散列函数。正式名称为 SHA 的家族第一个成员发布于 1993年。然而人们给它取了一个非正式的名称 SHA-0 以避免与它的后继者混淆。两年之后， SHA-1，第一个 SHA 的后继者发布了。 另外还有四种变体，曾经发布以提升输出的范围和变更一些细微设计： SHA-224, SHA-256, SHA-384 和 SHA-512 (这些有时候也被称做 SHA-2)。
最初载明的算法于1993年发布，称做安全散列标准 (Secure Hash Standard)，FIPS PUB 180。这个版本常被称为 "SHA-0"。它在发布之后很快就被NSA撤回，并且以 1995年发布的修订版本 FIPS PUB 180-1 (通常称为 "SHA-1") 取代。根据 NSA的说法，它修正了一个在原始算法中会降低密码安全性的错误。然而 NSA 并没有提供任何进一步的解释或证明该错误已被修正。1998年，在一次对 SHA-0 的攻击中发现这次攻击并不能适用于 SHA-1 — 我们不知道这是否就是NSA 所发现的错误，但这或许暗示我们这次修正已经提升了安全性。SHA-1已经被公众密码社群做了非常严密的检验而还没发现到有不安全的地方，它在一段时间被认为是安全的，直到Google宣布攻破SHA-1。
SHA-0 和 SHA-1 会从一个最大 264 位元的讯息中产生一串 160 位元的摘要，然后以设计 MD4 及 MD5 讯息摘要算法的 MIT 教授Ronald L. Rivest类似的原理为基础来加密。
- SHA-1算法介绍
- SHA-1算法步骤
填充消息：
假设输入消息M，首先应该填充消息，保证输入SHA-1计算的整个消息长度是512bits的倍数。
假设消息的长度为1bits，在原始消息M尾部增加1个比特位"1"和k个"0"比特位，l和k满足l + 1 + k ≡ 512 - 64(mod 512)，并且为最小负整数。
然后再在填充消息的末尾添加64-bit的块，该64-bit块是原始消息比特位长度变换为二进制块，如果消息长度变换为二进制块的位个数小于64，则在左边补0，使得块的长度刚好等于64bits。
被填充消息分组：
把填充后的整个消息按照512-bit块进行划分，假若刚好划分为N个512-bit块，依次为：M(0)，M(1)，···，M(N)。而每个512-bit块又可由16个32-bit字组成，第i个512-bit块的第一个32-bit字，记为M0(i)，M1(i)，···，M15(i)
初始化变量：
SHA-1的初值变量IV为160bits的数据块，即5个32-bit的字，依次为H0(0)，H1(0)，H2(0)，H3(0)，H4(0)，初值变量设置为：
H0(0) = 67452301，
H1(0) = EFCDAB89，
H2(0) = 98BADCFE，
H3(0) = 10325476，
H4(0) = C3D2E1F0
数据扩展：
分块处理中还需要使用W[t]，t=0，1，···，79。W[t]是由输入512-bit分块通过混合和移动扩充而来。由输入的M(i)分组，分为16个32-bit字M0(i)，M1(i)，···，M15(i)，然后将16个字扩充为80个32-bit字，扩充方法如下：
- 实验内容
按照消息摘要函数SHA-1算法的标准FIPS-180-2的要求，从文件中读取消息，然后对消息分组，并对最后一个分组进行填充，并通过数据扩充算法扩充到80个字。
输入为ASCII码，程序的默认输入为FIPS-180-2中示例的“abc”。
输出填充后的最后一个分组中的W0, W1，W14 ，W15.然后数据扩充到80个字，然后输出W16, W79 （十六进制）。其中填充过程写成一个函数，数据扩充过程写成一个函数，数据扩充中循环移位也可以写成一个函数。
- 实现代码
SHA-1的代码官方是有给出的，为了适配实验要求，这是经常修改后的代码，本人菜狗子一个，如果有错误或者不足之处，还望大佬指出。
#include <stdio.h>
include <string.h>
typedef struct SHA1Context
{
unsigned Message_Digest[5];
unsigned Length_Low;
unsigned Length_High;
unsigned char Message_Block[64];
int Message_Block_Index;
int Computed;
int Corrupted;
} SHA1Context;
define SHA1CircularShift(bits,word) ((((word) << (bits)) & 0xFFFFFFFF) | ((word) >> (32-(bits))))
void SHA1Reset(SHA1Context *context)
{
context->Length_Low = 0;
context->Length_High = 0;
context->Message_Block_Index = 0;
context->Message_Digest[0] = 0x67452301;
context->Message_Digest[1] = 0xEFCDAB89;
context->Message_Digest[2] = 0x98BADCFE;
context->Message_Digest[3] = 0x10325476;
context->Message_Digest[4] = 0xC3D2E1F0;
context->Computed = 0;
context->Corrupted = 0;
}
void SHA1ProcessMessageBlock(SHA1Context *context)
{
const unsigned K[] =
{
0x5A827999,
0x6ED9EBA1,
0x8F1BBCDC,
0xCA62C1D6
};
int t;
unsigned temp;
unsigned W[80];
unsigned A, B, C, D, E;
for(t = 0; t < 16; t++)
{
W[t] = ((unsigned) context->Message_Block[t * 4]) << 24;
W[t] |= ((unsigned) context->Message_Block[t * 4 + 1]) << 16;
W[t] |= ((unsigned) context->Message_Block[t * 4 + 2]) << 8;
W[t] |= ((unsigned) context->Message_Block[t * 4 + 3]);
}
for(t = 16; t < 80; t++)
{
W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
}
A = context->Message_Digest[0];
B = context->Message_Digest[1];
C = context->Message_Digest[2];
D = context->Message_Digest[3];
E = context->Message_Digest[4];
printf("W[0] = %08lx\n",W[0]);
printf("W[1] = %08lx\n",W[1]);
printf("W[14] = %08lx\n",W[14]);
printf("W[15] = %08lx\n",W[15]);
printf("W[16] = %08lx\n",W[16]);
printf("W[79] = %08lx\n",W[79]);
for(t = 0; t < 20; t++)
{
temp = SHA1CircularShift(5,A) + ((B & C) | ((~B) & D)) + E + W[t] + K[0];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
for(t = 20; t < 40; t++)
{
temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
for(t = 40; t < 60; t++)
{
temp = SHA1CircularShift(5,A) + ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
for(t = 60; t < 80; t++)
{
temp = SHA1CircularShift(5, A) + (B ^ C ^ D) + E + W[t] + K[3];
temp &= 0xFFFFFFFF;
E = D;
D = C;
C = SHA1CircularShift(30,B);
B = A;
A = temp;
}
context->Message_Digest[0] = (context->Message_Digest[0] + A) & 0xFFFFFFFF;
context->Message_Digest[1] = (context->Message_Digest[1] + B) & 0xFFFFFFFF;
context->Message_Digest[2] = (context->Message_Digest[2] + C) & 0xFFFFFFFF;
context->Message_Digest[3] = (context->Message_Digest[3] + D) & 0xFFFFFFFF;
context->Message_Digest[4] = (context->Message_Digest[4] + E) & 0xFFFFFFFF;
context->Message_Block_Index = 0;
}
void SHA1PadMessage(SHA1Context *context)
{
if (context->Message_Block_Index > 55)
{
context->Message_Block[context->Message_Block_Index++] = 0x80;
while(context->Message_Block_Index < 64)
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
SHA1ProcessMessageBlock(context);
while(context->Message_Block_Index < 56)
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
}
else
{
context->Message_Block[context->Message_Block_Index++] = 0x80;
while(context->Message_Block_Index < 56)
{
context->Message_Block[context->Message_Block_Index++] = 0;
}
}
context->Message_Block[56] = (context->Length_High >> 24) & 0xFF;
context->Message_Block[57] = (context->Length_High >> 16) & 0xFF;
context->Message_Block[58] = (context->Length_High >> 8) & 0xFF;
context->Message_Block[59] = (context->Length_High) & 0xFF;
context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF;
context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF;
context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF;
context->Message_Block[63] = (context->Length_Low) & 0xFF;
SHA1ProcessMessageBlock(context);
}
int SHA1Result(SHA1Context *context)
{
if (context->Corrupted)
{
return 0;
}
if (!context->Computed)
{
SHA1PadMessage(context);
context->Computed = 1;
}
return 1;
}
void SHA1Input(SHA1Context context, const unsigned char message_array, unsigned length)
{
if (!length)
{
return;
}
if (context->Computed || context->Corrupted)
{
context->Corrupted = 1;
return;
}
while(length-- && !context->Corrupted)
{
context->Message_Block[context->Message_Block_Index++] = (*message_array & 0xFF);
context->Length_Low += 8;
context->Length_Low &= 0xFFFFFFFF;
if (context->Length_Low == 0)
{
context->Length_High++;
context->Length_High &= 0xFFFFFFFF;
if (context->Length_High == 0)
{
context->Corrupted = 1;
}
}
if (context->Message_Block_Index == 64)
{
SHA1ProcessMessageBlock(context);
}
message_array++;
}
}
int main()
{
SHA1Context sha;
int i;
unsigned char input[64];
printf("ASCII string：");
scanf("%s", input);
printf("\n");
SHA1Reset(&sha);
SHA1Input(&sha, (const unsigned char *) input, strlen(input));
if (!SHA1Result(&sha))
{
fprintf(stderr, "ERROR-- could not compute message digest\n");
}
else
{
printf("\n\n\nThe resulting 160-bit message digest is：\n\n");
for(i = 0; i < 5 ; i++)
{
printf("%x ", sha.Message_Digest[i]);
}
printf("\n\n");
}
return 0;
}
- 输出结果
当输入小于64位时：
当输入大于64位时：
SHA1和MD5的算法说明
SHA1和MD5的算法都是从MD4算法改进而来的2种算法，基本思路都是将信息分成N个分组，每组64个字节，每个分组都进行摘要运算。当一个分组的摘要运算完毕后，将上一个分组的结果也用于下一个分组的运算。
信息的长度（注意是bit位长度，不是字节长度）用64位表示，也要参加信息摘要运算，而且是放在最后一个分组的末尾，所以长度信息要占据8个字节。
如果信息数据最后一个分组长度小于64个字节，在后面添加0x80标志结束，如果此时数据+结束标志已经<=56个字节，还可以放入长度数据，就在结束标志到第56个字节补0，然后放入长度，如果此时信息数据+结束标志已经大于56字节，那么这个分组后面补0，进行一次摘要运算，然后再建立一个分组，前面全部补0，最后16个字节放长度，再进行一次摘要。
需要注意的地方如下。
MD5最后生成的摘要信息是16个字节，SHA1是20个字节。
MD5和SHA1的分组信息运算，分组里面的的数据都会被视为16个DWORD，而MD5算法认为这些DWORD的字节序列是LITTLE-ENDIAN,而SHA1的算法认为DWORD是BIG-ENDIAN的。所以在不同字节序的主机上要进行转换。
放入最后一个分组的长度信息，是原始数据长度，而且是BIT位长度，其是一个uint64_t，而MD5算法要求放入的长度是LITTLE-ENDIAN的，而SHA1算法则要求这个长度是BIG-ENDIAN的。不同的平台要进行转换。
当然生成的结果，MD5也要求是LITTLE-ENDIAN，SHA1也要求结果是BIG-ENDIAN的，不同的平台还是要进行转换。
我们贴几个摘要处理过程的分组信息，帮助大家理解。如果要处理的数据是3个字节字符串”abc”，其在MD5的算法中，只需要一个分组参加，数据是16进制，如下：
61 62 63 80 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 18 00 00 00 00 00 00 00
而SHA1算法中，也只有一个分组，如下，大家注意长度位置上的差别。十六进制的18标识24个bit3个字节。
61 62 63 80 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 18
如果要处理的数据是80个字节的"12345678901234567890123456789012345678901234567890123456789012345678901234567890"，其在MD5的算法会被分成2个分组，
第一个分组如下，
31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36
37 38 39 30 31 32 33 34 35 36 37 38 39 30 31 32
33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38
39 30 31 32 33 34 35 36 37 38 39 30 31 32 33 34
第二个分组如下
35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 30
80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 80 02 00 00 00 00 00 00