近年来，传统的云计算开始有向移动云计算发展的趋势^{[1, 2]}，移动云计算中面向数据的应用服务要求云端拥有完备的数据保密机制，以免用户重要的私有数据丢失或者被盗^{[2, 3, 4]}.然而，云服务供应商的可信度是难以确定的，以云端数据完整性为例，一些遭受拜占庭失效(Byzantine failure)的云存储服务供应商可能会选择向用户隐藏数据错误，或者为节约成本故意删除用户不常用的数据^{[4, 5]}.因此，将数据安全机制完全交由云端负责是不可取的，用户必须能够按照意愿对云端数据完整性进行验证.文献[6] 提出了一种基于RSA算法的数据完整性远程验证方案，对整个文件做RSA指数运算，服务器的运算处理开销较大.文献[7]提出了一个基于标记(sentinal)的方案以验证云端数据是否完整，但此方案缺乏对动态数据的支持，并且随着标记码的减少需要重新上传整个数据文件.文献[8]中提出的使用同态可验证标签的方案可降低对通信带宽的要求，验证响应较快，但也缺乏对动态数据更新的有效支持.考虑到移动云计算环境中的移动端计算和存储能力的局限性，将复杂的数据完整性验证处理放在移动端也是不合适的.需提供一种解决方案，既能有效减轻移动端的计算压力和减少验证时的数据通信量，又能保障安全性.本文以云文件存储服务为应用场景，提出一种面向移动云计算环境的数据完整性验证方案.该方案支持移动端用户对云端数据进行完整性验证和数据更新操作，支持将验证外包给可信第三方处理，并具有无需文件块直接参与验证的特点，适合在移动云计算环境中部署.

本文研究的移动云计算数据完整性验证方案(mobile cloud computing data integrity，MCCDI)的原型系统由以下几部分组成：①数据拥有者(data owner,DO)，将数据提交给云服务供应商存储的用户；②云服务供应商(cloud service provider,CSP)，提供云存储服务的机构；③可信第三方(third-party auditor,TPA)，提供数据外包验证服务的机构；④存储服务供应商(storage service provider，SSP)，实际的数据存储服务提供者；系统的基本组成部分如图 1所示.

图 1(Figure 1)

Fig. 1

图 1 MCCDI方案的系统组成Fig. 1 System architecture of MCCDI scheme

MCCDI方案中的DO是安装在用户移动端软件，可与CSP交互，向CSP发送请求，并接受从CSP返回的数据.CSP由云端用户交互模块、数据验证服务(DAS)和用户数据库这3部分组成.其中用户交互模块是DAS和DO之间通信的桥梁；DAS负责执行具体的验证算法逻辑；用户数据库负责存储用户信息.TPA是可信的第三方验证机构，用户可把数据完整性验证外包给TPA，以减轻自身的计算和存储负担.SSP需要提供具有高可靠性、低错误率和高响应速率的存储服务.本文的算法描述中将把CSP和SSP看作同一个机构.

本文研究的MCCDI方案以基于椭圆曲线双线性对的BLS(Boneh-Lynn-Shacham)短签名方案^[9]为理论依据.BLS短签名方案基于椭圆曲线上双线性对映射：e:G₁×G₂→G_T，其中群G₁和G₂是两个Gap Diffie-Hellman (GDH)群，G_T是一个具有素数阶p的乘法群.映射e满足下面几条性质：

1) 可计算性：计算双线性映射e存在有效算法.

2) 双线性：对于任意h₁,h₂∈G,a,b∈Z_p(其中Z_p是小于p的非负整数的集合)，映射e满足：

3) 非退化性：e(h₁,h₂)≠1，其中g是群G的一个生成元.

采用BLS方案时，假设用户A想对一条消息签名，他按照下面的方法生成自己的公钥和私钥：私钥x是集合Z_r的任意一元素，与之对应的公钥是g^x.为了对消息签名，A必须将消息映射成群G上的某一元素h，并生成消息签名h^x.用户B想要验证这条消息，则检查e(h,g^x)=e(σ,g)是否成立，若满足则消息确认，反之，否认.

