可證數據完整性驗證方法、設備和系統的製作方法

2023-06-09 09:55:16

專利名稱：可證數據完整性驗證方法、設備和系統的製作方法
技術領域：
本發明涉及存儲網絡安全領域，具體涉及可證數據完整性(PDI) 驗證方法、設備和系統。
背景技術：
網際網路正朝著從個人的本地存儲向全球規模的數據存儲外包服 務而高速發展。Amazon Simple Storage Service (Amazon S3)(參考 文獻 1 : 爿鵬zo/ 6V邵Je Storage 5"ar7J.ce (Amazon S3)， http://aws. amazon. com/s3)是這禾中網際網路存儲系統之一。Amazon S3 提供了可用於存儲和獲取數據的網絡服務接口。 Amazon S3的服務是 全球規模和商業類別的，而其價格十分合理對於所用存儲量，US $0. 15GB/月；對於所有傳入數據，US$0. 10GB/月；對於第一個10TB/ 月的數據傳出，US $0. 18GB/月。對於尋求免費全球規模存儲服務的人， 也有如下服務。MediaMax(參考文獻2: JfeW屍ree 6^h'/7e Storage, http:〃www.mediamax. com)提供25GB免費在線存儲，Gmail File System (參考文獻 3 : 6"鵬j7 5T eJ2 ￡>&;757'0/7 ，
http:〃蘭.viksoe. dk/code/gmail. htm)項目已將免費Gmail帳戶轉 換為 一個永久免費的網絡存儲空間。
利用這些公共存儲空間服務，客戶端可以丟棄自己的本地存儲子 系統，通過網際網路從任何地方隨時獲取數據。這種驚人的前景吸引了 大量產業力量，這些力量己使存儲外包成為了不可避免的趨勢。
IETF Network WG抓住了這種趨勢，從而發布了 RFC 4810 "Long-Term Archive Service Requirement"(參考文獻4: RFC 4810， 厶077g-rery 7 Arc/n'ye Service /fegtAZ're/nar ￡ ， IETF Network WG ， http:〃www. ietf. org/rf c/rf c4810. txt) 。 RFC 4810描述了對負責長期保存數據的長期存檔服務的要求。支持數據存在的無抵顆性、完整
性和歸屬性是對長期存檔服務的主要要求。如RFC 4810所記載的，長
期存檔服務必須能夠在從接收到數據直到該數據的存檔周期到期時， 提供可用於證明該服務所負責的數據的完整性的證據。
從客戶端存儲到存檔服務外包數據具有兩個基本步驟， 一是提交 數據，另一步驟是獲取數據。用於數據完整性驗證的不成熟解決方案 包括從存檔伺服器中獲取數據。但是，在目前以及不遠的將來，要提 供從遠程存檔伺服器到客戶端驗證器的高帶寬是不切實際的。尤其對
於移動客戶端，難以享有高帶寬連接。此外，如RFC 4810所述，可以 是用於檢查用戶完整性的第三方驗證器。在這種情況下，第三方驗證 器不應該訪問用戶數據；否則它可能侵犯用戶數據隱私。為了驗證數 據完整性，同時避免從存檔伺服器中獲取數據，現有技術採用了三步 驟操作模型，如圖1所示。注意，為了簡化表示(並且不失一般性)， 以下將以客戶端(即，數據所有者)即是用戶數據完整性驗證器為例。 但如上所述，實際上驗證器也可以是第三方，而不是數據所有者。
在步驟0，數據的數字指紋由客戶端產生並與該數據一併發送至 存檔伺服器。除了數據本身，存檔伺服器還需要存儲數據的指紋。在 步驟1，客戶端向存檔伺服器發送關於數據完整性的質詢。存檔服務 器一併利用數據內容、數據指紋和客戶端質詢，計算數據完整性證明， 在步驟2，將該數據完整性證明返回客戶端，以用於驗證。步驟l和 步驟2可以重複多次，直到數據的存檔周期到期為止。
基於上述操作模型，以下列出了針對可證數據完整性問題的任何 技術方案應該考慮的關鍵因素。
(I )客戶端產生數據指紋所花費的時間
(II) 數據指紋所消耗的存檔伺服器存儲大小
(III) 驗證器向存檔伺服器發送的質詢的大小
(IV) 存檔伺服器計算數據完整性證明所用的時間
(V) 存檔伺服器向驗證器發送的數據完整性證明的大小
(VI) 驗證器檢査數據完整性證明所用的時間 存在看似可以處理數據完整性的簡單解決方法。初始，數據所有
12者將數據劃分成多個部分，並針對每個部分預先計算消息鑑別碼 (MAC)。無論驗證器、數據所有者或第三方何時需要數據完整性證明， 它從存檔服務中獲取多個隨機選擇的部分，並重新計算每個部分的
MAC,以用於比較。
Deswarte等人(參考文獻5: Y. Deswarte， J. J. Quisquater， A. Saidane， v e膨te j'/ te^ric力ecA"i/7g， In Proc. of Conference on Integrity and Internal control in Information systems (IICIS'03), 2003)和Filho等人(參考文獻6: D. L. G. Filho， P. S. L. M. Baretto. "e邁0;7s^i^tj'77g / ata屍05^es5"j'(9/7 a;^/er， http:〃印rint. iacr. org/2006/150, pdf)提出了使用 基於RSA的哈希函數來驗證存檔伺服器正確存儲了文件。
最近，Ateniese等人(參考文獻7: G. Ateniese， R. Burns, R. Curtmola， J. Herring, L Kissner， Z. Peterson, D. Song， /Vora67e
http:〃印rint. iacr. org/2007/202, pdf)提出了一種基於RSA的可證 數據持有方案，即S-PDP方案，其中"S"代表"採樣"。採樣的意思 是，客戶端隨機選擇一部分數據，並要求存檔伺服器顯示該隨機選擇 的數據處於健康狀態(即，所選數據的數據完整性被保持)的證據。 S-PDP方案不需要對整個文件進行冪運算，通信複雜度也是恆定的， 這使S-PDP方案成為現有技術方案中最有效的方案。
不成熟方案的缺點在於，其通信複雜度與所査詢的數據量大小是 成線性關係的。此外，在第三方驗證器的情況下，禁止向驗證器發送 用戶數據，因為這侵犯了數據所有者的隱私。為了避免從存儲伺服器 中獲取數據，可以通過選擇多個秘密密鑰並預先計算該數據的多個帶 密鑰哈希MAC。因此，驗證器可以每次向存儲伺服器公開秘密密鑰， 並要求其計算帶密鑰的哈希MAC,用於比較。但是，可以驗證特定數 據的次數受到必須先驗固定的秘密密鑰的數目的限制。當密鑰用完時， 為了計算新的帶密鑰的哈希MAC,不可避免要從存檔伺服器中獲取數 據。
參考文獻5和6的提議的缺點在於存檔伺服器不得不對整個文件進行冪運算。作為參考，給定2048比特RSA模數，在Intel Core Duo 2. 16GHz進行一次全指數冪運算要花費61.325毫秒。因此，每兆字節 的冪運算需要251.3秒。這意味著為了測試64MB文件的完整性，在客 戶端可以接收到數據完整性證明之前，存檔伺服器要花費16083. 8秒。 S-PDP方案的一個問題在於其設計目的，即採樣，有時對於數據 擁有者可能毫無意義。通過採樣，S-PDP方案試圖以似乎較高的檢測 概率容許文件塊錯誤。例如，參考文獻7論述了如何在1%的文件塊 錯誤的情況下達到99%的檢測概率。但是，很多類型的文件甚至不能 容忍一個比特的錯誤。例如，媒體文件中編解碼配置參數所處於的首 部的丟失會導致難以呈現該文件。另一示例是嵌入加密文件中的(公 鑰加密的)對稱加密密鑰的損壞會導致無法再恢復成明文的垃圾密文。 通常，數據所有者要求的是100%的數據安全。這是無論如何都不可 妥協的。
S-PDP方案的另一問題在於，利用其構建的可第三方驗證(或所 謂的公開可驗證性)系統效率非常低。為了公開可驗證，S-PDP方案 強制每個文件塊必須小於RSA公鑰e。以2048比特RSA模為例，公鑰 最多可以是1024比特。因此，根據公開可驗證S-PDP方案的解決方法 必須在邏輯上將文件分為多個1024比特的文件塊。結果產生大量文件 塊，並且必須為每個文件塊產生標籤。換言之，標籤的大小至少是文 件本身的兩倍，並且客戶端向文件加標籤所花費的時間也太長，從而 在實際中是不可行的。

發明內容
鑑於上述現有技術的缺點，本發明提出了可證數據完整性(PDI) 驗證方法，其中，首先在客戶端側產生數據的指紋，並將該指紋與數 據一併發送至存檔伺服器；當需要時，客戶端或第三方驗證器向存檔 伺服器發送"質詢"，以確定數據的完整性，存檔伺服器使用接收到的 指紋來證明數據的完整性；最後，客戶端或第三方驗證器根據來自存 檔伺服器的響應該"質詢"的輸出，驗證數據的完整性。
根據本發明的第一方面，提出了一種產生數據指紋的方法，包括步驟將數據劃分成W個塊M,， z = l，2,...,iV;將每 個塊組合成超塊， 以得到^pV ]個超塊；從有限循環群G^&〉中選擇 個元素、， J、l,2,…,n^通過使用針對第A超塊的定位符^、所選的 個元素/i,和 第一私鑰h分別產生第A超塊的指紋7;， & = l,2,...，n。
優選地，所述 個元素^是與第一私鑰o;相對應的公鑰的一部分。 優選地，所述 個元素^滿足關係、-W， r^是秘密密鑰。 優選地，根據
產生第/t超塊的指紋j;， ZM是所述數據的標識符。更加優選地，第*超
塊的定位符R是至少以*為輸入的哈希值。 優選地，根據
w也
、 X
產生第^超塊的指紋7;。更加優選地，第A超塊的定位符^是至少以)t 和所述數據的標識符ZM為輸入的哈希值。
根據本發明第二方面，提供了一種證明數據的數據完整性的方 法，其中採用根據本發明第一方面的產生數據指紋的方法產生所述數
據的指紋，所述方法包括步驟接收質詢，所述質詢至少包括第一隨
機性定義密鑰A和第二隨機性定義密鑰/S;構造①個盒子；以第一隨 機性定義密鑰 定義的第一隨機方式，隨機地將"個指紋分配到所述o
個盒子中，每個指紋放在一個盒子中；基於所述"個指紋的分配，產 生o)個封裝超塊和相應的封裝指紋；以由第二隨機性定義密鑰/S定義 的第二隨機方式，隨機地變換所述o)個封裝超塊和相應的封裝指紋， 以產生變換超塊和變換指紋；以及產生所述變換超塊的知識證明。 優選地，所述變換超塊的知識證明是所述變換超塊本身。 優選地，所述變換超塊的知識證明是基於所述公鑰和所述變換超 塊而產生的。更加優選地，變換超塊的知識證明h表示為
h=n《'^是第二私鑰，^是變換超塊。可選地，變換超塊的知識證 明H表示為

