SHA课程设计报告

PAGE成都信息工程学院课程设计报告SHA1散列算法的实现课程名称：应用密码算法程序设计学生姓名：邓兴全学生学号：2007122063专业班级：信安072任课教师：万武南2009附件：课程设计成绩评价表附件：课程设计成绩评价表学习与工作态度（30%）选题意义（10%）文献综述（10%）研究水平与设计能力（20%）课程设计说明说（论文）撰写质量（20%）设计创新（10%）总分指导老师签名：年月日课程设计答辩记录及评价表学生讲述情况教师主要提问记录学生回答问题情况答辩评分评分项目分值评价参考标准评分总分优良中及格差选题意义1098764文献综述1098764研究水平与设计能力201917151310课程设计说明书（论文）撰写质量201917151310设计创新1098764答辩效果302825221915答辩小组成员签名答辩小组组长签名：年月日课程设计成绩评定表成绩汇总评分项目评分比例分数课程设计总分指导老师评分50%答辩小组评分50%

目录1. 引言 11.1背景 11.2目的 11.3算法描述 12.系统设计 22.1系统主要目标 22.1.1主要软件需求 22.1.2运行环境 22.2系统结构 32.2.1软件操作流程 32.2.2功能模块与系统结构 33系统功能程序设计 33.1基本要求部分 33.1.1消息转换成二进制 33.1.2消息填充 43.1.3初始化消息摘要的缓冲区 53.1.4各轮使用到的逻辑函数 53.1.5十六进制转换 63.1.6分组hash 93.1.7消息hash 103.2较高要求部分 114.测试报告 125．结论 13参考文献 14第2页共14页引言1.1背景SHA_1是由美国尺度技术局（NIST）公布的国度尺度，是一种利用最为普遍的hash函数算法，也是目前最先进的加密技术，被政府部门和企业用来处置敏感的信息。1.2目的安全哈希算法（SecureHashAlgorithm）主要适用于数字签名标准（DigitalSignatureStandardDSS）里面定义的数字签名算法（DigitalSignatureAlgorithmDSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。SHA1特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。1.3算法描述在SHA1算法中，我们必须把原始消息（字符串，文件等）转换成位字符串。SHA1算法只接受位作为输入，以512位为单位分组处理。消息必须进行填充，以使其长度在对512取模以后的余数是448，然后再添加消息本身的长度，通常用一个64位的数据来表示原始消息的长度。算法中使用到的常量：一系列的常量字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).在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).必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由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个步骤。在处理每个数据块之前，缓冲区被初始化为下面的值（16进制）H0=0x67452301，H1=0xEFCDAB89，H2=0x98BADCFE，H3=0x10325476，H4=0xC3D2E1F0。为了处理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.2.系统设计2.1系统主要目标2.1.1主要软件需求使用编程语言（如Java、VC++等）实现SHA-1算法的软件系统设计。基本要求：(1)在深入理解算法的基础上，设计一个生成消息摘要的软件系统；(2)要求输入信息是ASCII码等，允许只有一个分组，运行后生成固定长度的消息摘要；（3）消息摘要值计算的中间结果输出并与标准对比；（4）提供所设计的报告及完整的软件。高级要求：(1)要求输入信息可以是汉字或英文，或者是文本文档，可以是多个分组；也可以是各种类型的文件;(2)程序有比较好的结构，方便代码重用。2.1.2运行环境本软件使用c#语言编写测试平台：Windows2003使用软件：Visualstudio2008C#简介C#是可用于创建运行在.NETCLR上的应用程序语言之一，它从C和C++语言演化而来，是microsoft专门为使用.NET平台而创建的。因为C#是近期发展起来的，所以吸取了以前的教训，考虑了其他语言的许多有点，并解决了它们的问题。2.2系统结构2.2.1软件操作流程进入软件界面后按要求输入消息并点击相应的功能键。2.2.2功能模块与系统结构编号模块名称模块标识1消息的二进制转换ConvertTo(输入为字符串或文件输出为二进制数组)2消息填充Pad(对二进制数组按算法要求进行填充)3初始化寄存器Init(初始化五个寄存器的值)4初始化常数值ktInit(初始化常数值kt)5逻辑函数Zip(四轮循环中使用到的逻辑函数)6十六进制转换HEX(将int32或者byte转换成十六进制)7512位块hash_512Hash(单独512位分组摘要值计算)8消息hashMessageHash(整个消息的摘要值计算)9上传文件openFileDialog(上传文件并调用响应的摘要值计算方法)3系统功能程序设计3.1基本要求部分3.1.1消息转换成二进制程序从文本框得到消息字符串，并将其以参数形式传到二进制转换函数B_message(Stringmessage)。函数首先用一个字符数组Byte[]接收字符串,然后再用Bitarray的带字节数组参数的构造方法将字节数组转换成布尔数组，得到消息的二进制表示。由于sha-1函数采用高位在前的处理方式(即大端序列)，所以为了能与后续的（填充）处理衔接，此处我们将输入的二进制转换为大端序列,即以八位二进制位为单位进行逆转处理（处理机默认的是小端序列），在填充完成之后再以同样的方式再从大端序列转成小端序列以得到在系统下的正确结果。程序如ConvertTo所示。classConvertTo{将消息转换成二进制数组publicstaticBitArrayB_message(Stringmessage){Byte[]_byte=newByte[message.Length];for(inti=0;i<message.Length;i++){_byte[i]=(Byte)message[i];}BitArray_bitArray=newBitArray(_byte);bool_exchange;序列转换for(inti=0;i<message.Length;i++){for(intj=0;j<4;j++){_exchange=_bitArray[8*i+j];_bitArray[8*i+j]=_bitArray[8*(i+1)-j-1];_bitArray[8*(i+1)-j-1]=_exchange;}}return_bitArray;}3.1.2消息填充算法是以512位为单位进行处理的，必须首先进行填充使得消息长度=448mod512.，并且处理的二进制序列最后需添加消息长度的二进制表示（64位）。首先用一个int32的数通过Bitarry的Count属性获消息长度，程序为了能方便的将其转换成Bitarry形式的bool数组，将此int32放在一个int32[]数组中，方法同上字节数组的转换，得到一个32位的bool数组，即消息长度的二进制表示。然后进行第一个填充位1的添加，若消息长度模512等于448，则直接进入消息长度的添加，若不等则通过Bitarry的Length属性将消息长度加1，并赋值为true。再进行填充位0的添加，程序通过设置Bitarry的元素个数来实现，因为Bitarry元素的默认值是1。若消息长度小于等于448则将消息长度设置为448，若大于448则需要进行下一步判断：若消息长度模512等于448则长度不变，不等则消息长度设置为原消息长度加512-(message.Count-448)%512；最后再将消息长度加64，用以添加消息长度的二进制表示，程序用一个循环赋值的方法实现。privateBitArrayPad(BitArraymessage){获取消息的二进制位数，此处用数组是为了向后转换成bitarry提供参数Int32[]_messageL=newInt32[1];_messageL[0]=message.Count;下标加1并对该位赋值true，即在消息后面第一位填充1if(message.Count%512!=448){message.Length+=1;message.Set(_messageL[0],true);}添加需要的零if(message.Count>448){message.Length+=(message.Count-448)%512==0?0:512-(message.Count-448)%512;}else{message.Length=448;}在最后添加消息长度BitArraylength=newBitArray(_messageL);message.Length+=64;for(intj=0;j<32;j++){message[message.Count-j-1]=length[j];}returnmessage;}3.1.3初始化程序使用160比特长的缓冲区存储中间结果和最终消息摘要值，缓冲区可表示为5个32比特长的寄存器(A,B,C,D,E)，其初始值分别为A=67452301B=EFCDAB89D=10325476E=C3D2E1F0。UInt32[]_Hvalue=newUInt32[5];_Hvalue[0]=0x67452301;_Hvalue[1]=0xEFCDAB89;_Hvalue[2]=0x98BADCFE;_Hvalue[3]=0x10325476;_Hvalue[4]=0xC3D2E1F0;以同样的方法可以初始化分别要在四轮循环中用到的常数值kt，Kt值如上算法中所描述。3.1.4四轮循环中的每一轮循环都用到各自的逻辑函数，一轮循环中的二十步是一样的，所以事先提取出来，如第一轮循环中即t=0到19使用的逻辑函数为((B&C)|((UInt32)(~B)&D))，用以寄存器A的值运算。代码如下：privateUInt32Zip(UInt32B,UInt32C,UInt32D,intt){各轮使用到的逻辑函数if(t<20){return((B&C)|((UInt32)(~B)&D));}elseif(t<40){returnB^C^D;}elseif(t<60){return(B&C)|(B&D)|(C&D);}else{returnB^C^D;}每一轮循环都以当前处理的512位和160位的缓存值ABCDE为输入，然后更新缓存的内容。每个循环还使用到之前所初始化的常数值。最后第四轮的输出加到第一轮循环的输入产生产生最后的消息摘要值。3.1.5十六进制转换程序的结果显示中要用到十六进制的转换，一个是在分组hash中的强制类型转换：_Wvalue[t]=Convert.ToUInt32(HEX.Hex(_byte[4*t])+HEX.Hex(_byte[4*t+1])+HEX.Hex(_byte[4*t+2])+HEX.Hex(_byte[4*t+3]),16)这是由于程序采用Convert.ToUInt32里第一个参数是指定基数的数字的字符串表式。这个十六进制转换函数以byte为处理参数，结果是用两个十六进制数分别表示byte数中的高四位和低四位，具体实现方法是将byte除以16和byte模16的值（即高四位和低四位）赋给两个int型的整数，然后对这两个数进行同样的处理：若在0到9之间则进行强制类型转换(char)(number+48)；若在10到15之间则用switch将10到15对应A到F显示出来，最后将这两个十六进制数合并成一个字符串返回。代码如下：classHEX{publicstaticstringHex(Byte_number){int_number1=_number/16;int_number2=_number%16;StringhexResult="";if(_number1<10){hexResult+=(char)(_number1+48);}else{switch(_number1){case10:hexResult+="A";break;case11:hexResult+="B";break;case12:hexResult+="C";break;case13:hexResult+="D";break;case14:hexResult+="E";break;case15:hexResult+="F";break;}}if(_number2<10){hexResult+=(char)(_number2+48);}else{switch(_number2){case10:hexResult+="A";break;case11:hexResult+="B";break;case12:hexResult+="C";break;case13:hexResult+="D";break;case14:hexResult+="E";break;case15:hexResult+="F";break;}}returnhexResult;}publicstaticstringHex(UInt32_number){stringhexResult="";inti=0;while(_number!=0){if(_number%16<10){hexResult+=(char)(_number%16+48);}else{switch(_number%16){case10:hexResult+="A";break;case11:hexResult+="B";break;case12:hexResult+="C";break;case13:hexResult+="D";break;case14:hexResult+="E";break;case15:hexResult+="F";break;}}_number/=16;i++;}while(i<8){hexResult+="0";i++;}Stringrresult="";for(i=7;i>=0;i--){rresult+=hexResult[i];}returnrresult;}另一个用到十六进制转换的地方就是最后的输出是以十六进制显示的，而直接的输出是五个寄存器中的32位字，所以需要进行一个将int32转化成十六进制显示的函数，当然两个的处理其实是类似的。3.1.6分组hash前后的准备工作都做好了，接下来进入本程序最核心的部分，对每一个分组进行hash。此过程以512位的字节数组表示为输入，首先将消息拆分成十六个三十二位字得到W0到W15，具体实现是通过下标寻找到响应的byte值进行强制类型转换，后续的W[t]值由下标为W[t-3],W[t-8],W[t-14],和W[t-16]异或之后循环左移一位得到：privatevoid_512Hash(Byte[]_byte){for(intt=0;t<16;t++){拆分消息得到w0到w15,w0是做左边的一个._Wvalue[t]=Convert.ToUInt32(HEX.Hex(_byte[4*t])+HEX.Hex(_byte[4*t+1])+HEX.Hex(_byte[4*t+2])+HEX.Hex(_byte[4*t+3]),16);}for(intt=16;t<80;t++){_Wvalue[t]=Shift(_Wvalue[t-3]^_Wvalue[t-8]^_Wvalue[t-14]^_Wvalue[t-16],1);}将之前初始化的寄存器值装入寄存器：UInt32AUInt32B=_Hvalue[1];UInt32CUInt32D=_Hvalue[3];UInt32E=_Hvalue[4];然后更新寄存器的值从t=0到79A寄存器的值TEMP=S5(A)(循环左移五位)+zip（B,C,D）(相应的逻辑函数)+E+Wt+Kt,%4294967296指的是模2^32次方加E=D;D=C;C=S30(B);B=A;A=TEMPfor(intt=0;t<80;t++){UInt32TEMP=(UInt32)((Shift(A,5)+Zip(B,C,D,t)+E+_Wvalue[t]+_Kvalue[t])%4294967296);E=D;D=C;C=Shift(B,30);B=A;A=TEMP;以string的形式记录中间结果用以输出mvalue+="A"+t+""+HEX.Hex(_Hvalue[0])+""+"B"+t+""+HEX.Hex(_Hvalue[1])+""+"C"+t+""+HEX.Hex(_Hvalue[2])+""+"D"+t+""+HEX.Hex(_Hvalue[3])+""+"E"+t+""+HEX.Hex(_Hvalue[4])+"\r\n";}最后的变换函数H0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E.得到消息摘要_Hvalue[0]=(UInt32)((_Hvalue[0]+A)%4294967296);_Hvalue[1]=(UInt32)((_Hvalue[1]+B)%4294967296);_Hvalue[2]=(UInt32)((_Hvalue[2]+C)%4294967296);_Hvalue[3]=(UInt32)((_Hvalue[3]+D)%4294967296);_Hvalue[4]=(UInt32)((_Hvalue[4]+E)%4294967296);}这便是一个分组的整个处理过程。3.1.7消息hash然后进行整个消息摘要值的计算，以消息字符转转换成的bitarry为输入首先初始化寄存器init();然后进行消息填充message=Pad(message);计算消息分组for(inti=0;i<message.Count/512;i++){以512位为处理单位一块一块处理BitArray_512Message=newBitArray(512);for(intj=0;j<512;j++){_512Message[j]=message[512*i+j];}这里是要转换成为小端序列，即以字节为单位将位的顺序逆转bool_exchange;for(intj=0;j<64;j++){for(intk=0;k<4;k++){_exchange=_512Message[8*j+k];_512Message[8*j+k]=_512Message[8*(j+1)-k-1];_512Message[8*(j+1)-k-1]=_exchange;