結城先生のCodeIQ問題(cryptan)

codeiq781_1.rb

#!/usr/bin/ruby
a=DATA.flat_map{|e|e.split.map{|f|f.to_i(16)}}
a.size.times{|i|
	#' ','e','t','h'は尤も推測が楽
	a[i]=' ' if a[i]==0xcb
	a[i]='e' if a[i]==0x9c
	a[i]='t' if a[i]==0xba
	a[i]='h' if a[i]==0x4d

	#1文字ずつ解読
	a[i]='l' if a[i]==0x97
	a[i]='i' if a[i]==0xc2
	a[i]='n' if a[i]==0x24
	a[i]='w' if a[i]==0x07
	a[i]='o' if a[i]==0xda
	a[i]='s' if a[i]==0x0d
	a[i]='b' if a[i]==0xd3
	a[i]='a' if a[i]==0xf0
	a[i]='d' if a[i]==0x7d
	a[i]='c' if a[i]==0xcd
	a[i]='g' if a[i]==0x08
	a[i]='u' if a[i]==0x58
	a[i]='r' if a[i]==0x1c
	a[i]='p' if a[i]==0x3f
	a[i]='f' if a[i]==0xf9
	a[i]='y' if a[i]==0x2c
	a[i]='m' if a[i]==0xe4
	a[i]='k' if a[i]==0xa9
	a[i]='v' if a[i]==0x7f

	#以下は本文中からの解読は困難であったため検索が必要であった
	a[i]='"' if a[i]==0x78
	a[i]=',' if a[i]==0x21
	a[i]='-' if a[i]==0x25
	a[i]='.' if a[i]==0x50
	a[i]='\'' if a[i]==0xc5
	a[i]='Y' if a[i]==0xab
	a[i]='N' if a[i]==0x88
	a[i]='O' if a[i]==0xac
	a[i]='T' if a[i]==0x9d
	a[i]='I' if a[i]==0xb7
	a[i]='W' if a[i]==0xce
}
puts a*''

=begin
"You see, my dear Watson," -- he propped his test-tube in the rack, and began to lecture with the air of a professor addressing his class -- "it is not really difficult to construct a series of inferences, each dependent upon its predecessor and each simple in itself.  If, after doing so, one simply knocks out all the central inferences and presents one's audience with the starting-point and the conclusion, one may produce a startling, though possibly a meretricious, effect. Now, it was not really difficult, by an inspection of the groove between your left forefinger and thumb, to feel sure that you did NOT propose to invest your small capital in the gold fields."
=end

