龙源期刊网 http://www.qikan.com.cn
基于大数据的SHA—1算法的适应性研究
作者：汪建 方洪鹰
来源：《电脑知识与技术》2014年第30期
摘要：安全哈希算法（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可以从一个最大[2]位的原始信息中产生一串 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=0xEFCDAB]，[h2=0x98BADCFE]，[h3=0x10325476]，[h4=0xC3D2E1F0]。
[K]集：散列计算时需要4个字长为32位的常量集合[K=k0，k1，k2，k3]。其中：[k0=0x5A827999]，[k1=0x6ED9EBA1]，[k2=0x8F1BBCDC]，[k3=0xCA62C1D6]。
龙源期刊网 http://www.qikan.com.cn
[ml]（Message Length）：原始代签名数据长度。采用位二进制数据表示原始消息的长度。
1.2 算法声明
考虑到算法的一致性，SHA-1算法用到的所有变量均为32位无符号整数，所有的常量，无论大小，数据均采用大端字节序（Big Endian）存放，即位元组由大到小，高位优先。 1.3 原始信息预处理
假设原始消息为[M0]，其长度为[l]。
首先在原始消息末尾增加1个位（Bit），并将其值置为1，由此得来的消息块命名为[M1]，其长度为[l+1]； 然后在[M1]之后添加[k0≤k
最后在[M2]之后添加位的常量[ml]，由此得来的消息块命名为[M]，其长度为[L=l+1+k]+。
比如原始消息[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]；
龙源期刊网 http://www.qikan.com.cn
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]；
龙源期刊网 http://www.qikan.com.cn
} 公式1] [h0=h0+a]； [h1=h1+b]； [h2=h2+c]； [h3=h3+d]； [h4=h4+e]； }
[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate ∨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作为通信协议。
龙源期刊网 http://www.qikan.com.cn
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=‘完’]；
龙源期刊网 http://www.qikan.com.cn
[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 ∨h3 leftrotate 32∨h4]； 2.4 客户端（云端）算法
从服务器获取计算任务和512位数据块[c]；
分解[c]成为16个32位的字[wj]，记为[W=wj|0≤j≤15]； 公式1向服务器汇报运算结果：[a，b，c，d，e]；
龙源期刊网 http://www.qikan.com.cn
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）.
