云计算环境下高效安全的冠字号码查询方法

侯作鑫，秦 拯，欧 露，胡玉鹏

（湖南大学信息科学与工程学院，长沙410012）

云计算环境下高效安全的冠字号码查询方法

侯作鑫，秦 拯，欧 露，胡玉鹏

（湖南大学信息科学与工程学院，长沙410012）

针对现有冠字号码管理系统查询时间长、数据存储可扩展性差等问题，将云计算技术应用于冠字号码的存储和查询中。根据银行ATM机加钞过程及网点清分过程，定义存储冠字号码信息的关联形式，结合钱币的冠字号码，提出可交换加密的折半查找索引算法，对索引及数据进行加密，保证冠字号码的安全性。理论分析与实验结果表明，该方法可利用云计算平台的虚拟存储和虚拟计算能力，满足银行对冠字号码管理系统的数据传输能力和扩展性能的要求，并且与当前主流查询方法相比，具有较高的查询效率及安全性。

云计算；冠字号码；可交换加密；查询；安全索引

1 概述

冠字号码是一种标记钞票唯一性的符号，由大写英文字母和十进制数字组成，总位数为10，其中，前4位中有2位是大写英文字母，其他2位是十进制数字；后6位是十进制数字。针对国家反洗钱、现钞追踪和数据统计等方面需求，中国人民银行规定，客户的每一笔存取款业务都要满足冠字号码查询需求。中国银行业服务改进情况报告显示，当前银行柜台和自助设备现金交易量数目巨大，2012年仅银行自助设备的交易情况已达321.56亿笔，总交易额达923.71万亿元。自2005年以来，全国年均增长超过20%的现金投放总量，对传统的人民币流通管理模式形成很大压力和挑战［1］。

虽然国内已有部分省市对冠字号码进行了管理，比如北京、上海等，但由于冠字号码数据量庞大，数据处理比较复杂，查询时间较长，给用户造成较差体验，影响了冠字号码管理系统的推广，不利于管理机构对钱币的监管统计。

同时，由于银行业的特殊性，需要保证客户信息的安全，传统的数据库索引加密是对整个数据库索引进行加密［2］，在索引查找时，需先解密再比较，I/O次数多、效率低。目前，有关云数据库下的密文检索研究，一般指检索文件［3-4］，不适合冠字号码的密文检索。

本文根据银行ATM机加钞过程及网点的清分过程，定义冠字号码在存储中的关联形式，结合冠字号码可转化为二进制形式的特征，提出可交换加密的折半查找索引算法（Commutative Encryption Binary Search-Chord，CEBS-Chord），考虑到云计算在海量存储以及高性能计算方面的优势［5-6］，设计基于云计算的冠字号码高效安全查询方法。

2 基于云计算的冠字号码查询框架

2.1 查询框架

云计算是继服务计算和网格计算之后的一种新的计算模式，在远程的数据中心，成千上万台电脑和服务器连接成一片电脑云，用户通过电脑、手机、其他智能终端等方式接入云计算，就可以按自己的需求进行存储和运算。它是能够提供动态资源池、虚拟化和高可用性的下一代计算平台［7-8］。云计算具有高可扩展性和高可用性。可扩展性表达了云计算能够无缝地扩展到大规模的集群之上，甚至包含数千个节点同时进行处理，而这正好能满足冠字号码不断增加所需的扩展容量。文献［9］介绍了银行业与云计算应用结合的必要性。

本文方法中的冠字号码数据不存储在本地，而是保存在云计算提供的虚拟存储中心，银行的各种查询、处理等应用程序也不运行在前置机中，而是运行在云计算的数据处理中心，即大规模的服务器集群中。基于云计算的冠字号码管理利用基于时间戳的数据库管理系统来追溯每一张纸币，特别是假币的历史信息，并可将此信息与用户个人身份认证信息、流通过程的信息进行对应，为纸币使用情况的统计提供数据支持。针对包含冠字号码的海量数据挖掘，分析用户的消费状况、监控可疑资金以及可疑人员的流动情况，从空间和时间2个层次上实现金融业的动态监管，为相关部门制定政策以及监管金融业运行提供强大的数据支撑服务。

