寫在前面

??在之前的工作中，用到了CRC16、MD5 和 SHA1 算法，主要用來校驗下發(fā)的文件。網(wǎng)上關(guān)于這些算法的文章鋪天蓋地，以下內(nèi)容僅僅是自己在學習時候的一個記錄，一些套話來自于互聯(lián)網(wǎng)。下面先來看看 SHA1。
?? 以下算法分析基于 RFC 3174。

Request For Comments (RFC），所有關(guān)于Internet 的正式標準都是以RFC(Request for Comment )文檔出版。需要注意的是，還有大量的RFC文檔都不是正式的標準，出版目的都是為了提供信息。

由互聯(lián)網(wǎng)協(xié)會（Internet Society，簡稱ISOC）贊助發(fā)行，會交到互聯(lián)網(wǎng)工程工作小組（IETF）和互聯(lián)網(wǎng)結(jié)構(gòu)委員會（IAB）。文檔可由網(wǎng)站 https://www.ietf.org/ 下載。

什么是 SHA1

??全稱為 Secure Hash Algorithm 1（安全散列算法1）。是一種密碼散列函數(shù)，美國國家安全局設(shè)計，并由美國國家標準技術(shù)研究所（NIST）發(fā)布為聯(lián)邦數(shù)據(jù)處理標準（FIPS）。1993年 發(fā)布 SHA0，1995年發(fā)布了SHA1。其設(shè)計原理相似于MIT教授 Ronald L. Rivest 所設(shè)計的密碼學散列算法 MD4 和 MD5。
??SHA1 可以生成一個被稱為消息摘要的160位（20字節(jié)）散列值，散列值通常的呈現(xiàn)形式為40個十六進制數(shù)。主要適用于數(shù)字簽名標準 （Digital Signature Standard DSS）里面定義的數(shù)字簽名算法（Digital Signature Algorithm DSA）。

SHA實際上是一系列算法的統(tǒng)稱，分別包括：SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。

類別消息長度分組長度計算字長計算步驟消息摘要長度

SHA-1	小于2^64位	512	32	80	160
SHA-224	小于2^64位	512	32	64	224
SHA-256	小于2^64位	512	32	64	256
SHA-384	小于2^128位	1024	64	80	384
SHA-512	小于2^128位	1024	64	80	512

安全性

??2005年二月，王小云、殷益群及于紅波發(fā)表了對完整版SHA-1的攻擊，只需少于269的計算復雜度，就能找到一組碰撞。（利用生日攻擊法找到碰撞需要280的計算復雜度。）
??2017年2月23日，CWI Amsterdam與Google宣布了一個成功的SHA-1碰撞攻擊，發(fā)布了兩份內(nèi)容不同但SHA-1散列值相同的PDF文件作為概念證明。

實現(xiàn)原理

??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位，產(chǎn)生的輸出是一個160位的報文摘要。）根據(jù)算法文檔，算法的實現(xiàn)主要由以下幾部分來組成。

RFC3174 中的第二部分，給出了一些術(shù)語，總結(jié)一下也就下面三點：

• SHA-1算法把輸入消息當做 比特位字符串 來處理
• 輸入是按 512 位（16個字）的分組進行處理的
• 字 等于32位字符串，可以表示為8個十六進制數(shù)字的序列。（A word equals a 32-bit string which may be represented as a sequence of 8 hex digits. ）

RFC3174 中的第三部分，給出了一些對于 字 的基本運算，總結(jié)一下：

• 按位邏輯字操作
  • 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 代表兩個整數(shù) x 和y, 其中 0 <= x < 2^32 且 0 <= y < 2^32. 令整數(shù)z = (x + y) mod 2^32. 這時候 0 <= z < 2^32。將z轉(zhuǎn)換成字Z，那么就是 Z = X + Y。
• 循環(huán)左移位操作符 S^n(X)。X是一個字，n是一個整數(shù)，0<=n<=32。S^n(X) = (X << n) OR (X >> 32-n)。X << n定義如下：拋棄最左邊的n位數(shù)字，將各個位依次向左移動n位，然后用0填補右邊的n位（最后結(jié)果還是32位）。X>>n是拋棄右邊的n位，將各個位依次向右移動n位，然后在左邊的n位填0。因此可以叫S^n(X)位循環(huán)右移位運算。

RFC3174 中的第四部分，介紹了 消息填充 。
??前面說了，SHA-1算法是以512一包來處理消息的，但是很多情況下，消息長度并不是512的整數(shù)倍，這個時候就需要對原始消息進行填充。

補位
原始消息必須進行補位，以使其長度在對512取模以后的余數(shù)是448。也就是說，（補位后的消息長度）%512 = 448。即使長度已經(jīng)滿足對512取模后余數(shù)是448，補位也必須要進行。
補位是這樣進行的：先補一個1，然后再補0 ，直到長度滿足對512取模后余數(shù)是448。總而言之，補位是至少補一位，最多補512位。

補長度
就是將原始數(shù)據(jù)的長度補到已經(jīng)進行了補位操作的消息后面。通常用兩個字（64位）來表示原始消息的長度。如果消息長度不大于2^64，那么第一個字就是0。

RFC3174 中的第五部分，給出了算法使用的各種函數(shù)和常量 。
??在SHA-1中使用了一系列邏輯函數(shù)f（0），f（1），…，f（79）。 每個f（t），0 <= t <= 79，對三個32位字B，C，D進行操作，并產(chǎn)生一個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中使用一系列常數(shù)字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).

