SHA-1

プログラミング

MD5もやったしついでにSHA-1もやるか、という夢を見て起きたので、
起きてすぐ作業に入って、1時間ぐらいで作成。
MD5作ったときは12時間ぐらいかかったのにね。*1
SHA1とMD5はMD4の派生なので、MD5と非常に似てる。
計算部分と、最後のパディング以外はほとんど流用可能。
また、計算部分もMD5と比べてわかりやすいと思う。


参考
US Secure Hash Algorithm 1 (SHA1)



sha1.h

#ifndef SHA1_H
#define SHA1_H

#define BYTE unsigned char     // Unsigned  8bit
#define UINT32 unsigned long int // Unsigned 32bit word


typedef struct sha1{
	BYTE tmp[64];
	UINT32 sha1[5];
	UINT32 length_high; // 上位
	UINT32 length_low;  // 下位
	BYTE i; // tmp参照カウンタ
} SHA1;

void sha1_init(SHA1 *p);
void sha1_add(SHA1 *p, BYTE *d, UINT32 length);
void sha1_finish(SHA1 *p);
static void _sha1_calc(SHA1 *p);

////////////////////////////////////////


// 初期化
void sha1_init(SHA1 *p){
	p->sha1[0] = 0x67452301;
	p->sha1[1] = 0xEFCDAB89;
	p->sha1[2] = 0x98BADCFE;
	p->sha1[3] = 0x10325476;
	p->sha1[4] = 0xC3D2E1F0;
	p->i = p->length_low = p->length_high = 0;
}
// バッファへ読み込む
void sha1_add(SHA1 *p, BYTE *d, UINT32 length){
#ifdef _STRING_H_
	p->length_low += length;
	while(length){
		if(length <= 64-p->i){ 
			memcpy(p->tmp+p->i, d, length);
			p->i += length;
			length = 0;
			if(p->i == 64) _sha1_calc(p);
		}else{
			memcpy(p->tmp+p->i, d, 64-p->i);
			length -= 64-p->i;
			d += 64-p->i;
			_sha1_calc(p);
		}
	}
#else
	p->length_low += length;
	while(length--){
		p->tmp[p->i++] = *d++;
		if(p->i == 64) _sha1_calc(p);
	}
#endif
}
// 最終処理
void sha1_finish(SHA1 *p){
	UINT32 n;
	p->tmp[p->i++] = 0x80; // 終端文字 0x80
	
	// 56byteより大きい場合、64byteまで0x00埋めをして、一度算出
	if(p->i > 56){
#ifdef _STRING_H_
		memset(&p->tmp[p->i], 0, 64-p->i);
#else
		while(p->i < 64) p->tmp[p->i++] = 0x00; // 1byteづつ
#endif		
		_sha1_calc(p);
	}
	
	// 56byte未満なら56byte(448bit)目まで0で穴埋め
#ifdef _STRING_H_
	if(p->i < 56) memset(p->tmp+p->i, '\0', 56-p->i); p->i = 56;
#else
	while(p->i < 56) p->tmp[p->i++] = 0x00; // 1byteづつ
#endif

	// 最後の64bit(8byte)の処理
	// データ長(読み込んだデータサイズ(bit)を64bitで表現)
	
	// 上位32bitにデータ長の上位32bit
	n = (p->length_low >> (32 - 3)) + (p->length_high << 3);
	p->tmp[p->i++] = n>>24  & 0xFF;
	p->tmp[p->i++] =(n>>16) & 0xFF;
	p->tmp[p->i++] =(n>> 8) & 0xFF;
	p->tmp[p->i++] = n      & 0xFF;
	
	// 下位32bitにデータ長の下位32bit,）
	n =  p->length_low << 3;
	p->tmp[p->i++] = n>>24  & 0xFF;
	p->tmp[p->i++] =(n>>16) & 0xFF;
	p->tmp[p->i++] =(n>> 8) & 0xFF;
	p->tmp[p->i++] = n      & 0xFF;
	
	// 最終計算
	_sha1_calc(p);

}
// SHA-1算出
static void _sha1_calc(SHA1 *p){
	UINT32 temp;
	UINT32 word[80];
	UINT32 a=p->sha1[0];
	UINT32 b=p->sha1[1];
	UINT32 c=p->sha1[2];
	UINT32 d=p->sha1[3];
	UINT32 e=p->sha1[4];
	
	enum{
		K0= 0x5A827999, //  0-19
		K1= 0x6ED9EBA1, // 20-39
		K2= 0x8F1BBCDC, // 40-59
		K3= 0xCA62C1D6  // 60-79
	};
	
	
#define SHIFT(N,S) (((N)<<(S))|((N)>>(32-S)))
	// W0-W15 
#define F(P) ((P)[0]<<24|(P)[1]<<16|(P)[2]<<8|(P)[3])
	word[0] = F(p->tmp+0);  word[1] = F(p->tmp+4);  word[2] = F(p->tmp+8);  word[3] = F(p->tmp+12);
	word[4] = F(p->tmp+16); word[5] = F(p->tmp+20); word[6] = F(p->tmp+24); word[7] = F(p->tmp+28);
	word[8] = F(p->tmp+32); word[9] = F(p->tmp+36); word[10]= F(p->tmp+40); word[11]= F(p->tmp+44);
	word[12]= F(p->tmp+48); word[13]= F(p->tmp+52); word[14]= F(p->tmp+56); word[15]= F(p->tmp+60);
#undef F
	// W16-W79
//	for(t=16; t<80; ++t) word[t] = word[t-3]^word[t-8]^word[t-14]^word[t-16], word[t]=SHIFT(word[t],1);
#define F(T) word[T] = word[T-3]^word[T-8]^word[T-14]^word[T-16], word[T]=SHIFT(word[T],1)
						  F(16); F(17); F(18); F(19);
	F(20); F(21); F(22); F(23); F(24); F(25); F(26); F(27); F(28); F(29);
	F(30); F(31); F(32); F(33); F(34); F(35); F(36); F(37); F(38); F(39);
	F(40); F(41); F(42); F(43); F(44); F(45); F(46); F(47); F(48); F(49);
	F(50); F(51); F(52); F(53); F(54); F(55); F(56); F(57); F(58); F(59);
	F(60); F(61); F(62); F(63); F(64); F(65); F(66); F(67); F(68); F(69);
	F(70); F(71); F(72); F(73); F(74); F(75); F(76); F(77); F(78); F(79);
#undef F

	// 0<=t<=19
#define F(A,B,C,D,E,T,K) temp=SHIFT((A),5)+(((B)&(C))|(~(B)&(D)))+(E)+word[(T)]+(K); E=D;D=C;C=SHIFT((B),30);B=A;A=temp;
	F(a,b,c,d,e, 0,K0); F(a,b,c,d,e, 1,K0); F(a,b,c,d,e, 2,K0); F(a,b,c,d,e, 3,K0);
	F(a,b,c,d,e, 4,K0); F(a,b,c,d,e, 5,K0); F(a,b,c,d,e, 6,K0); F(a,b,c,d,e, 7,K0);
	F(a,b,c,d,e, 8,K0); F(a,b,c,d,e, 9,K0); F(a,b,c,d,e,10,K0); F(a,b,c,d,e,11,K0);
	F(a,b,c,d,e,12,K0); F(a,b,c,d,e,13,K0); F(a,b,c,d,e,14,K0); F(a,b,c,d,e,15,K0);
	F(a,b,c,d,e,16,K0); F(a,b,c,d,e,17,K0); F(a,b,c,d,e,18,K0); F(a,b,c,d,e,19,K0);
#undef F
	// 20<=t<=39
#define F(A,B,C,D,E,T,K) temp=SHIFT((A),5)+((B)^(C)^(D))+(E)+word[(T)]+(K); E=D;D=C;C=SHIFT((B),30);B=A;A=temp;
	F(a,b,c,d,e,20,K1); F(a,b,c,d,e,21,K1); F(a,b,c,d,e,22,K1); F(a,b,c,d,e,23,K1);
	F(a,b,c,d,e,24,K1); F(a,b,c,d,e,25,K1); F(a,b,c,d,e,26,K1); F(a,b,c,d,e,27,K1);
	F(a,b,c,d,e,28,K1); F(a,b,c,d,e,29,K1); F(a,b,c,d,e,30,K1); F(a,b,c,d,e,31,K1);
	F(a,b,c,d,e,32,K1); F(a,b,c,d,e,33,K1); F(a,b,c,d,e,34,K1); F(a,b,c,d,e,35,K1);
	F(a,b,c,d,e,36,K1); F(a,b,c,d,e,37,K1); F(a,b,c,d,e,38,K1); F(a,b,c,d,e,39,K1);
#undef F
	// 40<=t<=59
#define F(A,B,C,D,E,T,K) temp=SHIFT((A),5)+(((B)&(C))|((B)&(D))|((C)&(D)))+(E)+word[(T)]+(K); E=D;D=C;C=SHIFT((B),30);B=A;A=temp;
	F(a,b,c,d,e,40,K2); F(a,b,c,d,e,41,K2); F(a,b,c,d,e,42,K2); F(a,b,c,d,e,43,K2);
	F(a,b,c,d,e,44,K2); F(a,b,c,d,e,45,K2); F(a,b,c,d,e,46,K2); F(a,b,c,d,e,47,K2);
	F(a,b,c,d,e,48,K2); F(a,b,c,d,e,49,K2); F(a,b,c,d,e,50,K2); F(a,b,c,d,e,51,K2);
	F(a,b,c,d,e,52,K2); F(a,b,c,d,e,53,K2); F(a,b,c,d,e,54,K2); F(a,b,c,d,e,55,K2);
	F(a,b,c,d,e,56,K2); F(a,b,c,d,e,57,K2); F(a,b,c,d,e,58,K2); F(a,b,c,d,e,59,K2);
#undef F
	// 60<=t<=79
#define F(A,B,C,D,E,T,K) temp=SHIFT((A),5)+((B)^(C)^(D))+(E)+word[(T)]+(K); E=D;D=C;C=SHIFT((B),30);B=A;A=temp;
	F(a,b,c,d,e,60,K3); F(a,b,c,d,e,61,K3); F(a,b,c,d,e,62,K3); F(a,b,c,d,e,63,K3);
	F(a,b,c,d,e,64,K3); F(a,b,c,d,e,65,K3); F(a,b,c,d,e,66,K3); F(a,b,c,d,e,67,K3);
	F(a,b,c,d,e,68,K3); F(a,b,c,d,e,69,K3); F(a,b,c,d,e,70,K3); F(a,b,c,d,e,71,K3);
	F(a,b,c,d,e,72,K3); F(a,b,c,d,e,73,K3); F(a,b,c,d,e,74,K3); F(a,b,c,d,e,75,K3);
	F(a,b,c,d,e,76,K3); F(a,b,c,d,e,77,K3); F(a,b,c,d,e,78,K3); F(a,b,c,d,e,79,K3);
#undef F
	p->sha1[0] += a;
	p->sha1[1] += b;
	p->sha1[2] += c;
	p->sha1[3] += d;
	p->sha1[4] += e;
	
	p->i = 0;
}