图1 基于云计算的冠字号码存储与查询结构

2.2 索引框架

云环境下的冠字号码数据按照水平分区的形式分成若干个数据块，这些数据块分布式地存储在数据中心的不同服务器上。存储节点是云数据中心分布式存储系统中的一个节点，保存着分配在此节点的原始冠字号码数据、根据原始冠字号码数据建立的本地索引和部分全局索引等信息。由于使用传统的中心服务器形式存储所有全局索引易形成性能瓶颈问题，因此将全局索引分布式地保存在各个存储节点。每个存储节点逻辑上按照Chord组织在一起，共同维护全局索引。为存储在从节点的数据建立局部索引，而全部存储节点按照Chord结构共同维护全局索引。根据索引公布策略，将局部索引信息通过Chord接口公布到整个覆盖网络形成全局索引。局部索引的信息格式为（ip，Uj），其中，ip指局部索引所在节点的IP地址；Uj是局部索引对应的第j个从节点，如图2所示。

图2 索引结构

数据查询分为2个阶段：（1）通过Chord覆盖网络查询全局索引，返回满足条件的索引信息条目（ip，Uj）；（2）通过索引信息条目中的ip地址和Uj定位到存储节点的CEBS索引中，并在此索引中进行数据查询，返回最终满足要求的结果。

3 冠字号码数据采集

冠字号码在云中主要存储的数据为：冠字号码编号，交易地点，交易时间，使用人。冠字号码的数据存储过程分为2种情况：ATM机上和银行前台的冠字号码存储。考虑第1种情况，针对现有ATM机有抓取冠字号码的能力才能投入使用的不足，提出一种关联模式，并且无需对ATM机进行加装冠字号抓取模块的改造，节省了大量的ATM机改造费用。具体过程是：将钱币在清分机中以捆扎为单位存储，在ATM加钞时，以捆扎为单位装入ATM钞箱，形成ATM机与所装钞箱对应、所装钞箱与捆扎对应、捆扎与冠字号码对应，当使用者取钱时可以记录使用者信息，这样使用者信息、交易时间信息、交易地点信息（所属ATM机）就被记录下来。考虑第2种情况，前台的冠字号码存储经清分机完成，当客户在前台存钱或者取钱时，就记录了使用者信息、交易时间、交易地点（所在网点）。具体对应关系如图3所示。

教育技术AECT1994定义的教学技术是为了促进学习对有关的资源与过程进行设计、开发、利用、管理和评价的理论和实践，明确了教育技术是关于理论与实践的学科。而现代教育技术是在教育技术的基础之上赋予“现代”二字，即把教育技术与现代信息技术相结合，运用新技术、新方法、新理念完成新的历史任务。通过对比分析，可以看出“十一五”“十二五”“十三五”三个阶段的现代教育技术教材的课程目标均是围绕教育技术理论与实践制定的，只是侧重点有所不同。具体见表2。

图3 冠字号码与ATM机、银行网点的对应关系

4 冠字号码安全索引查询

冠字号码的查询基于冠字号码的存储，根据以上存储过程及方法，结合冠字号码特征，提出一种快速、安全的两层索引结构——CEBS-Chord索引。

4.1 全局索引

