[C] Implement SHA-1

最近因為工作需要把一串字串經過處理後變成另一個長度最多 48-byte 的唯一的字串，能做到這類事情理所當然地就會往 MD5、SHA-1 這類 hash function 去找，而且因為不是要用作加密金鑰，對於安全性的要求並不高，所以後來就選了 SHA-1 當作目標。

實際看了下演算法，其實超簡單的...雖然會有一些細節要特別注意，但整體上的實作相當容易。以下就一一說明要注意的細節，C code 就放在最後面供參囉。

首先完整演算法可以直接參考 wikipedia 上的 pseudo code。不過最值得注意的一個重點在於 endian 的考量：SHA-1 基本上就是把 input 看成一串 bit stream，並且後面所有基於 32-bit WORD 為單位的 bitwise 及 arithmetic operations 都是基於 big endian 來做設計的，所以在現在許多平台都是走 little endian 的前提下，在運算上要特別注意這點，不然就會發現 hash 後的結果跟其他人都不同。這點在 SHA-1 基於 convention 的常數最為明顯 (下面列表的 H0 ~ H4 及 K1 ~ K4 這 9 個常數)

#define H0 0x67452301
#define H1 0xEFCDAB89
#define H2 0x98BADCFE
#define H3 0x10325476
#define H4 0xC3D2E1F0

#define K1 0x5A827999 // sqrt(2)
#define K2 0x6ED9EBA1 // sqrt(3)
#define K3 0x8F1BBCDC // sqrt(5)
#define K4 0xCA62C1D6 // sqrt(10)

同樣是 endian 衍伸的問題可以在 pseudo code 中的這一行發現：

append length of message (before pre-processing), in bits, as 64-bit big-endian integer

所以這一行對應的 code 就會發現抓那 64-bit 的 integer 的每個 byte 的時，放的順序會跟拿的順序相反 (line 49 ~ 56)

static inline void appendInputSize(char* chunk, int chunk_size, uint64_t input_size)
{
    char* ptr = (char*)(&input_size);
    for (int i = 0, idx = chunk_size; i < sizeof(input_size); ++i) {
        chunk[--idx] = *ptr;
        ++ptr;
    }
}

不過這邊可以再多注意一個細節：原始資料長度是用 bit 而不是 byte 計算，一開始沒注意到這點，還一直再想說到底哪邊寫錯為什麼就是不同...

preprocess 後、進入 main loop 前也有一段 code 是為了在轉成 32-bit unsigned integer 前確保運算結果符合 little endian 的方式所以做的轉換 (line 142 ~ 146)

// 32-bit big endian to 32-bit little endian
for (int i = 0; i < chunk_size; i += 4) {
    swap(chunk+i, chunk+i+3);
    swap(chunk+i+1, chunk+i+2);
}

當然，最後輸出時也要再轉成正確的順序 (line 117 ~ 127)

static inline void toHex(uint32_t value, char* out)
{
    const char* HEX_VAL = "0123456789ABCDEF";
    unsigned char* ptr = (unsigned char*)(&value);
    int idx = sizeof(value) << 1;
    for (int i = 0; i < sizeof(value); ++i) {
        out[--idx] = HEX_VAL[(*ptr) & 0x0F];
        out[--idx] = HEX_VAL[(*ptr) >> 4];
        ++ptr;
    }
}