本文的MCCDI方案依托基于Merkle哈希树(Merkle Hash tree，简称哈希树)^[10]的文件完整性检验方法，将文件块标签的哈希值按从左至右的顺序(文件块的自然顺序)依次对应哈希树的叶子节点，再按顺序两两级联哈希，最终计算出根节点的哈希值.如图 2所示，A节点的值h_a等于h(h(h(x₁)‖h(x₂))‖h(h(x₃)‖h(x₄))).对于一个拥有n个块(n为2的整数次幂)的文件，需要进行2n－1次哈希计算(包括最初对每个文件块标签的哈希)才能算出根节点的值.本方案中，哈希树的价值体现在对文件块完整性的验证上.验证任意一文件块m_i，只需知道该文件块的块标签所对应的叶子节点到哈希树根节点路径上的所有兄弟节点的值就可以了.

图 2(Figure 2)

Fig. 2

图 2 用于文件完整性验证的哈希树结构 Fig. 2 The architecture of hash tree used for verification of file data integrity

如图 2所示，想要验证块标签x₂所对应的文件块是否完整，则需要知道块标签x₂对应的叶子节点h(x₂)的值(计算x₂的哈希即可)，以及h(x₂)到根节点Root路径上的所有兄弟节点的值，即h(x₁),h_d和h_b的值.本文将这些兄弟节点称为AAI(auxiliary authentication information)节点.验证拥有n个块的文件中任意一块，只需要lbn次哈希值计算即可.这个值同时也是哈希树的层数(记叶子节点层高为0，依次往上递增).基于哈希树的文件完整性检验方法只需对少量文件块的检验就能以极高的概率检验出文件完整性^[10].哈希树对于动态数据有很好的支持，只需进行一些二叉树操作和更新即可.

MCCDI方案中的文件块标签不采用位置索引，而是直接以H(m_i)表示(H为哈希映射函数，m_i是加密后的源文件块).在验证阶段，DO(TPA)并不需要自己计算H(m_i)，H(m_i)应由CSP计算并返回给DO(TPA).MCCDI方案可以避免如文献[7]中用户更新操作造成的受影响文件块需重新签名上传的情况，降低了开销，适合于移动云计算环境.

KeyGen(l)→(pk,sk)：密钥生成算法.该算法由DO执行，输入秘密值l，输出公钥pk和私钥sk.

SigGen(sk,F)→(Φ,sig_sk(H(R)))：签名产生算法.该算法由DO执行，输入sk和F(F={m_i},1≤i≤n，m_i为经分块并用对称密钥加密后的源文件)，生成文件块签名Φ={σ_i},1≤i≤n.之后对m_i用H函数处理得到文件块标签，即计算H(m_i),1≤i≤n，再用密码学哈希函数(SHA-1)计算出h(H(m_i)),1≤i≤n，并构造哈希树，最后产生根节点R的签名sig_sk(R).

Gen Proof(F,Φ,chal)→(P)：验证信息产生算法.该算法由CSP执行，输入F,Φ,挑战值chal(此三者由DO上传所得)，产生验证信息P.Verify Proof(pk,chal,P)→{TRUE,FALSE}：验证信息算法.该算法由DO或TPA执行，输入DO的公钥pk，挑战值chal和从CSP返回来的验证信息

P，输出是否通过验证.

ExecUpdate(F,Φ,update)→{F′,Φ′,P_update}：更新执行算法.该算法由CSP执行，输入欲更新的原文件块、原文件块签名和从DO收到的update请求.输出为更新之后的文件块F′，更新后的文件块签名Φ′和更新操作的验证信息P_update.该算法包括批量更新操作.

ExecInsert(F,Φ,insert)→{F′,Φ′,P_insert}：插入执行算法.该算法由CSP执行，输入欲插入位置的原文件块、原文件块签名和从DO收到的insert请求.输出为更新之后的文件块F′，更新后的文件块签名Φ′和插入操作的验证信息P_insert.

