基于大数据的SHA—1算法的适应性研究

汪建　方洪鹰

摘要：安全哈希算法（Secure Hash Algorithm）诞生之初便作为优秀的签名算法得到安全界的重视，其中SHA-1更是因为其安全性和高效性被全球各个领域普遍采用。但是面对海量的待签信息，传统的算法将不再胜任。该文着力于基于大数据的SHA-1算法研究，通过改造散列计算步骤，提出分布式云计算模型，最终减少算法的空间复杂度提高计算效率。

关键词：大数据；云计算；分布式计算；SHA-1

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）30-7032-04

安全散列算法（Secure Hash Algorithm，SHA） 是1993年美国国家安全局（NSA）设计，由美国国家标准与技术研究院（NIST） 发布的密码散列算法，1995年升级发布了SHA-1[1]版本。SHA-1可以从一个最大[264]位的原始信息中产生一串 160位的摘要。其安全性体现在单向性和抗碰撞性两个方面[2]：单向性指的是的其散列函数[y=fSHA-1x]理论上不存在逆函数[f'SHA-1]使得[x=f'SHA-1y]；抗碰撞性指的是要找到两个不同的[x1]和[x2]，使得[fSHA-1x1=fSHA-1x2]，在有限计算上也是不可行的。

SHA-1正是因为其安全性和高效性被全球各个领域普遍采用。但自1995年诞生至今SHA-1已有20个年头的，面对当今海量的数据信息（G级文件比比皆是，T级文件也不罕见），其计算效率已不再具有优势。该文基于大数据需求对SHA-1算法进行研究，通过改造散列计算步骤，提出分布式云计算模型，利用分布式云计算，最终减少算法的空间复杂度提高计算效率。

1 传统的SHA-1算法介绍

1.1 常量定义[3]

[H]集：SHA-1算法需要5个字长为32位的初始散列集合[H=h0，h1，h2，h3，h4]。其中：[h0=0x67452301]，[h1=0xEFCDAB89]，[h2=0x98BADCFE]，[h3=0x10325476]，[h4=0xC3D2E1F0]。

[K]集：散列计算时需要4个字长为32位的常量集合[K=k0，k1，k2，k3]。其中：[k0=0x5A827999]，[k1=0x6ED9EBA1]，[k2=0x8F1BBCDC]，[k3=0xCA62C1D6]。

[ml]（Message Length）：原始代签名数据长度。采用64位二进制数据表示原始消息的长度。

1.2 算法声明

考虑到算法的一致性，SHA-1算法用到的所有变量均为32位无符号整数，所有的常量，无论大小，数据均采用大端字节序（Big Endian）存放，即位元组由大到小，高位优先。

1.3 原始信息预处理

假设原始消息为[M0]，其长度为[l]。

首先在原始消息末尾增加1个位（Bit），并将其值置为1，由此得来的消息块命名为[M1]，其长度为[l+1]；

然后在[M1]之后添加[k0≤k<512]个0，使得[l+1+k mod 512=448]，由此得来的消息块命名为[M2]，当然其长度为[l+1+k]；

最后在[M2]之后添加64位的常量[ml]，由此得来的消息块命名为[M]，其长度为[L=l+1+k]+64。

比如原始消息[M0]为“abc”，采用ASCII进行编码，其长度[l=8×3=24]；[k=423]。

1.4 信息分割

原始信息经过预处理之后，还必须进行分割。SHA-1将填充之后的信息[M]分割成长度为512位的块（Chunk），并记为集合[C=ci|0≤i≤L/512]。

1.5 哈希值计算[4]

SHA-1的核心部分即是哈希值的迭代计算过程，其算法可以用如下伪代码表示：

//定义临时变量[a，b，c，d，e，f，tmp]

//定义变量[sha1]

for each [ci0≤i≤L/512]

