Hash论文

Hash论文（通用8篇）

Hash论文 篇1

摘要：Hash函数也称散列函数,它是一种单向密码体制,可以将任意长度的输入信息经过变换后得到固定长度的输出。在数据完整性认证、数字签名等领域有广泛的应用,论文介绍了Hash函数的基本概念、特性及一般结构,对常用的Hash函数进行了对比分析,并对Hash函数的应用领域详细进行了研究,对以后的研究工作有一定的作用。

关键词：杂凑函数,加密解密,数字签名,消息认证

Ha sh函数也称杂凑函数或散列函数,通常用来构造数据的短“指纹”。即对任意长度的输入消息M,经过N次变换后,得到固定长度的输出。Ha sh函数是一种单向密码体制,它是一个从明文到密文的不可逆映射,只有加密过程,不能解密。Ha sh函数的这种单向性特征和输出数据的长度固定的特性使得它可以生成消息或其它数据块的“指纹”,在消息完整性认证、数字签名等领域有着广泛的应用[1]。

1 HASH函数概念及安全性要求

1.1 Ha sh函数概念[2]

一个Ha sh函数是满足以下要求的四元组(X,Y,K,H):

1)X代表所有消息的集合;

2)Y是所有消息指纹的集合;

3)K代表所有密钥的有限集;

4)H代表加密Ha sh函数;

1.2 HASH函数的安全性要求[3]

1)有数据压缩功能:能将任意长度的输入数据转换成一个固定长度的输出;

2)具有单向性:由H(M)计算消息指纹很容易,反之则不能,即对给定的一个散列值,不可能找出一条消息M'的散列值正好相等。