片i
& = 》是第二私鑰，A是變換超塊，p^O表示偽隨機函數。
優選地，所述質詢還包括超塊選擇密鑰對(/s,A)，用於定義將選 擇哪A個超塊和相應指紋來用於數據完整性證明，而不是所有n個超 塊及相應指紋。
優選地，所述質詢還包括重複因子^，將從構造盒子到產生知識 證明的步驟重複^次，每次均產生變換超塊的一個知識證明，表示為 變換超塊的第m個知識證明H^ m = l,2,...j。更加優選地，所述數目 cD等於2^ 0 = [Z/^ + l， ^是安全級別因子，用於確定所述方法的安 全級別。
優選地，由驗證器選擇第一和第二隨機性定義密鑰 和 以及超 塊選擇密鑰對K，A)。
優選地，所述質詢包含來自時間戳權威機構TSA的數字籤名時間 戳。更加優選地，根據所述數字籤名時間戳產生第一和第二隨機性定 義密鑰^和/S以及超塊選擇密鑰 中至少一個。
優選地，該證明數據完整性的方法還包括發送變換超塊的變換指 紋和知識證明。
根據本發明第三方面，提供了一種與根據本發明第二方面的證明 數據完整性的方法相結合的、驗證數據完整性的方法，其中採用根據 本發明第一方面的產生數據指紋的方法產生所述數據的指紋，該方法 包括步驟產生並發送質詢，所述質詢至少包括第一隨機性定義密鑰 和第二隨機性定義密鑰 ；接收變換超塊的變換指紋和知識證明；構 造O個盒子；以所述第一隨機方式，隨機地將n個定位符^分配到0)個
盒子中，每個定位符放在一個盒子中；基於所述n個定位符的分配， 產生O)個封裝定位符；以所述第二隨機方式，隨機變換所述O個封裝 定位符，以產生變換定位符；根據所述變換指紋和所述變換定位符， 產生所述變換超塊的推定知識證明；將所述變換超塊的推定知識證明
16與所接收的所述變換超塊的知識證明相比較；以及如果比較結果是肯 定的，則驗證所述數據的數據完整性。
優選地，基於所述數據的標識符ZM、所述變換指紋和所述變換定
位符產生所述變換超塊的推定知識證明。
優選地，還基於第一和第二私鑰:r和5產生所述變換超塊的推定 知識證明。更加優選地，所述變換超塊的推定知識證明表示為
T表示變換指紋，W表示變換定位符；並且第^超塊的定位符^是至 少以/t和所述數據的標識符ZM為輸入的哈希值。可選地，所述變換超 塊的推定知識證明表示為
河5((T W)"
T表示變換指紋，W表示變換定位符；並且第;t超塊的定位符^是至 少以A為輸入的哈希值。
更加優選地，所述變換超塊的推定知識證明產生為
e(T,VO.e(W，52l))
n = ^， ^ = ^' Y-《e^; G,〈&〉是在(G,〈^的情況下、具有 附加群^ =〈一的有限循環群，以使h卜l^卜lgl二p, p是大質數； e:^xG,4G是雙線性映射函數；T表示變換指紋，W表示變換定位 符；第yt超塊的定位符R是至少以&為輸入的哈希值；r和5是第一和 第二私鑰；如下將所述變換超塊的推定知識證明與所述變換超塊的知 識證明相比較，
formula see original document page 17
H表示所述變換超塊的知識證明。
更加優選地，所述變換超塊的推定知識證明產生為formula see original document page 17
^ = 9，， ~ = <， n2、G2; G^&〉是在G,〈"的情況下、具 有附加群《=〈"的有限循環群，以使l^卜lG」-^l二p， p是大質數； e:G，xG。—G是雙線性映射函數；T表示變換指紋，W表示變換定位符；第/t超塊的定位符R是至少以A:和所還數據的稱識付^刃湔入的
哈希值；工和》是第一和第二私鑰;如下將所述變換超塊的推定知識證
明與所述變換超塊的知識證明相比較，
e(H，^)"(T，i;).e(W，^)
H表示所述變換超塊的知識證明。
優選地所述質詢還包括超塊選擇密鑰對K，A)，用於定義將選擇
哪A個定位符來用於數據完整性證明，而不是所有"個定位符。
優選地，所述質詢還包括重複因子^，將從構造盒子到比較知識
證明和推定知識證明的步驟重複W次，僅當所有比較結果均為肯定的
時，才驗證所述數據的數據完整性。
優選地，由驗證器選擇第一和第二隨機性定義密鑰 和、以及超
塊選擇密鑰對( ，A)。
優選地，所述質詢包含來自時間戳權威機構TSA的數字籤名時間
戳，並根據所述數字籤名時間戳產生第一和第二隨機性定義密鑰/s和 以及超塊選擇密鑰 中至少一個。
根據本發明第四方面，提供了一種用於產生數據指紋的設備，包 括超塊產生單元，用於將數據劃分成W個塊M,， z = l,2，...，iV，並將 每 個塊組合成超塊，以得到"-pV/ ，個超塊；以及指紋產生單元， 用於從有限循環群G,二&〉中選擇 個元素/v j = l,2,..., ，並通過使 用針對第^超塊的定位符^、所選的 個元素^和第一私鑰^分別 產生第A超塊的指紋j;， A = l，2,...,n。
優選地，所述 個元素/^是與第一私鑰x相對應的公鑰的一部分。 優選地，所述 個元素^滿足關係、.-g ， r^是秘密密鑰。 根據本發明第五方面，提供了一種用於證明數據完整性的設備， 包括接收單元，用於接收質詢，所述質詢至少包括第一隨機性定義 密鑰 和第二隨機性定義密鑰 ；封裝單元，用於構造①個盒子；用 於以第一隨機性定義密鑰 定義的第一隨機方式，隨機地將n個指紋 分配到所述①個盒子中，每個指紋放在一個盒子中；並用於基於所述n 個指紋的分配，產生ci)個封裝超塊和相應的封裝指紋；變換單元，用 於以由第二隨機性定義密鑰/S定義的第二隨機方式，隨機地變換所述①個封裝超塊和相應的封裝指紋，以產生變換超塊和變換指紋；以及 知識證明產生單元，用於產生所述變換超塊的知識證明。
優選地，所述知識證明產生單元產生作為所述變換超塊本身的所 述變換超塊的知識證明。
優選地，所述知識證明產生單元基於所述公鑰和所述變換超塊而 產生所述變換超塊的知識證明。
優選地，所述質詢還包括超塊選擇密鑰對K，A)，用於定義將由 所述封裝單元選擇哪A個超塊和相應指紋來用於數據完整性證明，而 不是所有w個超塊及相應指紋。
優選地，所述質詢還包括重複因子VM將所述封裝單元、變換單 元和知識證明產生單元的操作重複仏次，每次均產生變換超塊的一個 知識證明，表示為變換超塊的第m個知識證明H^ m = l，2,...j。
優選地，所述質詢包含來自時間戳權威機構TSA的數字籤名時間 戳。更加優選地，根據所述數字籤名時間戳產生第一和第二隨機性定 義密鑰 和k2以及超塊選擇密鑰 中至少一個。
優選地，該證明數據完整性的設備，還包括發送單元，用於發 送變換超塊的變換指紋和知識證明。
根據本發明第六方面，提供了一種用於驗證數據完整性的設備， 包括質詢產生和發送單元，用於產生並發送質詢，所述質詢至少包 括第一隨機性定義密鑰 和第二隨機性定義密鑰/S;接收單元，用於 接收變換超塊的變換指紋和知識證明；定位符封裝單元，用於構造O個 盒子，以所述第一隨機方式，隨機地將w個定位符^分配到0個盒子 中，每個定位符放在一個盒子中，並基於所述n個定位符的分配，產 生①個封裝定位符；推定知識證明產生單元，用於以所述第二隨機方 式，隨機變換所述O個封裝定位符，以產生變換定位符，並根據所述 變換指紋和所述變換定位符，產生所述變換超塊的推定知識證明；比 較器，用於將所述變換超塊的推定知識證明與所接收的所述變換超塊 的知識證明相比較；以及驗證單元，如果比較結果是肯定的，則驗證 所述數據的數據完整性。
優選地，所述推定知識證明產生單元基於所述數據的標識符zm、所述變換指紋和所述變換定位符產生所述變換超塊的推定知識證明。 更加優選地，所述推定知識證明產生單元還基於第一和第二私鑰^和S
產生所述變換超塊的推定知識證明。
優選地，由所述質詢產生和發送單元產生的所述質詢還包括超塊 選擇密鑰對OS,A)，用於定義將由所述定位符封裝單元選擇哪A個定位
符來用於數據完整性證明，而不是所有"個定位符。
優選地，由所述質詢產生和發送單元產生的所述質詢還包括重複 因子W，將所述定位符封裝單元、推斷知識證明產生單元和比較器的 操作重複W次，僅當所有比較結果均為肯定的時，驗證單元才驗證所 述數據完整性。
優選地，由所述質詢產生和發送單元產生的所述質詢包含來自時 間戳權威機構(TSA)的數字籤名時間戳。更加優選地，所述質詢產生
和發送單元根據所述數字籤名時間戳來確定第一和第二隨機性定義密 鑰 和 以及超塊選擇密鑰 中至少一個。
根據本發明第七方面，提供了一種數據完整性驗證系統，包括根 據本發明第五方面的用於證明數據完整性的設備；以及根據本發明第
六方面的用於驗證數據完整性的設備。
優選地，該數據完整性驗證系統還包括根據本發明第四方面的
用於產生數據指紋的設備。更加優選地，該用於產生數據指紋的設備 也用作用於驗證數據完整性的設備。
本發明PDI方案可以在極高的概率(例如，1-2-64)上確保數據
的數據完整性。相比於實現了 (1)確保每一比特數據的數據完整性，
(2)客戶端發送至存檔伺服器的質詢的大小恆定，以及(3)存檔服
務器發送至客戶端的數據完整性證明的大小恆定，的現有技術，本發
明PDI方案主要具有如下四個優點
(I) 客戶端產生數據指紋的速度最快-，
(II) 存檔伺服器產生客戶端質詢響應的速度最快；
(III) 客戶端驗證存檔伺服器的響應的速度最快；
(IV) 驗證器可以是第三方驗證器，同時仍然保持上述三個優點
(i)-(m)。此外，指紋的大小最小。具體以64MB的數據文件為例。安全強度設為可與2048比特RSA 特徵相比，z=64。當客戶端是Intel Core Duo 2. 16GHz處理器，存檔 伺服器端是Intel Qx6700 Core2 Quad 2. 66GHz處理器時，使用PDI 方案，客戶端花費12. 7秒產生文件指紋；存檔伺服器花費1. 4秒產生 變換指紋和變換超塊的知識證明；客戶端花費0.4秒驗證知識證明。 所有這些時間值甚至低於現有基於RSA方案的存檔伺服器在最好情況 下所能達到的理論下限。