{分解[ci]成为16个32位的字[wj]，记为[W=wj|0≤j≤15]；

[扩展[W]集，使[W=wj|0≤j≤79]；

for [j] from 16 to 79

[wj=wj-3⊕wj-8⊕wj-14⊕wj-16 leftrotate 1]；

[a=h0]； [b=h1]； [c=h2]； [d=h3]； [e=h4]；

for [j] from 0 to 79

{if （[0≤j≤19]）

{[f=b?c?∽b?d]；

[temp=a leftrotate 5+f+e+k0+wj]；

}

else if （[20≤j≤39]）

{[f=b⊕c⊕d]；

[temp=a leftrotate 5+f+e+k1+wj]；

}

else if （4[0≤j≤59]）

{[f=b∧c∨b∧d∨c∧d]；

[temp=a leftrotate 5+f+e+k2+wj]；

}

else if （6[0≤j≤79]）

{[f=b⊕c⊕d]；

[temp=a leftrotate 5+f+e+k3+wj]；

}

[e=d]； [d=c]； [c=b leftrotate 30]； [b=a]； [a=temp]；

} 公式1]

[h0=h0+a]；endprint

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改进

2.1 传统SHA-1遇到的挑战

SHA-1具有两个重要的特性：单向性和抗碰撞性，并且以其高效性著称。但自从1995年SHA-1诞生以来经历了近20个年头，面对当今海量的数据信息（G级文件比比皆是，T级文件也不罕见），其计算效率已不再具有优势。

分布式云计算的出现给这个挑战带来了机遇，该文基于大数据[5]对SHA-1算法进行研究，通过改造散列计算步骤，提出分布式云计算模型，最终减少算法的空间复杂度提高计算效率。

2.2 分布式SHA-1算法架构

分布式云计算[6]采用C/S架构，系统包含一个服务器端的应用程序和一个客户端的应用程序。算法框架结构如图1所示。

图1 分布式云计算框架结构

服务器根据Chunk Table调度表指示的状态给客户端分发任务，客户端从服务器接收到Chunk块信息后进行单个Chunk Hash计算任务，计算完毕后把结果上传给服务器。两者之间采用TCP作为通信协议。

Chunk Table调度表是整个分布式云计算平台的中心，如表1所示，其中的控制信息是各个客户端（云端）协调一致工作的基础。

表1 Chunk Table结构

[字段名称＼&类型＼&说明＼&ChunkNO＼&bigint＼&分段信息序号＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段处理标志＼&]

2.3 服务器端算法

1） 通信请求处理线程

原始信息预处理（同1.3节）

信息分割（同1.4节）

switch（通信请求.类型）

{case 取任务：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘闲]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

读取取数据文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]区间（位）数据，并回复客户端；

}}

break；

case 存结果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信请求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信请求.a]；

[ChunkTable.recordi.b=通信请求.b]；

[ChunkTable.recordi.c=通信请求.c]；

[ChunkTable.recordi.d=通信请求.d]；

[ChunkTable.recordi.e=通信请求.e]；

}}

break；

}

2） 合并结果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客户端（云端）算法

从服务器获取计算任务和512位数据块[c]；

分解[c]成为16个32位的字[wj]，记为[W=wj|0≤j≤15]；

公式1向服务器汇报运算结果：[a，b，c，d，e]；

3 基于大数据的实验及结果分析

为了验证将分布式云计算引入SHA-1算法的有效性，特地在局域网中搭建了小型的云计算环境，1台服务器+10台客户机（云端），计算大小为500M和6T的文本文件的SHA-1签名值，实验得出传统算法和不同规模的分布计算耗时数据表：

表2

