搜索
SHA1算法原理1SHA1算法简介安全哈希算法（SecureHashAlgorithm）主要适用于数字签名标准（DigitalSignatureStandardDSS）里面定义的数字签名算法（DigitalSignatureAlgorithmDSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。SHA1有如下特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。2术语和概念2.1位(Bit)，字节（Byte）和字（Word）SHA1始终把消息当成一个位（bit）字符串来处理。本文中，一个“字”（Word）是32位，而一个“字节”（Byte）是8位。比如，字符串“abc”可以被转换成一个位字符串：011000010110001001100011。它也可以被表示成16进制字符串:0x616263.2.2运算符和符号下面的逻辑运算符都被运用于“字”（Word）X^Y=X，Y逻辑与X\/Y=X，Y逻辑或XXORY=X，Y逻辑异或~X=X逻辑取反X+Y定义如下：字X和Y代表两个整数x和y,其中0=x2^32且0=y2^32.令整数z=(x+y)mod2^32.这时候0=z2^32.将z转换成字Z,那么就是Z=X+Y.循环左移位操作符Sn(X)。X是一个字，n是一个整数，0=n=32。Sn(X)=(Xn)OR(X32-n)Xn定义如下：抛弃最左边的n位数字，将各个位依次向左移动n位，然后用0填补右边的n位（最后结果还是32位）。Xn是抛弃右边的n位，将各个位依次向右移动n位，然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算3SHA1算法描述在SHA1算法中，我们必须把原始消息（字符串，文件等）转换成位字符串。SHA1算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先，我们将它转换成位字符串如下：011000010110001001100011―――――――――――――‘a’=97‘b’=98‘c’=99这个位字符串的长度为24。下面我们需要5个步骤来计算MD5。3.1补位消息必须进行补位，以使其长度在对512取模以后的余数是448。也就是说，（补位后的消息长度）%512=448。即使长度已经满足对512取模后余数是448，补位也必须要进行。补位是这样进行的：先补一个1，然后再补0，直到长度满足对512取模后余数是448。总而言之，补位是至少补一位，最多补512位。还是以前面的“abc”为例显示补位的过程。原始信息：011000010110001001100011补位第一步：0110000101100010011000111首先补一个“1”补位第二步：01100001011000100110001110…..0然后补423个“0”我们可以把最后补位完成后的数据用16进制写成下面的样子6162638000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000现在，数据的长度是448了，我们可以进行下一步操作。3.2补长度所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0。在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）61626380000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018如果原始的消息长度超过了512，我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块，分别处理每一个数据块，从而得到消息摘要。3.3使用的常量一系列的常量字K(0),K(1),...,K(79)，如果以16进制给出。它们如下：Kt=0x5A827999(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)=(BANDC)or((NOTB)ANDD)(0=t=19)ft(B,C,D)=BXORCXORD(20=t=39)ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40=t=59)ft(B,C,D)=BXORCXORD(60=t=79).3.5计算消息摘要必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由5个32位的字组成，还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A，B，C，D，E。第一个5个字的缓冲区被标识为H0,H1,H2,H3,H4。80个字的缓冲区被标识为W0,W1,...,W79另外还需要一个一个字的TEMP缓冲区。为了产生消息摘要，在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理，处理每个数据块Mi包含80个步骤。在处理每个数据块之前，缓冲区{Hi}被初始化为下面的值（16进制）H0=0x67452301H1=0xEFCDAB89H2=0x98BADCFEH3=0x10325476H4=0xC3D2E1F0.现在开始处理M1,M2,...,Mn。为了处理Mi,需要进行下面的步骤(1).将Mi分成16个字W0,W1,...,W15,W0是最左边的字(2).对于t=16到79令Wt=S1(Wt-3XORWt-8XORWt-14XORWt-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;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位的字符串，以下面的顺序标识H0H1H2H3H4.对于SHA256,SHA384,SHA512。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。sha1是一种比md5的安全性强的算法，当然sha256和sha512更好，但计算开销更大一些,理论上，凡是采取“消息摘要”方式的数字验证算法都是有“碰撞”的——也就是两个不同的东西算出的消息摘要相同，互通作弊图就是如此。但是安全性高的算法要找到指定数据的“碰撞”很困难（困难到用暴力法寻找要花去几百年甚至几千年），而利用公式来计算“碰撞”就更困难——目前为止通用安全算法中仅有md5被破解.附：来自网络上的SHA－1算法，自己加了少量注释，方便以后需要的时候可以利用。代码：/*sha1sum.c-printSHA-1Message-DigestAlgorithm*Copyright(C)1998,1999,2000,2001FreeSoftwareFoundation,Inc.*Copyright(C)2004g10CodeGmbH**Thisprogramisfreesoftware;youcanredistributeitand/ormodifyit*underthetermsoftheGNUGeneralPublicLicenseaspublishedbythe*FreeSoftwareFoundation;eitherversion2,or(atyouroption)any*laterversion.**Thisprogramisdistributedinthehopethatitwillbeuseful,*butWITHOUTANYWARRANTY;withouteventheimpliedwarrantyof*MERCHANTABILITYorFITNESSFORAPARTICULARPURPOSE.Seethe*GNUGeneralPublicLicenseformoredetails.**YoushouldhavereceivedacopyoftheGNUGeneralPublicLicense*alongwiththisprogram;ifnot,writetotheFreeSoftwareFoundation,*Inc.,59TemplePlace-Suite330,Boston,MA02111-1307,USA.*//*SHA-1codentakefromgnupg1.3.92.Note,thatthisisasimpletooltobeusedforMSWindows.*/#includestdio.h#includestdlib.h#includestring.h#includeassert.h#includeerrno.h#undefBIG_ENDIAN_HOSTtypedefunsignedintu32;/*****************Rotatea32bitintegerbynbytes****************/#ifdefined(__GNUC__)&&defined(__i386__)staticinlineu32rol(u32x,intn){__asm__(roll%%cl,%0:=r(x):0(x),c(n));returnx;}#else#definerol(x,n)(((x)(n))|((x)(32-(n))))#endiftypedefstruct{u32h0,h1,h2,h3,h4;//哈希计算后的结果是20个bit，刚好相当于5个unsignedint(4字节)类型的数据u32nblocks;unsignedcharbuf[64];intcount;}SHA1_CONTEXT;voidsha1_init(SHA1_CONTEXT*hd)//计算前进行初始化{hd-h0=0x67452301;hd-h1=0xefcdab89;hd-h2=0x98badcfe;hd-h3=0x10325476;hd-h4=0xc3d2e1f0;hd-nblocks=0;hd-count=0;}/**TransformthemessageXwhichconsistsof1632-bit-words*/staticvoidtransform(SHA1_CONTEXT*hd,unsignedchar*data){u32a,b,c,d,e,tm;u32x[16];/*getvaluesfromthechainingvars*/a=hd-h0;b=hd-h1;c=hd-h2;d=hd-h3;e=hd-h4;#ifdefBIG_ENDIAN_HOSTmemcpy(x,data,64);#else{inti;unsignedchar*p2;for(i=0,p2=(unsignedchar*)x;i16;i++,p2+=4){p2[3]=*data++;p2[2]=*data++;p2[1]=*data++;p2[0]=*data++;}}#endif#defineK10x5A827999L#defineK20x6ED9EBA1L#defineK30x8F1BBCDCL#defineK40xCA62C1D6L#defineF1(x,y,z)(z^(x&(y^z)))#defineF2(x,y,z)(x^y^z)#de