__END__
78 AB DA 58 CB 0D 9C 9C 21 CB E4 2C CB 7D 9C F0
1C CB CE F0 BA 0D DA 24 21 78 CB 25 25 CB 4D 9C
CB 3F 1C DA 3F 3F 9C 7D CB 4D C2 0D CB BA 9C 0D
BA 25 BA 58 D3 9C CB C2 24 CB BA 4D 9C CB 1C F0
CD A9 21 CB F0 24 7D CB D3 9C 08 F0 24 CB BA DA
CB 97 9C CD BA 58 1C 9C CB 07 C2 BA 4D CB BA 4D
9C CB F0 C2 1C CB DA F9 CB F0 CB 3F 1C DA F9 9C
0D 0D DA 1C CB F0 7D 7D 1C 9C 0D 0D C2 24 08 CB
4D C2 0D CB CD 97 F0 0D 0D CB 25 25 CB 78 C2 BA
CB C2 0D CB 24 DA BA CB 1C 9C F0 97 97 2C CB 7D
C2 F9 F9 C2 CD 58 97 BA CB BA DA CB CD DA 24 0D
BA 1C 58 CD BA CB F0 CB 0D 9C 1C C2 9C 0D CB DA
F9 CB C2 24 F9 9C 1C 9C 24 CD 9C 0D 21 CB 9C F0
CD 4D CB 7D 9C 3F 9C 24 7D 9C 24 BA CB 58 3F DA
24 CB C2 BA 0D CB 3F 1C 9C 7D 9C CD 9C 0D 0D DA
1C CB F0 24 7D CB 9C F0 CD 4D CB 0D C2 E4 3F 97
9C CB C2 24 CB C2 BA 0D 9C 97 F9 50 CB CB B7 F9
21 CB F0 F9 BA 9C 1C CB 7D DA C2 24 08 CB 0D DA
21 CB DA 24 9C CB 0D C2 E4 3F 97 2C CB A9 24 DA
CD A9 0D CB DA 58 BA CB F0 97 97 CB BA 4D 9C CB
CD 9C 24 BA 1C F0 97 CB C2 24 F9 9C 1C 9C 24 CD
9C 0D CB F0 24 7D CB 3F 1C 9C 0D 9C 24 BA 0D CB
DA 24 9C C5 0D CB F0 58 7D C2 9C 24 CD 9C CB 07
C2 BA 4D CB BA 4D 9C CB 0D BA F0 1C BA C2 24 08
25 3F DA C2 24 BA CB F0 24 7D CB BA 4D 9C CB CD
DA 24 CD 97 58 0D C2 DA 24 21 CB DA 24 9C CB E4
F0 2C CB 3F 1C DA 7D 58 CD 9C CB F0 CB 0D BA F0
1C BA 97 C2 24 08 21 CB BA 4D DA 58 08 4D CB 3F
DA 0D 0D C2 D3 97 2C CB F0 CB E4 9C 1C 9C BA 1C
C2 CD C2 DA 58 0D 21 CB 9C F9 F9 9C CD BA 50 CB
88 DA 07 21 CB C2 BA CB 07 F0 0D CB 24 DA BA CB
1C 9C F0 97 97 2C CB 7D C2 F9 F9 C2 CD 58 97 BA
21 CB D3 2C CB F0 24 CB C2 24 0D 3F 9C CD BA C2
DA 24 CB DA F9 CB BA 4D 9C CB 08 1C DA DA 7F 9C
CB D3 9C BA 07 9C 9C 24 CB 2C DA 58 1C CB 97 9C
F9 BA CB F9 DA 1C 9C F9 C2 24 08 9C 1C CB F0 24
7D CB BA 4D 58 E4 D3 21 CB BA DA CB F9 9C 9C 97
CB 0D 58 1C 9C CB BA 4D F0 BA CB 2C DA 58 CB 7D
C2 7D CB 88 AC 9D CB 3F 1C DA 3F DA 0D 9C CB BA
DA CB C2 24 7F 9C 0D BA CB 2C DA 58 1C CB 0D E4
F0 97 97 CB CD F0 3F C2 BA F0 97 CB C2 24 CB BA
4D 9C CB 08 DA 97 7D CB F9 C2 9C 97 7D 0D 50 78

codeiq781_2.c

//gcc -O3 tyama_codeiq781_1.c tyama_codeiq781_2_sha1.c

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

//#include "sha1.h"
#include <stdint.h>
struct sha1_ctxt {
	union {
		uint8_t	b8[20];
		uint32_t	b32[5];
	} h;
	union {
		uint8_t	b8[8];
		uint64_t	b64[1];
	} c;
	union {
		uint8_t	b8[64];
		uint32_t	b32[16];
	} m;
	uint8_t	count;
};
void sha1_init(struct sha1_ctxt *ctxt);
void sha1_loop(struct sha1_ctxt *ctxt,const uint8_t *input,size_t len);
void sha1_result(struct sha1_ctxt *ctxt,uint8_t *digest);