[算法＼&500M＼&6T＼&传统SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

从表中数据可以看出：传统SHA-1算法，单机承担了巨大的计算量，效率随计算规模增加而降低；而本文提出的改进算法优势明显，具有很高的实时性和技术可行性。

5 结论

本文将全面剖析SHA-1摘要算法，研讨了大数据模式下将云计算引入到传统的SHA-1中的具体实现细节，提出基于分布式云计算的改进算法，并且通过试验证明该算法的实用性和高效性，取得了令人满意的结果。

参考文献：

[1] 张松敏，陶荣，于国华.安全散列算法SHA-1的研究[J].计算机安全，2010（10）.

[2] 孙楠楠，韩银河，许都.一种基于循环展开结构的SHA-1算法实现[J].信息技术，2007（3）：29.

[3] 朱雷钧.哈希函数加密算法的高速实现[D].上海：上海交通大学，2007.

[4] 高铭达.基于SHA-1安全认证的题库管理系统[D].厦门：厦门大学，2009.

[5] 万泽春.大数据的应用与解决方案浅析[J].电脑知识与技术，2013（27）.

[6] 周祥峰.智能电网中虚拟化云计算安全的研究[J].计算机安全，2013（5）.

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改进

2.1 传统SHA-1遇到的挑战

SHA-1具有两个重要的特性：单向性和抗碰撞性，并且以其高效性著称。但自从1995年SHA-1诞生以来经历了近20个年头，面对当今海量的数据信息（G级文件比比皆是，T级文件也不罕见），其计算效率已不再具有优势。

分布式云计算的出现给这个挑战带来了机遇，该文基于大数据[5]对SHA-1算法进行研究，通过改造散列计算步骤，提出分布式云计算模型，最终减少算法的空间复杂度提高计算效率。

2.2 分布式SHA-1算法架构

分布式云计算[6]采用C/S架构，系统包含一个服务器端的应用程序和一个客户端的应用程序。算法框架结构如图1所示。

图1 分布式云计算框架结构

服务器根据Chunk Table调度表指示的状态给客户端分发任务，客户端从服务器接收到Chunk块信息后进行单个Chunk Hash计算任务，计算完毕后把结果上传给服务器。两者之间采用TCP作为通信协议。

Chunk Table调度表是整个分布式云计算平台的中心，如表1所示，其中的控制信息是各个客户端（云端）协调一致工作的基础。

表1 Chunk Table结构

[字段名称＼&类型＼&说明＼&ChunkNO＼&bigint＼&分段信息序号＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段处理标志＼&]

2.3 服务器端算法

1） 通信请求处理线程

原始信息预处理（同1.3节）

信息分割（同1.4节）

switch（通信请求.类型）

{case 取任务：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘闲]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

读取取数据文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]区间（位）数据，并回复客户端；

}}

break；

case 存结果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信请求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信请求.a]；

[ChunkTable.recordi.b=通信请求.b]；

[ChunkTable.recordi.c=通信请求.c]；

[ChunkTable.recordi.d=通信请求.d]；

[ChunkTable.recordi.e=通信请求.e]；

}}

break；

}

2） 合并结果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客户端（云端）算法

从服务器获取计算任务和512位数据块[c]；

分解[c]成为16个32位的字[wj]，记为[W=wj|0≤j≤15]；

公式1向服务器汇报运算结果：[a，b，c，d，e]；

3 基于大数据的实验及结果分析

为了验证将分布式云计算引入SHA-1算法的有效性，特地在局域网中搭建了小型的云计算环境，1台服务器+10台客户机（云端），计算大小为500M和6T的文本文件的SHA-1签名值，实验得出传统算法和不同规模的分布计算耗时数据表：

表2