3)抗碰撞性:所谓碰撞性是指两个不同的消息M和M',如果它们的散列值相同,即H(M)=H(M'),则发生碰撞。如果M≠M',则有H(M)≠H(M'),即使M和M'差别非常小,甚至只有一个比特的差别,它们的散列值也会有很大的不同(强抗碰撞性);给定消息M和其散列值H(M),要找到另一个与M不同的消息M',使得H(M)=H(M')是不可能的(弱抗碰撞性)。

2 HASH函数的一般结构

安全Ha sh函数一般结构如下图所示,这是一种迭代结构Ha sh函数,对于输入的报文M,首先将其分为N个固定长度的分组,如果最后一个数据块不满足输入分组的长度要求,可以进行填充[4]。

3 安全HASH函数比较

安全Ha sh算法(SHA)由美国国家标准技术研究所NIST开发,作为联邦信息处理标准于1993年发表,1995年修订为SHA-1。SHA-1基于MD4算法,并且在设计方面很大程度上是模仿MD4的。后来还新增了SHA-256、SHA-384和SHA-512三个散列算法标准,它们的消息摘要长度分别为256、384和512,以便与AES的使用相匹配,现在最新的是SHA-3,以下是各种SHA的比较[5]:

4 HASH函数的应用

4.1 消息认证

消息认证的目的主要有两个:一个是验证信息的来源真实性,即信息来源认证;另一个是验证信息的完整性,即验证信息在公共信道传送或存储过程是否被篡改、重放或延迟等。可以用作认证的函数有消息加密函数、消息认证码(MAC)和散列函数三种,而散列函数是一个不需要密钥的公开函数,它将任意长度的输入消息映射成一个固定长度的输出值,度以此值作为认证标识[6]。

Ha sh函数可以将任意长度的输入消息M经过若干次变换,成为固定长度的输出,得到文档的散列值输出,即“消息指纹”可与放在安全地方的原有“指纹”进行比对,如果消息被修改,那么这个两个指纹就不会相等,从而表明此消息被篡改过。这就是保证了数据的完整性,实现消息认证。

4.2 数字签名

数字签名是一种给以电子形式存储的消息签名方法。并以某种形式将签名“绑”到所签文件上,与传统的手写签名具有同等的效果,并能通过一个公开的验证算法对它进行确认。

由于公钥密码学和对称密码学在加密和解密速度上的区别,在数字签名中往往先使用杂凑函数对消息M实施“压缩”运算,接着对消息M的杂凑值实施签名,这样既起到了保密作用,又提高了加密速度。对于在数字签名中使用的杂凑函数,要求它们具有更强的安全性能[7]。一个使用杂凑函数H(M)的数字签名方案中的合法用户Alice不能找到一对不同的消息(M,M')满足H(M)=H(M'),如果Alice能找到这样的消息,那她就可以签署消息M',后来却宣布她签名的消息是M'而不是M。如果找到这样的消息对在计算上是不可行的,那么我们就称它是抗碰撞(Collision Resistant)的或是碰撞自由(Collision Free)的。

4.3 其他应用

杂凑函数在现代密码学中具有非常广泛的用途,比如用于安全存储口令方面。基于Ha sh函数生成口令的散列值,比如在操作系统中保存用户的ID和他的口令散列值,而不是口令本身,这有助于提高系统的安全性。当用户进入系统时要求输入口令,这时系统重新计算用户输入口令的散列值并与系统中保存的数值相比较,当等时进入系统,否则将被系统拒绝[8]。

Ha sh函数在入侵检测和病毒扫描方面也有很好的应用,比如可以为系统中每个文件进行哈希函数运算得到安全的Ha sh值,如果某个文件被非法修改就可以及时发现。

5 结论

单向散列函数可选的方案比较多,一般有SHA、MD5和基于分组密码的构造,而其他方案实在没有得到足够的重视和研究,目前比较流行的还是SHA,它的散列值比其他的要长,比各种分组密码构造更快[9],并且由NSA研制,虽然山东大的王小云团队已在破解SHA-1上有很大的突破,但要投入实用还有很长的路要走,并且随着SHA-384、SHA-512及SHA-3的出现,我们坚信SHA在密码学上的应用还是有很大的前途。

参考文献

[1]Stinson D R.密码学原理与实践[M].冯登国,译.3版.北京:电子工业出版社,2009:130-180.

[2]Wenbo Mao.现代密码学理论与实践[M].王继林,伍前红,译.北京:电子工业出版社,2006:305-330.

[3]William Stallings.密码编码学与网络安全——原理与实践[M].孟庆树,王丽娜,傅建明,译.4版.北京:电子工业出版社,2006:229-249.

[4]Bruce Schneier.应用密码学协议、算法与C语言源程序[M].吴世忠,祝世雄,张文政.2版.北京:机械工业出版社,2010:307-329.

[5]Forouzan B A.Cryptography and Network Security[M].北京:清华大学出版社,2009:200-280.

[6]胡向东,魏琴芳,胡蓉.应用密码学[M].2版.北京:电子工业出版社,2011:166-200.

[7]Forouzan B A.Cryptography and Network Security[M].Bei-jing:Tsinghua university press,2009:363-385.

[8]William Stallings.Cryptography and Network Security[M].Beijing:Electronic industry press,2011:327-393.

[9]张月,李海青.浅析加密技术在保密通信中的应用[J].电脑知识与技术,2015(21):230-235.

Hash论文 篇2

VIEW CODE

#include#include#include#include#include#include#include#include#include

字符串hash ： 直接2分了 很好写的

VIEW CODE

Hash论文 篇3

射频识别是一种利用射频信号自动识别目标对象并获取相关信息的技术,它的应用领域日益扩大,目前已在制造、零售、物流等领域显示出强大的实用价值和发展潜力,并将成为未来信息社会建设的一项基础技术,被评为本世纪十大重要技术之一。

如何在RFID标签各种资源非常有限的情况下,设计安全、高效的通信协议,是RFID系统应用中一个非常具有挑战性的问题。本文提出一种改进的Hash链协议,用于RFID系统中标签和读写器之间双向认证和进行保密通信的协议,并对它的安全性进行了分析。

1 态势评估介绍

到目前为止,已有许多RFID认证协议被提出。多数安全认证协议都是基于密码机制的,而且采用的是Hash函数。基于Hash链的改进协议也是基于此函数,并且是基于关于RFID系统信道的基本假设来进行。此外,我们假定这些协议所使用的基本密码构造,如伪随机生成函数、加密体制、签名算法、MAC机制以及杂凑函数,都是安全的。本文中H、G表示两个不同的抗碰撞的安全杂凑函数。

本质上,Hash链协议也是基于共享秘密的询问-应答协议。但是,在Hash链协议中,当使用两个不同杂凑函数的读写器发起认证时,Tag总是发送不同的应答,其协议流程如图1所示。值得提出的是,Hash链协议被声称具有完美的前向安全性。由于G是单向函数,因此攻击者能够获得标签输出at,j,但是不能从at,j中获得st,j。

在系统运行之前,Tag和后端数据库首先要预共享一个初始秘密值st,1,则Tag和读写器之间执行第j次Hash链的过程如下:

(1)读写器向Tag发送Query认证请求;

(2)Tag使用当前的秘密值st,j计算at,j=G(st,j),并更新其秘密值为st,j+1=H(st,j)。Tag将at,j发送给读写器;

(3)读写器将at,j转发给后端数据库;

(4)后端数据库系统针对所有的Tag数据项查找并计算是否存在某个IDt(1≤t≤n)以及是否存在某个j(1≤j≤m,其中m为系统预设置的最大链长度)使得at,j=G(Hj-1(st,1))成立。如果有,则认证通过,并将IDt发送给Tag;否则,认证失败。

实质上,在Hash链协议中,Tag成为了一个具有自主ID更新能力的主动式Tag,同时,由上述流程可以看出,Hash链协议是一个单向认证协议,即它只能对Tag身份进行认证。不难看出,Hash链协议非常容易受到重传和假冒攻击,只要攻击者截获某个at,j,它就可以进行重传攻击,伪装Tag通过认证。此外,每一次Tag认证发生时,后端数据库都要对每一个Tag进行j次杂凑运算,因此其计算载荷也很大。同时,该协议需要两个不同的杂凑函数,也增加了Tag的成本。

2 改进Hash-Chain协议的设计

为了避免Has-Lock协议中没有ID动态刷新机制,且ID是以明文的形式通过不安全信道传送,同时为了克服Hash-Chain协议是一个单向认证协议,针对后端数据库搜索时候的效率问题,本文提出了一种基于Hash-Chain的改进RFID认证协议。改进的协议在后端数据库中增加了一个访问计数器k,提高了后端数据库搜索数据的效率,这对于多标签的RFID系统具有十分重要的意义。

2.1 协议的初始条件和相关说明

基于Hash-Chain的改进的协议中,需要后端数据库DB、读写器R、标签Ti(1≤i≤n,n为数据库中标签的最大数)。其中后端数据库是授权的惟一可以追踪标签的实体。R是没有密码保护功能的不可信装置,Ti是可读写的标签。每一个标签Ti在出厂时存储一个随机设置的初始化标识符si,1,同时这个标识符si,1也记录在后端数据库DB中对应的每个标签中,标签采用EEPROM存储,写标识信息并写入两个Hash函数G和H(标准化以后可以固化到标签ROM)。后端数据库DB存储标签身份序列号IDi、访问计数器k,以及所有标签的随机设置的初始化标识符si,k(1≤i≤n),组成序列对(IDi,k,si,k)以及Hash函数G和H,还有一个随机数发生器。

2.2 协议认证过程

在系统运行之前,后端数据库和标签共享一个标签出厂时随机设置的初始化标识符si,1(1≤i≤n,n为最大的标签数),读写器第k次访问标签的通信如图2。

(1)RFID读写器产生一个随机数NR,并向标签发送NR和Query认证请求;此时可能会发生三种情况:(1)没有标签响应;(2)一个标签响应;(3)多个标签同时响应。当发生多个标签冲突的时候,会执行一次冲突仲裁(collision arbitration)过程,如二进制搜索算法,这一过程完毕后会从中选取一个标签与阅读器进行信息交互;

(2)标签计算ri,k=G(si,k)⊕NR后,更新其标识符为si,k+1=H(si,k)和访问计数器为k=k+1,并将ri,k和k发送给读写器;

(3)读写器将ri,k和k转发给后端数据库;

(4)后端数据库检索访问计数器k找到与之相同的序列对,对每个序列的si,1计算rj,k=G(Hk-1(si,1)),检查rj,k与ri,k是否相等。若相等,则说明标签通过认证,更新k=k+1,si,k+1=Hk-1(si,1),并将(NR,H(IDj⊕NR))发给读写器;若不相等,则发送认证失败的消息给读写器,不进行更新;

(5)若标签通过认证,读写器将(R,H(IDj⊕NR))转发给标签;

(6)标签收到消息5后,验证H(IDj⊕NR)=H(ID⊕NR)是否相同,若相同,则阅读器认证通过。

3 安全性分析与形式化证明

3.1 安全性分析

前节中RFID协议的安全需求已经介绍了RFID面临的主要攻击,并结合RFID系统的通信模型,对改进的协议进行安全性分析。

(1)重传攻击:读写器通过前向信道向标签发送Query和NR之后,攻击者获取标签的响应:ir,k=G(si,k⊕NR),k;在以后的认证过程中,攻击者通过后向信道响应ir,k=G(is,k⊕NR),k,从而对后端数据库发起重传攻击;

通过前一次对“标签”(实为攻击者)的认证和该协议中标签每次更新si,k+1=H(is,k),ir,k=G(is,k⊕NR),攻击者无法伪造ir,k=G(is,k⊕NR),因为读写器每次产生的随机数都是不同的,所以该协议对重传攻击具有安全性。

(2)假冒攻击:攻击者伪装成合法的阅读器通过前向信道R->T向标签发送Query和NR;攻击者获取标签的响应:ir,k=G(is,k⊕NR),k,在下一次认证过程中,当真正合法的阅读器发送Query和N'R的时候,攻击者通过后向信道T->R响应刚才所得的信息ir,k=G(is,k⊕NR),k。

但是由于阅读器在每一次认证会话过程中都会产生一个新的伪随机数,即NR≠NR,所以攻击者就无法假冒合法标签进行假冒攻击。所以该协议对假冒攻击具有安全性。

(3)前向安全性:由于G是单向函数,攻击者能够获得标签输出ir,k,但是不能从ir,k中获得si,k。因此改进的协议具有良好的前向安全性。

(4)追踪:由于标签在每次询问后ir,k都将更新,并且同一标签在不同认证过程中,标签回应得ir,k的值也不相同,攻击者也无法确定此次通信的标签与下次通信的标签是否为同一标签,从而无法对标签进行有效跟踪。

(5)窃听:即使攻击者可以窃听到读写器与标签之间通信的消息数据,由于重要的数据都使用了单向函数G或者H进行处理,所以攻击者无法获得任何有用信息,即协议能够较好地防御攻击者的窃听。

本文协议及以上安全性分析都是基于密钥ID绝对保密的假设而给出的,不管在任何时候都要注意对密钥的严格保护。本文的方案属于静态ID的RFID认证协议,近年来同类的研究有Sarmar,Weis,Rhee等文献。

3.2 形式化证明

RFID认证协议的目的是使读写器和标签能够互相证实双方的身份。本文中改进的协议属于无可信第三方参与的认证协议,我们采用经典的安全协议分析方法BAN逻辑完成其形式化的分析和证明。

为了适应形式化分析的需要,在此协议中,我们将整个协议的执行过程可缩减为三条通信消息,如图3所示。

三条通信消息如下:

(1)R一>T:NR(NR即为读写器产生的随机数)

(2)T一>R:NR,G(si,k⊕NR)

遵循BAN逻辑证明的过程,首先需要理想化协议,然后初始状态及假设,最后写出协议目标,其证明过程如下:

(1)理想化协议

M1 R一>T:NR

M2 T 一>R：RN ，

M3 R 一>T：

(2)初始状态及假设

A1 bel (R，secret (R，NR、T))

A2 bel (T，secret (T，IDj，R))

(3)协议目标

G1：bel(R，said (T，NR))

G2：bel(T，said (R，IDj))

(4)逻辑推理

由M2得,

由A2与○1得,

由M2得,

由A2与(3)得,

(4)see(R,(is,k,NR))

由(2)与(4)得,

(5)bel(R,said(T,(is,k,NR)))

由(5)得,

即证明了协议满足目标G1。

由M3得,

由A3与(7)得,

由M1得,

由A3与(9)得,

由(8)与(10)得,

由得,

即证明了协议满足目标G2。以上BAN逻辑分析过程证明了协议可以实现阅读器R和标签T之间的双向认证。

4 结论

本文通过分析现有协议的优点和在安全性及效率上的不足,提出基于Hash链的RFID改进协议低成本RFID双向认证协议。通过BAN逻辑的证明显示,基于所采用的Hash函数是安全的假设下,新协议可以达到阅读器和标签之间双向认证的安全目标;同时,针对各种常见攻击场景的分析表明,协议可以抵抗假冒攻击、重传攻击等常见针对RFID认证协议的攻击;此外,降低了标签运算能力的要求,使得新协议可适合于一些价格低廉RFID系统的应用需求。

摘要：由于RFID技术的特殊性和局限性带来了很多安全问题,针对这些安全问题,本文提出了一种Hash链的改进认证协议,以解决假冒攻击、重传攻击、跟踪、前向安全性等安全问题,并基于BAN逻辑给出了形式化的分析,说明改进的协议在BAN逻辑分析下是安全的。由于在RFID标签中仅使用了Hash函数,因此改进的协议更适合于低成本的RFID系统。

关键词：认证协议,Hash链,形式化分析,BAN逻辑

参考文献

[1]Ohkubo M.,Suzuki K.,Kinoshita S..Hash-chain based for ward-secure privacy protection scheme for low-cost RFID.In:Proceedings of the2004Symposium on Cryptography and Information Security(SCIS2004),Sendai.2004.

[2]丁振华,李锦涛,冯波.基于Hash函数的RFID安全认证协议研究[J].计算机研究与发展.2009.

[3]李振汕.RFID系统安全问题研究[J].网络安全技术与应用.2011.

[4]Ohkubo M,Suzuki K,Kinoshita S.Cryptographic approach to“Privacy-Friendly”tags[OL].[2007-10-07]http://ww.rfidprivacy.us//2003//papers//ohkubo.Pdf.

[5]周永彬,冯登国.RFID安全协议的设计与分析[J].计算机学报.2006.

[6]Rhee K,Kwak J,Kim S,et al.Challenge-response based RFID authentication protocol for distributed database environment[C]//Proc of the2nd Int Conf on Security in Pervasive Computing.Berlin:Springer,2005.

Hash论文 篇4

关键词：认证协议,Hash链,Verilog HDL

0 引言

无线射频识别(Radio Frequency Identification, RFID)是一种无接触的数据采集和自动识别技术,由标签技术和识别装置技术组成,利用它可以在远距离、恶劣环境下对集群目标和移动目标进行快速信息采集和自动识别。

本文提出了一个基于Hash函数的RFID改进认证协议,然后采用Verilog HDL硬件编程语言,对标签和读写器之间的无线传输信道中的信号流进行仿真,此仿真对一个FPGA目标设备的硬件实现而言,可以得到一个快速的实现原型。

1 基于Hash函数的RFID改进认证协议

近年来,已经提出了许多RFID认证方案,这些方案所采用的安全机制主要有物理机制和密码机制。由于物理机制需要额外的物理设备或增加了RFID系统的成本,所以在最新的RFID安全方案中,多数采用密码机制。但是,标签资源有限,使得现有的许多成熟的安全认证协议不适合RFID系统。由于Hash函数具有快速、低耗的特点,所以基于Hash函数的RFID认证协议的设计近年来备受关注。本文中H、G表示来表示两个不同的抗碰撞的安全杂凑函数。

1.1 Hash链(Hash-Chain)[1]协议的介绍

在Hash链协议中,若采用两个不同杂凑函数的读写器向Tag发起认证时,Tag 总是给予不同的应答;另外,Hash链协议具有完美的前向安全性(由于G是单向函数,因此攻击者能够获得标签输出at,j,但是不能从at,j中获得st,j),其协议流程认证过程如图 1 所示。

在RFID系统运行之前,Tag和DB首先要共享一个初始秘密值 st,1,那么Tag和Reader之间第j次H认证过程如下:

(1)Reader向Tag发送Query认证请求。

(2)Tag使用当前的秘密值st,j计算at,j=G(st,j),并更新其秘密值为st,j+1=H(st,j)。Tag将at,j发送给Reader。

(3)Reader将at,j转发给DB。

(4)后端数据库系统针对所有的 Tag 数据项查找并计算是否存在某个 IDt(1≤t≤n)以及是否存在某个j(1≤j≤m,其中m为系统预设置的最大链长度) 使得at,j=G( Hj-1(st,1))成立。如果有,则认证通过,并将IDt发送给Tag;否则,认证失败。

从上述协议执行过程中可看出,第一,Hash链协议是一个单向认证协议,即只对Tag身份进行认证;第二,此时Tag是一个具有自主更新ID的主动式Tag;第三,只要攻击者截获某个at,j,它就可以进行重传攻击,伪装Tag通过认证;第四,当Tag发起认证时,后端数据库都要对每一个Tag进行j次杂凑运算,后端数据库计算载荷也很大。

1.2 基于Hash函数的RFID认证协议的设计

针对Hash-Chain协议是一个单向认证协议及其搜索效率低的问题,本文提出基于Hash函数的RFID改进认证协议。在改进协议中,后端数据库中增加了一个访问计数器k,为了提高其搜索数据的效率,这对于多个标签的RFID系统具有十分重要的意义。

(1)协议的初始条件和相关说明

在改进的认证协议中,DB(后端数据库)是授权的唯一可以追踪标签的实体,存储标签唯一的标识符IDi、访问计数器k及所有标签的初始化标识符si,k(1≤i≤n),组成序列对(IDi,k,si,k)和Hash函数G和H,还有一个随机数发生器;R(读写器)是没有密码保护功能的不可信装置;Ti(1≤i≤n,n为数据库中标签的最大数)是可读写的标签。每个Ti在出厂时存储一个随机设置的初始化标识符si,1,它是采用EEPROM存储,写标识信息并写入两个Hash函数G和H(标准化以后可以固化到标签ROM)。

(2) 协议认证过程

在RFID系统运行之前, DB和Ti共享一个标签出厂时随机设置的si,1R第k次访问标签的认证过程如图2所示。

Step 1:R产生一个随机数NR,并向T发送NR和Query认证请求;此时可能会发生三种情况:①没有标签响应;②一个标签响应;③多个标签同时响应。当发生多个标签冲突的时候,会执行一次冲突仲裁(collision arbitration)过程,如二进制搜索算法,执行完此算法后会从中选取一个T与R进行信息交互。

Step 2:T计算ri,k=G(si,k)⊕NR后,然后更新标识符为si,k+1=H(si,k)和访问计数器为k=k+1, 并将ri,k和k发送给R。

Step 3:R将ri,k和k转发给DB。

Step 4:DB通过检索计数器k找到与之相同的序列对,对每个序列的si,1计算rj,k=G(Hk-1(si,1)),检查rj,k与ri,k是否相等。若相等,则说明标签通过认证,更新k=k+1,si,k+1=Hk-1(si,1),并将(NR,H(IDj⊕NR))发给R;若不相等,则发送认证失败的消息给R,不进行更新。

Step 5:若T通过认证,R将(R,H(IDj⊕NR))转发给T。

Step 6:T收到消息5后,验证H(IDj⊕NR)=H(ID⊕NR)是否相同,若相同,则R通过认证。

(3)安全性分析

针对RFID协议面临的主要攻击[2,3],对改进协议进行安全性分析如下。

①重传攻击:

读写器向标签发送 Query和NR之后,攻击者获取标签的响应:ri,k=G(si,k⊕NR),k;在以后的认证过程中,攻击者响应ri,k=G(si,k⊕NR),k,从而对后端数据库发起重传攻击;

通过前一次对“标签”(实为攻击者)的认证和该协议中标签每次更新si,k+1=H(si,k),ri,k=G(si,k⊕NR),攻击者无法伪造ri,k=G(si,k⊕NR),因为读写器每次产生的随机数都是不同的,所以该协议对重传攻击具有安全性。

②假冒攻击:

攻击者伪装成合法的阅读器通过前向信道R→T向标签发送Query和NR;攻击者获取标签的响应:ri,k=G(si,k⊕NR),k,在下一次认证过程中,当真正合法的阅读器发送Query和N′R的时候,攻击者响应刚才所得的信息ri,k=G(si,k⊕NR),k。

但是由于阅读器在每一次认证会话过程中都会产生一个新的伪随机数,即NR≠N′R,所以攻击者就无法假冒合法标签进行假冒攻击。所以该协议对假冒攻击具有安全性。

③前向安全性:

由于G是单向函数,攻击者能够获得标签输出ri,k,但是不能从ri,k中获得si,k。因此改进的协议具有良好的前向安全性。

④追踪:

由于标签在每次询问后ri,k都将更新,并且同一标签在不同认证过程中,标签回应得ri,k的值也不相同,攻击者也无法确定此次通信的标签与下次通信的标签是否为同一标签,从而无法对标签进行有效跟踪。

⑤窃听:

即使攻击者可以窃听到读写器与标签之间通信的消息数据,由于重要的数据都使用了单向函数G或者H进行处理,所以攻击者无法获得任何有用信息,即协议能够较好地防御攻击者的窃听。

改进的协议和以上的安全性分析的前提是密钥ID绝对保密,不管在任何时候都要注意对密钥的严格保护。改进的协议属于静态ID的RFID认证协议,近年来同类的研究有Sarmar[4],Weis[5],Rhee[6]等文献。

2 协议仿真

在Actel Libero IDE version 8.5环境中,采用Verilog HDL语言[7]对无线传输信道中的信号流进行仿真,利用测试文件testbench对标签进行激励。仿真中采用的Hash函数采用CRC16循环校验码[8]来实现的。

2.1 消息的帧格式和规则

图3是提出新协议的消息交换过程。

在仿真中,伪随机数NR设定为8bit,标签的ID即密钥设定为16 bit, 帧头和帧尾都定义为十六进制的0xaa,即二进制为10101010,如图4所示。

2.2 模块设计

本文的仿真由接收模块、发送模块、状态机和存储器ROM组成,另外,还有CRC及LFSR(线性移位寄存器)。如图5所示标志了模块间的连接及数据信号的流向。

2.3 通用异步收发器

UART(Universal Asynchronous Receiver Transmitter)是各种设备之间进行相互通信的关键模块,通常采用数字信号进行通信。文中,规定每个消息的帧格式为64 bit(如图4所示),但发送端每次只发送8 bit,为此每发送一次8 bit信号需要进行一次并——串转换,每个消息共需要进行8次转换;在接收端需要处理64 bit的信号时,必须要把8 bit串行信号转换为一组8位的并行信号,待到8组并行信号全部转换完毕后输出64 bit数据,所以该仿真需要UART进行并——串和串——并转换。

UART是由发送模块、接收模块、顶层模块组成,下面分别介绍各个模块。

(1)发送模块

发送模块是把并行数据转换成串行数据并行,然后串行输出,如图6-7所示。

(2)接收模块

接收模块是把接收到的串行数据转换成并行数据后输出,收到的数据串后判断其是否有错,如图8-9所示。

(3)顶层模块

顶层模块是把发送模块和接收模块的对应端口连接在一起,并给UART设定输入输出引脚,如图10-11所示。

2.4 仿真

仿真中,data代表伪随机数NR为8 bit,在某一刻,使能信号able_en为1时,此时系统产生的伪随机数有效;标签标识符ID(密钥),存储在存储器中,为16 bit,设定为0x1010,u_din表示每个消息的输入,为64 bit;data_out表示每个消息的输出,为64 bit;data_change表示攻击测试信号通道,为64 bit, control_e为1时,表示通信过程中报错;control_a为1时,表示标签成功验证读写器,此时本次认证结束。

(1)协议的合法认证过程

在协议的合法验证中,查看state、u_din以及data_out的值的变化,验证过程如图12-17所示。

通过分析协议的合法验证,标签收到消息1:aa01ff00000000aa,然后将收到的消息与存储器中的消息对比后,得知符合其帧格式,表明该读写器不是假冒的读写器;当state为101时,标签收到消息3:aa03ff6f939800aa,然后通过存储器中的NR和ID计算CRC值,经验证该值与接收到的消息3的值相等,表明攻击者对消息3没有进行篡改。

(2)模拟攻击的认证过程

图18是模拟假冒读写器向标签发起询问请求的行为。此模拟攻击认证过程中的验证过程1与合法认证中的验证过程1相同,如图11所示,不在此赘述。

图18的验证过程表明,当state为010时,标签收到的消息1为bb01ff00000000bb,验证其帧头和帧尾不符合规定的消息1的帧格式,此过程模拟了读写器的假冒攻击。对于重传和跟踪攻击,由于仿真中每次NR在变化,所以攻击者无法通过此类方法对系统进行攻击。另外,由于Hash函数的单向性,攻击者不可能篡改消息3的内容。

3 结束语

本文通过分析现有的Hash链协议的安全隐患和其效率上的不足,提出了基于Hash函数的RFID改进认证协议;针对RFID认证协议的常见攻击类型,改进的协议可以抵抗假冒攻击、重传攻击等常见攻击;采用Verilog HDL硬件编程语言,对标签和读写器之间的信号流进行了仿真,此仿真对于FPGA目标设备的硬件实现,可以得到一个快速的原型。

参考文献

[1]Ohkubo M,Suzuki K,Kinoshita S.Hash-chain based for ward-se-cure privacy protection scheme for low-cost RFID[C]//Proceedingsof the 2004 Symposium on Cryptography and Information Security(SCIS 2004),Sendai,2004:719-724.

[2]丁振华,李锦涛,冯波.基于Hash函数的RFID安全认证协议研究[J].计算机研究与发展,2009,46(4):583-592.

[3]李振汕.RFID系统安全问题研究[J].网络安全技术与应用,2011(4):61-63.

[4]Ohkubo M,Suzuki K,Kinoshita S.Cryptographic approach to“Pri-vacy-Friendly”tags[EB/OL].[2007-10-07].http://www.rfidprivacy.us//2003//papers//ohkubo.pdf.

[5]周永彬,冯登国.RFID安全协议的设计与分析[J].计算机学报,2006,29(4):581-589.

[6]Rhee K,Kwak J,Kim S,et al.Challenge-response based RFID au-thentication protocol for distributed database environment[C]//Proc of the 2nd Int Conf on Security in Pervasive Computing.Ber-lin:Springer,2005:70-84.

[7]王伟.Verilog HDL程序设计与应用[M].北京:北京人民出版社,2005.

Hash论文 篇5

射频识别技术RFID (Radio Frequency Identification) 是一种利用射频通信实现的非接触式双向通信技术, 以达到自动识别目标对象并获取相关数据的目的, 具有精度高、适应环境能力强、抗干扰性强、操作快捷、非可视识别等多方面优点。因此, RFID系统已被越来越多地应用于零售、物流、仓储、自动收费、图书管理、军事等领域[1]。

然而, 随着RFID技术的广泛应用, 所引起的安全和隐私问题也日益突出。RFID系统的安全问题逐渐成为国内外学者的研究热点。当前RFID系统的安全机制主要有物理安全机制和认证安全机制两大类。但由于物理安全机制受到成本和法律等因素的限制, 使得认证安全机制, 特别是基于Hash函数的认证安全机制越来越受到人们的青睐, 其主要研究内容则是利用Hash函数的单向性这一特点来设计和实现符合RFID安全需求的认证协议。因此, 设计安全、高效、低成本的基于Hash函数的RFID认证协议成为了一个新的具有挑战性的问题。

1 RFID 系统的组成及安全需求

1.1 RFID 系统的组成

RFID系统一般由标签 (Tag) 、读写器 (Reader) 以及后端数据库 (Database) 三大部分组成。Tag是RFID系统中数据的载体, 由IC芯片和天线构成, 存储着被识别物体的相关信息。Reader可利用射频技术对Tag中的信息进行读写, 并能够将读取的信息传送到DB。DB则具有强大的数据分析和存储能力。其中Tag和Reader之间是进行无线射频通信, 而Reader与DB之间则是有线通信。一般而言, 我们通常做如下基本假设:Tag与Reader之间的通信信道是不安全的[2];而Reader与DB之间的通信信道是安全的。RFID系统的基本组成如图1所示。

1.2 RFID 系统的安全需求

RFID的安全风险主要来自于“系统开放”的设计思想。此外, RFID设计和应用的目的就是了为降低成本, 提高效率。所以要求被大规模使用的Tag具有低廉的价格和简单的元件, 从而不能实现复杂的密码算法。这些局限对RFID系统的安全机制的设计带来了特殊的要求。

一般来说, 一个安全的RFID系统应该解决3个基本的安全问题:保密性、信息泄露和可追踪性[2]。具体说来需要满足以下几个方面的安全需求:

1.2.1 前向安全性

指攻击者不能通过联系当前数据和历史数据对Tag进行分析获得Tag中的隐私信息。

1.2.2 不可分辨性

指攻击者即使获得了来自于不同Tag的输出, 也无法区分出是那一张Tag的输出;另一方面是即使攻击者获得了来自于同一张Tag的多次输出, 同样无法区分该Tag的输出。

1.2.3 访问控制

指避免攻击者伪装成合法的Reader进行未授权的扫描;同时保证合法的Reader能够顺利读写Tag中的信息。

1.2.4 抗通信量分析指攻击者即使获得了大量的通信数据样本 也无法从中分析获得一定的规律性, 从而破解通信协议。

1.2.5 抗重放攻击

指攻击者无法通过重放截取的信息而骗取Reader, 来达到通过认证的目的。

2 基于 Hash 函数的 RFID 认证协议分析

为解决RFID系统的安全问题, 国内外学者作了大量的研究, 提出了许多认证方案。下面将详细分析几种典型的基于Hash函数的RFID认证协议。

2.1 Hash-Lock 协议

Hash-Lock协议[34]是由Sarma等人于2003年提出的一个RFID认证协议。为了避免信息泄露和被追踪, 在该协议中, 每个Tag都有自己独立的访问密钥key, 并使用metaID来代替真实的TagID, 其中metalID=H (key) 。DB存储了每一个Tag的key、metalID以及ID。其协议的认证流程如图2所示。

该协议利用Hash函数的单向性这一特点, 使用metalID来代替真实的TagID, 能够在一定程度上解决访问控制和隐私保护的问题。但是由于metalID一旦生成, 在以后的所有认证过程中也就会保持不变。因此, 攻击者极有可能利用截获的metalID对Tag进行位置追踪、重放攻击和假冒攻击。所以, Hash-Lock协议存在着严重的漏洞, 完全没有满足安全需求。

2.2 随机化 Hash-Lock 协议

随机化Hash-Lock协议[5]是由Weis等提出的一种Hash-Lock协议的改进形式。Tag中除了采用了Hash函数外, 还嵌入了伪随机数发生器, 协议作者设想对于Reader发出的不同询问, 以Tag的ID值串连上随机数值后再进行Hash运算予以应答。其协议的认证流程如图3所示。

在该协议中, 尽管提出了添加伪随机数以保证数据在每次传输过程中都不一致的想法。但该协议的缺陷在于, 一是由于伪随机数发生器是集成在Tag内部, 导致了运算能力有限的低成本Tag实现该方案的困难。二是在协议的第5步, Tag经Reader认证通过后, Reader将Tag标识ID以明文的方式通过前向信道传送, 因此攻击者一旦截获了Tag标识ID, 就可以对Tag进行有效的追踪, 同时, 也可以用截获的ID假冒成合法的Tag。三是在认证过程的第4步, DB都需要将系统内所有Tag的标识ID全部发送给Reader, 在拥有大量Tag的系统中, 会产生巨大的通信量并有可能造成系统的延时。因此, 该协议在安全性和适用性上也完全没有达到预期的目标。

2.3 Hash 链协议

Hash链[6]协议是NTT实验室的Ohkubo等于2004年提出的一个基于共享秘密的询问-应答的协议。在该协议中, Tag集成了H和G两个不同的Hash函数, 并与DB拥有共同的初始秘密值st, 1。同时, DB还存储了所有Tag的标识和共享秘密数据对 (IDt, st, 1) 。作者认为该协议在前向安全性上是无懈可击的。其协议的认证流程如图4所示。

在该协议中, Tag具有自主更新能力, 具有了不可分辨性和前向安全性, 从而可以在一定程度上有效地防止因固定输出而引起的跟踪、假冒和重放攻击。然而, 从整个协议的认证过程来看, 该协议是一个单向认证协议, 只能实现Reader对Tag的认证而不能使Tag认证Reader的合法身份。同时, 攻击者一旦截获了at, j=G (st, j) , 就能进行假冒和重传攻击, 伪装成合法Tag通过认证。在适用性方面, 为了实现协议, Tag中集成了两个Hash函数, 也相应增加了Tag的成本。

3 基于 Hash 链的 RFID 双向认证协议的设计

针对以上几种安全协议存在的各种安全隐患, 效率低下等问题。本文在研究国内外学者提出的各种协议的基础上, 提出了一种基于随机数和Hash链的RFID双向认证协议, 实现了Reader和Tag身份的双向认证, 并具有前向安全性、抗重传、假冒、窃听和位置跟踪等优点。

3.1 协议描述

在系统运行之前, 为Database分配一个初始秘密值st, 0, Tag要存储一个初始秘密值s t, 1=H (st, 0) , 同时DB还存放Tag的身份IDi和经Hash运算计算后的秘密值st, j-1的序列对 (IDi、st, j-1) , 则此协议的双向认证过程如图5所示。

①Reader向Tag发送Query和随机数R;

②Tag使用当前 秘密值st, j计算at, j=G (st, j||R) , Tag将at, j发送给Reader;

③Reader将at, j和R发送给DB;

④DB系统针对所有的Tag数据项查找并计算是否存在某个IDi (1≤i≤n) 以及是否存在某个j ( 1≤j≤m, 其中m为系统预 设置的最 大链长度 ) 使得at, j=G (H (st, j-1) ||R) 成立, 若有, 则DB存储st, j=H (st, j-1) , Tag通过DB的验证; DB计算bt, j=G (H (St, j) ||R||IDi) , 并将bt, j发送给Reader;

⑤Reader将bt, j发送给Tag;

⑥Tag计算b't, j=G (H (st, j) ||R||IDt; 若b't, j=bt, j 成立;则DB通过Tag的验证。Tag更新其秘密值为Sb't, j+1=H (St, j) 。

3.2 性能分析

本协议在原Hash链认证协议的基础上, 增加了随机数以及Tag对Reader验证这一环节。除具有Hash链协议的前向安全性以外, 还具有以下几个特点。

3.2.1 实现了 Tag—Reader 身份的双向认证

在协议的第4步后台数据库通过验证at, j=G (st, j||R) 可对Tag身份进行 认证 ; 在第6步Tag通过b't, j=G (H (st, j) ||R||IDt) 可对Reader身份进行认证。

3.2.2 防窃听

Tag和Reader之间的通信都经过了Hash函数G加密。根据Hash函数的单向性, 攻击者无法根据密文推断出明文。

3.2.3 抗重放攻击

每次认证, 后台数据库和Tag共享的秘密都是变化的。攻击者即 使截取到 随机数R , at, j=G (st, j||R) 或者bt, j=G (H (st, j) ||R||IDi) , 根据Hash函数的抗碰撞性以及R的随机性, 也无法伪装成合法的Tag通过认证。

3.2.4 抗假冒攻击

攻击者即使截获了随机数R和at, j=G (st, j||R) , 并伪装成合法Tag将以上内容发送给Reader, 但由于R和st, j均是变化的, 所以, 攻击者也无法通过Reader认证。

3.2.5 防位置跟踪

由于随机数R和st, j的值在每一次认证过程中都不同, 因此Tag每次给Reader的响应at, j=G (st, j||R) 也是不同的。因此可以抵抗攻击者根据特定的输出而对Tag进行定位。

3.2.6 不可分辨性

对于Tag对Reader的响应at, j=G (st, j||R) 。根据Hash函数的单向性和随机数R的不确定性。攻击者即使获得了多个Tag的输出, 也无法区分出所对应的具体Tag的输出。即G (st, j||R) ≠G (si, j||R) ;攻击者即使获得了同一个Tag的输出 , 也无法区 分出该Tag的具体某 一次输出 。即G (t, j||R) ≠G (st, m||R') 。

4 结束语

本文在分析总结已有的基于Hash函数的RFID认证协议的基础上, 提出了一种新的基于Hash链的RFID双向认证协议。通过对该协议的定性分析, 证明该协议具有前向安全性、抗重放、哄骗、窃听、跟踪等优点。通过BAN逻辑对其进行形式化分析, 结果表明该协议完全能够满足安全需求。弥补了当前Hash链认证协议的不足。但本方案在一次双向认证过程中, Tag需要进行3次Hash运算, 这与Tag低成本的要求产生了矛盾。还有待于进一步研究。

本文的创新点在于, 提出了一种基于Hash链的RFID双向认证协议。并通过形式化方法证明该协议能够满足系统安全的需求。具有抵抗各种攻击的特点。在下一步研究中, 将对该协议进行具体的仿真和评估, 使其成为完整的RFID系统安全体系。

参考文献

[1]游战清, 李苏剑.无线射频识别技术 (RFID) 理论与应用[M].北京:电子工业出版社.2005:13-17.

[2]周永彬, 冯登国.RFID安全协议的设计与分析.计算机学报, 2006, 29 (4) :581-589.

[3]Sarma S.E., Weis S.A., Engels D.W..RFID systems an security and privacy implications.In:Kaliski B.S., Koc C.K., Paar C.eds..Proceedings of the 4th International Workshop on Cryptographic Hardware and Embedded System (CHES2002) .Lectures Notes in Computer Science 2523.Berlin:Springer-Verlag, 2003, 454-469.

[4]Sarma S.E., Weis S.A., Engels D.W..Radio-frequency identification:Secure risks and challenges.RSA Laboratories Cryptobytes, 2003, 6 (1) :2-9.

[5]Weis S.A., Sarma S.E., Rivest R.L., Engels D.W..Security and privacy aspects of low-cost radio frequency identification systems.In:Hutter D., Müller G., Stephan W., Ullmann M.eds..Proceedings of the 1st International Conference on Security in Pervasive Computing.Lectures Notes in Computer Science2802.Berlin:Springer-Verlag, 2004, 201-212.

[6]Ohkubo M., Suzuki K., Kinoshita S.Hash-chain based forward-secure privacy protection scheme for low-cost RFID.In:Proceedings of the 2004 Symposium on Cryptography and Information Security (SCIS 2004) , Sendai, 2004, 719-724.

Hash论文 篇6

在自然语言处理中，"词是最小的能够独立活动的有意义的语言成分"[1]，而汉语和英语等其它西文比起来, 有着自身的特点。英语、法语等欧美语言在书写时就以词为基本构成单位，以空格作为分词的依据；而汉语在书写时是一大串汉字的字符串，从形式上根本没有词的概念。中文分词指的就是将一个汉字序列切分成一个一个单独的具有实际意义的词，它是中文信息处理的基础。随着信息技术的飞速增长和互联网在中国的迅速普及，Google、百度等搜索引擎已经成为越来越多的人们工作生活的必备工具。中文信息搜索的商业价值和学术地位吸引了越来越多的不同领域的学者们，在中文信息处理这个问题上展开广泛而深入的研究。

分词是中文信息处理的基础一环，分词方法的性能直接影响到中文信息搜索的实时性及准确性。考虑到中文分词算法的应用领域大多对实时性和准确性两方面有很高的要求。因此, 实现较简单的基于Hash算法中的正向最大匹配法仍然是应用最为广泛的一种方法。针对这种算法，有人提出一种改进的最大匹配分词算法, 词典支持首字Hash查找[2]，后来又出现了首字Hash+全词二分查找的词典组织方式和算法, 进一步提高了分词速度[3]。这些算法都是根据汉字机内码的编码规律, 通过一对一映射的Hash函数实现词首字的快速查找。下面就通过对该种方法的分析, 提出一种可以提高分词效率的改进的基于Hash的中文分词方法。

2、正向最大匹配分词算法分析

传统的正向最大匹配分词算法 (Maximum Match-ing, 简称MM算法) 基于的理念是找到最大的匹配词[4], 其算法流程如图1所示。

假设分词词典中的最长词的字数为M, 令其作为最大匹配系数。假设读取的汉字序列字数为L，判断L是否小于最大匹配系数M。如果L大于最大匹配系数M，则截取前M个汉字进行匹配，否则直接在分词词典中进行匹配。若字典中存在这样的一个字数为M的词, 则匹配成功, 匹配字段被作为一个词切分出来；若词典中找不到这样的词, 则匹配失败, 将匹配字段中的最后一个字去掉, 对剩下的汉字序列重新进行匹配处理……如此进行下去, 直到匹配成功, 即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配, 然后取剩下的汉字序列以同样的方法进行匹配处理, 直到文档被扫描完为止。由于最大匹配法每次比较时都有许多重复的匹配操作, 所以效率不高。

3、改进的分词算法

在对分词算法的理解和对最大匹配分词算法分析的基础上, 本文提出了一种改进的基于Hash的最大匹配分词算法。

3.1 词库结构

根据汉语中词条的分布情况统计, 在汉语中双字词语最多而4字以上的词则比较少，如下表所示[3]。

由汉语的词频统计得出结论，在汉语中, 99%的词集中在四字以下的词语，尤其以双字词为数最多。如果能在词典中实现对四字以内的词的快速查找, 那么系统的效率会明显提高。我们利用哈希算法中的多次哈希来满足这种需求, 同时Hash结构在几种词典结构中的查询速度也是理想的。因此本文词典采用Hash存储结构, 以实现词典的快速查找。

算法使用以下数据结构:词库组织结构为首字索引结构, 所有以同一个字为首的词条都组织在一起。词库由两部分组成, 一部分为索引部分, 另一部分为词库正文。索引部分由字、以该字为首的词条的开始位置、以该字为首的词条数目三部分组成。正文部分为词条、词条的一些属性组成, 相同字首的词条按汉字内码值的升序排列。其结构如图2所示:

其中, 如果有以词条为首的词条, 那么词条的属性为以该词条为首的词条的开始位置和结束位置, 否则为0。

3.2 分词算法

分词算法首先由Hash计算的首字的地址, 然后利用二分查找是否有以前两字为首的词条。如果没有则作为单字词输出;否则有以这两个字为首的词, 依次利用二分查找法比较下一个字是否相等, 比较前先判断当前匹配成功的是否组成词, 如果是先输出。具体算法如下:

3.2.1 查找前两个字

3.2.2 分词算法

step 1.将要分词的汉字序列的前两个字word与词库比较，如果是词，转step 3;

step 2.否则作为单字输出，off=1, 转step 7;

step 3.若存在以word为首的词，off=2, 若word为词，matchlength=2，输出word;

step 4.根据状态判断如果存在以word为首的词，取以word为首的词条的开始位置start和结束位置end；否则转step 7;

step 5.查询词库与待分词汉字序列的第off+1字是否相等；如果不相等转step 7;

step 6.若有相等，off=off+1；若前off个字是词，赋给word输出，matchlength=matchlength+1；转step 4；否则转step 5;

step 7.将待分词的汉字序列去掉前matchlength个字，off=0, matchlength=0;

step 8.若汉字序列没有分词结束，转step 1，否则结束。

3.3 算法举例及评估

例如待分词的汉字序列"常用的搜索引擎"。首先取得"常"字的机内码，以Hash函数计算其在首字Hash表中的位置。将汉字序列的前两个字"常用"与词库比较，得出"常用"与词库中的词条匹配，是词，将off值设为2, matchlength值设为2，输出第一个词"常用"。进一步查询词库与待分词汉字序列的第三个字"的"是否相等，结果不匹配，则将该汉字序列去掉前两个字，并且off值和matchlength值均赋值为零，继续对剩余汉字序列进行类似的切分。

根据本算法单字词查找无需匹配，对于多字词采用Hash和二分法查找，根据文献[5]对分词算法的测试方法，新的算法在分词速度上有很大的提高。

4、结语

以上这种基于Hash的中文分词算法属于基本的分词算法，旨在使读者了解中文分词的一般处理过程，对进一步研究中文分词的算法起到积极的推动作用。同时，目前已经推出的分词系统均是以采用传统的分词算法为主, 辅之以能部分反映词法、句法和语义规则的改进算法。理想的分词系统应该是综合词法、句法和语义信息的, 因而把人工智能技术应用于中文分词的研究将是今后研究的一个方向[6]。

摘要：在分析已有的中文分词算法的基础上, 利用改进的词典结构, 提出一种新的基于Hash的中文分词算法。理论和实验证明, 改进的算法可以进一步提高分词的效率。

关键词：中文分词,哈希算法

参考文献

[1]朱德熙, 语法讲义[M], 商务印书馆, 1982

[2]赵曾贻, 一种基于语词的分词方法[J], 苏州大学学报, 2002, 18 (3) 44-48

[3]李振星, 徐泽平, 唐卫清, 全二分最大匹配快速分词算法[J], 计算机工程与应用, 2002, 38 (11) 106-109

[4]刘源, 谭强, 等.信息处理用现代汉语分词规范及自动分词方法[M].北京:清华大学出版社, 1994.

[5]孙茂松, 左正平, 黄昌宁.汉语自动分词词典机制的实验研究[J].中文信息学报, 2000, 14 (1) :1-7.

Hash论文 篇7

关键词：Hash函数,归属地,查询

1 引言

随着互联网应用的深入, 特别是微博、 微信、 朋友圈等社交网络的兴起, 手机使用功能的多元化, 使得人们每天的生活行为产生大量的数据信息, 如何快速地从大量数据中提取价值信息成为当前计算机应用领域的重要课题。 在手机应用中, 来电归属地显示已成为智能手机必备的功能, 其基本做法是将来电号码在已建索引的归属地数据库中进行查询匹配, 返回相应的归属地结果。 但是, 在对来电号码进行大数据量分析时, 需要对成千上万的号码进行电话号码归属地匹配, 反复多次查询数据库, 效率不高, 结合电话号码的结构特点, 设计了自定义Hash函数, 对归属地数据进行缓存, 实现了归属地直接寻址匹配, 大幅提升了号码归属地匹配的性能。

2 方法

现有互联网公开的归属地数据库, 通常包含电话号码、归属地两个字段, 其中手机号码类通常包含条目约30 余万条, 固话类通常包含条目325 条。

2.1 手机号码归属地Hash函数设计

国内手机号码通常由11 位数字组成, 其前7 位为归属地代号, 但由于第1 位均为1 开头 (主要包括18x、 17x、 15x、13x等号段) , 因此手机号码的归属地匹配只涉及到手机号码的第2 至第7 位, 共6 位数字, 最多不超过1000000 种可能情况。 采用大小为1000000 的一维字符串数组Mobile来缓存归属地数据库, 数组下标由手机号码的第2 至第7 位转换为整数得到, 下标对应的数组值表示该号码对应的归属地。 在进行匹配时, 只需取待匹配号码的第2 至第7 位, 以数组下标的形式直接寻址访问mobile数组即可获得对应的归属地, 避免了查询带来的计算开销。

对于字符串类型手机号码x, 其哈希地址计算如下:

2.2 固话号码归属地Hash函数设计

固话号码前的国内区号分为3 位和4 位两种, 在计算时要区分对待, 但最多不超过1000 种可能, 采用大小为1000的一维字符串数组tel来缓存区号归属地, 如图2 所示。

对于字符串类型固话x, 其哈希地址计算如下:

在匹配固定电话归属地时, 因国内固定电话从11 位至13位不等, 无法判断号码应该取几位来匹配归属地。 在处理固定电话时, 上述两种情况均计算, 取缓存数组中非空值作为最终的归属地匹配结果。

3 编程实现

3.1 缓存归属地数据

手机类 (mobilearea为手机数据库归属地表) :

固话类 (telarea为固话区号数据库归属地表) :

3.2匹配归属地数据

手机类 (tel No为待匹配号码) :

固话类 (tel No为待匹配号码) :

4 性能对比

为对比归属地Hash匹配性能, 随机生成1000 个、 2000个、 5000 个手机号码, 对数据库查询和自定义Hash函数两种方法进行对比。 测试在一台普通微机上进行, 该机器配置i55470 四核处理器, 8G内存, 安装Windows 8 操作系统和Oracle 11g数据库。

从测试结果表1 来看, 数据库查询方式的批量匹配性能随着号码数目的增加, 其耗时也成倍增加, 究其原因, 其匹配过程需要反复查询数据库, 开销较大; 而自定义Hash函数利用号码的特点, 直接将号码映射为数组地址, 时间开销很少, 且不会随着号码数目的增多有明显变化, 仅仅是在缓存归属地数据时, 30 万条归属地条目仅占用了约4MB的内存空间, 在大数据量条件下优势明显。

5 结语

小数据量下的传统计算方法或方式在遇到大数据量时并不一定适用。 比如所研究的号码归属地匹配问题, 在针对少量或几个号码进行匹配时, 数据库查询方式无需初次缓存的耗时, 更具优势。 但在遇到大数据量的情况, 反复查询的开销与号码数成正比, 导致性能急剧下降。 所提出的自定义Hash函数, 将归属地数据缓存后, 在匹配时完全避免了Hash冲突, 可大幅提升大数据量下的归属地匹配性能。

参考文献

[1]徐君锋.手机归属地查询.电脑编程技巧与维护, 2007, (8) :19-22.

[2]郭毅棋.基于Android的手机号码归属地查询系统的设计与实现.厦门城市职业学院学报, 2013, 15 (2) :43-47.

Hash论文 篇8

无线射频识别(Radio Frequency Identification,RFID)技术是一种自动识别技术,作为物联网的关键技术之一,应用领域已涉及日常生活的方方面面。而RFID系统中阅读器与标签之间的无线信道决定了RFID系统安全性差,易受到攻击。主要攻击手段有欺骗攻击、插入攻击、重放攻击、假冒攻击、跟踪以及拒绝服务攻击。因此,RFID的安全机制问题越来越重要。

目前,实现RFID安全机制所采用的主要方法分物理方法和采用安全认证机制的方法。安全认证机制通过消息传递来实现标签与读写器合法身份的确认。随着密码学的发展,已经提出多种RFID安全协议,具有代表性的是Hash-Lock、随机化Hash-Lock和Hash链协议,但这些协议也存在安全性问题。本文从RFID系统的安全机制入手,研究分析一种改进RFID安全认证协议。

2 改进的安全认证协议

本文提出的改进协议同样基于Hash函数,并引入读写器-标签双向认证的机制以及标签ID动态刷新机制。下文中所用的符号“‖”为字符串连接符号,符号“笒”为字符串异或符号,H(x)表示对x取哈希运算的值。

在改进协议中,后台服务器和标签共享一个密钥。一个RFID系统中密钥可以有多个,如每64个标签公用一个密钥,密钥可当作标签ID的索引号。一个RFID系统也可以只有一个密钥。本文改进协议中密钥K的数量的选取在一定程度上取决于RFID系统后台服务器的存储能力以及标签总的数量。如果标签数量众多并且服务器有足够的存储空间,那么可以选取多个密钥,每个密钥对应一定数量的标签以减少服务器搜寻标签ID的时间。如果系统中只有少量的标签,那么可以只有一个密钥。标签和读写器之间的通信数据采用Hash函数加密,标签和读写器之间的信息均动态更新。流程如图1所示。

改进协议流程如下:

1)标签进入读写器有效读取范围,读写器向标签发送查询命令Query和随机数R;

2)标签接收到查询命令后计算H(R‖Kj)发送回读写器;