RFC3174 中的第六部分，給出了算法具體實現(xiàn)方法 。
經(jīng)過前面的準備，接下來就是計算信息摘要了。SHA1有4輪運算，每一輪包括20個步驟，一共80步，最終產(chǎn)生160位的信息摘要，這160位的摘要存放在5個32位的鏈接變量中。
在SHA1的4論運算中，雖然進行的就具體操作函數(shù)不同，但邏輯過程卻是一致的。首先，定義5個變量，假設(shè)為H0、H1、H2、H3、H4，對其分別進行如下操作：
（A）將A左移5為與 函數(shù)的結(jié)果求和，再與對應的子明文分組、E以及計算常數(shù)求和后的結(jié)果賦予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_ENDIANtypedef struct {unsigned long state[5]; /* 160(5×32)比特的消息摘要（即SHA-1算法要得出的） */unsigned long count[2]; /* 儲存消息的長度（單位：比特） */unsigned char buffer[64]; /* 512(64×8)比特（位）的消息塊（由原始消息經(jīng)處理得出） */ } 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 SHA1HANDSOFFstatic unsigned char workspace[64];block = (CHAR64LONG16 *)workspace;memcpy(block, buffer, 64); #elseblock = (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兩個宏函數(shù)，其原因前面已經(jīng)介紹了。因為第0~15輪運算和16~79輪運算的時候消息塊M(i)和字塊W(i)的轉(zhuǎn)換是不一樣的。后面的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);/* 完成的就是更新緩沖區(qū)H0～H4的內(nèi)容。然后把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獲得的就是字節(jié)數(shù)，j = (j >> 3) & 63得到的就是低6位的值，也就是代表64個字節(jié)（512位）長度的消息。，因為我們每次進行計算都是處理512位的消息數(shù)據(jù)。 */j = (context->count[0] >> 3) & 63;/* context->count[ ]存儲的是消息的長度，超出context->count[0]的存儲范圍的部分存儲在context->count[1]中。len<<3就是len*8的意思，因為len的單位是字節(jié)，而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個字節(jié)，就分開處理，每64個字節(jié)處理一次，然后再處理后面的64個字節(jié)，重復這個過程；否則就直接將數(shù)據(jù)附加到buffer末尾 */if ((j + len) > 63){memcpy(&context->buffer[j], data, (i = 64 - j)); /* i=64-j，然后從data中復制i個字節(jié)的數(shù)據(jù)附加到context->buffer[j]末尾，也就是說給buffer湊成了64個字節(jié) */SHA1Transform(context->state, context->buffer); /* 執(zhí)行SHA1Transform()來開始一次消息摘要的計算 *//* 每64個字節(jié)處理一次 */for (; i + 63 < len; i += 64){SHA1Transform(context->state, &data[i]);}j = 0;}else{i = 0;}/* 如果前面的if不成立，那么也就是說原始數(shù)據(jù)context->buffer加上新的數(shù)據(jù)data的長度還不足以湊成64個字節(jié)，所以直接附加上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 */}/* 填充的時候是以字節(jié)為單位的，最少1個字節(jié)，最多64個字節(jié)。并且第一位要填充1，后面都填充0。所以拿到一個消息我們首先要給他填充一個字節(jié)的10 000 000.SHA1Update() 函數(shù)就是完成的數(shù)據(jù)填充（附加）操作 */SHA1Update(context, (unsigned char *)"\200 ", 1);/* 循環(huán)測試數(shù)據(jù)模512是否與448同余。不滿足條件就填充全一個字節(jié)0。 *//* 使用 while ((context->count[0] & 511) != 448) 貌似更合適。但是，504后三位全0,511后三位全1。context->count中存儲的是消息的長度，它的單位是：位。前面我們提到了我們的數(shù)據(jù)是以字節(jié)來存儲的，所以context->count[ ]中的數(shù)據(jù)肯定是8個倍數(shù)，所以后三位肯定是000。所以不管是000&000，還是000&111其結(jié)果都是0。 */while ((context->count[0] & 504) != 448){SHA1Update(context, (unsigned char *)"\0 ", 1);}/* 這將觸發(fā)SHA1Transform()函數(shù)的調(diào)用，該函數(shù)的功能就是進行運算，得出160位的消息摘要（message digest）并儲存在context-state[ ]中，它是整個SHA-1算法的核心 */SHA1Update(context, finalcount, 8); /* Should cause a SHA1Transform() *//* 最后的這步轉(zhuǎn)換將消息摘要轉(zhuǎn)換成單字節(jié)序列。用代碼來解釋就是：將context-state[5]中儲存的20個字節(jié)（5×4字節(jié)）的消息摘要取出，將其存儲在20個單字節(jié)的數(shù)組digest中。并且按大端序存儲（與之前分析context->count[ ]到finalcount[ ]轉(zhuǎn)換的思路相同） */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 }

使用方式

??在實際使用時，往往需要多次調(diào)用循環(huán)計算。因為要計算的內(nèi)容可能很長，需要分包一次次計算。上面的源碼就是考慮到該種問題而實現(xiàn)的！使用方式如下：

SHA1_CTX ctx; unsigned char hash[20]; unsigned char abc[] = "abc"; /* 計算前，先初始化 */ SHA1Init(&ctx); /* 多次調(diào)用 SHA1Update 循環(huán)計算多個包數(shù)據(jù)（如果有的話） */ SHA1Update(&ctx, abc, 3); /* 最后調(diào)用 SHA1Final 獲取最終結(jié)果 */ SHA1Final(hash, &ctx);

最終，在數(shù)組hash中存放的就是最終計算結(jié)果！

附件

SHA1 算法 官方文檔 rfc3174

總結(jié)

以上是生活随笔為你收集整理的常用算法 之三 详解 SHA1 实现（基于算法的官方原文档）及源码详细注释的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。