实验四 SHA1算法原理 (1)

1、SHA1算法原理1 SHA1算法简介安全哈希算法（Secure HashAlgorithm）主要适用于数字签名标准（Digital Signature StandardDSS）里面定义的数字签名算法（Digital Signature AlgorithmDSA）。对于长度小于264位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。 SHA1有如下特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。2 术语和概念2.1位(Bit)，字节（B

2、yte）和字（Word）SHA1始终把消息当成一个位（bit）字符串来处理。本文中，一个“字”（Word）是32位，而一个“字节”（Byte）是8位。比如，字符串“abc”可以被转换成一个位字符串：01100001 0110001001100011。它也可以被表示成16进制字符串: 0x616263.2.2 运算符和符号下面的逻辑运算符都被运用于“字”（Word） XY = X， Y逻辑与 X / Y = X， Y逻辑或 X XOR Y= X， Y逻辑异或 X = X逻辑取反 X+Y定义如下： 字 X 和 Y 代表两个整数 x 和y,

3、 其中 0 <= x < 232且 0 <= y < 232. 令整数z = (x + y) mod 232. 这时候 0 <= z <232. 将z转换成字Z, 那么就是 Z = X + Y. 循环左移位操作符Sn(X)。X是一个字，n是一个整数，0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n) X<<n定义如下：抛弃最左边的n位数字，将各个位依次向左移动n位，然后用0填补右边的n位（最后结果还是32位）。X>>n是抛弃右边的n位，将各个位依次向右移动n位，

4、然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算3 SHA1算法描述在SHA1算法中，我们必须把原始消息（字符串，文件等）转换成位字符串。SHA1算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先，我们将它转换成位字符串如下： 01100001 01100010 01100011  a=97 b=98 c=99 这个位字符串的长度为24。下面我们需要5个步骤来计算MD5。3.1 补位消息必须进行补位，以使其长度在对512取模以后的余数是448。也就是说，（补位后的消息长度）%512 = 448。即使长度已经满足对512取模后余数是

5、448，补位也必须要进行。 补位是这样进行的：先补一个1，然后再补0，直到长度满足对512取模后余数是448。总而言之，补位是至少补一位，最多补512位。还是以前面的“abc”为例显示补位的过程。 原始信息： 01100001 01100010 01100011 补位第一步：01100001 01100010 01100011 1 首先补一个“1” 补位第二步：01100001 01100010 01100011 10.0 然后补423个“0” 我们可以把最后补位完成后的数据用16进制写成下面的样子 6162638

6、0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 现在，数据的长度是448了，我们可以进行下一步操作。3.2 补长度所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于264，那么第一个字就是0。在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式） 61626380 000

7、00000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018 如果原始的消息长度超过了512，我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块，分别处理每一个数据块，从而得到消息摘要。3.3 使用的常量一系列的常量字K(0), K(1), . , K(79)，如果以16进制给出。它们如下： Kt = 0x5A82799

8、9 (0 <= t <= 19) Kt = 0x6ED9EBA1 (20 <= t <= 39) Kt = 0x8F1BBCDC (40 <= t <= 59) Kt = 0xCA62C1D6 (60 <= t <= 79).3.4 需要使用的函数在SHA1中我们需要一系列的函数。每个函数ft (0 <= t <= 79)都操作32位字B，C，D并且产生32位字作为输出。ft(B,C,D)可以如下定义 ft(B,C,D) = (B AND C) or (NOT B) AND D) ( 0 <

9、;= t <= 19) ft(B,C,D) = B XOR C XOR D (20 <= t <= 39) ft(B,C,D) = (B AND C) or (B AND D) or (C AND D) (40 <= t <= 59) ft(B,C,D) = B XOR C XOR D (60 <= t <= 79).3.5 计算消息摘要必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由5个32位的字组成，还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A，B，C，D，E。第一个5

10、个字的缓冲区被标识为H0, H1, H2, H3, H4 。80个字的缓冲区被标识为W0, W1,., W79 另外还需要一个一个字的TEMP缓冲区。 为了产生消息摘要，在第4部分中定义的16个字的数据块M1, M2,., Mn 会依次进行处理，处理每个数据块Mi 包含80个步骤。 在处理每个数据块之前，缓冲区Hi 被初始化为下面的值（16进制） H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2

