SHA课程设计报告

成都信息工程学院

课程设计报告

SHA1散列算法的实现

课程名称:应用密码算法程序设计

学生姓名:       邓兴全        

学生学号:    2007122063      

专业班级:       信安072       

任课教师:      万武南         

20##年11月 4日



目  录

1.    引言... 1

1.1背景... 1

1.2目的... 1

1.3算法描述... 1

2.系统设计... 2

2.1系统主要目标... 2

2.1.1主要软件需求... 2

2.1.2运行环境... 2

2.2 系统结构... 3

2.2.1 软件操作流程... 3

2.2.2功能模块与系统结构... 3

3 系统功能程序设计... 3

3.1基本要求部分... 3

3.1.1消息转换成二进制... 3

3.1.2消息填充... 4

3.1.3初始化消息摘要的缓冲区... 5

3.1.4各轮使用到的逻辑函数... 5

3.1.5十六进制转换... 6

3.1.6分组hash. 9

3.1.7消息hash. 10

3.2较高要求部分... 11

4. 测试报告... 12

5.结论... 13

参考文献... 14


1.   引言

1.1背景

SHA_1是由美国尺度技术局(NIST)公布的国度尺度,是一种利用最为普遍的hash函数算法,也是目前最先进的加密技术,被政府部门和企业用来处置敏感的信息。

1.2目的

安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于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) = (B AND C) or ((NOT B) AND D) ( 0 <= 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).

必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由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-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; 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.

2.系统设计

2.1系统主要目标

2.1.1主要软件需求

使用编程语言(如Java、VC++等)实现SHA-1算法的软件系统设计。

基本要求:(1)在深入理解算法的基础上,设计一个生成消息摘要的软件系统;(2)要求输入信息是ASCII码等,允许只有一个分组,运行后生成固定长度的消息摘要;(3)消息摘要值计算的中间结果输出并与标准对比;(4 )提供所设计的报告及完整的软件。

高级要求:(1)要求输入信息可以是汉字或英文,或者是文本文档,可以是多个分组;也可以是各种类型的文件;(2)程序有比较好的结构,方便代码重用。

                       

2.1.2运行环境

本软件使用c#语言编写

测试平台:Windows 2003

使用软件:Visual studio 2008

C#简介

C#是可用于创建运行在.NET CLR上的应用程序语言之一,它从C和C++语言演化而来,是microsoft专门为使用.NET平台而创建的。因为C#是近期发展起来的,所以吸取了以前的教训,考虑了其他语言的许多有点,并解决了它们的问题。

2.2 系统结构

2.2.1 软件操作流程

进入软件界面后按要求输入消息并点击相应的功能键。

2.2.2功能模块与系统结构

3 系统功能程序设计

3.1基本要求部分

3.1.1消息转换成二进制

程序从文本框得到消息字符串,并将其以参数形式传到二进制转换函数B_message(String message)。函数首先用一个字符数组Byte[]接收字符串,然后再用Bitarray的带字节数组参数的构造方法将字节数组转换成布尔数组,得到消息的二进制表示。

由于sha-1函数采用高位在前的处理方式(即大端序列),所以为了能与后续的(填充)处理衔接,此处我们将输入的二进制转换为大端序列,即以八位二进制位为单位进行逆转处理(处理机默认的是小端序列),在填充完成之后再以同样的方式再从大端序列转成小端序列以得到在系统下的正确结果。程序如ConvertTo所示。

class ConvertTo

{     

 将消息转换成二进制数组       

 public static BitArray B_message(String message)

