有限域向量空间上的细粒度数据完整性检验方法转让专利
申请号 : CN200810237142.4
文献号 : CN101477599B
文献日 : 2010-10-20
发明人 : 陈龙 , 王国胤
申请人 : 重庆邮电大学
摘要 :
本发明有限域向量空间上的细粒度数据完整性检验方法，属于计算机及信息安全领域，在细粒度层次上实现利用较少的检验数据指示较多的数据对象的完整性，可根据用户需求设定压缩程度、准确指示出错的数据对象数量。所述的细粒度数据完整性检验方法将待检验源数据对象映射到有限域GF(q)上的d维向量空间，将所有数据对象进行均匀划分，不同划分之间实现均匀交叉。每一种划分生成一组Hash，最终得到全面的数据完整性检验方案。本发明可节省存储完整性检验数据需要的存储空间和传输完整性检验数据需要的网络带宽，适用于大量数据的完整性检验，及电子数据业务中的数据安全验证，原始取证映像完整性和电子数据证据固定等场合。
权利要求 :
1.有限域向量空间上的细粒度数据完整性检验方法，将待检验的若干细粒度数据对象组织成有限域GF(q)上以素数或素数幂q为阶的立方体或超方体结构——向量空间；根据不同有限域和不同维度d生成一个向量组，向量组中任意d个向量都线性无关，选取q及d，使得数据对象个数n≤qd且k＝(d-1)t+1，其中，t为错误指示能力；从有限域上的线性无关向量组中选取k个向量，把数据对象依次编号为0到n-1，将每个数据对象表示为GF(q)上的d维向量；对数据对象进行投影划分，计算数据对象i在第j个向量上的投影，把投影向量和数据对象的对应分量分别相乘再相加计算投影函数，利用投影函数对数据对象集合进行均匀划分，划分的每份数据对象集合都生成一个Hash数据，每个投影函数上投影相同的所有数据对象用一个Hash数据监督，如此交叉实现均匀交叉Hash检验，实现出错数据对象的准确指示和Hash数据压缩。
2.根据权利要求1所述的细粒度数据完整性检验方法，其特征在于，每个Hash数据都是由相同投影函数下投影相同的qd-1个数据对象计算得到，通过只读入一次数据对象，采用Hash并发计算或再Hash计算方式生成Hash矩阵，根据Hash矩阵确定监督关系。
3.根据权利要求1所述的细粒度数据完整性检验方法，其特征在于，数据对象的粒度、错误指示能力t和Hash数据压缩程度η根据用户需求选择。
4.根据权利要求2所述的细粒度数据完整性检验方法，其特征在于，所述Hash并发计算包括步骤：步骤1：读入一个数据对象；
步骤2：由k个投影向量计算该数据对象的监督关系，确定需参与计算的k个Hash数据；
步骤3：分别取出对应中间结果或初值计算所有k个Hash数据，再暂存中间结果。
5.根据权利要求2所述的细粒度数据完整性检验方法，其特征在于，所述再Hash计算包括步骤：步骤1：建立一个q行k列的缓冲数据矩阵；
步骤2：读入一个数据对象；
步骤3：计算该数据对象的Hash数据；
步骤4：由k个投影向量计算该数据对象的监督关系，确定该数据对象的k个Hash数据缓冲位置；
步骤5：将Hash数据分别存入缓冲数据矩阵；
步骤6：如果k个位置中某个或某几个位置的数据达到规定的规模，分别用对应Hash中间结果或初值计算缓冲数据的对应Hash，再暂存中间结果，随后清除缓冲数据。
说明书 :
技术领域
本发明涉及计算机学科、信息安全学科中的数据安全领域，具体涉及计算机取证领域的证据固定。
背景技术
使用单向Hash函数生成数据的数字摘要信息后存储下来，通过重新生成待检验数据的数字摘要信息和所存储的信息进行比较可以检查验证数据是否有变化，从而实现数据完整性检验——如果数字摘要信息不完全相同，则数据已发生变化。上述数字摘要信息是具有固定长度的Hash数据。数字摘要信息的实际长度取决于完整性检验中采用的单向Hash函数，该长度和Hash函数本身的安全性对完整性检验问题的安全性产生影响。为方便描述，Hash函数生成的一份Hash数据称为一个Hash数据或一个Hash。在关心源数据是否具有完整性时，重新生成Hash数据进行比较，验证数据的完整性。信息社会人们面对的往往是海量数据，大量的场合需要确认数据(信息)的安全性。计算机取证领域典型的应用是在进行取证复制的过程中计算并存储取证映像的数字摘要信息以实现证据固定，从而保证取证分析用的副本、最后的实际证据等的完整性。
取证映像(完全复制件)的完整性如果只停留在整体是否可靠的层面，则偶然的数据变化就会影响全部数据的可用性，给数据的安全、证据的选用带来灾难性的影响。所以，使用细粒度的数据完整性检验是计算机取证的必然需求，即我们需要分别判断单个文件或小数据块(以下统称为数据对象)是否具有完整性。依照传统的方法就需要每个数据对象都需要单独存储一份固定长度的Hash数据。当处理海量数据对象时，细粒度完整性检验面临新问题——完整性检验Hash数据也成了大规模数据，且Hash检验数据具有随机性，无法使用数据压缩技术进行压缩，这将给完整性检验数据的存储和网络传输效率带来较大的负面影响。例如：一个512GB硬盘的扇区级MD5Hash值将需要16GB的存储量，如果使用强度较高的SHA-256则需要32GB。
Vassil Roussev等人在文献“md5bloom：Forensic Filesystem HashingRevisited”(见期刊Digital Investigation，2006，vol.3(s1)：82-90)中考虑衡量海量数据之间的相似性时意识到了Hash数据的大数据量问题，引入Bloomfilter技术将若干数据对象的Hash存储到一起形成一个Hash包——Bloomfilter。该方法的Hash包不满足原来单向Hash函数的单向性，即不具有抗碰撞性，即使两个相同的Hash包对应的原始数据也可能不同，所以不能用于完整性检验。
Merkel在文献“Protocols for Public Key Cryptosystems”(见论文集IEEESymposium on Security and Privacy，Oakland，California，USA，1980，122-134)中讨论存储器内容完整性检验时为了加快频繁计算单个Hash时的计算速度，采用了Hash数据的再Hash方式，其Hash数据关系形成一个多叉树结构。侯方勇、王志英、刘真在可信计算问题中对非可信存储器的完整性检验应用中也采用与此相同的基本思想，参见文献“基于Hash树热点窗口的存储器完整性校验方法”(计算机学报.2004，Vol.27(11)：1471-1479)。该方法的本质仍是单Hash检验单个数据对象——一个Hash检验一片存储区域。
由于人们过去没有关注细粒度的大量、海量数据，按照传统思路，有以下三种选择：
一是忽略细粒度的完整性检验的需求，仍使用单一Hash数据；
二是每份细粒度数据都生成独立Hash数据，存储大规模的Hash数据；
三是折衷使用某一中等规模的粒度，生成适量的Hash数据。
第一、二种选择即会出现前面分析的问题，或者完整性检验需求未得到满足，或者Hash数据规模太大。第三种选择只实现了比细粒度要大的中等粒度的完整性检验，也没有很好地满足完整性检验的需求。
陈龙等在“基于纠错码的电子证据网络化保全方法”(通信技术，2008，Vol.41(11)：156-157，159)论文中讨论了细粒度数据完整性检验的简单情形，只能指示很少的几个错误，且只能进行少量Hash压缩。
本发明在有限域的多维向量空间上设计了一种高效的均匀交叉的完整性检验方案，在数据对象出现不满足完整性(简称出错)的可能性较小，或者在所有数据对象中出错的数据对象较少时(以下简称低错误率)，利用该方案使用适量的Hash数据即可实现细粒度的数据完整性检验。
取证映像(完全复制件)的完整性如果只停留在整体是否可靠的层面，则偶然的数据变化就会影响全部数据的可用性，给数据的安全、证据的选用带来灾难性的影响。所以，使用细粒度的数据完整性检验是计算机取证的必然需求，即我们需要分别判断单个文件或小数据块(以下统称为数据对象)是否具有完整性。依照传统的方法就需要每个数据对象都需要单独存储一份固定长度的Hash数据。当处理海量数据对象时，细粒度完整性检验面临新问题——完整性检验Hash数据也成了大规模数据，且Hash检验数据具有随机性，无法使用数据压缩技术进行压缩，这将给完整性检验数据的存储和网络传输效率带来较大的负面影响。例如：一个512GB硬盘的扇区级MD5Hash值将需要16GB的存储量，如果使用强度较高的SHA-256则需要32GB。
Vassil Roussev等人在文献“md5bloom：Forensic Filesystem HashingRevisited”(见期刊Digital Investigation，2006，vol.3(s1)：82-90)中考虑衡量海量数据之间的相似性时意识到了Hash数据的大数据量问题，引入Bloomfilter技术将若干数据对象的Hash存储到一起形成一个Hash包——Bloomfilter。该方法的Hash包不满足原来单向Hash函数的单向性，即不具有抗碰撞性，即使两个相同的Hash包对应的原始数据也可能不同，所以不能用于完整性检验。
Merkel在文献“Protocols for Public Key Cryptosystems”(见论文集IEEESymposium on Security and Privacy，Oakland，California，USA，1980，122-134)中讨论存储器内容完整性检验时为了加快频繁计算单个Hash时的计算速度，采用了Hash数据的再Hash方式，其Hash数据关系形成一个多叉树结构。侯方勇、王志英、刘真在可信计算问题中对非可信存储器的完整性检验应用中也采用与此相同的基本思想，参见文献“基于Hash树热点窗口的存储器完整性校验方法”(计算机学报.2004，Vol.27(11)：1471-1479)。该方法的本质仍是单Hash检验单个数据对象——一个Hash检验一片存储区域。
由于人们过去没有关注细粒度的大量、海量数据，按照传统思路，有以下三种选择：
一是忽略细粒度的完整性检验的需求，仍使用单一Hash数据；
二是每份细粒度数据都生成独立Hash数据，存储大规模的Hash数据；
三是折衷使用某一中等规模的粒度，生成适量的Hash数据。
第一、二种选择即会出现前面分析的问题，或者完整性检验需求未得到满足，或者Hash数据规模太大。第三种选择只实现了比细粒度要大的中等粒度的完整性检验，也没有很好地满足完整性检验的需求。
陈龙等在“基于纠错码的电子证据网络化保全方法”(通信技术，2008，Vol.41(11)：156-157，159)论文中讨论了细粒度数据完整性检验的简单情形，只能指示很少的几个错误，且只能进行少量Hash压缩。
本发明在有限域的多维向量空间上设计了一种高效的均匀交叉的完整性检验方案，在数据对象出现不满足完整性(简称出错)的可能性较小，或者在所有数据对象中出错的数据对象较少时(以下简称低错误率)，利用该方案使用适量的Hash数据即可实现细粒度的数据完整性检验。
发明内容
本发明设计了一种新的数据组合交叉完整性检验方法，在低错误率的条件下将所有数据对象进行组合交叉，一个Hash监督若干数据对象，一个数据对象被若干个Hash监督。本发明实现了细粒度的数据完整性检验，且实现了Hash数据压缩，从而提供一种高压缩率的细粒度数据完整性检验方案。利用较少的完整性检验数据——Hash数据指示较多的数据对象的完整性，节省存储完整性检验数据需要的存储空间和传输完整性检验数据需要的网络带宽。
为了实现完整性检验并同时实现Hash数据压缩的目的，本发明采用如下的技术方案：首先根据需求，生成不同有限域GF(q)(具有q个元素的有限域记为GF(q))和不同维度d(d＞2)上具有特殊性质的向量组T。其中T的每个向量都是d维向量，向量分量的元素属于GF(q)有限域。该特殊性质指从向量组中任取的d个向量都满足线性无关的性质(称T为d-线性无关向量组)。依据T中的每个向量设计一个对应的投影函数实现GF(qd)到GF(q)的映射。该映射实现了将qd个元素映射到q个元素，且映射到每个元素的元素个数都相同。
然后确定数据对象监督关系。一个Hash由某个数据对象作为其数据来源的一部分，则该Hash对该数据对象进行了监督，依据该Hash可检验该数据对象的完整性。依照固定的次序将qd个数据对象进行编号以对应到GF(qd)的每个元素。上面的映射可把qd个数据对象进行划分为q个部分——数据对象集合，每个部分有qd-1个数据对象，即得到所有数据对象的一种均匀划分。一个划分的每个数据对象集都生成1个Hash，一种划分就得到q个Hash。若使用k个向量，k个映射就可以得到k个划分，由向量之间的线性无关特性，不同划分之间实现了均匀交叉。
本发明实现时每个数据对象受k个Hash监督，即需要参与k次Hash生成的计算过程。Hash计算的数据对象读取是时间性能方面的主要制约因素，因此，提供并发计算方式保证数据对象只需读取一次，减少磁盘等外设数据的输入时间，此部分的时间花费和传统方案相同。同时，由于Hash生成时计算量较大，所以在保证只读入一次数据的同时，还提供一种可选的快速再Hash计算方式实现Hash生成，所需时间只比传统的所有数据生成单一Hash的方法略有增加，从而实现和传统简单完整性检验大体相当的时间性能而计算速度无大的差异。
本方法可按照用户的需求来自由设定数据对象的实际粒度，例如，具体数据对象既可以是一个大文件中的逻辑数据块，也可以是一系列物理扇区数据块，同时还可以是目录中的具体文件。本方法可在一定范围内按照用户的需求来设定准确指示的错误数量t和Hash数据压缩的程度。本发明生成较多的独立Hash数据组，任一组Hash数据可在某一中间粒度独立指示所有数据的完整性，多组Hash数据组合起来则在更小的基本粒度指示数据的完整性。
该方法可实现细粒度的数据完整性检验，能准确指示出出错的任意t个数据对象，在超出该数量范围的情形，也能大部分正确指示出实际错误来，但不会出现出错对象被判定为正常对象，从而不影响实际的应用。可广泛应用于计算机取证领域的证据固定。
说明书附图
图1Hash并发计算流程图
图2再Hash计算流程图
图3完整性检验流程图
为了实现完整性检验并同时实现Hash数据压缩的目的，本发明采用如下的技术方案：首先根据需求，生成不同有限域GF(q)(具有q个元素的有限域记为GF(q))和不同维度d(d＞2)上具有特殊性质的向量组T。其中T的每个向量都是d维向量，向量分量的元素属于GF(q)有限域。该特殊性质指从向量组中任取的d个向量都满足线性无关的性质(称T为d-线性无关向量组)。依据T中的每个向量设计一个对应的投影函数实现GF(qd)到GF(q)的映射。该映射实现了将qd个元素映射到q个元素，且映射到每个元素的元素个数都相同。
然后确定数据对象监督关系。一个Hash由某个数据对象作为其数据来源的一部分，则该Hash对该数据对象进行了监督，依据该Hash可检验该数据对象的完整性。依照固定的次序将qd个数据对象进行编号以对应到GF(qd)的每个元素。上面的映射可把qd个数据对象进行划分为q个部分——数据对象集合，每个部分有qd-1个数据对象，即得到所有数据对象的一种均匀划分。一个划分的每个数据对象集都生成1个Hash，一种划分就得到q个Hash。若使用k个向量，k个映射就可以得到k个划分，由向量之间的线性无关特性，不同划分之间实现了均匀交叉。
本发明实现时每个数据对象受k个Hash监督，即需要参与k次Hash生成的计算过程。Hash计算的数据对象读取是时间性能方面的主要制约因素，因此，提供并发计算方式保证数据对象只需读取一次，减少磁盘等外设数据的输入时间，此部分的时间花费和传统方案相同。同时，由于Hash生成时计算量较大，所以在保证只读入一次数据的同时，还提供一种可选的快速再Hash计算方式实现Hash生成，所需时间只比传统的所有数据生成单一Hash的方法略有增加，从而实现和传统简单完整性检验大体相当的时间性能而计算速度无大的差异。
本方法可按照用户的需求来自由设定数据对象的实际粒度，例如，具体数据对象既可以是一个大文件中的逻辑数据块，也可以是一系列物理扇区数据块，同时还可以是目录中的具体文件。本方法可在一定范围内按照用户的需求来设定准确指示的错误数量t和Hash数据压缩的程度。本发明生成较多的独立Hash数据组，任一组Hash数据可在某一中间粒度独立指示所有数据的完整性，多组Hash数据组合起来则在更小的基本粒度指示数据的完整性。
该方法可实现细粒度的数据完整性检验，能准确指示出出错的任意t个数据对象，在超出该数量范围的情形，也能大部分正确指示出实际错误来，但不会出现出错对象被判定为正常对象，从而不影响实际的应用。可广泛应用于计算机取证领域的证据固定。
说明书附图
图1Hash并发计算流程图
图2再Hash计算流程图
图3完整性检验流程图
具体实施方式
细粒度数据完整性检验可以减小因偶然的错误或少数的篡改而造成整体数据失效的灾难性影响。本方法针对总量较多的细粒度数据对象，通过交叉检验的方法，使用较少的Hash数据实现较多数据对象的完整性检验。
本方法包括向量组系列生成，确定数据对象监督关系，数据的完整性Hash生成(其中含Hash并发计算方式和Hash后再Hash计算方式两种具体实现方式)，完整性Hash数据比较、待检验数据的完整性判定等模块组成。将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结构，即依照固定的次序将qd个数据对象进行编号以对应到有限域GF(qd)的每个元素。使用有限域向量空间上的投影函数对数据对象进行均匀划分，每一种划分生成一组Hash数据，进行均匀交叉检验，最终得到全面的数据完整性检验方案，实现一定数量的出错数据对象的准确指示和Hash数据压缩。Hash检验方法本身基于通用的安全单向Hash函数。
本方法按以下步骤实施：
1)生成向量组系列
将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结构，不同的有限域GF(q)和不同维度d(d＞2)上都生成各自的d-线性无关向量组T，有限域GF(q)中q只能取素数或素数的幂，常用的情形是d＝3，4≤q≤23。其中T的每个向量都是d维向量，向量的分量的元素属于GF(q)，从向量组T中任取的d个向量都线性无关。
显然，GF(q)上的d维向量中的任一非0向量及其所有的线性表示中只有一个有可能加入d-线性无关向量组，于是选择d个向量(1，0，...，0)、(0，1，...，0)、...、(0，...，0，1)构成初始的向量组T，他们的其中1个分量为单位元1、其它分量为0。同样根据单位元1的特殊性再将全1向量(1，1，...，1)加入向量组T。理论上与上述某个向量线性相关的向量都可以替换该向量，而且其它向量在满足加入后向量组T中的任意d个向量都线性无关的条件时都可以加入。只依据这一原则任选某个向量并测试是否可以加入，效率很低。
利用该条件我们知道某个向量及其所有的线性表示中只有一个有可能加入，所以可直接进行限制加快搜索速度。所有新加入向量都限制第1个分量为1(其它任意非0元素均是其线性表示)，第2个分量为与已加入向量对应分量不同的任意元素，第3个分量为与第2个分量不等且与已加入向量对应分量不同的任意元素，其它分量依据相同原则处理。逐个加入新向量直到不能添加任何新的向量。
由于可能的组合还是非常多，基于这些启发式规则进行搜索逐步加入其它向量，以找到最多的向量加入d-线性无关向量组。现已得到常用有限域GF(q)上的3-线性无关向量组的总体信息见表1。
表1已知3-线性无关向量组的最大向量数γ及编码可用参数
有限域 GF(q) T中的向量数γ 错误指示 能力最大t 数据对象数 n＝q3 数据对象受 监督次数 k＝2t+1 GF(4) 6 2 64 5 GF(5) 6 2 125 5 GF(7) 7 3 343 7 GF(8) 10 4 512 9 GF(9) 9 4 729 9 GF(11) 10 4 1331 9 GF(13) 12 5 2197 11 GF(16) 18 8 4096 17 GF(17) 14 6 4913 13 GF(19) 15 7 6859 15 GF(23) 17 8 12167 17
2)用户设定需求
用户可自主设定自己的需求。由用户选择Hash压缩率，错误指示能力t，提供需要实现检验的数据对象的粒度和总的数据对象规模。对所有数据对象进行分组，每组数据对象分别应用该交叉检验方法。下面即设定每组数据对象数量为n。
3)确定数据对象监督关系
设数据对象个数为n，错误指示能力为t。选取适当的素数或素数幂q，及维数d，使得n≤qd且k＝(d-1)t+1≤γ。从有限域GF(q)上的d-线性无关向量组中选取k个向量(包含全部有0分量的向量)。数据对象对应到有限域的元素：把数据对象依次编号为0到n-1，将每个编号i(i＝0，1，...，n-1)表示为GF(q)上的d维向量(rd，...，r2，r1)，满足i＝(rd，...，r2，r1)＝rdqd-1+...+r2q+r1。对数据对象进行投影划分：计算数据对象i(i＝0，1，...，n-1)在第j个(j＝1，2，...，k)向量(记vj＝(ad，...，a2，a1))上的投影u，即(投影函数即为把投影向量和数据对象向量的对应分量分别相乘再相加，其乘法及加法为有限域GF(q)中的特殊运算)，依据投影u判定第i个数据对象参与第u+1行第j列的Hash计算，即同一投影函数下投影相同的元素受同一个Hash监督。每个Hash值都是由同一投影函数下投影相同的qd-1个数据对象计算Hash值得到的。每个投影函数可生成一组Hash，有q个。k个投影函数所生成的Hash共得到q行k列的Hash矩阵，见表2。
表2Hash矩阵
Hash k ... 2 1 1 h1，k ... h1，2 h1，1 2 h2，k ... h2，2 h2，1 ... ... ... ... ... q hq，k ... hq，2 hq，1
下面以实例详细说明有限域向量空间上的数据对象划分。以有限域GF(2)，d＝3为例，数据对象的划分方法如下：
假设共有23＝8个待检测的数据对象，依次编号为0、1、2、3、4、5、6、7，将8个对象的编号表示为有限域3维向量空间上的点(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，(1，0，0)，(1，0，1)，(1，1，0)，(1，1，1)。q＝2，d＝3对应线性无关向量组T的4个向量为{(1，0，0)、(0，1，0)、(0，0，1)、(1，1，1)}。用T中的1个向量和数据对象对应的向量进行投影运算：对应分量相乘再相加(加法和异或运算结果相同)。如向量(1，0，0)——投影向量的第3维为1，且有限域GF(2)只有0和1两个元素，所以划分的依据就是数据对象的向量在该维上是0还是1；结果前4个数据对象得到0，后4个数据对象得到1，所以第1个向量将数据对象分为(0，1，2，3)和(4，5，6，7)，可分别生成两个Hash。同理，第2个向量将数据对象分为(0，1，4，5)和(2，3，6，7)；第3个向量将数据对象分为(0，2，4，6)和(1，3，5，7)；第4个向量将数据对象分为(0，3，5，6)和(1，2，4，7)。
如表3所示为数据对象与Hash之间的均匀交叉检验关系(以GF(2)，d＝3，t＝1为例，表中1表示有监督关系，0表示没有)。
表3数据对象与Hash之间的均匀交叉检验关系
4)Hash矩阵生成算法：
Hash矩阵生成包含并发计算和再Hash两种方式，可选其中之一生成Hash矩阵。
并发计算方式依次读入数据对象，同时推进所有Hash的计算过程，该方式保证源数据只需读入一次，每个数据对象参与Hash计算k次，所得Hash与将相关数据读入直接计算Hash结果相同。Hash的数据计算总量为原来的k倍。
如图1所示为Hash并发计算方式Hash矩阵生成流程图。
并发计算算法描述如下：
步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；
步骤2：初始化Hash矩阵(由单向Hash函数决定)，i＝0；
步骤3：读入数据对象i；
步骤4：由k个投影向量按前述方法计算该数据对象的监督关系，确定需参与计算的k个Hash；
步骤5：分别取出Hash矩阵中对应中间结果或初值计算所有k个Hash，将中间结果再存入Hash矩阵；
步骤6：i＝i+1，重复3到5直到数据对象处理完；
步骤7：输出Hash矩阵
再Hash计算方式的原理是用完整性数据H(H(D1)+H(D2)+...+H(Dq×q))替代H(D1+D2+...+Dq×q)作为检验用的依据。其中H表示完整性检验单向Hash函数，+表示数据连接，Di为数据对象。该方式同样保证源数据只需读入一次，每个数据对象只参与Hash计算1次，另每个数据对象的Hash数据参与k次Hash计算。由于一般情况下Hash数据比源数据少得多(按512字节的数据块大小计算，MD5的Hash数据量是源数据的1/32)，所以最终Hash计算数据总量只比源数据多出少量数据。又因为数据输入占实际执行时间的相当大一部分，所以总时间将和传统所有数据计算单个Hash的时间相差很小。再Hash方式的计算过程中也采用了并发计算方式同时推进所有Hash计算过程的思想。
如图2所示为再Hash计算方式Hash矩阵生成流程图。
再Hash计算算法描述如下：
步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；
步骤2：初始化Hash矩阵(由单向Hash函数决定)，置数据对象i＝0；
步骤3：建立和Hash矩阵一一对应的缓冲数据矩阵；
步骤4：读入数据对象i；
步骤5：计算该数据对象的Hash数据h；
步骤6：由k个投影向量按前述方法计算该数据对象的监督关系，确定监督该数据对象的k个Hash以及相应的Hash数据缓冲位置(两者在各自矩阵中位置相同)；
步骤7：将Hash数据h分别存入缓冲数据矩阵中的对应k个位置(已有缓冲数据之后)；
步骤8：如果k个位置中某个或某几个位置的数据达到合适的规模(如32字节、512字节等)，分别取出Hash矩阵中对应中间结果或初值计算缓冲数据的对应Hash，将中间结果再存入Hash矩阵，并把缓冲数据清除；否则继续；
步骤9：i＝i+1，重复4到8直到数据对象处理完；
步骤10：输出Hash矩阵
5)Hash检验算法：
如图3所示为细粒度完整性检验流程图。
步骤1：选取原Hash数据生成时相同的参数，采用相同的Hash计算方式生成Hash矩阵
步骤2：将所得Hash矩阵和原Hash矩阵进行比较，如果任意一组(列)Hash完全相符，则没有出错，所有数据都具有完整性，结束。否则任意一组中至少有一个Hash不相符，继续下一步；
步骤3：先检查含0分量的d个向量生成的Hash组，统计不相符的Hash数量；
步骤4：设这d组分别有xd，...，x2，x1个Hash不相符，则最多有xd*...*x2*x1个数据对象出错；
步骤5：从Hash矩阵相应列xd个hash中取1个得到其行号(从小到大)rd，同理取得rd-1，...，r2，r1。向量(rd-1，...，r2-1，r1-1)可对应到一数据对象i；
依据数据对象监督关系依次检查数据对象i在其他(d-1)t-d+1组Hash中对应Hash是否相符，若全都不相符，则数据对象i出错，不具有完整性；
步骤6：重复步骤5验证其它数据对象是否出错。
本发明的目的是设计出新的数据完整性交叉检验方法，能在准确指示一定数量的出错数据对象的同时实现Hash数据压缩，显著地提高了Hash数据的压缩效率；可以减小因偶然的错误或少数的篡改而造成整体数据失效的灾难性影响；可以有效压缩海量Hash数据，节省完整性检验数据的存储空间和传输时的网络带宽。
本方法主要应用于大量数据的完整性检验，适合包括电子数据业务等各类数据安全验证场合，计算机取证领域的原始取证映像完整性和电子数据证据固定等等场合。
本方法包括向量组系列生成，确定数据对象监督关系，数据的完整性Hash生成(其中含Hash并发计算方式和Hash后再Hash计算方式两种具体实现方式)，完整性Hash数据比较、待检验数据的完整性判定等模块组成。将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结构，即依照固定的次序将qd个数据对象进行编号以对应到有限域GF(qd)的每个元素。使用有限域向量空间上的投影函数对数据对象进行均匀划分，每一种划分生成一组Hash数据，进行均匀交叉检验，最终得到全面的数据完整性检验方案，实现一定数量的出错数据对象的准确指示和Hash数据压缩。Hash检验方法本身基于通用的安全单向Hash函数。
本方法按以下步骤实施：
1)生成向量组系列
将待检验的若干细粒度数据对象组织成有限域上的立方体或超方体结构，不同的有限域GF(q)和不同维度d(d＞2)上都生成各自的d-线性无关向量组T，有限域GF(q)中q只能取素数或素数的幂，常用的情形是d＝3，4≤q≤23。其中T的每个向量都是d维向量，向量的分量的元素属于GF(q)，从向量组T中任取的d个向量都线性无关。
显然，GF(q)上的d维向量中的任一非0向量及其所有的线性表示中只有一个有可能加入d-线性无关向量组，于是选择d个向量(1，0，...，0)、(0，1，...，0)、...、(0，...，0，1)构成初始的向量组T，他们的其中1个分量为单位元1、其它分量为0。同样根据单位元1的特殊性再将全1向量(1，1，...，1)加入向量组T。理论上与上述某个向量线性相关的向量都可以替换该向量，而且其它向量在满足加入后向量组T中的任意d个向量都线性无关的条件时都可以加入。只依据这一原则任选某个向量并测试是否可以加入，效率很低。
利用该条件我们知道某个向量及其所有的线性表示中只有一个有可能加入，所以可直接进行限制加快搜索速度。所有新加入向量都限制第1个分量为1(其它任意非0元素均是其线性表示)，第2个分量为与已加入向量对应分量不同的任意元素，第3个分量为与第2个分量不等且与已加入向量对应分量不同的任意元素，其它分量依据相同原则处理。逐个加入新向量直到不能添加任何新的向量。
由于可能的组合还是非常多，基于这些启发式规则进行搜索逐步加入其它向量，以找到最多的向量加入d-线性无关向量组。现已得到常用有限域GF(q)上的3-线性无关向量组的总体信息见表1。
表1已知3-线性无关向量组的最大向量数γ及编码可用参数
有限域 GF(q) T中的向量数γ 错误指示 能力最大t 数据对象数 n＝q3 数据对象受 监督次数 k＝2t+1 GF(4) 6 2 64 5 GF(5) 6 2 125 5 GF(7) 7 3 343 7 GF(8) 10 4 512 9 GF(9) 9 4 729 9 GF(11) 10 4 1331 9 GF(13) 12 5 2197 11 GF(16) 18 8 4096 17 GF(17) 14 6 4913 13 GF(19) 15 7 6859 15 GF(23) 17 8 12167 17
2)用户设定需求
用户可自主设定自己的需求。由用户选择Hash压缩率，错误指示能力t，提供需要实现检验的数据对象的粒度和总的数据对象规模。对所有数据对象进行分组，每组数据对象分别应用该交叉检验方法。下面即设定每组数据对象数量为n。
3)确定数据对象监督关系
设数据对象个数为n，错误指示能力为t。选取适当的素数或素数幂q，及维数d，使得n≤qd且k＝(d-1)t+1≤γ。从有限域GF(q)上的d-线性无关向量组中选取k个向量(包含全部有0分量的向量)。数据对象对应到有限域的元素：把数据对象依次编号为0到n-1，将每个编号i(i＝0，1，...，n-1)表示为GF(q)上的d维向量(rd，...，r2，r1)，满足i＝(rd，...，r2，r1)＝rdqd-1+...+r2q+r1。对数据对象进行投影划分：计算数据对象i(i＝0，1，...，n-1)在第j个(j＝1，2，...，k)向量(记vj＝(ad，...，a2，a1))上的投影u，即(投影函数即为把投影向量和数据对象向量的对应分量分别相乘再相加，其乘法及加法为有限域GF(q)中的特殊运算)，依据投影u判定第i个数据对象参与第u+1行第j列的Hash计算，即同一投影函数下投影相同的元素受同一个Hash监督。每个Hash值都是由同一投影函数下投影相同的qd-1个数据对象计算Hash值得到的。每个投影函数可生成一组Hash，有q个。k个投影函数所生成的Hash共得到q行k列的Hash矩阵，见表2。
表2Hash矩阵
Hash k ... 2 1 1 h1，k ... h1，2 h1，1 2 h2，k ... h2，2 h2，1 ... ... ... ... ... q hq，k ... hq，2 hq，1
下面以实例详细说明有限域向量空间上的数据对象划分。以有限域GF(2)，d＝3为例，数据对象的划分方法如下：
假设共有23＝8个待检测的数据对象，依次编号为0、1、2、3、4、5、6、7，将8个对象的编号表示为有限域3维向量空间上的点(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，(1，0，0)，(1，0，1)，(1，1，0)，(1，1，1)。q＝2，d＝3对应线性无关向量组T的4个向量为{(1，0，0)、(0，1，0)、(0，0，1)、(1，1，1)}。用T中的1个向量和数据对象对应的向量进行投影运算：对应分量相乘再相加(加法和异或运算结果相同)。如向量(1，0，0)——投影向量的第3维为1，且有限域GF(2)只有0和1两个元素，所以划分的依据就是数据对象的向量在该维上是0还是1；结果前4个数据对象得到0，后4个数据对象得到1，所以第1个向量将数据对象分为(0，1，2，3)和(4，5，6，7)，可分别生成两个Hash。同理，第2个向量将数据对象分为(0，1，4，5)和(2，3，6，7)；第3个向量将数据对象分为(0，2，4，6)和(1，3，5，7)；第4个向量将数据对象分为(0，3，5，6)和(1，2，4，7)。
如表3所示为数据对象与Hash之间的均匀交叉检验关系(以GF(2)，d＝3，t＝1为例，表中1表示有监督关系，0表示没有)。
表3数据对象与Hash之间的均匀交叉检验关系
4)Hash矩阵生成算法：
Hash矩阵生成包含并发计算和再Hash两种方式，可选其中之一生成Hash矩阵。
并发计算方式依次读入数据对象，同时推进所有Hash的计算过程，该方式保证源数据只需读入一次，每个数据对象参与Hash计算k次，所得Hash与将相关数据读入直接计算Hash结果相同。Hash的数据计算总量为原来的k倍。
如图1所示为Hash并发计算方式Hash矩阵生成流程图。
并发计算算法描述如下：
步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；
步骤2：初始化Hash矩阵(由单向Hash函数决定)，i＝0；
步骤3：读入数据对象i；
步骤4：由k个投影向量按前述方法计算该数据对象的监督关系，确定需参与计算的k个Hash；
步骤5：分别取出Hash矩阵中对应中间结果或初值计算所有k个Hash，将中间结果再存入Hash矩阵；
步骤6：i＝i+1，重复3到5直到数据对象处理完；
步骤7：输出Hash矩阵
再Hash计算方式的原理是用完整性数据H(H(D1)+H(D2)+...+H(Dq×q))替代H(D1+D2+...+Dq×q)作为检验用的依据。其中H表示完整性检验单向Hash函数，+表示数据连接，Di为数据对象。该方式同样保证源数据只需读入一次，每个数据对象只参与Hash计算1次，另每个数据对象的Hash数据参与k次Hash计算。由于一般情况下Hash数据比源数据少得多(按512字节的数据块大小计算，MD5的Hash数据量是源数据的1/32)，所以最终Hash计算数据总量只比源数据多出少量数据。又因为数据输入占实际执行时间的相当大一部分，所以总时间将和传统所有数据计算单个Hash的时间相差很小。再Hash方式的计算过程中也采用了并发计算方式同时推进所有Hash计算过程的思想。
如图2所示为再Hash计算方式Hash矩阵生成流程图。
再Hash计算算法描述如下：
步骤1：根据有限域GF(q)、维数d以及指示错误能力t值从准备好的相应d-线性无关向量组中取出k＝(d-1)*t+1个向量；
步骤2：初始化Hash矩阵(由单向Hash函数决定)，置数据对象i＝0；
步骤3：建立和Hash矩阵一一对应的缓冲数据矩阵；
步骤4：读入数据对象i；
步骤5：计算该数据对象的Hash数据h；
步骤6：由k个投影向量按前述方法计算该数据对象的监督关系，确定监督该数据对象的k个Hash以及相应的Hash数据缓冲位置(两者在各自矩阵中位置相同)；
步骤7：将Hash数据h分别存入缓冲数据矩阵中的对应k个位置(已有缓冲数据之后)；
步骤8：如果k个位置中某个或某几个位置的数据达到合适的规模(如32字节、512字节等)，分别取出Hash矩阵中对应中间结果或初值计算缓冲数据的对应Hash，将中间结果再存入Hash矩阵，并把缓冲数据清除；否则继续；
步骤9：i＝i+1，重复4到8直到数据对象处理完；
步骤10：输出Hash矩阵
5)Hash检验算法：
如图3所示为细粒度完整性检验流程图。
步骤1：选取原Hash数据生成时相同的参数，采用相同的Hash计算方式生成Hash矩阵
步骤2：将所得Hash矩阵和原Hash矩阵进行比较，如果任意一组(列)Hash完全相符，则没有出错，所有数据都具有完整性，结束。否则任意一组中至少有一个Hash不相符，继续下一步；
步骤3：先检查含0分量的d个向量生成的Hash组，统计不相符的Hash数量；
步骤4：设这d组分别有xd，...，x2，x1个Hash不相符，则最多有xd*...*x2*x1个数据对象出错；
步骤5：从Hash矩阵相应列xd个hash中取1个得到其行号(从小到大)rd，同理取得rd-1，...，r2，r1。向量(rd-1，...，r2-1，r1-1)可对应到一数据对象i；
依据数据对象监督关系依次检查数据对象i在其他(d-1)t-d+1组Hash中对应Hash是否相符，若全都不相符，则数据对象i出错，不具有完整性；
步骤6：重复步骤5验证其它数据对象是否出错。
本发明的目的是设计出新的数据完整性交叉检验方法，能在准确指示一定数量的出错数据对象的同时实现Hash数据压缩，显著地提高了Hash数据的压缩效率；可以减小因偶然的错误或少数的篡改而造成整体数据失效的灾难性影响；可以有效压缩海量Hash数据，节省完整性检验数据的存储空间和传输时的网络带宽。
本方法主要应用于大量数据的完整性检验，适合包括电子数据业务等各类数据安全验证场合，计算机取证领域的原始取证映像完整性和电子数据证据固定等等场合。