11、E1F0. 现在开始处理M1, M2, . , Mn。为了处理 Mi,需要进行下面的步骤 (1). 将 Mi 分成 16 个字 W0, W1, . , W15, W0 是最左边的字 (2). 对于 t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16). (3). 令 A = H0, B = H1, C = H2, D = H3, E = H4. (4) 对于 t = 0 到 79，执行下面的循环 TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;

12、 E = D; D = C; C = S30(B); B = A; A = TEMP; (5). 令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. 在处理完所有的 Mn, 后，消息摘要是一个160位的字符串，以下面的顺序标识 H0 H1 H2 H3 H4.对于SHA256,SHA384,SHA512。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。sha1是一种比md5的安全性强的算法，当然sha256和sha512更好，但计算开销更大一些,理论上，

13、凡是采取“消息摘要”方式的数字验证算法都是有“碰撞”的也就是两个不同的东西算出的消息摘要相同，互通作弊图就是如此。但是安全性高的算法要找到指定数据的“碰撞”很困难（困难到用暴力法寻找要花去几百年甚至几千年），而利用公式来计算“碰撞”就更困难目前为止通用安全算法中仅有md5被破解.附：来自网络上的SHA1算法，自己加了少量注释，方便以后需要的时候可以利用。代码：/* sha1sum.c - print SHA-1 Message-Digest Algorithm  * Copyright (C) 1998, 1999, 2000, 2001 Free Software Fou

14、ndation, Inc. * Copyright (C) 2004 g10 Code GmbH * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the * Free Software Foundation; either version 2, or (at your option) any * l

15、ater version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the * GNU General Public License for more details. * 

16、* You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software Foundation, * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */* SHA-1 coden take from gnupg 1.3.92.   Note, that this is a simpl

17、e tool to be used for MS Windows.*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>#include <errno.h>#undef BIG_ENDIAN_HOSTtypedef unsigned int u32;/* * Rotate a 32 bit integer by n bytes */#if defined(_GNUC_) && defined(_i38