ExecDelete(delete)→{P_delete}：删除执行算法.该算法由CSP执行，输入从DO收到的delete请求(删除文件不需要上传文件块和块签名).输出删除操作的验证信息P_delete.

VerifyUpdate(pk,update,P_update)→{(TRUE,sig_sk(R′)),FALSE}：更新、插入、删除操作的验证算法.该算法由DO或TPA执行，输入DO公钥pk,update(insert,delete)请求和从CSP返回的P_update(P_insert,P_delete)验证信息，3种操作的验证过程类似.

本方案中数据完整性的算法执行步骤主要分为3个部分：准备阶段、完整性验证以及数据更新，每个部分的关键算法执行步骤描述如下：

1)执行算法KeyGen(l)：DO选择一个公钥密码体系密钥对(spk,ssk)，选择一随机数α∈Z_p，计算υ=g^α.然后令sk=(α,ssk)，pk=(υ,spk).

2)执行算法SigGen(sk,F)：DO将源文件分块并用对称密钥加密生成F={m_i},1≤i≤n.之后DO随机选择u∈G，令

其中:name代表文件名;n代表文件的块数.将t作为文件F的标签.之后计算文件块签名σ_i=(H(m_i)·u^m_i)^α(将文件块m_i看作∈Z_p的大整数)，令Φ={σ_i},1≤i≤n.随后根据h(H(m_i)),1≤i≤n构造一棵哈希树.构造哈希树时需要注意，由于哈希树初构建时是一棵满二叉树(后面可能变成完全二叉树)，其叶子节点数目必须是2的整数次幂，那么构建时往往需要填充叶子节点使之满足条件.建树完成后，记其根节点为R，用私钥α对R签名：sig_sk(R)=(R)^α.DO构造{F,t,Φ,sig_sk(R)}，将其上传给CSP，并删除本地的{F,Φ,sig_sk(R)}.

1)构造挑战信息chal：DO可在本地验证数据完整性，亦可将验证外包给TPA实现，以此降低DO的计算和存储负担.下面将以TPA代理验证叙述.TPA在向CSP发送验证挑战chal之前，先要求CSP将文件标签t发送过来，通过DO的公钥pk验证文件标签t(用spk对t包含的签名验证即可).若验证通过则说明文件标签完好，反之直接返回FALSE.文件标签验证通过后TPA着手构造chal.TPA随机选择有c个元素的集合[1,n]的子集I={s₁,…,s_c}，假定s₁≤…≤s_c.对于每个i∈I，TPA选择一个随机数v_i∈Z_p，构造chal{(i,v_i)}_s1≤i≤sc，将其发送给CSP.关于chal的意义：有c个元素的集合{i}即表示想要挑战的c个文件块的位置索引，随机数集合{v_i}供CSP生成验证信息.

2)执行算法Gen Proof(F,Φ,chal)：在收到chal{(i,v_i)}_s1≤i≤sc后，CSP计算下面两个值：

其中:m_i是文件的第i个文件块(同样，看做∈Z_p的大整数);σ_i是第i个文件块对应的签名.除此之外，CSP还需提供{Ω_i}_s1≤i≤sc，其为2.2节所述的AAI节点，供TPA重构哈希树的根节点R.之后CSP返回P={μ,σ,{H(m_i),Ω_i}_s1≤i≤sc,sig_sk(R)}给TPA供其验证.

3)执行算法Verify Proof(pk,chal,P)：在收到CSP返回的验证信息P后，TPA利用{H(m_i),Ω_i}_s1≤i≤sc重构哈希树根节点R.并进行下面两个验证：

验证1： e(sig_sk(R),g)=e(R,g^α) .

证明 e(sig_sk(R),g)=e((R)^α,g)=e(R,g^α).

若该验证失败，则返回FALSE.若验证通过则说明在CSP给定根节点签名sig_sk(R)的前提下，根节点R与签名sig_sk(R)是匹配的，还可以说明文件块标签{H(m_i)}_s1≤i≤sc是完好的(因为根据它可以重构出匹配签名的根节点).继续进行下一个验证.