Chord是一种结构化P2P覆盖网络。Chord把节点和资源标识映射到相同空间，以保证一致性哈希，并选择SHA-1作为哈希函数，是分布式哈希（Distributed Hash Table，DHT）的一种实现。Chord是一个算法，也是一个协议。作为一个算法，Chord可以从数学的角度严格证明其正确性和收敛性；作为一个协议，Chord详细定义了每个环节的消息类型。Chord通过使用一致性杂凑函数，把关键值存储在Chord中的相应节点上［10-11］。一致性杂凑函数通过使每个节点存储数量大致相等的关键值来平衡负载，并且使得当节点加入或退出时关键值的相对移动比较小。Chord中的路由表是分散的，每个节点通过和其他的少数节点交流来获取路径信息。一个由N个节点组成的索引在稳定状态时，每个节点仅保存O（log N）个其他节点的信息，查询操作也仅需要发送O（log N）条消息到其他节点。当索引更新时所产生的消息量在绝大多数情况下不超过O（log2N）。其中，每个节点都维护一个Finger表，该表长度为m，其第i项存放节点n的第（n+2i-1）mod 2m个successor（1≤i≤m）。每个节点都维护一个predecessor和successor列表，该列表的作用是能快速定位前继和后继，并能周期性地检测前继和后继的健康状态。存放的successor是按2的倍数等比递增。资源Key存储在下面的Node上：沿Chord环，Hash（Node）≥Hash（Key）的第1个Node为这个Key的successor。给定一个Key，查找其对应资源的节点（即查找该Key的successor）步骤如下：

（1）检查Hash（Key）是否在节点m和m的直接successor之间。

（2）若是，则查找结束，m的直接successor即为目标。

（3）在m的Finger表中，找出与Hash（Key）距离最近且小于Hash（Key）的m的successor，然后把查找请求转发到该节点。

（4）继续上述过程，直至找到Key的successor节点。

4.2 CEBS索引

云计算中从节点中的索引［12］一般采用B树［13-15］结构，CEBS索引相对原索引算法进行以下3点改进：

（1）在结构上根据冠字号码特征将其存储形式由字符串改为二进制数，既减少了存储空间，又降低了查询时的比对次数，提高了查询效率。

（2）对索引结构中的存储信息进行交替加密，保护查询数据。具体加密方法如下：令s=snsn-1…s1∈｛0，1｝n为一个长度为n的二进制数据流，表示需要进行比较的数据。

定义1 二进制数据流S的0编码由如下形式表示：

定义2 二进制数据流S的1编码由如下形式表示：

（3）在B树节点中的查询加密的冠字号码时采用折半查找的查询算法，提高了其查询效率，具体步骤如下：

1）主节点发送查询请求，根据存储的全局Chord索引找出对应的本地B树索引。

2）从属节点将查询请求中的冠字号码转换为二进制类型，每一个字符占6 bit，如0对应二进制000000，9对应二进制001001，A对应二进制001100，Z对应二进制100011，冠字号码T2U5025132对应二进制数011101 000010 011110 000101 000000 000010 000101 000001 000011 000010。

3）对转换后的二进制形式冠字号码采用1编码的形式进行交替加密，然后计算：

4）设要查询的冠字号码二进制0编码后为target，加密后的冠字号码ta=Ea（Eb（target）），B树节点中含冠字号码个数为n，设存储的索引节点的二进制流的1编码形式为A［n］，在CEBS索引中采用折半查找ta的算法具体如下：

步骤1 设置low=0，high=n-1。

步骤2 mid=（low+high）/2，如果low≥high，则进入步骤3；如果Rx≠0，则low=m id+1；如果Rx=0&&Rx+1≠0，则结束查询，返回结果。如果Rx=0&&Rx+1=0，则high=mid-1；如果low＜high，则重复步骤2。

步骤3 如果A［mid］.next==NULL，则返回A［mid］的值；如果A［m id-1］＜ta和A［m id-1］≥ta，而且A［mid］.next！=NULL，则执行下一层搜索，返回步骤1。

在算法执行过程中，输入的数据都进行了加密处理，因此，不会导致冠字号码信息的泄漏，满足了银行对数据安全性的要求。查询得到的返回值是符合查询条件键值的地址块，该地址对应相应的冠字号码信息。将该冠字号码信息返回给主节点，便完成了整个查询。