[算法＼&500M＼&6T＼&传统SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

从表中数据可以看出：传统SHA-1算法，单机承担了巨大的计算量，效率随计算规模增加而降低；而本文提出的改进算法优势明显，具有很高的实时性和技术可行性。

5 结论

本文将全面剖析SHA-1摘要算法，研讨了大数据模式下将云计算引入到传统的SHA-1中的具体实现细节，提出基于分布式云计算的改进算法，并且通过试验证明该算法的实用性和高效性，取得了令人满意的结果。

参考文献：

[1] 张松敏，陶荣，于国华.安全散列算法SHA-1的研究[J].计算机安全，2010（10）.

[2] 孙楠楠，韩银河，许都.一种基于循环展开结构的SHA-1算法实现[J].信息技术，2007（3）：29.

[3] 朱雷钧.哈希函数加密算法的高速实现[D].上海：上海交通大学，2007.

[4] 高铭达.基于SHA-1安全认证的题库管理系统[D].厦门：厦门大学，2009.

[5] 万泽春.大数据的应用与解决方案浅析[J].电脑知识与技术，2013（27）.

[6] 周祥峰.智能电网中虚拟化云计算安全的研究[J].计算机安全，2013（5）.

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改进

2.1 传统SHA-1遇到的挑战

SHA-1具有两个重要的特性：单向性和抗碰撞性，并且以其高效性著称。但自从1995年SHA-1诞生以来经历了近20个年头，面对当今海量的数据信息（G级文件比比皆是，T级文件也不罕见），其计算效率已不再具有优势。

分布式云计算的出现给这个挑战带来了机遇，该文基于大数据[5]对SHA-1算法进行研究，通过改造散列计算步骤，提出分布式云计算模型，最终减少算法的空间复杂度提高计算效率。

2.2 分布式SHA-1算法架构

分布式云计算[6]采用C/S架构，系统包含一个服务器端的应用程序和一个客户端的应用程序。算法框架结构如图1所示。

图1 分布式云计算框架结构

服务器根据Chunk Table调度表指示的状态给客户端分发任务，客户端从服务器接收到Chunk块信息后进行单个Chunk Hash计算任务，计算完毕后把结果上传给服务器。两者之间采用TCP作为通信协议。

Chunk Table调度表是整个分布式云计算平台的中心，如表1所示，其中的控制信息是各个客户端（云端）协调一致工作的基础。

表1 Chunk Table结构

[字段名称＼&类型＼&说明＼&ChunkNO＼&bigint＼&分段信息序号＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段处理标志＼&]

2.3 服务器端算法

1） 通信请求处理线程

原始信息预处理（同1.3节）

信息分割（同1.4节）

switch（通信请求.类型）

{case 取任务：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘闲]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

读取取数据文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]区间（位）数据，并回复客户端；

}}

break；

case 存结果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信请求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信请求.a]；

[ChunkTable.recordi.b=通信请求.b]；

[ChunkTable.recordi.c=通信请求.c]；

[ChunkTable.recordi.d=通信请求.d]；

[ChunkTable.recordi.e=通信请求.e]；

}}

break；

}

2） 合并结果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客户端（云端）算法

从服务器获取计算任务和512位数据块[c]；

分解[c]成为16个32位的字[wj]，记为[W=wj|0≤j≤15]；

公式1向服务器汇报运算结果：[a，b，c，d，e]；

3 基于大数据的实验及结果分析

为了验证将分布式云计算引入SHA-1算法的有效性，特地在局域网中搭建了小型的云计算环境，1台服务器+10台客户机（云端），计算大小为500M和6T的文本文件的SHA-1签名值，实验得出传统算法和不同规模的分布计算耗时数据表：

表2

[算法＼&500M＼&6T＼&传统SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

从表中数据可以看出：传统SHA-1算法，单机承担了巨大的计算量，效率随计算规模增加而降低；而本文提出的改进算法优势明显，具有很高的实时性和技术可行性。

5 结论

本文将全面剖析SHA-1摘要算法，研讨了大数据模式下将云计算引入到传统的SHA-1中的具体实现细节，提出基于分布式云计算的改进算法，并且通过试验证明该算法的实用性和高效性，取得了令人满意的结果。

参考文献：

[1] 张松敏，陶荣，于国华.安全散列算法SHA-1的研究[J].计算机安全，2010（10）.

[2] 孙楠楠，韩银河，许都.一种基于循环展开结构的SHA-1算法实现[J].信息技术，2007（3）：29.

[3] 朱雷钧.哈希函数加密算法的高速实现[D].上海：上海交通大学，2007.

[4] 高铭达.基于SHA-1安全认证的题库管理系统[D].厦门：厦门大学，2009.

[5] 万泽春.大数据的应用与解决方案浅析[J].电脑知识与技术，2013（27）.

[6] 周祥峰.智能电网中虚拟化云计算安全的研究[J].计算机安全，2013（5）.