3)读写器逐个对所有的Ki计算H(R‖Ki)并与接收到的H(R‖Kj)进行比较,若存在某个Ki与Kj的哈希值相同,则标签认证通过,并向标签发送读取指令Read以及H(Kj);

4)标签将接收到的H(Kj)与自身存储的H(Kj)’值进行对比,若一致,则读写器认证通过,标签计算H(R‖Kj‖IDi)返回给读写器;

5)读写器接收到H(R‖Kj‖IDi)后,向后台服务器发送H(R‖Kj‖IDi)、R、Kj。服务器根据接收到的Ki查询对应ID的存储区域,然后对该区域内的所有IDi计算H(R‖Kj‖IDi)并与接收到的值进行比较,若存在相同的值,则计算H(IDi茌R)并用H(IDi茌R)代替原来的IDi,同时原来的IDi存储为IDi’,并向读写器发送新的IDi。若不存在相同的值,则对该区域内所有的IDi’计算H(IDi’茌R)并与接收到的值进行比较,若存在与接收到的值相同的IDi’,则数据库保持IDi和IDi’不变,同时向读写器发送IDi;

6)读写器接收到IDi后向标签发送确认指令ACK,标签接收到ACK指令后用计算H(IDi茌R)并用H(IDi茌R)代替原来的IDi,至此读写器读取流程完成。