結合附圖，從下面對本發明非限制性實施例的詳細描述中，本發
明的上述和其他目的、特徵和優點將更加明顯，附圖中 圖1示出了用於證明數據完整性的工作模型； 圖2示出了根據本發明的數據完整性證明方法(原子證明過程)
和數據完整性驗證方法(原子驗證過程)的流程圖； 圖3是數據的邏輯圖4 7示出了本發明的具體示例及其正確性的演示，其中使用6 個塊^ Me，並以 =2形成3個超塊；
圖8 11示出了實際實驗結果，其中將各自均具有27個字節的 256個塊組合成一個超塊，使用0=29二512個盒子，數據文件的大小為 64M字節；
圖12示出了可選的數據完整性證明的工作模型；
圖13示出了另一可選的數據完整性證明的工作模型；
圖14示出了用於實現本發明的客戶端1400的框圖15示出了用於實現本發明的存檔伺服器1500的框圖；以及
圖16示出了用於實現本發明的驗證器1600的框圖。
具體實施例方式
下面，根據附圖描述本發明。在以下描述中， 一些具體實施例僅 用於描述目的，而不應該理解為對本發明有任何限制，而只是本發明 的示例。省略了常規結構或構造，以免導致對本發明的理解不清楚。
21原理說明
這裡提出的可證數據完整性(PDI)方案不僅克服了現有技術中 遇到的所有問題，在性能上還優於各種現有技術。
PD工方案基本具有如下三個步驟，這與圖1所示的工作模型相符合。
步驟0':
PDI方案需要有限循環群(^-^〉。優選地，(^是橢圓曲線上的有 限循環群。在本發明公開中，使用傳統的乘法群符號，而不是在橢圓
曲線背景下經常使用的加法符號。客戶端具有私鑰^和相應的公鑰。 客戶端將數據文件劃分成AT個塊M,， z = l,2,...,W。每 個塊組合
在一起，形成超塊。因此，將數據劃分成"=「^/"^個超塊。如果數據 文件的長度小於n個超塊所需的，則在邏輯上對數據文件加零。
對於每個數據文件，客戶端準備C^的 個元素&， z = l,2,...,ns。
在優選情況下，客戶端選擇n，以使^=&，並保持r;是秘密的。更優 選的，這些元素/i,是客戶端公鑰的一部分，從而獨立於數據文件。
客戶端利用其私鑰和上述 個元素&，產生所有超塊的指紋。例
如，第/個超塊的指紋的形式為2:=
，i
其中定位符w
是至少以/為輸入的哈希值，例如，定位符w的輸入還可以包括數據文
件的文件名和/或版本號；^是針對數據文件而特別挑選的標識符，例 如，為一組數據文件選擇一個標識符^，而為另一組數據文件選擇另
一個標識符《。可選地，指紋可以計算為r,-h.ft/^,—1，其中定
位符W,採用和zM作為輸入。在優選情況下，客戶端知道r;，以使、=W 。 因此，通過將J[C替換為^^-'一，客戶端可以利用知識r,來加
快指紋產生過程。
步驟0'的結果為，客戶端得到n個超塊的n個指紋。客戶端將所
22有指紋與數據文件和 個元素A,—並發送給存檔伺服器。在優選情況 下， 個元素A,客戶端公鑰的一部分，存檔伺服器可以己從例如公鑰
目錄中得到這些元素。因此，不必將這些元素連同數據文件一起傳送。
步驟r:
客戶端向存檔伺服器發送"質詢"，以確定數據的完整性。 基於從客戶端接收到的質詢，存檔伺服器需要執行多次原子證明
過程，例如，執行仏次。
對於每個原子證明過程，存檔伺服器首先構造①二y個盒子，並隨
機地將n個指紋分配到盒子中。數目O和隨機性由從客戶端接收到的 "質詢"確定。每個指紋必須放入一個且僅這一個盒子中。注意，每 個指紋精確地對應於一個超塊，在所有n個指紋全部放入盒子之後， 每個盒子均有"封裝超塊"及該"封裝超塊"的"封裝指紋"，後者是 基於分配給該盒子的指紋產生。例如，考慮只有第77和第w個超塊上 的兩個指紋放入第A個盒子的情況。該盒子的"封裝超塊"包含 < ， "1,2,..為，該"封裝超塊"上的"封裝指紋"是
An
接下來，通過向所有盒子的"封裝超塊"和"封裝指紋"應用另 一隨機性，存檔伺服器產生一個"變換超塊"和該"變換超塊"上的 一個"變換指紋"。這裡的隨機性同樣由從客戶端接收到的"質詢"確
定的。繼續採用上述示例，"變換超塊"包含醜^icvi^， ； = 1,2,...,^，
"變換超塊"上的"變換指紋"是r-fjf,，其中A是由客戶端的"質
詢"確定的隨機數。
最後，存檔伺服器產生"變換超塊的知識證明"，這可以直接是 "變換超塊"。可選地，變換超塊的知識證明可以是通過標準交互式或 非交互式零知識證明技術的"變換超塊"的內容的知識。可選地，客
戶端"質詢"包含^=/^， ； = 1，2,...， ，客戶端為每個質詢選擇不同W的 並對W呆密。在優選情況下，A是客戶端公鑰的一部分，d是客戶端私 鑰的一部分。存檔伺服器利用仏，計算"變換超塊的知識證明"為
23
存檔伺服器需要向客戶端發送作為原子證明過程輸出的"變換指
紋"r和"變換超塊的知識證明"H。
存檔伺服器總共應該重複原子證明過程仏次，從而可以選擇 0 =卩/^ + 1用於決定構造的盒子總數，其中z由客戶端選擇，並確定
了安全級別。選擇隨機數aA的位長度為0。通過重複該原子過程W 次，PDI方案的安全級別可以是(rz/V0.2-'，這表示如果至少一個塊受 到損壞，則存檔伺服器能夠說服驗證器的概率最多為(n / VO . 2-'。
上述的"數目①和隨機性由從客戶端接收到的質詢確定"以及" 是由客戶端的質詢確定的隨機數"還有其他參考實現。例如選擇0 = 1 並將n個指紋均勻地分配到rz個盒子中。即每個盒子有且只有一個指 紋。選擇aA的位長度為Z。此時選擇仏=1可實現安全級別^2-'。
步驟2':
客戶端接收來自存檔伺服器的全部W次原子證明過程的輸出。
對於一次原子證明過程的每個"變換超塊"上的"變換指紋"和 "變換超塊的知識證明"，客戶端執行原子驗證過程。
對於每個原子驗證過程，客戶端首先構造O)個盒子，並在邏輯上 隨機地將定位符^分配到盒子中。因為該隨機性由客戶端選擇的"質 詢"確定，所以該隨機性與存檔伺服器用於分配指紋的隨機性完全相 同。每個定位符必須放進且僅放進一個盒子中。在所有rz個定位符全 部放入盒子之後，每個盒子中有基於分配給該盒子的定位符產生"封 裝定位符"。例如，考慮只有兩個定位符^和^放入第A個盒子的情況。 該盒子的"封裝定位符"是A"H。
接下來，通過向所有盒子的"封裝定位符"應用上述另一隨機性， 客戶端產生一個"變換定位符"。因為該隨機性由客戶端選擇的"質詢" 確定，所以該隨機性與存檔伺服器用於計算"變換指紋"的隨機性完
全相同。"變換定位符"是^ = ^^。'，其中 是由客戶端的"質詢" 確定的隨機數。最後，如果存檔伺服器產生"變換超塊的知識證明"就是"變換
超塊"本身，客戶端計算"變換超塊的推定知識證明"為i7、(r"'vw)
並將其與ftC比較。如果相等，則原子驗證過程輸出成功。可選的，
客戶端計算"變換超塊的推定知識證明"為H、(r""w)、並將其與 從存檔伺服器接收到的值H比較。如果^ = ^'，則原子驗證過程輸出
成功。可選地，如果指紋計算為？:=
i將"變換超塊
的推定知識證明"計算為Cr"7w)。。
僅在所有的原子驗證過程均成功時，才使客戶端相信存檔伺服器 端保持了數據完整性。在存檔伺服器端有至少一個塊損壞的情況下，
客戶端被錯誤說服的概率最大是(n / V0 2-'。
詳細說明
下面將更加詳細地描述本發明。
使用傳統的乘法群符號，而不是橢圓曲線設置中常用的加法符號。
設^ = &〉和G2 ="〉是具有附加群口 = 〈^的兩個有限循環群，以使 1G^icgHS卜P，其中P是某一較大質數。雙線性映射e:G,(^ — g是 函數，以確保
雙線性對於所有&eGp 、eG2，所有MeZp， e(V,、') = e(~A)°'。 非退化3&eG,， 3、￡([52，以使e(、W-"其中/是S的么元。 可計算存在用於計算e的高效算法。
假設有設置算法Se鄉(.)，當輸入安全參數"時，輸出上述雙線性映 射設置，並寫作(p,G,，G2,g,^^e) —Sei邵(l"。
因為G,, G,和^都具有相同的質數階p，根據雙線性特性和非退化 特性，易得e(^&卜^。
給定(p,G^2,"^^e) —Se一(l"， 以及5個偽隨機函數 ^ : {0,1}' — Zp 、 : {0，1}* — ^ 、 p訓:{0,1}* — ~ 、 p訓:{0,1}* — ^
和WA —{0，1}16。作為系統參數。客戶端產生數據指紋
客戶端具有秘密密鑰Or一)二Z/和公鑰r-^e(^。優選地，客戶端
具有來自認證權威機構的關於r的證書。可選地，例如，客戶端秘密 密鑰d可以計算為W - pr/Jx,"second private key")。
此外，客戶端計算(、-^^'^U,二OeG/， 2 = 1,2,..., 作為其公鑰。
給定劃分成W個塊M, (1 = 1,2,..的數據M，每個塊是Q比特長， 必須滿足Qd。gP。以M為參考，例如，其合格的文件名稱表示為i^M。
圖3示出了邏輯上如何將劃分數據M並構造成n個超塊。 ^pV/wJ表示超塊的數量。注意在數據M的長度不等於7V人或 n.( .W的情況下，在邏輯上向數據M追加零。
客戶端執行如下過程以產生數據的指紋。
a)客戶端選擇^厶^，並計算定位符^ = ^^,、,屍 )￡&，
名為第z個超塊的指紋。
b) 客戶端用秘密密鑰o;籤署(^WM，M,ZM,化n，產生籤名S。
C) 客戶端針對i^M存儲^。
d) 客戶端向存檔伺服器發送，M， M， 、eZp， (rJeGf和s。
e) 當接收到^Vm， M， eZp，化)eG,和s時，存檔伺服器驗
證S是(FiVM，M，^，化"的有效籤名。
存檔伺服器證明數據完整性
為了確定存檔伺服器是否以0比特誤差保持i^M的內容(除了最
大允許錯誤概率2-')，客戶端質詢存檔伺服器，並且存檔伺服器如下響應。
i) 客戶端選擇重複因子i^"^z。
ii) 客戶端選擇( )厶"，並向存檔伺服器發送FiVM ，
iii) 當接收到i^M和c/^^(Z一, , )時，存檔伺服器首先計算 0=^/^ + 1，並初始化變換指紋Tt二0eG「 A; = 1,2,...,W,其中O是g
的么元。然後，存檔伺服器重複如下原子證明過程獨立的^次
iii-a.初始化封裝指紋g = 0 e G,,封裝超塊、=o ，變換超塊
五；=0， u = 1,2，..., = 2* ， j = l,2,...，ns
iii-b.對於每個&1,2,...^，計算
b-ii. r,，表示向第c7個盒子的封裝指紋加上r,
b-iii.對於每個；=1,2,計算e" += M(i—D、+,m。dp， 表示向第a個盒子的封裝超塊加上M(,一
+,
iii-c.對於每個"=1,2,...,$，計算
C—11, 丄*—、
C-iii.對於每個J、1,2,…， ，計算S += a"'e"m。dP ，
iii-d.計算A =F/5(ftO，作為變換超塊的知識證明 iv)存檔伺服器向客戶端發送(T,凡)，hl,2,…j。
可選地，例如，客戶端選擇 二Zp並且計算 =pr/J "second randomness defining key")。 這樣 可以不必傳輸。
客戶端驗證數據完整性
當接收到(Tt,H,)， fc-l,U時，客戶端獨立地重複如下原子驗證 過程^次I) 初始化w,/eG,，封裝定位符^-/eG,，
w = 0，1,…，《一l = —1
II) 對於每個1 = 1,2,...;，計算￡7 = ^/3(" )禾口 WC *= WA滯m) °
III) 對於每個"=1,2,...,$ ，計算 =pr/>,fc, )和* = 。
IV) 計算和驗證H^;^((ir、Wj)。僅當一致性成立，輸出真。 如果所有的原子驗證過程都輸出真，則客戶被數據完整性證明說服。
具體示例
圖4 7示出了本發明的具體示例及其正確性的演示，其中使用6
個塊碼 軌，並以 =2形成3個超塊。相信本領域技術人員通過參
照圖4 7，並結合上述的逐步描述，能夠完全清楚地理解本發明。 實際實驗
圖8 11示出了實際實驗結果，其中將各自均具有27個字節的 256個塊組合成一個超塊，使用0=29二512個盒子，數據文件的大小為 64M字節。同時，圖9 11也列出了參考文獻7的結果，從中可見， 相比於參考文獻7，本發明在計算時間成本方面取得了顯著改進。
其他實施例 可選方案l:
對"客戶端產生數據指紋"的步驟iii-d和"客戶端驗證數據完整 性"的步驟IV)稍作修改，獲得PDI-2方案。這是支持公共可驗證性的 方案。
附加地，客戶端需要計算r,-"和^二^/，作為其公鑰。
對"存檔伺服器證明數據完整性"的步驟m-d的修改
iii-dd.計算A-f[77,，作為變換超塊的知識證明。
卜l
對"客戶端驗證數據完整性"的步驟IV)的修改 IV')計算並驗證e(H^2)"(TW^/M).e(Wk，^)。PDI-2方案支持公共可驗證性，這是因為"存檔伺服器證明數據 完整性"和"客戶端驗證數據完整性"的任何步驟均未涉及客戶端的 密鑰，從而可以由第三方驗證器有效地執行。
可選方案l.l:
對於上述可選方案l，對"客戶端驗證數據完整性"的iv')步驟
稍作修改，產生支持驗證加速的方案。
對"客戶端驗證數據完整性"的步驟IV')的修改
IV-e)選擇&個隨機數r;eZ;^ ， fc = l，2,...,^，計算並驗證
(* 、,^ 、
、" ，
採用可選方案1.1，客戶端驗證數據完整性所需要執行的雙線性 對計算個數得到減少。
可選方案2:
對"客戶端產生數據指紋"的步驟a)和"客戶端驗證數據完整 性"的步驟IV)稍作修改，獲得PDI-3方案。
對"客戶端產生數據指紋"的步驟a)的修改
aa)客戶端選擇標識符&厶Zp，並計算w^^幼,ZM,，M)e^，
7; = (W;. W )1 e G, ， i = 1,2,...,n
對"客戶端驗證數據完整性"的步驟IV)的修改 IV")計算並驗證H^河5((T，.WJ)
可選方案3:
在上述可選方案2之後，對"存檔伺服器證明數據完整性"的步 驟iii-d和"客戶端驗證數據完整性"的步驟IV)稍作修改，獲得PDI-3 方案。這是支持公共可驗證性的另一方案。
附加地，客戶端需要計算i;-^〃和^-^,作為其公鑰。
對"存檔伺服器證明數據完整性"的步驟iii-d的修改iii-ddd.計算^=[]化5 ，作為變換超塊的知識證明。
對"客戶端驗證數據完整性"的步驟IV)的修改 『')計算並驗證e(H^2)"(m).e(W^2,)。
PDI-3方案支持公共可驗證性，這是因為"存檔伺服器證明數據 完整性"和"客戶端驗證數據完整性"的任何步驟均未涉及客戶端的 秘密密鑰，從而可以由第三方驗證器有效地執行。
可選方案3.1:
對於上述可選方案3，對"客戶端驗證數據完整性"的IV"')步驟 稍作修改，產生支持驗證加速的方案。
對"客戶端驗證數據完整性"的步驟IV"')的修改
IV-f)選擇fc個隨機數^ezg^ ， it = i,2，...，^ ，計算並驗證
、jb=i ,一i '
採用可選方案3.1，客戶端驗證數據完整性所需要執行的雙線性 對計算個數得到減少。
可選方案4:
對於上述所有方案，對"客戶端產生數據指紋"的系統參數和步 驟以及"客戶端驗證數據完整性"的步驟稍作修改，產生支持採樣的 方案。
為了支持採樣，需要附加的系統參數^/6:{0,1}' —{l,2，...,n}。質詢
c/mh(^, /g還附加地包括密鑰 二Zp和正數A。
然後，對於"客戶端產生數據指紋"和"客戶端驗證數據完整性" 所有步驟，用i = p《( ，l),pr/e( 2),…,pr/6( ，A)取代所有的i = 1，2,…,n 。 因此，由於只涉及由"pr/e( ,l)，p"( ,2),…,pr/6( ,A)選擇的A個超塊，
所以只驗證所採樣的超塊的數據完整性。
所以，採用可選方案4，存檔伺服器可以不使用所有超塊來產生
30數據完整性證明。而是，客戶端的質詢向存檔伺服器通知將選擇哪些 和多少個超塊來產生證明。
可選工作模型
通過引入參考文獻4(RFC 4810)所建議的時間戳權威機構(TSA)， 可以用來自TSA的數字籤名時間戳替換質詢密鑰( , )Az/，如圖12
所示。例如，將該時間戳表示為T。使用標準哈希算法SHA-1，可以獲 得k,SHA-l(T， "1")和k,SHA-l(T， "2")。採用這種替換，客戶
端所質詢的是直到不早於由TSA發布的時間戳為止，數據是否被正 確地保持。此時，除了原子驗證過程的最後步驟(該步驟必須利用存 檔伺服器的響應，即，(Tt,H,))之外，存檔伺服器和客戶端均可以很 大程度地受益於預計算。
此外，如圖13所示，在驗證器是第三方驗證器的情況下，也可 以從TSA的時間戳推導出 和 。在能夠進行採樣的情況下，例如， 可以從TSA的時間戳推導出s為k,SHA-l(T， "3")。
硬體實現
對本領域技術人員而言，顯而易見的是本發明也可以通過硬體結 構實現。以下示出了一些示例，這些示例僅用於描述目的，而不應該 視為對本發明有任何限制。
客戶端
圖14示出了用於實現本發明的客戶端1400的框圖。這裡，客戶 端1400用作產生數據指紋的設備。
如圖14所示，客戶端1400包括超塊產生單元1410，用於將數 據劃分成W個塊M,， i = l,2，...，W,並將每 個塊組合成超塊，以得到 = ^/^個超±央；以及指紋產生單元1420，用於從有限循環群G,&〉 中選擇 個元素^， j = l,2，..., ，並通過使用針對第A超塊的定位符 R、所選的 個元素^和第一私鑰o;，分別產生第;t超塊的指紋7;， A二l,2,…,n。客戶端1400也包括存儲器1430，用於存儲由超塊產生單
31元1410和指紋產生單元1420使用或產生的信息，例如所產生的超塊、 有限循環群、所產生的指紋、定位符和私鑰。但是，本領域技術人員
必須清楚，存儲器1430可以是上述獨立的單元，或者可以是結合在超 塊產生單元1410和/或指紋產生單元1420中的一個/多個集成單元。
類似地， 個元素、可以是與第一私鑰工相對應的公鑰的一部分。 此外， 個元素~可以滿足關係 =^，。是秘密密鑰。公鑰和/或秘 密密鑰也可以存儲在存儲器1430中。
存檔伺服器
圖15示出了用於實現本發明的存檔伺服器1500的框圖。這裡， 存檔伺服器1500用作證明數據完整性的設備。
如圖15所示，存檔伺服器1500包括接收單元1510，用於接收
質詢，所述質詢至少包括第一隨機性定義密鑰 和第二隨機性定義密 鑰 ；封裝單元1520，用於構造①個盒子，所述數目①由所述質詢確 定；用於以第一隨機性定義密鑰A定義的第一隨機方式，隨機地將n個 指紋分配到所述O個盒子中，每個指紋放在一個盒子中；並用於基於 所述n個指紋的分配，產生①個封裝超塊和相應的封裝指紋；變換單 元1530，用於以由第二隨機性定義密鑰 定義的第二隨機方式，隨機 地變換所述①個封裝超塊和相應的封裝指紋，以產生變換超塊和變換 指紋；以及知識證明產生單元1540，用於產生所述變換超塊的知識證 明。存檔伺服器1500還可以包括存儲器1550，用於存儲由接收單元 1510、封裝單元1520、變換單元1530和知識證明產生單元1540使用 或產生的信息。但是，本領域技術人員必須清楚，存儲器1550可以是 上述獨立的單元，或者可以是結合在接收單元1510、封裝單元1520、 變換單元1530和知識證明產生單元1540中的一個/多個集成單元。
知識證明產生單元1540可以產生作為變換超塊本身的變換超塊 的知識證明。可選地，知識證明產生單元1540可以基於公鑰和變換超 塊而產生變換超塊的知識證明。
質詢還可以包括超塊選擇密鑰對( ,A)，用於定義將由封裝單元 1520選擇哪A個超塊和相應指紋來用於數據完整性證明，而不是所有n個超塊及相應指紋。
質詢還可以包括重複因子仏，將接收單元1510、封裝單元1520、
變換單元1530和知識證明產生單元1540的操作重複^次，每次均產 生變換超塊的一個知識證明，表示為變換超塊的第m個知識證明Hm，
m 二 1，2，...，^ 。
質詢可以包含來自時間戳權烕機構(TSA)的數字籤名時間戳。 此外，根據數字籤名時間戳產生第一和第二隨機性定義密鑰 和 以及超塊選擇密鑰 中至少一個。
此外，存檔伺服器1500還可以包括發送單元1560，用於發送變 換超塊的變換指紋和知識證明。
驗證器(客戶端或第三方驗證器)
圖16示出了用於實現本發明的驗證器1600的框圖。這裡，驗證 器1600用作驗證數據完整性的設備。對於本領域技術人員而言，顯而 易見的是驗證器1600可以是客戶端1400本身或第三方驗證器。在驗 證器1600是客戶端1400本身的前一種情況下，是指客戶端1400包括 如圖14所示的用於產生數據指紋的子系統和如圖16所示的用於驗證 數據的子系統。另一方面，在驗證器1600是第三方驗證器的後一種情 況下，是指第三方驗證器所必需的只是如圖16所示的結構，而圖14 所示的結構是可選的。
如圖16所示，驗證器1600包括質詢產生和發送單元1610，用 於產生並發送質詢，所述質詢至少包括第一隨機性定義密鑰 和第二 隨機性定義密鑰 ；接收單元1620，用於接收變換超塊的變換指紋和 知識證明；定位符封裝單元1630，用於構造O)個盒子，以所述第一隨 機方式，隨機地將"個定位符W分配到①個盒子中，每個定位符放在 一個盒子中，並基於所述n個定位符的分配，產生①個封裝定位符； 推定知識證明產生單元1640，用於以所述第二隨機方式，隨機變換所 述O個封裝定位符，以產生變換定位符，並根據所述變換指紋和所述 變換定位符，產生所述變換超塊的推定知識證明；比較器1650，用於 將所述變換超塊的推定知識證明與所接收的所述變換超塊的知識證明相比較；以及驗證單元1660，如果比較結果是肯定的，則驗證所述數 據的數據完整性。驗證器1600也可以包括存儲器1670，用於存儲由 質詢產生和發送單元1610、接收單元1620、定位符封裝單元1630、 推定知識證明產生單元1640、比較器1650和驗證單元1660使用或產 生的信息。但是，本領域技術人員必須清楚，存儲器1670可以是上述 獨立的單元，或者可以是結合在質詢產生和發送單元1610、接收單元 1620、定位符封裝單元1630、推定知識證明產生單元1640、比較器 1650和驗證單元1660中的一個/多個集成單元。
推定知識證明產生單元1640基於數據的標識符^、變換指紋和
變換定位符，產生變換超塊的推定知識證明。
推定知識證明產生單元1640還基於第一和第二私鑰:r和》產生所 述變換超塊的推定知識證明。
由質詢產生和發送單元1610產生的質詢還包括超塊選擇密鑰對 K,A)，用於定義將由定位符封裝單元1630選擇哪A個定位符來用於 數據完整性證明，而不是所有n個定位符。
由質詢產生和發送單元1610產生的質詢還包括重複因子^，將定 位符封裝單元1630、推斷知識證明產生單元1640和比較器1650的操 作重複W次，僅當所有比較結果均為肯定的時，驗證單元1660才驗證 所述數據完整性。
由質詢產生和發送單元1610產生的質詢包含來自時間戳權威機 構(TSA)的數字籤名時間戳。
由質詢產生和發送單元1610根據所述數字籤名時間戳來確定第 一和第二隨機性定義密鑰 和 以及超塊選擇密鑰 中至少一個。
以上描述僅給出了本發明的優選實施例，而並不是要以任何方式 限制本發明。因此，在本發明精神和原理內進行的任何修改、替換、 改進等應該由本發明範圍所涵蓋。
權利要求
1. 一種產生數據指紋的方法，包括步驟將數據劃分成N個塊Mi，i＝1，2，...，N；將每nB個塊組合成超塊，以得到個超塊；從有限循環群中選擇nB個元素hj，j＝1，2，...，nB；通過使用針對第k超塊的定位符Wk、所選的nB個元素hj和第一私鑰x，分別產生第k超塊的指紋Tk，k＝1，2，...，n。
2. 根據權利要求1所述的產生數據指紋的方法，其中所述 個 元素^是與第一私鑰^相對應的公鑰的一部分。
3. 根據權利要求1所述的產生數據指紋的方法，其中所述 個 元素~滿足關係~=^，。是秘密密鑰。
4. 根據權利要求l所述的產生數據指紋的方法，其中根據formula see original document page 2產生第A超塊的指紋j;, ZM是所述數據的標識符。
5. 根據權利要求4所述的產生數據指紋的方法，其中第yt超塊的 定位符^是至少以&為輸入的哈希值。
6. 根據權利要求l所述的產生數據指紋的方法，其中根據formula see original document page 2產生第^超塊的指紋7;。
7. 根據權利要求6所述的產生數據指紋的方法，其中第)t超塊的 的定位符^是至少以yt和所述數據的標識符ZM為輸入的哈希值。
8. 根據權利要求5或7所述的產生數據指紋的方法，其中第;t超塊的定位符K還包括針對所述數據的數據文件名和/或數據版本號。
9. 根據權利要求4或7所述的產生數據指紋的方法，其中所述 標識符^根據所述數據的不同而不同。
10. —種證明數據的數據完整性的方法，其中採用根據權利要求1 9之一所述的產生數據指紋的方法產生所述數據的指紋，所述方法 包括步驟接收質詢，所述質詢至少包括第一隨機性定義密鑰 和第二隨機性定義密鑰 ；構造d)個盒子；以第一隨機性定義密鑰 定義的第一隨機方式，隨機地將n個指紋分配到所述①個盒子中，每個指紋放在一個盒子中；基於所述n個指紋的分配，產生d)個封裝超塊和相應的封裝指紋； 以由第二隨機性定義密鑰 定義的第二隨機方式，隨機地變換所述O個封裝超塊和相應的封裝指紋，以產生變換超塊和變換指紋；以及產生所述變換超塊的知識證明。
11. 根據權利要求10所述的證明數據完整性的方法，其中所述 變換超塊的知識證明是所述變換超塊本身。
12. 根據權利要求10所述的證明數據完整性的方法，其中所述 變換超塊的知識證明是基於所述公鑰和所述變換超塊而產生的。
13. 根據權利要求12所述的證明數據完整性的方法，其中變換 超塊的知識證明H表示為Tl醜& =》是第二私鑰，A是變換超塊。
14. 根據權利要求12所述的證明數據完整性的方法，其中變換 超塊的知識證明H表示為& = 》是第二私鑰，A是變換超塊，p&(.)表示偽隨機函數。
15. 根據權利要求10所述的證明數據完整性的方法，其中所述 質詢還包括超塊選擇密鑰對K,A)，用於定義將選擇哪A個超塊和相應指紋來用於數據完整性證明，而不是所有"個超塊及相應指紋。
16. 根據權利要求10所述的證明數據完整性的方法，其中所述質詢還包括重複因子^，將從構造盒子到產生知識證明的歩驟裡復^ 次，每次均產生變換超塊的一個知識證明，表示為變換超塊的第m個 知識證明Hm， m = l，2，...,V>。
17. 根據權利要求16所述的證明數據完整性的方法，其中所述 數目0等於2-， 0 =卩/^ + 1， Z是安全級別因子，用於確定所述方法的安全級別。
18. 根據權利要求10所述的證明數據完整性的方法，其中由驗 證器選擇第一和第二隨機性定義密鑰 和 以及超塊選擇密鑰對 (k3,A)。
19. 根據權利要求10所述的證明數據完整性的方法，其中所述 質詢包含來自時間戳權威機構TSA的數字籤名時間戳。
20. 根據權利要求19所述的證明數據完整性的方法，其中根據 所述數字籤名時間戳產生第一和第二隨機性定義密鑰 和 以及超塊 選擇密鑰 中至少一個。
21. 根據權利要求10所述的證明數據完整性的方法，還包括發 送變換超塊的變換指紋和知識證明。
22. —種與根據權利要求10 21之一所述的證明數據完整性的 方法相結合的、驗證數據完整性的方法，其中採用根據權利要求1 9 之一所述的產生數據指紋的方法產生所述數據的指紋，所述方法包括 步驟產生並發送質詢，所述質詢至少包括第一隨機性定義密鑰 和第 二隨機性定義密鑰^;接收變換超塊的變換指紋和知識證明； 構造①個盒子；以所述第一隨機方式，隨機地將"個定位符^分配到①個盒子中，每個定位符放在一個盒子中；基於所述"個定位符的分配，產生①個封裝定位符； 以所述第二隨機方式，隨機變換所述O個封裝定位符，以產生變換定位符；根據所述變換指紋和所述變換定位符，產生所述變換超塊的推定知識證明；將所述變換超塊的推定知識證明與所接收的所述變換超塊的知 識證明相比較；以及如果比較結果是肯定的，則驗證所述數據的數據完整性。
23. 根據權利要求22所述的驗證數據完整性的方法，其中基於 所述數據的標識符ZM、所述變換指紋和所述變換定位符產生所述變換超塊的推定知識證明。
24. 根據權利要求23所述的驗證數據完整性的方法，其中還基 於第一和第二私鑰r和》產生所述變換超塊的推定知識證明。
25. 根據權利要求24所述的驗證數據完整性的方法，其中所述 變換超塊的推定知識證明表示為F/5((，W,)T表示變換指紋，W表示變換定位符；並且第&超塊的定位符K是至少以*和所述數據的標識符&為輸入的哈希值。
26. 根據權利要求25所述的驗證數據完整性的方法，其中第^t超塊的定位符^還包括針對所述數據的數據文件名和/或數據版本號。
27. 根據權利要求22所述的產生數據指紋的方法，其中所述標識符zM根據所述數據的不同而不同。
28. 根據權利要求24所述的驗證數據完整性的方法，其中所述 變換超塊的推定知識證明表示為T表示變換指紋，W表示變換定位符；並且第)t超塊的定位符^是至 少以/t為輸入的哈希值。
29. 根據權利要求28所述的驗證數據完整性的方法，其中第A超塊的定位符^還包括針對所述數據的數據文件名和/或數據版本號。
30. 根據權利要求23所述的驗證數據完整性的方法，其中所述變換超塊的推定知識證明產生為e(T，VO.e(W,i)(52〉是在^=^〉的情況下、具有p是大質數；g，附加群《=〈^)的有限循環群，以使' e:glxg2—S是雙線性映射函數；T表示變換指紋，W表示變換定位 符；第it超塊的定位符R是至少以/t為輸入的哈希值；i和》是第一和 第二私鑰；如下將所述變換超塊的推定知識證明與所述變換超塊的知識證 明相比較，e(H,&):e(T,i;,/M).e(W,^) H表示所述變換超塊的知識證明。
31. 根據權利要求30所述的驗證數據完整性的方法，其中第A超塊的定位符^還包括針對所述數據的數據文件名和/或數據版本號。
32. 根據權利要求30所述的驗證數據完整性的方法，其中所述 質詢還包括快驗證因子^，並選擇&個隨機數r; eZ;Zp， & = 1,2，...一，計算並驗證fc=lifc=l
33.根據權利要求23所述的驗證數據完整性的方法，其中所述 變換超塊的推定知識證明產生為乖~ = <， y = ^e(G2; G2-〈^〉是在g,〈^〉的情況下.有附加群9 =〈》的有限循環群，以使^卜Ig"二^I:p， p是大質數； e:glx(g2 —G是雙線性映射函數；T表示變換指紋，W表示變換定位 符；第^超塊的定位符^是至少以A和所述數據的標識符^為輸入的 哈希值；^和<9是第一和第二私鑰；如下將所述變換超塊的推定知識證明與所述變換超塊的知識證 明相比較，e(H,&)"(T，i;).e(W,^) H表示所述變換超塊的知識證明。
34.根據權利要求33所述的驗證數據完整性的方法，其中第A超 塊的定位符^還包括針對所述數據的數據文件名和/或數據版本號。
35. 根據權利要求33所述的產生數據指紋的方法，其中所述標 識符^根據所述數據的不同而不同。
36. 根據權利要求33所述的產生數據指紋的方法，其中所述質 詢還包括快速驗證因子^，並選擇&個隨機數^eZ;Zp， A; = 1,2,...，^，計算並驗證
37. 根據權利要求22所述的驗證數據完整性的方法，其中所述 質詢還包括超塊選擇密鑰對( ,A)，用於定義將選擇哪A個定位符來用 於數據完整性證明，而不是所有w個定位符。
38. 根據權利要求22所述的驗證數據完整性的方法，其中所述 質詢還包括重複因子^，將從構造盒子到比較知識證明和推定知識證 明的步驟重複仏次，僅當所有比較結果均為肯定的時，才驗證所述數 據的數據完整性。
39. 根據權利要求22所述的驗證數據完整性的方法，其中由驗 證器選擇第一和第二隨機性定義密鑰 和 以及超塊選擇密鑰對 K,A)。
40. 根據權利要求22所述的驗證數據完整性的方法，其中所述 質詢包含來自時間戳權威機構TSA的數字籤名時間戳。
41. 根據權利要求40所述的驗證數據完整性的方法，其中根據 所述數字籤名時間戳產生第一和第二隨機性定義密鑰 和 以及超塊 選擇密鑰 中至少一個。
42. —種用於產生數據指紋的設備，包括超塊產生單元，用於將數據劃分成iV個塊M,， z = l，2,...,iV，並將 每 個塊組合成超塊，以得到n-「V/ ，個超塊；以及指紋產生單元，用於從有限循環群^—^中選擇 個元素^， j = l，2，...,ns ，並通過使用針對第;t超塊的定位符^ 、所選的 個元素^ 和第一私鑰i，分別產生第it超塊的指紋 ;， fc = l,2,...，n。
43. 根據權利要求42所述的產生數據指紋的設備，其中所述r^個 元素^是與第一私鑰x相對應的公鑰的一部分。
44. 根據權利要求42所述的產生數據指紋的設備，其中所述 個 元素~滿足關係~=&， r;.是秘密密鑰。
45. —種用於證明數據完整性的設備，包括接收單元，用於接收質詢，所述質詢至少包括第一隨機性定義密鑰 和第二隨機性定義密鑰 ；封裝單元，用於構造①個盒子；用於以第一隨機性定義密鑰 定 義的第一隨機方式，隨機地將"個指紋分配到所述①個盒子中，每個指紋放在一個盒子中；並用於基於所述"個指紋的分配，產生O個封 裝超塊和相應的封裝指紋；變換單元，用於以由第二隨機性定義密鑰/S定義的第二隨機方式， 隨機地變換所述O)個封裝超塊和相應的封裝指紋，以產生變換超塊和 變換指紋；以及知識證明產生單元，用於產生所述變換超塊的知識證明。
46. 根據權利要求45所述的證明數據完整性的設備，其中所述 知識證明產生單元產生作為所述變換超塊本身的所述變換超塊的知識 證明。
47. 根據權利要求45所述的證明數據完整性的設備，其中所述 知識證明產生單元基於所述公鑰和所述變換超塊而產生所述變換超塊 的知識證明。
48. 根據權利要求45所述的證明數據完整性的設備，其中所述 質詢還包括超塊選擇密鑰對( ，A)，用於定義將由所述封裝單元選擇哪 A個超塊和相應指紋來用於數據完整性證明，而不是所有n個超塊及 相應指紋。
49. 根據權利要求45所述的證明數據完整性的設備，其中所述 質詢還包括重複因子仏，將所述封裝單元、變換單元和知識證明產生 單元的操作重複^次，每次均產生變換超塊的一個知識證明，表示為 變換超塊的第w個知識證明H一 m = l,2，...^。
50. 根據權利要求45所述的證明數據完整性的設備，其中所述 質詢包含來自時間戳權威機構TSA的數字籤名時間戳。
51. 根據權利要求50所述的證明數據完整性的設備，其中根據所述數字籤名時間戳產生第一和第二隨機性定義密鑰 和/s以及超塊 選擇密鑰 中至少一個。
52. 根據權利要求45所述的證明數據完整性的設備，還包括 發送單元，用於發送變換超塊的變換指紋和知識證明。
53. —種用於驗證數據完整性的設備，包括質詢產生和發送單元，用於產生並發送質詢，所述質詢至少包括第一隨機性定義密鑰 和第二隨機性定義密鑰 ；接收單元，用於接收變換超塊的變換指紋和知識證明； 定位符封裝單元，用於構造①個盒子，以所述第一隨機方式，隨機地將n個定位符K分配到O)個盒子中，每個定位符放在一個盒子中，並基於所述n個定位符的分配，產生O)個封裝定位符；推定知識證明產生單元，用於以所述第二隨機方式，隨機變換所述cD個封裝定位符，以產生變換定位符，並根據所述變換指紋和所述變換定位符，產生所述變換超塊的推定知識證明；比較器，用於將所述變換超塊的推定知識證明與所接收的所述變換超塊的知識證明相比較；以及驗證單元，如果比較結果是肯定的，則驗證所述數據的數據完整性。
54. 根據權利要求53所述的驗證數據完整性的設備，其中所述 推定知識證明產生單元基於所述數據的標識符^ 、所述變換指紋和所述變換定位符產生所述變換超塊的推定知識證明。
55. 根據權利要求54所述的驗證數據完整性的設備，其中還基 於第一和第二私鑰:r和"產生所述變換超塊的推定知識證明。
56. 根據權利要求53所述的驗證數據完整性的設備，其中由所 述質詢產生和發送單元產生的所述質詢還包括超塊選擇密鑰對K,A)， 用於定義將由所述定位符封裝單元選擇哪A個定位符來用於數據完整 性證明，而不是所有n個定位符。
57. 根據權利要求53所述的驗證數據完整性的設備，其中由所 述質詢產生和發送單元產生的所述質詢還包括重複因子W ，將所述定 位符封裝單元、推斷知識證明產生單元和比較器的操作重複W次，僅當所有比較結果均為肯定的時，驗證單元才驗證所述數據完整性。
58. 根據權利要求53所述的驗證數據完整性的設備，其中由所述質詢產生和發送單元產生的所述質詢包含來自時間戳權烕機構TSA的數字籤名時間戳。
59. 根據權利要求58所述的驗證數據完整性的設備，其中所述質詢產生和發送單元根據所述數字籤名時間戳來確定第一和第二隨機 性定義密鑰 和/s以及超塊選擇密鑰 中至少一個。
60. —種數據完整性驗證系統，包括根據權利要求45-52之一所述的用於證明數據完整性的設備；以及根據權利要求53-59之一所述的用於驗證數據完整性的設備。
61. 根據權利要求60所述的數據完整性驗證系統，還包括-根據權利要求42-44之一所述的用於產生數據指紋的設備。
62. 根據權利要求61所述的數據完整性驗證系統，其中用於產 生數據指紋的設備也用作用於驗證數據完整性的設備。
全文摘要
本發明提出了一種可證數據完整性(PDI)驗證方法，其中首先在客戶端側產生數據的數字指紋，將指紋與數據一併發送至存檔伺服器；當需要時，客戶端或第三方驗證器向該存檔伺服器發送「質詢」，以確定數據的完整性，該存檔伺服器通過使用接收到的指紋來證明數據的完整性；最後，客戶端或第三方驗證器根據來自存檔伺服器的響應該「質詢」的輸出，驗證數據的完整性。具體地，在本發明中，分別提出了一種產生數據指紋的方法和設備、一種證明數據的數據完整性的方法和設備、以及一種驗證數據完整性的方法和設備。
文檔編號H04L9/32GK101471779SQ20081016586
公開日2009年7月1日 申請日期2008年9月25日 優先權日2007年12月29日
發明者珂 曾 申請人:日電(中國)有限公司