验证2：

证明

若该验证失败说明文件块损坏，返回FALSE.反之，说明文件块完整，验证通过.一旦通过了以上两个验证，则算法返回TRUE，验证成功.文件数据完整性验证的关键步骤如图 3所示.

图 3(Figure 3)

Fig. 3

图 3 文件数据的完整性验证步骤 Fig. 3 Steps of file data integrity verification

数据更新操作关键步骤和数据流如图 4所示.

图 4(Figure 4)

Fig. 4

图 4 文件数据的更新操作步骤 Fig. 4 Steps of updating for file data

1) 构造更新信息.假设DO想将第i块数据m_i更新为m′_i.DO为m′_i产生签名σ_i=(H(m′_i)·u^m′_i)^α.然后构造更新信息update=(i,m′_i,σ′_i)发送给CSP.

2) 执行算法ExecUpdate(F,Φ,update).CSP替换块m′_i和块签名σ′_i，更新哈希树(此时CSP可缓存某些哈希树节点以提高构造效率)，生成新的根节点R′.随后CSP产生更新验证信息P_update=(Ω_i,H(m_i),sig_sk(R),R′)，发送给TPA.TPA利用{Ω_i,H(m_i)}重构根节点R，并验证e(sig_sk(R),g)=e(R,g^α)，即2.4.2节所述验证1.若验证通过，DO继续检查CSP是否真的完成了更新数据操作.DO利用{Ω_i,H(m′_i)}构造更新后的根节点值(若在DO本地验证，DO可根据m′_i直接算出H(m′_i)；若为TPA代理验证，则由DO算出H(m′_i)发送给TPA)，并将该值同R′比对，若一致，则说明CSP完成了数据更新工作，已算出新的根节点值.这时由DO用自己的私钥sk对新的根节点R′签名得到sig_sk(R′)，将其发送给CSP更新.

MCCDI方案的安全性建立在无有效算法能够解决椭圆曲线上的离散对数问题及GDH(Gap Diffie-Hellman)群的特性上.该方案中，如果CSP不把陈旧信息删除，反而在执行Gen Proof操作时将“陈旧”的{H(m_i),Ω_i}_s1≤i≤sc和sig_sk(R)值返回给DO(TPA)的话，在完整性验证阶段Verify Proof的验证1中比较重构出的根节点R与存放在TPA处的R′是否一致，就可判定CSP是否返回了陈旧的验证信息.该方案中的DO在SigGen阶段生成文件块签名时并没有直接套用BLS方案计算σ_i=H(m_i)^α而是将文件块m_i 带入计算(σ_i=(H(m_i)·u^m_i)^α)是基于以下考量：CSP可能已经把用户的文件数据删除，但是却保留了文件块标签H(m_i)(块标签比文件块小得多).由于DO(TPA)在验证过程中不接触任何文件块{m_i}_s1≤i≤sc(而是块标签)，对于DO(TPA)来说CSP所做出的举动它们一无所知.因为块标签完好，验证操作仍然可以顺利进行，但实际上文件块可能已经被CSP删除了.所以，在生成文件块签名时必须要将文件块代入计算，这样一来CSP在Gen Proof过程中也必须将文件块{m_i}_s1≤i≤sc带入计算()，CSP也就不能随便删除用户的文件数据了.另外，由于MCCDI支持外包验证，而DO并不对TPA返回的验证结果做任何处理而是直接采纳，即便TPA与CSP“共谋”，用户的文件数据和私钥也不会暴露给TPA.因此，在VerifyProof阶段的两个验证和一个充分可信赖的TPA的保证下，MCCDI方案是安全的.

1) 支持验证过程外包，可减轻移动端的计算和存储负担.

2) 验证过程无状态信息保存，CSP只需根据DO(TPA)发来的挑战请求chal构造相应的验证数据返回给DO(TPA)即可.

3) 验证无需源文件块参与，DO(TPA)端在整个验证流程中操作的是经映射函数H处理过的文件块，可保证文件信息不暴露给TPA.