18、6_)static inline u32 rol( u32 x, int n) _asm_("roll %cl,%0"            :"=r" (x)            :"0" (x),"c" (n); return x;#else#define rol(x,n)

19、 ( (x) << (n) | (x) >> (32-(n) )#endiftypedef struct     u32  h0,h1,h2,h3,h4;   /哈希计算后的结果是20个bit，刚好相当于5个unsigned int(4字节)类型的数据    u32  nblocks;    unsigned char buf64;    int  count; SHA1_CONTEXT;&#

20、160;void sha1_init( SHA1_CONTEXT *hd ) /计算前进行初始化    hd->h0 = 0x67452301;    hd->h1 = 0xefcdab89;    hd->h2 = 0x98badcfe;    hd->h3 = 0x10325476;    hd->h4 = 0xc3d2e1f0;    hd->nblocks = 0

21、;    hd->count = 0;/* * Transform the message X which consists of 16 32-bit-words */static voidtransform( SHA1_CONTEXT *hd, unsigned char *data )    u32 a,b,c,d,e,tm;    u32 x16;    /* get values from the chaining vars */ 

22、   a = hd->h0;    b = hd->h1;    c = hd->h2;    d = hd->h3;    e = hd->h4;#ifdef BIG_ENDIAN_HOST    memcpy( x, data, 64 );#else    int i;        unsig

23、ned char *p2;        for(i=0, p2=(unsigned char*)x; i < 16; i+, p2 += 4 )             p23 = *data+;            p22 = *data+;    

24、0;       p21 = *data+;            p20 = *data+;            #endif#define K1  0x5A827999L#define K2  0x6ED9EBA1L#define K3  0x8F1BBCDCL#define K4 

25、 0xCA62C1D6L#define F1(x,y,z)   ( z ( x & ( y z ) ) )#define F2(x,y,z)   ( x y z )#define F3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )#define F4(x,y,z)   ( x y z )#define M(i) ( tm =   xi&0x0f x(i-14)&0x0f    /

26、0;              x(i-8)&0x0f x(i-3)&0x0f      /               , (xi&0x0f = rol(tm,1) )#define R(a,b,c,d,e,f,k,m)  do e += ro

27、l( a, 5 )   /            + f( b, c, d )                          /       &#

28、160;    + k                                     /         &#

29、160;  + m;                                    /        b = rol( b, 30 );  &

30、#160;                        /    while(0)    R( a, b, c, d, e, F1, K1, x 0 );    R( e, a, b, c, d, F1, K1, x 1 );    R( d, e

31、, a, b, c, F1, K1, x 2 );    R( c, d, e, a, b, F1, K1, x 3 );    R( b, c, d, e, a, F1, K1, x 4 );    R( a, b, c, d, e, F1, K1, x 5 );    R( e, a, b, c, d, F1, K1, x 6 );    R( d, e, a, b, c, F1, K1, x 7 );    R

32、( c, d, e, a, b, F1, K1, x 8 );    R( b, c, d, e, a, F1, K1, x 9 );    R( a, b, c, d, e, F1, K1, x10 );    R( e, a, b, c, d, F1, K1, x11 );    R( d, e, a, b, c, F1, K1, x12 );    R( c, d, e, a, b, F1, K1, x13 );  &#

33、160; R( b, c, d, e, a, F1, K1, x14 );    R( a, b, c, d, e, F1, K1, x15 );    R( e, a, b, c, d, F1, K1, M(16) );    R( d, e, a, b, c, F1, K1, M(17) );    R( c, d, e, a, b, F1, K1, M(18) );    R( b, c, d, e, a, F1, K1, M(19) );

34、    R( a, b, c, d, e, F2, K2, M(20) );    R( e, a, b, c, d, F2, K2, M(21) );    R( d, e, a, b, c, F2, K2, M(22) );    R( c, d, e, a, b, F2, K2, M(23) );    R( b, c, d, e, a, F2, K2, M(24) );    R( a, b, c, d, e

35、, F2, K2, M(25) );    R( e, a, b, c, d, F2, K2, M(26) );    R( d, e, a, b, c, F2, K2, M(27) );    R( c, d, e, a, b, F2, K2, M(28) );    R( b, c, d, e, a, F2, K2, M(29) );    R( a, b, c, d, e, F2, K2, M(30) );   

36、; R( e, a, b, c, d, F2, K2, M(31) );    R( d, e, a, b, c, F2, K2, M(32) );    R( c, d, e, a, b, F2, K2, M(33) );    R( b, c, d, e, a, F2, K2, M(34) );    R( a, b, c, d, e, F2, K2, M(35) );    R( e, a, b, c, d, F2, K2, M(36) )

37、;    R( d, e, a, b, c, F2, K2, M(37) );    R( c, d, e, a, b, F2, K2, M(38) );    R( b, c, d, e, a, F2, K2, M(39) );    R( a, b, c, d, e, F3, K3, M(40) );    R( e, a, b, c, d, F3, K3, M(41) );    R( d, e, a, b,

38、c, F3, K3, M(42) );    R( c, d, e, a, b, F3, K3, M(43) );    R( b, c, d, e, a, F3, K3, M(44) );    R( a, b, c, d, e, F3, K3, M(45) );    R( e, a, b, c, d, F3, K3, M(46) );    R( d, e, a, b, c, F3, K3, M(47) );  

39、0; R( c, d, e, a, b, F3, K3, M(48) );    R( b, c, d, e, a, F3, K3, M(49) );    R( a, b, c, d, e, F3, K3, M(50) );    R( e, a, b, c, d, F3, K3, M(51) );    R( d, e, a, b, c, F3, K3, M(52) );    R( c, d, e, a, b, F3, K3, M(53)

40、);    R( b, c, d, e, a, F3, K3, M(54) );    R( a, b, c, d, e, F3, K3, M(55) );    R( e, a, b, c, d, F3, K3, M(56) );    R( d, e, a, b, c, F3, K3, M(57) );    R( c, d, e, a, b, F3, K3, M(58) );    R( b, c, d, e,

41、 a, F3, K3, M(59) );    R( a, b, c, d, e, F4, K4, M(60) );    R( e, a, b, c, d, F4, K4, M(61) );    R( d, e, a, b, c, F4, K4, M(62) );    R( c, d, e, a, b, F4, K4, M(63) );    R( b, c, d, e, a, F4, K4, M(64) );  

42、60; R( a, b, c, d, e, F4, K4, M(65) );    R( e, a, b, c, d, F4, K4, M(66) );    R( d, e, a, b, c, F4, K4, M(67) );    R( c, d, e, a, b, F4, K4, M(68) );    R( b, c, d, e, a, F4, K4, M(69) );    R( a, b, c, d, e, F4, K4, M(70)

43、 );    R( e, a, b, c, d, F4, K4, M(71) );    R( d, e, a, b, c, F4, K4, M(72) );    R( c, d, e, a, b, F4, K4, M(73) );    R( b, c, d, e, a, F4, K4, M(74) );    R( a, b, c, d, e, F4, K4, M(75) );    R( e, a, b, c

44、, d, F4, K4, M(76) );    R( d, e, a, b, c, F4, K4, M(77) );    R( c, d, e, a, b, F4, K4, M(78) );    R( b, c, d, e, a, F4, K4, M(79) );    /* Update chaining vars */    hd->h0 += a;    hd->h1 += b; &

45、#160;  hd->h2 += c;    hd->h3 += d;    hd->h4 += e;/* Update the message digest with the contents * of INBUF with length INLEN. */static void sha1_write( SHA1_CONTEXT *hd, unsigned char *inbuf, size_t inlen)    if( hd->count = 6

46、4 ) /* flush the buffer */        transform( hd, hd->buf );        hd->count = 0;        hd->nblocks+;        if( !inbuf )     