5 实验与结果分析

实验中使用实验室局域网中的3台计算机来模拟云计算平台，每台机器的通信带宽为10 M b/s，处理器为Inter（R）Core（TM）i5CPU，2.40 Hz，内存为2 GB，硬盘为500 GB，实验数据取自于某合作银行的真实数据。

实验从索引建立效率和查询吞吐量2个方面来评估本文查询方法的性能。其中，索引建立效率反映了索引更新和建立性能以及索引的可扩展性；查询吞吐量用于评估查询方法的速度。在下文实验中，将CEBS-Chord索引算法与SNB索引算法［17］进行相关性能的对比。选择SNB索引算法的原因是SNB索引是现有云环境下使用树型结构的典型索引。分别建立1×106条～5×106条冠字号码数据，为了更全面准确地比较2种索引算法，考虑树形结构索引中唯一的参数M（M表示M叉树）对索引性能的影响，选取M=7和M=14比较建立索引时间，分析2种查询算法建立索引的效率，实验结果如图4所示。

图4 索引建立效率对比

根据图4可知，虽然CEBS-Chord索引算法需要对冠字号码数据进行预处理，但其建立时间仍要优于SNB索引算法，这是因为相对于预处理时间，其在CEBS-Chord索引中的查找比对时间远少于原索引查找比对时间。因此，CEBS-Chord索引建立效率要优于原索引，并且这种优势不以M的变化而变化，但是针对同一种索引算法，M的大小影响查询效率［18］。

查询吞吐量是指单位时间内可以处理的查询数量，反映了单位时间内索引可以支持的查询量，是衡量索引结构的重要指标。该实验比较了CEBSChord和SNB算法的查询性能，从数据库中随机选择1 000条记录作为查询样本，取这1 000条记录的查询时间代表各自的查询性能。在1×106条～5×106条冠字号码数据中，对1 000条冠字号码记录进行查询，记录其查询时间，得出M=7和M= 14下2种算法在单位时间内的查询条数，如图5所示。

图5 查询效率对比

根据图5可知，当冠字号码数量增加时，2种索引算法对应的查询吞吐量均增加。CEBS-Chord索引算法的查询效率要优于SNB索引算法，这是因为CEBS-Chord索引节点内及节点间的数据比较是二进制数，相对于SNB索引算法的字符型比较，其效率要高很多。此时查询效率的提高与M的大小无关。综上所述，CEBS-Chord索引算法有效地提高了整体查询性能。

6 结束语

本文利用云计算的海量虚拟存储能力和虚拟计算能力，将云计算技术运用到冠字号码的存储和查询中。采用CEBS-Chord索引查询算法，给出针对冠字号码特征的二进制存储形式，将字符转化为二进制数，既能提高查询效率，又能减少存储空间。通过对索引数据进行可交换加密保证了查询时数据的安全性。采用云计算技术及可交换加密技术，在保障冠字号码安全存储的前提下，增强了冠字号码存储结构的易扩展性，同时为云数据库中针对冠字号码的安全索引查询提供了一种优化方法。由于本文只对二级索引进行改进，查询性能还有提升空间，下一步将根据二级索引中节点的查询热度，优化二级索引在一级索引中的部署，提高整体查询性能。

［1］ 李 文.冠字号码技术应用有利于人民币流通管理［J］.金融博览，2012，（12）：53-54.

［2］ 雷春红，余建桥.基于密文块数组折半查找的B+树密文数据库索引［J］.计算机工程与设计，2010，31（4）：713-716.

［3］ 冯贵兰，谭 良.云环境中基于多属性排序的密文检索方案［J］.计算机科学，2013，40（11）：131-136.

［4］ 项 菲，刘川意.云计算环境下密文搜索算法的研究［J］.通信学报，2013，34（7）：143-152.

［5］ 陈 康，郑纬民.云计算：系统实例与研究现状［J］.软件学报，2009，20（5）：1337-1348.