unsigned char data[]={0xc8,0xee,0xa8,0x0f,0x80,0xfd,0x60,0xe9,0x00,0x3f,0xc4,0xb0,0x10,0x2c,0xe7,0x33,0xdc,0x82,0x1e,0x6b,0xd3,0x5b,0xbb,0xfa,0x8a,0x48,0xc2,0xf0,0x97,0x7f,0xa6,0xc0,0x9c,0x32,0x15,0x89,0x37,0x51,0xaa,0xc9,0xd8,0x93,0x9d,0x86,0xda,0x28,0xbb,0x58,0xa2,0x6d,0xe2,0x7f,0x3a,0x3b,0xa5,0xf1,0xa5,0x31,0x89,0x6c,0xd8,0xb5,0xe6,0x15,0xbc,0xa4,0xbc,0x59,0x93,0xcd,0x68,0x85,0x52,0x48,0x93,0x36,0xb1,0xf4,0x5e,0xfa,0xd1,0x62,0x7c,0x4b,0xc1,0xa2,0xe4,0x98,0x7f,0x17,0xd5,0x21,0x37,0x7f,0xc5,0xa0,0x2c,0xbe,0x67,0x4d,0xdc,0x5a,0x0b,0x66,0xd9,0xd4,0x5b,0x09,0x58,0x2f,0x72,0xed,0x4f,0x45,0x81,0x36,0x73,0xab,0x18,0xdf,0x51,0x5c,0x1a,0xd3,0x7f,0x2e,0xef,0xb8,0xd8,0xc8,0xc0,0x8a,0x4c,0xba,0x87,0x23,0x01,0x44,0x46,0xe7,0x03,0x42,0xef,0x44,0xea,0x05,0x36,0x11,0x3c,0x03,0x67,0x24,0xa4,0xbc,0x53,0xef,0x6e,0x2d,0xc3,0x66,0xb9,0xcf,0x9c,0xc2,0x55,0x04,0x9c,0xf8,0xf4,0x99,0xb8,0xaf,0xff,0xea,0x16,0x7d,0xaa,0xec,0xff,0x7d,0xe2,0x52,0x8b,0xb7,0x65,0xee,0x2c,0x69,0x07,0x1d,0xd9,0x14,0xc5,0x5a,0x6b,0x5a,0xbc,0xef,0x34,0x12,0xc4,0x0d,0x7d,0x4e,0xaa,0xdd,0x19,0x0a,0x2b,0x5f,0x8b,0xce,0x06,0x2d,0xa0,0x6c,0x76,0x49,0xe2,0x62,0xac,0x4b,0x04,0x46,0xfa,0xe6,0x58,0x3e,0xd0,0x7b,0x58,0xf0,0x8a,0x9e,0x67,0x1b,0x96,0x3c,0xb3,0x93,0x94,0x66,0x8a,0x44,0x50,0xd5,0x4f,0xf8,0x49,0x33,0x4e,0xba,0xca,0xe1,0x95,0x24,0x92,0x43,0x85,0xfc,0xa8,0xb1,0x66,0x6f,0x46,0x57,0xbd,0xa5,0xb3,0x1e,0x1b,0x47,0x5b,0x95,0xeb,0xe7,0x8c,0x41,0x25,0xdc,0x88,0x9d,0x66,0x72,0x36,0x6b,0xc1,0xd8,0xe8,0x60,0x59,0xba,0x1f,0xbd,0x66,0xa7,0x3c,0xa3,0x1d,0x08,0xde,0xcf,0xeb,0x02,0x10,0x90,0xfd,0x9a,0xf9,0x51,0x83,0x6c,0x22,0x79,0x6f,0x79,0xd7,0x98,0x52,0x43,0xdd,0x1e,0x66,0xab,0xe1,0xf0,0xe2,0xe4,0x85,0x0d,0x5f,0xe5,0xb9,0x83,0x07,0xe0,0x84,0x9c,0xb8,0x3a,0x60,0x1e,0x00,0x31,0x8b,0xe9,0x7b,0x9b,0x6e,0x56,0xf0,0x84,0x81,0xa7,0xae,0xae,0xbe,0xb2,0x56,0x0a,0xc3,0xb8,0xde,0xb8,0x5c,0x8a,0x09,0x83,0x4c,0x9f,0x12,0xd3,0xde,0xc2,0x08,0xf2,0x79,0xcf,0x71,0x51,0xb3,0xe5,0xf0,0xd2,0x47,0x12,0x0e,0xdf,0x98,0xb2,0x5c,0x02,0xe7,0xe3,0x4d,0xb3,0x6b,0x20,0x91,0x0d,0x7c,0x0e,0xe2,0x95,0x2e,0x7a,0x29,0xe2,0x7c,0xc0,0xa8,0x9a,0xb6,0x25,0xc1,0xfb,0xe5,0xeb,0xa5,0xa0,0xf6,0xe2,0xe6,0xa0,0x70,0x4e,0xe5,0x8f,0xde,0x1e,0x9c,0x33,0x29,0x2f,0xda,0x85,0xe0,0x9a,0xc2,0xf6,0x6f,0x71,0xa9,0x84,0xe7,0xf9,0x61,0x29,0x50,0x3a,0x0a,0x65,0xc3,0xbd,0x91,0xcc,0x7e,0x52,0x69,0x84,0x12,0x27,0x6c,0x97,0x0c,0x9c,0xfc,0x60,0x32,0x58,0x7d,0xbd,0x2e,0x4f,0x5a,0x36,0x97,0xed,0x34,0x5a,0x35,0x2f,0xa8,0xed,0xdc,0xa0,0x67,0xf0,0xfe,0x17,0xc9,0xe0,0x6e,0xd6,0xd1,0x9d,0x58,0xc2,0xe0,0x81,0x6f,0xc1,0x7f,0xe9,0x38,0x5c,0xec,0x5a,0x30,0x08,0x00,0xcb,0xc3,0x65,0x2f,0xa9,0x78,0x6d,0xf5,0xc0,0xd1,0x34,0x8e,0x99,0xc8,0x52,0x85,0xe4,0xf7,0x06,0xfd,0xe7,0x1b,0x14,0x9f,0x97,0xbd,0xd9,0x97,0x29,0x18,0x8a,0x2a,0xe4,0x76,0xaa,0x36,0x2d,0xce,0x4e,0xe4,0xd0,0x84,0x69,0x65,0x22,0x0c,0x9b,0xa4,0x42};