3 改进协议的安全性证明

为了规范证明改进协议的安全性,下面将采用经典的安全协议证明分析方法———BAN逻辑对改进协议进行形式化分析和证明。

假设D代表后台系统,R代表阅读器,T代表标签,S代表阅读器产生的随机数,K代表标签密钥,ID代表标签标识符,则协议开始的假设为:

改进协议的理想化模型:

其中由于读写器和后台系统之间是安全信道传输数据,所以相互信任,用后台系统D代替读写器T,又因为M1是以明文形式传输的,所以可以将上述模型简化为:

M2:D茳H(S,K)

M3:T茳H(K)

M4:D茳H(S,K,ID)

协议的安全目标:(1)D|≡T|~#(K)

下面证明改进协议能达到以上安全目标。

可得:D|≡T|~H(S,K)

由于D|~S,所以由D茳H(S,K)可以推出:D茳S,D茳K。再由规则

推出:D|≡T|~(S,K),得:D|≡T|~K(2)

综合(1)(2)可得:D|≡T|~#(K),达到安全目标(1)。

由M3:T茳H(K)和规则可知:T|≡D|~K,即达到安全目标(2)。

同目标(1)证明过程,由M4:D茳H(S,K,ID)、D|≡#(S)、安全目标(1):D|≡T|~#(K)、规则

和新鲜性规则可知:D|≡T|~#(ID),即达到安全目标(3)。

上述证明分析可知,本文改进协议能实现预期的安全目标D|≡T|~#(K)、T|≡D|~K和D|≡T|~ID,即能实现读写器与标签双向认证和读写器安全读取标签ID,且由于读写器读取标签数据时具有新鲜性,所以能有效防止标签位置跟踪。

4 改进协议的性能分析

在实际标签芯片制造中,一个电子标签可用于安全和隐私保护的门电路数量限制在5000个以内,而设计一个hash函数模块大约需要1700个门电路,因此在标签中嵌入hash函数模块是可行的。对比各个协议,假设读写器完成一次读取过程,RFID系统中标签的个数为N,改进协议中密钥的个数为M(M

通过对比不难发现本文协议不仅能够有效抵御各种攻击,安全性高,而且可以根据读写器和后台运算能力来选择恰当的密钥个数M,来提高系统的运算效率,协议中标签不需要内置随机数生成器,有效降低了标签的成本。

5 结束语