大致上只要注意這些點、照著做就能寫出來了，演算法流程這邊就不多說了，請參考下面完整的 source code

	#include <stdlib.h>
	#include <stdint.h> // for uint32_t
	#include <limits.h> // for CHAR_BIT
	#include <assert.h>
	#include <stdbool.h>
	#define H0 0x67452301
	#define H1 0xEFCDAB89
	#define H2 0x98BADCFE
	#define H3 0x10325476
	#define H4 0xC3D2E1F0
	#define K1 0x5A827999
	#define K2 0x6ED9EBA1
	#define K3 0x8F1BBCDC
	#define K4 0xCA62C1D6
	inline char* mymalloc(size_t size)
	{
	return (char*)malloc(size);
	}
	inline void myfree(char* ptr)
	{
	free(ptr);
	}
	static inline uint32_t rotateLeft32 (uint32_t n, unsigned int c)
	{
	const unsigned int mask = (CHAR_BIT * sizeof(n) - 1); // assumes width is a power of 2.
	c &= mask; // make sure c is not larger than (CHAR_BIT * sizeof(n))
	return (n<<c) | (n>>( (-c)&mask ));
	}
	static inline uint32_t getPaddingSize(uint32_t input_size)
	{
	input_size = input_size * CHAR_BIT + 1; // change to bit length, and always append bit "1" at the last
	const uint32_t mask = 0x1FF; // 511
	return (448 - input_size) & mask;
	}
	static inline void appendInputSize(char* chunk, int chunk_size, uint64_t input_size)
	{
	char* ptr = (char*)(&input_size);
	for (int i = 0, idx = chunk_size; i < sizeof(input_size); ++i) {
	chunk[--idx] = *ptr;
	++ptr;
	}
	}
	char* preprocess(const char* input, uint32_t input_size, uint32_t *chunk_size)
	{
	const uint32_t pad_size = getPaddingSize(input_size);
	const uint32_t byte_cnt = (input_size * CHAR_BIT + 1 + pad_size + 64) / CHAR_BIT;
	char* chunk = mymalloc(byte_cnt);
	int idx = 0;
	for (int i = 0; i < input_size; ++i) {
	chunk[idx++] = input[i];
	}
	chunk[idx++] = 0x80; // pad 1 at the last of input
	for (int i = 0; i < (pad_size / CHAR_BIT); ++i) {
	chunk[idx++] = 0; // pad 0
	}
	assert( ((idx + 8) == byte_cnt) && "byte count does not match with pre-computed chunk size after padding 0");
	appendInputSize(chunk, byte_cnt, input_size * CHAR_BIT);
	*chunk_size = byte_cnt;
	return chunk;
	}
	struct HashComponent {
	uint32_t A, B, C, D, E;
	};
	typedef struct HashComponent HashComponent;
	static void SHA1(uint32_t* chunk, HashComponent *out)
	{
	uint32_t word[80];
	for (int i = 0; i < 16; ++i) { word[i] = chunk[i]; }
	for (int i = 16; i < 80; ++i) {
	word[i] = rotateLeft32(((word[i-3] ^ word[i-8]) ^ word[i-14]) ^ word[i-16], 1);
	}
	uint32_t A = H0, B = H1, C = H2, D = H3, E = H4, tmp;
	#define HASH(beg, end, f, K) \
	for (int i = beg; i < end; ++i) { \
	tmp = rotateLeft32(A, 5) + E + (f) + K + word[i]; \
	E = D; D = C; C = rotateLeft32(B, 30); B = A; A = tmp; \
	}
	HASH( 0, 20, (B & C) | ((~B) & D), K1)
	HASH(20, 40, (B ^ C) ^ D, K2)
	HASH(40, 60, (B & C) | (B & D) | (C & D), K3)
	HASH(60, 80, (B ^ C) ^ D, K4)
	#undef HASH
	out->A += A;
	out->B += B;
	out->C += C;
	out->D += D;
	out->E += E;
	}
	static inline void toHex(uint32_t value, char* out)
	{
	const char* HEX_VAL = "0123456789ABCDEF";
	unsigned char* ptr = (unsigned char*)(&value);
	int idx = sizeof(value) << 1;
	for (int i = 0; i < sizeof(value); ++i) {
	out[--idx] = HEX_VAL[(*ptr) & 0x0F];
	out[--idx] = HEX_VAL[(*ptr) >> 4];
	++ptr;
	}
	}
	static inline void swap(char *lhs, char *rhs)
	{
	char tmp = *lhs;
	*lhs = *rhs;
	*rhs = tmp;
	}
	const char* genSHA1(const char* input, size_t input_size)
	{
	uint32_t chunk_size = 0;
	char *chunk = preprocess(input, input_size, &chunk_size);
	// 32-bit big endian to 32-bit little endian
	for (int i = 0; i < chunk_size; i += 4) {
	swap(chunk+i, chunk+i+3);
	swap(chunk+i+1, chunk+i+2);
	}
	HashComponent out = {.A=H0, .B=H1, .C=H2, .D=H3, .E=H4};
	uint32_t *numeric_chunk = (uint32_t*)chunk;
	for (uint32_t i = 0; i < chunk_size / 4; i += 16) {
	SHA1(numeric_chunk+i, &out);
	}
	char* digest = mymalloc(41);
	toHex(out.A, digest);
	toHex(out.B, digest + 8);
	toHex(out.C, digest + 16);
	toHex(out.D, digest + 24);
	toHex(out.E, digest + 32);
	digest[40] = '\0';
	myfree(chunk);
	return digest;
	}

view raw sha1.c hosted with ❤ by GitHub