int main(){
	const int l=sizeof(data);
	int i,seed=234; ///
	unsigned char buf[l+1],digest[20],c;

	struct sha1_ctxt sha1ctx,sha1ctx2;
	for(seed=128;seed<256;seed++){
		sha1_init(&sha1ctx);
		c=seed;
		for(i=0;i<l;i++){
			buf[i]=data[i]^c;
			if(buf[i]<32||127<buf[i])break;
			sha1_loop(&sha1ctx,&c,1);
#if 1
			memcpy(&sha1ctx2,&sha1ctx,sizeof(struct sha1_ctxt));
			sha1_result(&sha1ctx2,digest);
#else
			sha1_result(&sha1ctx,digest);
#endif
			c=digest[19];
		}
		if(i==l){
			buf[l]=0;
			puts(buf);
			break;
		}
	}
	if(seed==256){
		puts("No luck.");
	}
	return 0;
}

codeiq781_2.rb

#!/usr/bin/ruby
require 'digest/sha1'
=begin
def sha1(s,n)
	if true
		#s=s.chr
		#s=s.chr*20
		#s="\0"*19+s.chr
		s=s.chr+"\0"*19
		#p s
		n.times{s=Digest::SHA1.digest(s)}
	else
		#s=s.to_s(16)*20
		s=s.to_s
		(n-1).times{s=Digest::SHA1.hexdigest(s)}
		s=Digest::SHA1.digest(s)
	end
	s
end
=end

A=DATA.flat_map{|e|e.split.map{|f|f.to_i(16)}}
#h=Hash.new(0)
#A.each{|e|h[e]+=1}
#p h
#p h.size
#exit
def test(enum)
	a=A.dup
	#p a
	if a.size.times{|i|
		n=enum.next
		#p [i,a[i],n]
		a[i]^=n
		#p [i,a[i].chr]
		break if a[i]<0x20 || 0x7f<=a[i]
	}
		puts a.map(&:chr)*''
		exit
	end
end

#1.step(10){|z|
256.times{|_s| # brute force all seeds
	#色々試してみたんですよ、ほんと。
=begin
	20.times{|_i|
		test(Enumerator.new{|y|
			cur=_s
			loop{
				y<<cur
				cur=sha1(cur,z)[_i].ord
			}
		})
	}
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z)[cur&0xf].ord
		}
	})
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z)[cur%20].ord
		}
	})
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z)[cur>>4].ord
		}
	})

	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.reduce(:+)%256
		}
	})
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.reduce(:^)%256
		}
	})

	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.each_slice(2).map{|a,b|(a<<8)|b}.reduce(:+)%256
		}
	})
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.each_slice(2).map{|a,b|(a<<8)|b}.reduce(:^)%256
		}
	})

	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.each_slice(2).map{|a,b|(b<<8)|a}.reduce(:+)%256
		}
	})
	test(Enumerator.new{|y|
		cur=_s
		loop{
			y<<cur
			cur=sha1(cur,z).bytes.each_slice(2).map{|a,b|(b<<8)|a}.reduce(:^)%256
		}
	})
=end

	#解説を見た後に
	test(Enumerator.new{|y|
		cur=_s # correct seed is 234.
		str=''
		loop{
			y<<cur
			str+=cur.chr #このような連結はわかるはずがない…
			cur=Digest::SHA1.digest(str)[-1].ord
		}
	})
	#まあ、最もなことを言えば、今回キーストリームの連結ではなくストレッチングの方に思考が行ってしまった時点で運が悪かったということになりましょうか。
}
#}
puts 'No luck...'