// 16進数出力(TENUKI)
const char * sha1_hexstr(SHA1 *p){
	static char str[40+1];
	sprintf( str, 
		"%08X%08X%08X%08X%08X",
		p->sha1[0],p->sha1[1],p->sha1[2],p->sha1[3],p->sha1[4]
	);
	return str;
}

// 指定ファイルのSHA1を取得する。
const char * file2sha1(const char *filename){
	#define BUFFER 4096
	SHA1 sha1;
	BYTE buffer[BUFFER];
	UINT32 length;
	FILE *fp = fopen(filename, "rb");
	if(fp == NULL){ return NULL; }
	sha1_init(&sha1);
	while(length = fread(buffer, 1, BUFFER, fp)) sha1_add(&sha1, buffer, length);
	sha1_finish(&sha1);
	fclose(fp);
	return sha1_hexstr(&sha1);
}

#endif // SHA1_H

使い方

#include <stdio.h>
#include <string.h>

#include "sha1.h"

int main(int argc, char **argv){
	if(argc >= 2){
		const char *p = file2sha1(argv[1]);
		if(p != NULL){
			printf("%s", p);
		}
	}
	return 0;
}

memo

マクロ部分はPerlでワンライナーすると楽。
実行速度ははかってない。時間がないので夜にでも。
例によって4GB以上のファイルには未対応。length_highはいらない子。

*1:ちなみにそのうちタイプミスが原因ということに気づくまでの時間が9時間ぐらい。小文字のbとdをマクロに使ったのが原因。FF(a,b,c,b,...)とかやってた。今回は大文字を使ってます。