1.一种基于哈希前缀树的数据完整性验证方法,其特征在于,所述哈希前缀树包括:一个根节点以及若干分支节点、中间节点和叶子节点;其中,分支节点和中间节点由编码部分和指针部分构成,分支节点的编码部分包含n个字符,指针部分包含与所述n个字符分别对应的n个节点指针,每个节点指针指向空或分支节点的后继节点;中间节点的编码部分包含一字符串,指针部分包含1个指针,该指针指向中间节点的后继节点;叶子节点由编码部分和哈希值部分构成,叶子节点的编码部分包含一字符串;每个叶子节点对应存储于服务器的一个文件块,从根节点到每个叶子节点均存在唯一一条路径,路径上所有节点的编码部分按照从上到下的顺序排列而成所得的字符串即为对应文件块的编码字符串,叶子节点的哈希值部分即为所述文件块的存储位置哈希值;
所述方法包括:
客户端生成私钥及公钥,将待上传文件文件F分割为N个大小相同的文件块,并使用哈希加密算法计算各文件块的数据指纹,对数据指纹进行十六进制编码,进而将编码得到的数据作为各文件块对应的编码字符串,向所述服务器发送各文件块对应的编码字符串;N为整数且N≥2;
所述服务器接收各文件块对应的编码字符串,并根据所述编码字符串查询所述哈希前缀树,确定其中的非重复块和重复块;
对于所述文件F的各非重复块:所述服务器向所述客户端发送上传指示消息,所述上传指示消息中携带有各非重复块的逻辑块号;所述客户端接收到所述上传指示消息后,根据生成的私钥为各非重复块生成对应的同态认证标签,并向所述服务器发送各非重复块及对应的同态认证标签;所述服务器接收各非重复块及对应的同态认证标签,存储各非重复块及对应的同态认证标签,并在所述哈希前缀树中增加各非重复块对应的路径,将各非重复块的存储位置哈希值写入所述文件F的存储索引表;其中,各非重复块的存储位置与其对应的同态认证标签的存储位置相隔固定存储空间Δ,Δ为单个文件块占用的存储空间;
对于所述文件F的各重复块:所述服务器查询所述哈希前缀树以确定各重复块的存储位置哈希值,将各重复块的存储位置哈希值写入所述文件F的存储索引表;
所述客户端生成挑战请求,向所述服务器发送所述挑战请求,请求对所述文件F进行完整性验证;
所述服务器接收所述挑战请求,并根据所述挑战请求以及所述文件F的存储索引表,生成对应的证据,向所述客户端发送所述证据;
所述客户端接收所述证据,根据所述证据以及生成的公钥进行验证,判定所述服务器是否完整地持有所述文件F。
2.根据权利要求1所述的方法,其特征在于,在所述服务器得到所述文件F的存储索引表之后,所述方法还包括:
所述服务器根据所述存储索引表中各文件块的存储位置哈希值构造对应的默克尔哈希树,得到根节点R,向所述客户端发送所述根节点R;
所述客户端接收所述根节点R,并计算所述根节点R的签名Sig(H(R)),并向所述服务器α
发送签名Sig(H(R));其中,H()表示哈希函数,Sig()表示签名函数,Sig()=() ,α表示客户端生成的私钥;
所述服务器接收并存储签名Sig(H(R))。
3.根据权利要求2所述的方法,其特征在于,在所述服务器接收并存储签名Sig(H(R))之后,所述方法还包括:
所述客户端向所述服务器发送动态更新请求,所述动态更新请求中携带有此次动态更新对应的操作类型及操作位置,所述操作类型包括删除操作、更新操作以及添加操作,当所述操作类型为更新操作或添加操作时,所述动态更新请求中还携带有新文件块m′的编码字符串;
所述服务器接收所述动态更新请求,根据所述动态更新请求对所述文件F进行动态更新,同时更新默克尔哈希树得到根节点R1,并向所述客户端发送根节点R1、签名Sig(H(R))以及被修改文件块的辅助信息;其中,所述被修改文件块的辅助信息包括被修改文件块对应的叶子节点信息以及被修改文件块对应的辅助路径上的所有节点信息集合;
所述客户端接收所述根节点R1、签名Sig(H(R))以及被修改文件块的辅助信息,并利用所述辅助信息计算得到根节点R′,对所述根节点R′进行签名得到签名Sig(H(R′)),判断签名Sig(H(R))和签名Sig(H(R′))是否相等:若不相等,则判定所述服务器未完整地持有所述文件F;
若相等,则判定服务器完整地持有所述文件F,并根据此次动态更新对应的操作类型和操作位置以及接收到的所述辅助信息,计算得到新的根节点R1′;根据根节点R1′和根节点R1,判定此次动态更新操作是否成功,并在判定此次动态更新操作成功后,对根节点R1′进行签名得到签名Sig(H(R1′)),向所述服务器发送签名Sig(H(R1′));
所述服务器接收签名Sig(H(R1′)),并使用签名Sig(H(R1′))替换签名Sig(H(R))。
4.根据权利要求3所述的方法,其特征在于,所述服务器根据所述动态更新请求对所述文件F进行动态更新,具体包括:
若所述动态更新请求中携带的操作类型为删除操作,所述服务器根据所述动态更新请求中携带的操作位置,确定对应的删除文件,将所述存储索引表中所述删除文件块对应的存储位置哈希值更改为‑1,以表示该文件块已被删除;
若所述动态更新请求中携带的操作类型为更新操作,所述服务器根据所述动态更新请求中携带的所述新文件块m′的编码字符串查询所述哈希前缀树,确定所述新文件块m′是否为重复块:
若为重复块,所述服务器查询所述哈希前缀树确定所述新文件块m′的存储位置哈希值,将所述文件F的存储索引表中待更新文件块m的存储位置哈希值更新为所述新文件块m′的存储位置哈希值;
若为非重复块,所述服务器向所述客户端发送上传指示消息;所述客户端接收到所述上传指示消息后,生成所述新文件块m′对应的同态认证标签,并向所述服务器发送所述新文件块m′及对应的同态认证标签;所述服务器接收所述同态认证标签,存储所述新文件块m′及对应的同态认证标签,并在所述哈希前缀树中增加所述新文件块m′对应的路径,将所述文件F的存储索引表中待更新文件块m的存储位置哈希值更新为所述新文件块m′的存储位置哈希值;
若所述动态更新请求中携带的操作类型为添加操作,所述服务器根据所述动态更新请求中携带的所述新文件块m′的编码字符串查询所述哈希前缀树,确定所述新文件块m′是否为重复块:
若所述新文件块m′为重复块,所述服务器查询所述哈希前缀树以确定所述新文件块m′的存储位置哈希值,将所述新文件块m′的逻辑块号及存储位置哈希值对应写入所述文件F的存储索引表;
若所述新文件块m′为非重复块,所述服务器向所述客户端发送上传指示消息;所述客户端接收到所述上传指示消息后,生成所述新文件块m′对应的同态认证标签,并向所述服务器发送所述新文件块m′及对应的同态认证标签;所述服务器接收所述新文件块m′及对应的同态认证标签,存储所述新文件块m′及对应的同态认证标签,并在所述哈希前缀树中增加所述新文件块m′对应的路径,将所述新文件块m′的逻辑块号及存储位置哈希值对应写入所述文件F的存储索引表。
5.根据权利要求3所述的方法,其特征在于,所述客户端根据根节点R1′和根节点R1,判定此次动态更新操作是否成功,具体包括:所述客户端判断根节点R1和根节点R1′是否相等:若相等,则判定对此次动态更新操作成功;若不相等,则判定此次动态更新操作失败。
6.根据权利要求1所述的方法,其特征在于,所述客户端生成私钥及公钥,具体包括:定义双线性映射e:G×G=GT,其中G是一个迪菲‑赫尔曼群,GT是一个素阶数乘法循环群,定义g是G的生成元;
α
所述客户端从GT中随机选取素数α作为私钥,并根据私钥计算得到对应的公钥v=g。
7.根据权利要求6所述的方法,其特征在于,所述客户端根据生成的私钥为各非重复块生成对应的同态认证标签,具体包括:所述客户端在迪菲‑赫尔曼群G中随机选取元素u作为辅助变量;
对于所述文件F的任一文件块Fi,根据辅助变量u、私钥α,生成文件块Fi对应的标签其中,H()表示哈希函数,α表示客户端生成的私钥,u表示辅助变量,mi表示将文件块Fi通过特定函数转换所得的整数,i表示文件块序号,i为整数且1≤i≤N。
8.根据权利要求7所述的方法,其特征在于,所述客户端生成挑战请求,具体包括:所述客户端确定用户从所述文件F的N个文件块中随机选取的C个文件块其中s1,s2,…sj…sC分别表示C个文件块的索引,sj表示C个文件块中第j个文件块的索引,1≤j≤C,C为整数且1≤C≤N;
对于所述C个文件块中的每个文件块 从模p的加法群Zp={0,1,2,....,p‑1}中为其选取对应的随机整数vj;
利用所述C个文件块的索引及对应的随机整数,组成对应的挑战请求chal={sj,vj},j取1到C之间的所有整数。
9.根据权利要求8所述的方法,其特征在于,所述服务器根据所述挑战请求以及所述文件F的存储索引表生成证据,具体包括:所述服务器确定所述挑战请求中所述C个文件块的索引,并根据所述C个文件块的索引查询所述文件F的存储索引表,确定所述C个文件块的存储位置哈希值,进而在所述C个文件块的存储位置哈希值的基础上得到对应的同态认证标签的存储位置,读取所述C个文件块对应的同态认证标签;
根据所述C个文件块对应的同态认证标签以及所述挑战请求中所述C个文件块对应的随机整数,利用预设公式,生成证据P={σ,μ};
其中,所述预设公式包括:
10.根据权利要求9所述的方法,其特征在于,所述客户端根据所述证据以及生成的公钥进行验证,判定所述服务器是否完整地持有所述文件F,具体包括:所述客户端根据所述证据P={σ,μ}以及生成的公钥v,判断等式:是否成立;其中,e()表示双线性映射运算;
若成立,则判定所述服务器完整地持有所述文件F;
若不成立,则判定所述服务器未完整地持有所述文件F。