=begin
"If you use the code which I have explained," said Holmes,"you will find that it simply means 'Come here at once.' I was convinced that it was an invitation which he would not refuse, since he could never imagine that it could come from anyone but the lady. And so, my dear Watson, we have ended by turning the dancing men to good when they have so often been the agents of evil, and I think that I have fulfilled my promise of giving you something unusual for your notebook. Three-forty is our train, and I fancy we should be back in Baker Street for dinner."
=end

__END__
C8 EE A8 0F 80 FD 60 E9 00 3F C4 B0 10 2C E7 33
DC 82 1E 6B D3 5B BB FA 8A 48 C2 F0 97 7F A6 C0
9C 32 15 89 37 51 AA C9 D8 93 9D 86 DA 28 BB 58
A2 6D E2 7F 3A 3B A5 F1 A5 31 89 6C D8 B5 E6 15
BC A4 BC 59 93 CD 68 85 52 48 93 36 B1 F4 5E FA
D1 62 7C 4B C1 A2 E4 98 7F 17 D5 21 37 7F C5 A0
2C BE 67 4D DC 5A 0B 66 D9 D4 5B 09 58 2F 72 ED
4F 45 81 36 73 AB 18 DF 51 5C 1A D3 7F 2E EF B8
D8 C8 C0 8A 4C BA 87 23 01 44 46 E7 03 42 EF 44
EA 05 36 11 3C 03 67 24 A4 BC 53 EF 6E 2D C3 66
B9 CF 9C C2 55 04 9C F8 F4 99 B8 AF FF EA 16 7D
AA EC FF 7D E2 52 8B B7 65 EE 2C 69 07 1D D9 14
C5 5A 6B 5A BC EF 34 12 C4 0D 7D 4E AA DD 19 0A
2B 5F 8B CE 06 2D A0 6C 76 49 E2 62 AC 4B 04 46
FA E6 58 3E D0 7B 58 F0 8A 9E 67 1B 96 3C B3 93
94 66 8A 44 50 D5 4F F8 49 33 4E BA CA E1 95 24
92 43 85 FC A8 B1 66 6F 46 57 BD A5 B3 1E 1B 47
5B 95 EB E7 8C 41 25 DC 88 9D 66 72 36 6B C1 D8
E8 60 59 BA 1F BD 66 A7 3C A3 1D 08 DE CF EB 02
10 90 FD 9A F9 51 83 6C 22 79 6F 79 D7 98 52 43
DD 1E 66 AB E1 F0 E2 E4 85 0D 5F E5 B9 83 07 E0
84 9C B8 3A 60 1E 00 31 8B E9 7B 9B 6E 56 F0 84
81 A7 AE AE BE B2 56 0A C3 B8 DE B8 5C 8A 09 83
4C 9F 12 D3 DE C2 08 F2 79 CF 71 51 B3 E5 F0 D2
47 12 0E DF 98 B2 5C 02 E7 E3 4D B3 6B 20 91 0D
7C 0E E2 95 2E 7A 29 E2 7C C0 A8 9A B6 25 C1 FB
E5 EB A5 A0 F6 E2 E6 A0 70 4E E5 8F DE 1E 9C 33
29 2F DA 85 E0 9A C2 F6 6F 71 A9 84 E7 F9 61 29
50 3A 0A 65 C3 BD 91 CC 7E 52 69 84 12 27 6C 97
0C 9C FC 60 32 58 7D BD 2E 4F 5A 36 97 ED 34 5A
35 2F A8 ED DC A0 67 F0 FE 17 C9 E0 6E D6 D1 9D
58 C2 E0 81 6F C1 7F E9 38 5C EC 5A 30 08 00 CB
C3 65 2F A9 78 6D F5 C0 D1 34 8E 99 C8 52 85 E4
F7 06 FD E7 1B 14 9F 97 BD D9 97 29 18 8A 2A E4
76 AA 36 2D CE 4E E4 D0 84 69 65 22 0C 9B A4 42

codeiq781_2_sha1.c

/*	$FreeBSD: src/sys/crypto/sha1.c,v 1.2.2.4 2001/07/03 11:01:27 ume Exp $	*/
/*	$KAME: sha1.c,v 1.5 2000/11/08 06:13:08 itojun Exp $	*/

/*
 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the project nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
/*
 * FIPS pub 180-1: Secure Hash Algorithm (SHA-1)
 * based on: http://csrc.nist.gov/fips/fip180-1.txt
 * implemented by Jun-ichiro itojun Itoh <itojun@itojun.org>
 */