        {

            Byte[] _byte = new Byte[message.Length];

            for (int i = 0; i < message.Length; i++)

            {

                _byte[i] = (Byte)message[i];

            }

            BitArray _bitArray = new BitArray(_byte);

            bool _exchange;

            序列转换

            for (int i = 0; i < message.Length; i++)

            {

                for (int j = 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,用以添加消息长度的二进制表示,程序用一个循环赋值的方法实现。

private BitArray Pad(BitArray message)

        {

           获取消息的二进制位数,此处用数组是为了向后转换成bitarry提供参数

            Int32[] _messageL = new Int32[1];

            _messageL[0] = message.Count;

            下标加1并对该位赋值true,即在消息后面第一位填充1   

          if (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;

            }

            在最后添加消息长度

            BitArray length = new BitArray(_messageL);

            message.Length += 64;

            for (int j = 0; j < 32; j++)

            {

                message[message.Count - j - 1] = length[j];

            }

            return message;

        }

3.1.3初始化消息摘要的缓冲区

程序使用160比特长的缓冲区存储中间结果和最终消息摘要值,缓冲区可表示为5个32比特长的寄存器(A, B, C, D, E),其初始值分别为

A=67452301  B=EFCDAB89  C=98BADCFB

          D=10325476  E=C3D2E1F0。

UInt32[] _Hvalue = new UInt32[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的值运算。代码如下:

private UInt32 Zip(UInt32 B, UInt32 C, UInt32 D, int t)

        {

            各轮使用到的逻辑函数

            if (t < 20)

            {

                return ((B & C) | ((UInt32)(~B) & D));

            }

            else if (t < 40)

            {

                return B ^ C ^ D;

            }

            else if (t < 60)

            {

                return (B & C) | (B & D) | (C & D);

            }

            else

            {

                return B ^ 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显示出来,最后将这两个十六进制数合并成一个字符串返回。代码如下:

class HEX

    {

        public static string Hex(Byte _number)

        {

            int _number1 = _number / 16;

            int _number2 = _number % 16;

            String hexResult = "";

            if (_number1 < 10)

            {

                hexResult += (char)(_number1 + 48);

            }

            else

            {

                switch (_number1)

                {

                    case 10:

                        hexResult += "A";

                        break;

                    case 11:

                        hexResult += "B";

                        break;

                    case 12:

                        hexResult += "C";

                        break;

                    case 13:

                        hexResult += "D";

                        break;

                    case 14:

                        hexResult += "E";

                        break;

                    case 15:

                        hexResult += "F";

                        break;

                }

            }

            if (_number2 < 10)

            {

                hexResult += (char)(_number2 + 48);

            }

            else

            {

                switch (_number2)

                {

                    case 10:

                        hexResult += "A";

                        break;

                    case 11:

                        hexResult += "B";

                        break;

                    case 12:

                        hexResult += "C";

                        break;

                    case 13:

                        hexResult += "D";

                        break;

                    case 14:

                        hexResult += "E";

                        break;

                    case 15:

                        hexResult += "F";

                        break;

                }

            }

            return hexResult;

        }

        public static string Hex(UInt32 _number)

        {

            string hexResult = "";

            int i = 0;

            while (_number != 0)

            {

                if (_number % 16 < 10)

                {

                    hexResult += (char)(_number % 16 + 48);

                }

                else

                {

                    switch (_number % 16)

                    {

                        case 10:

                            hexResult += "A";

                            break;

                        case 11:

                            hexResult += "B";

                            break;

                        case 12:

                            hexResult += "C";

                            break;

                        case 13:

                            hexResult += "D";

                            break;

                        case 14:

                            hexResult += "E";

                            break;

                        case 15:

                            hexResult += "F";

                            break;

                    }

                }

                _number /= 16;

                i++;

            }

            while (i < 8)

            {

                hexResult += "0";

                i++;

            }

            String rresult = "";

            for (i = 7; i >= 0; i--)

            {

                rresult += hexResult[i];

            }

            return rresult;

        }

另一个用到十六进制转换的地方就是最后的输出是以十六进制显示的,而直接的输出是五个寄存器中的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]异或之后循环左移一位得到:

        private void _512Hash(Byte[] _byte)

        {

            for (int t = 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 (int t = 16; t < 80; t++)

            {

                _Wvalue[t] = Shift(_Wvalue[t - 3] ^ _Wvalue[t - 8] ^ _Wvalue[t - 14] ^ _Wvalue[t - 16], 1);

            }

将之前初始化的寄存器值装入寄存器:

            UInt32 A = _Hvalue[0];

            UInt32 B = _Hvalue[1];

            UInt32 C = _Hvalue[2];

            UInt32 D = _Hvalue[3];

            UInt32 E = _Hvalue[4];

           然后更新寄存器的值从t=0到79

           A寄存器的值 TEMP=S5(A)(循环左移五位)+zip(B,C,D)(相应的逻辑函数)+E+Wt+Kt, % 4294967296指的是模2^32次方加

           E=D;D=C;C=S30(B);B=A;A=TEMP       

               for (int t = 0; t < 80; t++)

            {

                UInt32 TEMP = (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 (int i = 0; i < message.Count / 512; i++)

            {

                以512位为处理单位一块一块处理

                BitArray _512Message = new BitArray(512);

                for (int j = 0; j < 512; j++)

                {

                    _512Message[j] = message[512 * i + j];

                }

这里是要转换成为小端序列,即以字节为单位将位的顺序逆转

                bool _exchange;

                for (int j = 0; j < 64; j++)

                {

                    for (int k = 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;

                    }

                }

                复制到字节数组里边去做好最后的hash准备

                Byte[] _byte= new Byte[64];

                _512Message.CopyTo(_byte, 0);

                 对512位块进行hash

                _512Hash(_byte);

            }

            得到最后的消息摘要值并转换成为十六进制

            return HEX.Hex(_Hvalue[0]) + HEX.Hex(_Hvalue[1]) + HEX.Hex(_Hvalue[2]) + HEX.Hex(_Hvalue[3]) + HEX.Hex(_Hvalue[4]);

            顺序记录分组处理的结果,用以中间值的显示

mvalue +="第"+(i+1)+"分组加密结果"+" "+ "A"  + " " + HEX.Hex(_Hvalue[0]) + " " + "B"  + " " + HEX.Hex(_Hvalue[1]) + " " + "C"  + " " + HEX.Hex(_Hvalue[2]) + " " + "D" + " " + HEX.Hex(_Hvalue[3]) + " " + "E" +  " " + HEX.Hex(_Hvalue[4]) + "\r\n";

        }

    }

3.2较高要求部分

在实际应用中我们不只是要用到对输入的消息的消息摘要的生成,更重要的是对文件的hash所以程序添加了对文件的hash功能上传文件由控件openFileDialog实现,后续处理如下:

textBox2.Tex=HEX.HexPrint(sha_1.MessageHash(ConvertTo.B_message(message)));即对前面功能模块的调用。类似的在输入的字符串的hash功能空间button关联的事件如下: 获取文本框输入信息

  _message = textBox1.Text;

将字符串转换为二进制

             b_Message = ConvertTo.B_message(_message);

调用hash方法计算摘要值

             _hashResult = sha_1.MessageHash(b_Message);

美化输出

         textBox2.Text = HEX.HexPrint(_hashResult);

4. 测试报告

软件界面如图:

输入消息值:abc得到如图

上传文件如图

其中上传的文件内容为abc得到信息如图

Abc的消息摘要信息与标准的消息摘要信息一致。

5.结论

经过检测:本软件能进行正常消息摘要,结果没有错误;

根据上面两个消息的测试结果,证明该程序代码正确并且可行。从设计到最后测试结果来看,效果比较好,能较好的实现对简单字符串及2^32-1bit以下文件大小的消息摘要值生成。当然,该程序肯定还存在很多不足的地方,比如没有实现算法中对2^64-1bit的hash,主要是由于时间关系和对c#数据结构和函数的不熟悉,希望在以后的运用当中能够得到改进。

参考文献

[1]  Visual C#.NET(修订本) 清华大学出版社 2004

[2]  胡向东 应用密码学   电子工业出版社2006

[3] 杨波  现代密码学 清华大学出版社 2003

[4] 张福泰  密码学教程(第一版)    武汉大学出版社 2006

相关推荐