47、0;  return;    if( hd->count )         for( ; inlen && hd->count < 64; inlen- )            hd->bufhd->count+ = *inbuf+;        sha1_

48、write( hd, NULL, 0 );        if( !inlen )            return;        while( inlen >= 64 )         transform( hd, inbuf );   

49、0;    hd->count = 0;        hd->nblocks+;        inlen -= 64;        inbuf += 64;        for( ; inlen && hd->count < 64; inlen- )&

50、#160;       hd->bufhd->count+ = *inbuf+;/* The routine final terminates the computation and * returns the digest. * The handle is prepared for a new cycle, but adding bytes to the * handle will the destroy the returned buffer. * Returns: 20 byt

51、es representing the digest. */static void sha1_final(SHA1_CONTEXT *hd)    u32 t, msb, lsb;    unsigned char *p;    sha1_write(hd, NULL, 0); /* flush */;    t = hd->nblocks;    /* multiply by 64 to make a byte count */

52、    lsb = t << 6;    msb = t >> 26;    /* add the count */    t = lsb;    if( (lsb += hd->count) < t )        msb+;    /* multiply by 8 to make a bit count *

53、/    t = lsb;    lsb <<= 3;    msb <<= 3;    msb |= t >> 29;    if( hd->count < 56 ) /* enough room */        hd->bufhd->count+ = 0x80; /* pad */  

54、60;     while( hd->count < 56 )            hd->bufhd->count+ = 0;  /* pad */        else /* need one extra block */        hd->bufhd->cou

55、nt+ = 0x80; /* pad character */        while( hd->count < 64 )            hd->bufhd->count+ = 0;        sha1_write(hd, NULL, 0);  /* flush */;  

56、0;     memset(hd->buf, 0, 56 ); /* fill next block with zeroes */        /* append the 64 bit count */    hd->buf56 = msb >> 24;    hd->buf57 = msb >> 16;    hd->buf58 = msb >>

57、;  8;    hd->buf59 = msb    ;    hd->buf60 = lsb >> 24;    hd->buf61 = lsb >> 16;    hd->buf62 = lsb >>  8;    hd->buf63 = lsb    ;    tr

58、ansform( hd, hd->buf );    p = hd->buf;#ifdef BIG_ENDIAN_HOST#define X(a) do *(u32*)p = hd->h#a ; p += 4; while(0)#else /* little endian */#define X(a) do *p+ = hd->h#a >> 24; *p+ = hd->h#a >> 16; /        *p+ = hd->h#a

59、>> 8; *p+ = hd->h#a; while(0)#endif    X(0);    X(1);    X(2);    X(3);    X(4);#undef X/用法如：SHA1.exe c.txt cc.txt     /对c.txt和cc.txt中的内容进行哈希计算int main (int argc, char *argv)   

60、; assert (sizeof (u32) = 4);    if (argc < 2)            fprintf (stderr, "usage: sha1sum filenames/n");        exit (1);        for (argc-, argv+; argc; argv+, argc-) /实现对多个文件批量签名，循环一次签名一个文件            FILE *fp;        char buffer4096;