#include <string.h>
#include <stdint.h>

//#include <sys/types.h>
//#include <sys/cdefs.h>
//#include <sys/time.h>
//#include <sys/systm.h>

//#include <crypto/sha1.h>

//endian.h
//#define BYTE_ORDER L_ENDIAN

/* sanity check */
#if 0 //somehow not working ^^
#if BYTE_ORDER != BIG_ENDIAN
# if BYTE_ORDER != LITTLE_ENDIAN
#  define unsupported 1
# endif
#endif
#endif

#ifndef unsupported

#define bcopy(src,dst,n) memcpy((dst),(src),(n))
#define bzero(s,n) memset((s),0,(n))

struct sha1_ctxt {
	union {
		uint8_t	b8[20];
		uint32_t	b32[5];
	} h;
	union {
		uint8_t	b8[8];
		uint64_t	b64[1];
	} c;
	union {
		uint8_t	b8[64];
		uint32_t	b32[16];
	} m;
	uint8_t	count;
};

/* constant table */
static uint32_t _K[] = { 0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6 };
#define	K(t)	_K[(t) / 20]

#define	F0(b, c, d)	(((b) & (c)) | ((~(b)) & (d)))
#define	F1(b, c, d)	(((b) ^ (c)) ^ (d))
#define	F2(b, c, d)	(((b) & (c)) | ((b) & (d)) | ((c) & (d)))
#define	F3(b, c, d)	(((b) ^ (c)) ^ (d))

#define	S(n, x)		(((x) << (n)) | ((x) >> (32 - n)))

#define	H(n)	(ctxt->h.b32[(n)])
#define	COUNT	(ctxt->count)
#define	BCOUNT	(ctxt->c.b64[0] / 8)
#define	W(n)	(ctxt->m.b32[(n)])

#define	PUTBYTE(x)	{ \
	ctxt->m.b8[(COUNT % 64)] = (x);		\
	COUNT++;				\
	COUNT %= 64;				\
	ctxt->c.b64[0] += 8;			\
	if (COUNT % 64 == 0)			\
		sha1_step(ctxt);		\
     }

#define	PUTPAD(x)	{ \
	ctxt->m.b8[(COUNT % 64)] = (x);		\
	COUNT++;				\
	COUNT %= 64;				\
	if (COUNT % 64 == 0)			\
		sha1_step(ctxt);		\
     }

//static void sha1_step __P((struct sha1_ctxt *));