［6］ Ding Linlin，Qiao Baiyou，Wang Guoren，et al.An Efficient Quad-tree Based Index Structure for Cloud Data Management［C］//Proceedings of the 12 th International Conference on Web-age Information M anagement. Berlin，Germany：Springer，2011：238-250.

［7］ 刘 鹏.云计算［M］.北京：电子工业出版社，2010.

［8］ 郭又铭，王 鹏，唐 华，等.基于相空间的云计算专用监控系统［J］.计算机工程，2013，39（7）：40-44.

［9］ 蔚赵春，凌 鸿.我国商业银行私有云建设研究［J］.浙江金融，2012，（5）：59-62.

［10］ Chord算法（原理）［EB/OL］.（2013-06-05）.http：//blog. sina.com.

［11］ 蔡瑞青.覆盖网络自组织结构及其QoS路由研究［D］.杭州：浙江大学，2007.

［12］ Wu Sai，Jiang Dawei.Efficient B-tree Based Indexing for Cloud Data Processing［J］.Proceedings of the VLDB Endowment，2010，3（1）：1207-1218.

［13］ Wu Sai，W u Kun-Lung.An Indexing Framework for Efficient Retrieval on the Cloud［J］.IEEE Data Engineering Bulletin，2009，32（1）：77-84.

［14］ W ang Jinbao，W u Sai.Indexing Multi-dimensional Data in a Cloud System［C］//Proceedings of the ACM International Conference on Management of Data. New York，USA：ACM Press，2010：591-602.

［15］ 林子雨，赖永炫.云数据库研究［J］.软件学报，2012，23（5）：1148-1166.

［16］ 查 俊，苏锦海.姚氏百万富翁问题的高效解决方案［J］.计算机工程，2010，36（14）：124-126.

［17］ Zhou W ei，Lu Jin.SNB-index：A SkipNet and B+Tree Based Auxiliary Cloud Index［J］.Cluster Computing，2014，17（2）：453-462.

［18］ 余祥宣，刘 伟.数据库的密文索引机制［J］.华中科技大学学报：自然科学版，2002，30（3）：16-18.

编辑 陆燕菲

Efficient and Safe Query Method of Crown Word Number in Cloud Computing Environment

HOU Zuoxin，QIN Zheng，OU Lu，HU Yupeng
（College of Information Science and Engineering，Hunan University，Changsha 410012，China）

For the problem s of long query time and poor data storage scalability of the existing crown word number management system，the cloud Computing is applied to the storage and query of crown word number.The association form of storing information of crown word numbers is defined according to the money-adding process of bank ATM and the counting process of bank branches.In order to ensure the safety of crown word number，a Commutative Encryption Binary Search-Chord（CEBS-Chord）is proposed in this paper to realize index and data encryption.Theoretical analysis and experimental result show that the method can make full use of the virtual storage and virtual computing power of cloud computing platform，and it can meet the data transmission capacity and extension performance requirements of an crown word number management system.Compared with the current query methods，it has efficient query efficiency and high security.

cloud computing；crown word number；commutative encryption；query；safe index

侯作鑫，秦 拯，欧 露，等.云计算环境下高效安全的冠字号码查询方法［J］.计算机工程，2015，41（11）：47-51.

英文引用格式：Hou Zuoxin，Qin Zheng，Ou Lu，et al.Efficient and Safe Query Method of Crown Word Number in Cloud Computing Environment［J］.Computer Engineering，2015，41（11）：47-51.

1000-3428（2015）11-0047-05

A

TP393.09

10.3969/j.issn.1000-3428.2015.11.009

国家自然科学基金资助项目（61272546）。

侯作鑫（1989-），男，硕士，主研方向：云计算，数据库索引技术；秦 拯，教授；欧 露，博士；胡玉鹏，副教授。

2014-07-15

2014-09-15 E-m ail：houzuoxin@163.com