static void
sha1_step(ctxt)
	struct sha1_ctxt *ctxt;
{
	uint32_t	a, b, c, d, e;
	size_t t, s;
	uint32_t	tmp;

#if 1
//BYTE_ORDER == LITTLE_ENDIAN
	struct sha1_ctxt tctxt;
	bcopy(&ctxt->m.b8[0], &tctxt.m.b8[0], 64);
	ctxt->m.b8[0] = tctxt.m.b8[3]; ctxt->m.b8[1] = tctxt.m.b8[2];
	ctxt->m.b8[2] = tctxt.m.b8[1]; ctxt->m.b8[3] = tctxt.m.b8[0];
	ctxt->m.b8[4] = tctxt.m.b8[7]; ctxt->m.b8[5] = tctxt.m.b8[6];
	ctxt->m.b8[6] = tctxt.m.b8[5]; ctxt->m.b8[7] = tctxt.m.b8[4];
	ctxt->m.b8[8] = tctxt.m.b8[11]; ctxt->m.b8[9] = tctxt.m.b8[10];
	ctxt->m.b8[10] = tctxt.m.b8[9]; ctxt->m.b8[11] = tctxt.m.b8[8];
	ctxt->m.b8[12] = tctxt.m.b8[15]; ctxt->m.b8[13] = tctxt.m.b8[14];
	ctxt->m.b8[14] = tctxt.m.b8[13]; ctxt->m.b8[15] = tctxt.m.b8[12];
	ctxt->m.b8[16] = tctxt.m.b8[19]; ctxt->m.b8[17] = tctxt.m.b8[18];
	ctxt->m.b8[18] = tctxt.m.b8[17]; ctxt->m.b8[19] = tctxt.m.b8[16];
	ctxt->m.b8[20] = tctxt.m.b8[23]; ctxt->m.b8[21] = tctxt.m.b8[22];
	ctxt->m.b8[22] = tctxt.m.b8[21]; ctxt->m.b8[23] = tctxt.m.b8[20];
	ctxt->m.b8[24] = tctxt.m.b8[27]; ctxt->m.b8[25] = tctxt.m.b8[26];
	ctxt->m.b8[26] = tctxt.m.b8[25]; ctxt->m.b8[27] = tctxt.m.b8[24];
	ctxt->m.b8[28] = tctxt.m.b8[31]; ctxt->m.b8[29] = tctxt.m.b8[30];
	ctxt->m.b8[30] = tctxt.m.b8[29]; ctxt->m.b8[31] = tctxt.m.b8[28];
	ctxt->m.b8[32] = tctxt.m.b8[35]; ctxt->m.b8[33] = tctxt.m.b8[34];
	ctxt->m.b8[34] = tctxt.m.b8[33]; ctxt->m.b8[35] = tctxt.m.b8[32];
	ctxt->m.b8[36] = tctxt.m.b8[39]; ctxt->m.b8[37] = tctxt.m.b8[38];
	ctxt->m.b8[38] = tctxt.m.b8[37]; ctxt->m.b8[39] = tctxt.m.b8[36];
	ctxt->m.b8[40] = tctxt.m.b8[43]; ctxt->m.b8[41] = tctxt.m.b8[42];
	ctxt->m.b8[42] = tctxt.m.b8[41]; ctxt->m.b8[43] = tctxt.m.b8[40];
	ctxt->m.b8[44] = tctxt.m.b8[47]; ctxt->m.b8[45] = tctxt.m.b8[46];
	ctxt->m.b8[46] = tctxt.m.b8[45]; ctxt->m.b8[47] = tctxt.m.b8[44];
	ctxt->m.b8[48] = tctxt.m.b8[51]; ctxt->m.b8[49] = tctxt.m.b8[50];
	ctxt->m.b8[50] = tctxt.m.b8[49]; ctxt->m.b8[51] = tctxt.m.b8[48];
	ctxt->m.b8[52] = tctxt.m.b8[55]; ctxt->m.b8[53] = tctxt.m.b8[54];
	ctxt->m.b8[54] = tctxt.m.b8[53]; ctxt->m.b8[55] = tctxt.m.b8[52];
	ctxt->m.b8[56] = tctxt.m.b8[59]; ctxt->m.b8[57] = tctxt.m.b8[58];
	ctxt->m.b8[58] = tctxt.m.b8[57]; ctxt->m.b8[59] = tctxt.m.b8[56];
	ctxt->m.b8[60] = tctxt.m.b8[63]; ctxt->m.b8[61] = tctxt.m.b8[62];
	ctxt->m.b8[62] = tctxt.m.b8[61]; ctxt->m.b8[63] = tctxt.m.b8[60];
#endif

	a = H(0); b = H(1); c = H(2); d = H(3); e = H(4);

	for (t = 0; t < 20; t++) {
		s = t & 0x0f;
		if (t >= 16) {
			W(s) = S(1, W((s+13) & 0x0f) ^ W((s+8) & 0x0f) ^ W((s+2) & 0x0f) ^ W(s));
		}
		tmp = S(5, a) + F0(b, c, d) + e + W(s) + K(t);
		e = d; d = c; c = S(30, b); b = a; a = tmp;
	}
	for (t = 20; t < 40; t++) {
		s = t & 0x0f;
		W(s) = S(1, W((s+13) & 0x0f) ^ W((s+8) & 0x0f) ^ W((s+2) & 0x0f) ^ W(s));
		tmp = S(5, a) + F1(b, c, d) + e + W(s) + K(t);
		e = d; d = c; c = S(30, b); b = a; a = tmp;
	}
	for (t = 40; t < 60; t++) {
		s = t & 0x0f;
		W(s) = S(1, W((s+13) & 0x0f) ^ W((s+8) & 0x0f) ^ W((s+2) & 0x0f) ^ W(s));
		tmp = S(5, a) + F2(b, c, d) + e + W(s) + K(t);
		e = d; d = c; c = S(30, b); b = a; a = tmp;
	}
	for (t = 60; t < 80; t++) {
		s = t & 0x0f;
		W(s) = S(1, W((s+13) & 0x0f) ^ W((s+8) & 0x0f) ^ W((s+2) & 0x0f) ^ W(s));
		tmp = S(5, a) + F3(b, c, d) + e + W(s) + K(t);
		e = d; d = c; c = S(30, b); b = a; a = tmp;
	}

	H(0) = H(0) + a;
	H(1) = H(1) + b;
	H(2) = H(2) + c;
	H(3) = H(3) + d;
	H(4) = H(4) + e;

	bzero(&ctxt->m.b8[0], 64);
}

/*------------------------------------------------------------*/

void
sha1_init(ctxt)
	struct sha1_ctxt *ctxt;
{
	bzero(ctxt, sizeof(struct sha1_ctxt));
	H(0) = 0x67452301;
	H(1) = 0xefcdab89;
	H(2) = 0x98badcfe;
	H(3) = 0x10325476;
	H(4) = 0xc3d2e1f0;
}

void
sha1_pad(ctxt)
	struct sha1_ctxt *ctxt;
{
	size_t padlen;		/*pad length in bytes*/
	size_t padstart;

	PUTPAD(0x80);

	padstart = COUNT % 64;
	padlen = 64 - padstart;
	if (padlen < 8) {
		bzero(&ctxt->m.b8[padstart], padlen);
		COUNT += padlen;
		COUNT %= 64;
		sha1_step(ctxt);
		padstart = COUNT % 64;	/* should be 0 */
		padlen = 64 - padstart;	/* should be 64 */
	}
	bzero(&ctxt->m.b8[padstart], padlen - 8);
	COUNT += (padlen - 8);
	COUNT %= 64;
#if 0
//BYTE_ORDER == BIG_ENDIAN
	PUTPAD(ctxt->c.b8[0]); PUTPAD(ctxt->c.b8[1]);
	PUTPAD(ctxt->c.b8[2]); PUTPAD(ctxt->c.b8[3]);
	PUTPAD(ctxt->c.b8[4]); PUTPAD(ctxt->c.b8[5]);
	PUTPAD(ctxt->c.b8[6]); PUTPAD(ctxt->c.b8[7]);
#else
	PUTPAD(ctxt->c.b8[7]); PUTPAD(ctxt->c.b8[6]);
	PUTPAD(ctxt->c.b8[5]); PUTPAD(ctxt->c.b8[4]);
	PUTPAD(ctxt->c.b8[3]); PUTPAD(ctxt->c.b8[2]);
	PUTPAD(ctxt->c.b8[1]); PUTPAD(ctxt->c.b8[0]);
#endif
}

void
sha1_loop(ctxt, input, len)
	struct sha1_ctxt *ctxt;
	const uint8_t *input;
	size_t len;
{
	size_t gaplen;
	size_t gapstart;
	size_t off;
	size_t copysiz;

	off = 0;

	while (off < len) {
		gapstart = COUNT % 64;
		gaplen = 64 - gapstart;

		copysiz = (gaplen < len - off) ? gaplen : len - off;
		bcopy(&input[off], &ctxt->m.b8[gapstart], copysiz);
		COUNT += copysiz;
		COUNT %= 64;
		ctxt->c.b64[0] += copysiz * 8;
		if (COUNT % 64 == 0)
			sha1_step(ctxt);
		off += copysiz;
	}
}

void
sha1_result(ctxt, digest)
	struct sha1_ctxt *ctxt;
	uint8_t *digest;
{
	sha1_pad(ctxt);
#if 0
//BYTE_ORDER == BIG_ENDIAN
	bcopy(&ctxt->h.b8[0], digest, 20);
#else
	digest[0] = ctxt->h.b8[3]; digest[1] = ctxt->h.b8[2];
	digest[2] = ctxt->h.b8[1]; digest[3] = ctxt->h.b8[0];
	digest[4] = ctxt->h.b8[7]; digest[5] = ctxt->h.b8[6];
	digest[6] = ctxt->h.b8[5]; digest[7] = ctxt->h.b8[4];
	digest[8] = ctxt->h.b8[11]; digest[9] = ctxt->h.b8[10];
	digest[10] = ctxt->h.b8[9]; digest[11] = ctxt->h.b8[8];
	digest[12] = ctxt->h.b8[15]; digest[13] = ctxt->h.b8[14];
	digest[14] = ctxt->h.b8[13]; digest[15] = ctxt->h.b8[12];
	digest[16] = ctxt->h.b8[19]; digest[17] = ctxt->h.b8[18];
	digest[18] = ctxt->h.b8[17]; digest[19] = ctxt->h.b8[16];
#endif
}

#endif /*unsupported*/