基於辮群的傳遞數字籤名的方法和系統的製作方法

2023-06-19 19:17:16

專利名稱：基於辮群的傳遞數字籤名的方法和系統的製作方法
技術領域：
本發明總體上涉及用於數據傳輸的安全通信中的信任鏈管理的方法和系 統。更具體地說，本發明涉及使用辮群作為底層數學平臺建立傳遞數字籤名 系統進而實現信任鏈管理的方法和系統。
背景技術：
傳遞籤名是由Micali和Rivest1]在2002年首先提出的，主要用於對具 有傳遞性的二元關係進行高效籤名。籤名的傳遞代表的是信任關係的傳遞， 因而，傳遞籤名在與信任鏈管理有關的軍事、政治和經濟等領域都有重要應 用["3]。傳遞籤名一經提出，立刻引起了許多研究人員的關注，經過Micali、 Rivest[1]、 BellareP'"等密碼學家W,的努力，現在人們已經知道了如何基於大 整數分解難題(IFP ， Integer Factoring Problem ) [2'3]、離散對數難題(DLP, Discrete Logarithm Problem ) [1]以及與雙線性配對(Bilinear Pairings )有關的密碼學難題假設[7]來實現傳遞籤名。然而，在量子計算環境下，上述難題均是可以在多項式時間複雜度和多項式空間複雜度之內被解決的[11];也就是說，上述傳遞籤名體制在量子計算 環境下均是不安全的。因此，我們認為有必要基於新的可以抵抗量子攻擊的——至少可以抵抗已知量子攻擊的-公鑰密碼學平臺來重新設計傳遞籤名。為了增強公鑰密碼體制在量子計算環境下的安全性，人們已經提出了 一 些新的公鑰密碼學平臺，其中包括基於辮群等非交換群上的一些公鑰密碼系 統。辮群密碼系統最早是由韓國的Ko等人於2000年提出的問，雖然至今已 經發展了 6、 7年，但是具有可證安全性的密碼體制並不多。第一個基於辮群 的數字籤名系統也是由Ko等人於2002年提出的問；在這之後，雖然也有人 對該體制提出了改進[14],甚至也申請了專利[15],但是都沒有嚴格的可證明安 全性規約。直到最近，才有人針對該籤名體制(以及後來的改進體制)，給出
了可證明安全性規約[16]。正是在這樣的背景下，我們提出本發明。旨在基於辮群實現安全的傳遞 數字籤名系統。上述引用的文獻如下[1] S. MicaliandR. L. Rivest， Transitive signature schemes. InB. Preneel (Ed. ): CT-RSA2002, LNCS 2271, pp. 236-243， Springer-Verlag, 2002[2] M. Bellare and G. Neven, Transitive signatures based on factoring and RSA. InY. Zheng (Ed. ): ASIACRYPT 2002, LNCS 2501, pp. 397~414, Springer-Verlag, 2002[3] M. Bellare and G. Neven, Transitive signatures: New schemes and proofs. IEEE Transactions on Information Theory, Vol. 51 ， No. 6， pp. 2133-2151, J薦2005[4]黃振傑，郝豔華，王育民，陳克非. 一個高效的有向傳遞籤名方案， 電子學報，第33巻第8期，第1497-1501頁，2005年8月[5] H. Kuwakado, H. Tanaka. Transitive Signature Scheme for Directed Trees. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol. E86-A, No. 5, pp. 1120-1126, May 2003[6] C. Ma， P. Wu, andG. Gu. A New Method for the Design of Stateless Transitive Signature Schemes. In H. T. Shen et al. (Eds. ): APWeb Workshops 2006, LNCS 3842, pp. 897-904, Springer-Verlag, 2006[7] S. F. Shahandashti, M. Salmasizadeh, J. Mohajeri. A provably secure short transitive signature scheme from bilinear group Pairs. In C. Blundo and S. Cimato(Eds. ):SCN2004, LNCS 3352， pp. 60—76, Springer-Verlag, 2005[8] X. Yi. Directed transitive signature scheme. In CT-RSA，07， LNCS 4377, pages 129—144. Springer-Verlag Berlin Heidelberg, 2007[9] X. Yi, C. -H. Tan, E. Okamoto. Security of Kuwakado-Tanaka transitive signature scheme for directed trees. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol. E87-A, No. 4, pp. 955-957, April 2004[10] H. Zhu. Model for undirected transitive signatures. IEE Proceedings: Communications Vol. 151, No. 4, pp. 312-315, August 2004[11] P. Shor. Polynomial-time algorithms for prime factorization and discretelogarithms on a quantum computer. SIAM J. Comput. 5 (1997): 1484-1509 [12] K. H. Ko， S. J. Lee, J. H. Cheon, and J. W. Han. New public-keycryptosystem using braid groups. In CRYPTO 2000, LNCS 1880, pages166—183. Springer-Verlag Berlin Heidelberg, 2000[13] K. H. Ko, D. H. Choi, M. S. Cho, and J. W. Lee. New signaturescheme using conjugacy problem. Preprint, http: 〃eprint. iacr. org/2002/168，2002[14] 丁勇，田海博，王育民. 一種改進的基於辮群的數字籤名體制.西 安電子科技大學學報，第33巻第1期，第50-61頁，2006年2月[15] 丁勇，陳劍勇，李亞暉. 一種基於辮群共軛問題的數字籤名方法， 中國專利申請號200310113604;公開號1545242;
公開日20041110[16] L. Wang, Z. Cao， P. Zeng, andX. Li. One-more matching conjugate problem and security of braid-based signatures. In ASIACCS,07 , pages 295-301. ACM, March 2007發明內容本發明優選實施方式提供了基於辮群的傳遞數字籤名方法和系統，其中 用基於辮群的籤名方案代替了傳統傳遞籤名中的普通籤名，以便所產生的籤 名能抵抗已知的量子分析，因而更加安全。根據本發明的一個方面，提供一種基於辮群的傳遞數字籤名系統，包括 密鑰生成模塊，用於根據系統安全性要求選擇系統參數，根據系統參數確定 辮群，並根據所選擇的系統參數和所述辮群生成籤名私鑰和相應的驗證籤名 的公鑰，其中，所述系統參數包括辮群的辮指數"、工作辮子的長度規模、 由欲籤名的消息的二元組所構成的消息空間以及用來為消息空間中的消息而 在所述辮群中選擇籤名辮子的哈希函數；籤名辮子生成模塊，用於根據共軛 操作和所述密鑰生成模塊生成的私鑰，將該哈希函數應用到消息空間中欲籤 名的表示成二元組的消息來在所述辮群中選擇相應籤名辮子，並將欲籤名的 消息與其籤名辮子組合成該消息的完整的籤名；以及籤名合成模塊，用於根據所述籤名辮子生成模塊所生成的至少兩個消息的籤名和公鑰，合成第三消
息的籤名辮子。根據本發明的另一方面，提供一種基於辮群的傳遞數字籤名方法，該方法包括步驟根據系統安全性要求選擇系統參數，根據系統參數確定辮群， 並根據所選#^的系統參數和所述辮群生成籤名私鑰和相應的驗證籤名的公 鑰，其中，所述系統參數包括辮群的辮指數w、工作辮子的長度規模、由欲 籤名的消息的二元組所構成的消息空間以及用來為消息空間中的消息而在所 述辮群中選擇籤名辮子的哈希函數；根據共軛操作和所生成的私鑰，將該哈 希函數應用到消息空間中欲籤名的表示成二元組的消息來在所述辮群中選擇 相應籤名辮子，並將欲籤名的消息與其籤名辮子組合成該消息的完整的籤名； 以及根據至少兩個消息及其所生成的籤名和公鑰，合成第三消息的籤名辮子。根據本發明的再一方面，提供一種計算機產品，其上實施有基於辮群的 傳遞數字籤名方法的程序，該方法包括步驟根據系統安全性要求選擇系統 參數.，根據系統參數確定辮群，並根據所選擇的系統參數和所述辮群生成籤 名私鑰和相應的驗證籤名的公鑰，其中，所述系統參數包括辮群的辮指數w、 工作辮子的長度規模、由欲籤名的消息的二元組所構成的消息空間以及用來 為消息空間中的消息而在所述辮群中選擇籤名辮子的哈希函數；根據共軛操 作和所生成的私鑰，將該哈希函數應用到消息空間中欲籤名的表示成二元組 的消息來在所述辮群中選4奪相應籤名辮子，並將名夂籤名的消息與其籤名辮子 組合成該消息的完整的籤名；以及根據至少兩個消息及其所生成的籤名和公 鑰，合成第三消息的籤名辮子。本發明與已有成果相比，有如下突出特點 一是與已發表的傳遞籤名方 案相比，本發明有望抵抗已知的量子分析，因而更加安全，而已發表的傳遞 籤名所基於的數論難題在量子計算環境下都是可以高效求解的，因而是不安 全的；二是與已有的基於辮群的籤名方案或專利相比，本發明適合傳遞籤名 的應用場景。傳遞籤名往往包含了一個普通籤名在內，作為節點證書的籤名 方案，但是普通籤名無法代替傳遞籤名，傳遞籤名比普通籤名有更多的屬性 和要求，因此，已有的普通籤名方案和專利不能取代本發明。


通過結合附圖參照下面的詳細描述，本發明的上述和其它目的、特徵和 優點將變得更加清楚，其中
圖1圖解根據本發明優選實施方式的基於辮群的傳遞數字籤名系統示意圖；圖2是圖解根據本發明的密鑰生成模塊的方框圖； 圖3是圖解籤名辮子生成模塊的詳細結構的方框圖； 圖4是圖解根據本發明的籤名合成模塊的結構的方框圖； 圖5是圖解籤名驗證模塊的結構的方框圖；以及 圖6圖解根據本發明優選實施方式的基於辮群的傳遞數字籤名方法的流 程圖。
具體實施方式
為使本發明的目的、技術方案和優點更加清楚，下面將結合附圖對本發 明實施方式作進一步地詳細描述。應該理解，本發明可以用其他不同的實施 方式來實現，而不應當限於這裡所描述的實施方式。事實上，提供下述實施 方式只是為了全面和完整地將本發明的範圍傳達給本領域的普通技術人員。另外，在所有附圖中相同的附圖參考標記指示相同的組成部分、特徵和 結構。此外，以下的詳細描述中還將省略在這裡結合的公知功能和配置的描 述，因為它可能混淆本發明。本發明優選實施方式提供了基於辮群的傳遞數字籤名方法和系統，本發 明基於共軛搜索問題(CSP, Conjugator Search Problem)進行傳遞數字籤名， 以增強籤名的安全性。所謂共軛搜索問題是指給定兩個辮子/7e^和^A,其中《是;？關於某個辮子^A的共軛，即《=s"jm (其中s被稱為p和《的共軛子， 一般是未 公開的，用作用戶私鑰)，求某個辮子/^A,使得r也是p和g的共軛子(不要求r一定等於"，用公式表述為這裡，辮群A通常由如下群表示方法來定義formula see original document page 10其中每個q稱為Artin生成子，w被稱為辮指數。如果將每個a,及其逆(記為《1 )都看作是字母，則由這2("-l)個字母構成字母表，那麼定義在該字母表上的任何字都稱為辮子。辮子的長度定義為 辮子所包含的生成子的個數，例如，辮子cr"3的長度等於2。 一般情況下，可以通過限定辮子的長度規模來規定所使用的辮子長度特性。
規定長度為零的空串就是辮群的單位元(Identity,也稱么元)，辮子和辮子之間的乘法就定義為字的連接。例如q《1 和C72CT3相乘的結果就是 c^cr^c^ cr2(T3 ， 而c^crjVj和CTiCrf1相乘的結果貝'J是CTiCT「c^ (因為o^cr^o^ o^o^1 =下面首先根據圖l描述本優選實施方式的、基於辮群的傳遞數字籤名系 統。圖1圖解了根據本發明的優選實施方式的、基於辮群的傳遞數字籤名系 統的框圖。參考圖1,根據本發明優選實施方式的基於辮群的傳遞數字籤名系統包括密鑰生成模塊101、籤名辮子生成模塊102、籤名合成模塊103和 籤名驗證模塊104。該密鑰生成模塊101用於根據系統安全性要求選擇系統參數，並根據所 選擇的系統參數生成籤名私鑰和相應的驗證籤名的公鑰。圖2是圖解根據本 發明的密鑰生成模塊101的方框圖。參考圖2，密鑰生成模塊101包括系統 參數選擇單元201、辮子選擇單元203、辮子獲取單元205和密鑰生成單元 207。系統參數選擇單元201根據系統安全性要求選擇合適的系統參數。這些 參數主要包括辮群的辮指數"，工作辮子的長度規模，消息空間，籤名空間， 籤名中所需要的哈希函數等等。具體來說，首先，系統參數選擇單元201根據系統安全性要求選擇w為 系統安全參數，以便以"為辮指數構造辮群5 。在該傳遞籤名系統中，為了方便和簡化計算的目的，所有工作辮子均來自於辮群A,並且規定工作辮子的(自然)長度(即所包含的生成子的個數)的規模為(9("2)。本領域技術人員應該清楚，工作辮子的長度規模可以選擇為其他值。根據本發明的優選實施方式，建議選擇w至少為16,此時本發明的安全 級別至少為2，。而工作辮子的長度應該選擇在162=256左右。下面為了舉例 的方便，我們取w為5，而且工作辮子辮子的長度也不超過10。其次，系統參數選擇單元201根據所指定的辮指數w和工作辮子的長度 規模構造消息空間和籤名空間。構造消息空間和籤名空間的具體過程如下 將每個待籤名的消息對應為一條無向邊，將該無向邊的兩個頂點編號，例如，每個頂點可以編號為一個自然數。因此， 一條消息與該消息對應的無向邊的 兩個頂點的編號組成的二元組——對應。在這種情況下，消息空間可以看作 是可能的無向邊的集合，並由二元組進行表示。在具有m個頂點的情況下，
消息空間中含有m (m-l) /2條無向邊。將每條邊的籤名作為一個辮子，故籤名空間也可以看作是辮群5 。然後，選擇哈希函數Z/: iV今^作為單向Hash函數，用來把頂點編號映射為隨機辮 子，這裡7V表示自然數集合。需要注意的是，這裡是以自然數作為消息空間 的無向邊的頂點的編號為例來選擇哈希函數的，實際上哈希函數不限於這裡 所述的形式，比如集合可以換成用來對消息空間的無向邊的頂點進行編號 的其他集合。接下來，辮子選擇單元203從系統參數選擇單元201所確定的辮群S"中 隨機選擇兩個辮子，分別記為第一辮子『和第二辮子凡然後，辮子獲取單元205將辮子選擇單元203所選擇的第一辮子『作為 共軛子，根據該共軛子獲取與第二辮子P共軛的第三辮子2,這裡可以通過 g =礦;屍『計算得到。然後，密鑰生成單元207將辮子選擇單元203所選才傘的第一辮子『作為 私鑰，得到籤名私鑰sk =『，而將辮子選擇單元203所選^^的第二辮子P和 辮子獲取單元205獲取的第三辮子g作為相應的驗證籤名的公鑰pk =(屍， 0。例如，當取"=5時，假設隨機選擇的第一辮子f^qc^Aav^o"^,第 二辮子戶= ，則第三辮子formula see original document page 12回到圖1,根據本發明優選實施方式的基於辮群的傳遞數字籤名系統中 的籤名辮子生成模塊102根據共軛操作和密鑰生成模塊101生成的籤名私鑰 sk=『，對欲籤名的消息(即邊)進行計算，以生成籤名辮子。然後，籤名辮 子生成模塊102將欲籤名的消息與所獲得的關於該消息的籤名辮子組合成該 消息的完整籤名。圖3是圖解籤名辮子生成模塊102的詳細結構的方框圖。參考圖3,該 籤名辮子生成模塊102包括消息辮子對生成單元301、中間辮子生成單元303 和籤名辮子生成單元305。消息辮子對生成單元301用於對欲籤名的消息，即邊的兩個頂點，進行 哈希運算，得到消息辮子對。例如，根據本發明的優選實施方式，如果將對
應於欲籤名的消息的邊(/， y)的兩個頂點設為/和力則進行哈希運算得到消息辮子對，(6產即),6廣H(/))。然後，中間辮子生成單元303將消息辮子對生成單元301生成的消息辮 子對中的第一辮子與第二辮子的逆辮子進行乘積運算，得到中間辮子。具體 來說，對於本實施方式，將消息辮子對中的第一辮子6,乘以消息辮子對的第 二辮子、.的逆辮子6/1，得到中間辮子，即6,6/、籤名辮子生成單元305將辮子選擇單元203中選擇的第一辮子作為共軛 子，獲取與中間辮子生成單元303生成的中間辮子共軛的籤名辮子。具體來 說，根據本發明的一個優選實施方式，將辮子選擇單元203所選擇的第一辮 子『(即籤名私鑰)作為共軛子，獲取與中間辮子6 6/共軛的籤名辮子，即 W『fT16》/1『。然後，通過將要籤名的消息與所述籤名辮子組合起來得到完整 的籤名。在才艮據本發明的優選實施方式中，所述消息表示為邊(,'，力，而所述 籤名辮子為i 『^T16》/1『，因此，得到該消息的完整籤名(/, i 》。例如，假設待籤名的邊為(1， 2),並且假設formula see original document page 13則中間辮子為formula see original document page 13, 籤名辨子貝'j為再回到圖1,籤名合成模塊103根據籤名辮子生成模塊102生成的兩個 共享頂點的消息的籤名，合成新消息的籤名。圖4是圖解根據本發明的籤名 合成模塊103的結構的方框圖。參考圖4，該籤名合成才莫塊103包括籤名驗 證單元401和籤名合成單元403。這裡，籤名驗證單元401用於調用將在以下詳細描述的籤名驗證模塊104來判斷待合成的兩個籤名是否有效。如果待合成的兩個籤名中任何一個無效， 則拒絕合成並輸出無效標誌。如果待合成的兩個籤名中每一個都有效，則執行調用籤名合成單元403 的操作。籤名合成單元403用於把待合成的兩個籤名相乘，得到並輸出合成 後的籤名辮子。具體來說，根據本發明的優選實施方式，共享頂點信息的兩 個消息設為邊(/,力和(/, 它們共享頂點)的所述籤名(/, 乂， 和(y, A:， 《J和所述公鑰(屍，0),合成第三個消息即邊(/， Q的籤名，該籤名為O', h 其中凡屍iV^，即對應兩個籤名辮子相乘。 在本發明中，合成籤名時所述公鑰並未使用，這跟傳遞籤名的定義並不名的合成。而一般地，公鑰作為公開信息，是人人可獲得的，使用與否無關 緊要。本發明中，只要獲得了共享頂點信息的兩個消息的所述籤名，人人均 可合成新的籤名，故功能上完全符合傳遞籤名的定義。例如，假設共享頂點信息的兩條邊為邊(1， 2)和邊(2, 3)，即他們共 享頂點2，假設他們各自的籤名分別為i 12=(Ti W ^^10^ 1 "4"3^V。3 ^々1 "3 1 。3 "4 1 "3 1 。i 1<:1" 3則，它們合成後的籤名為再回到圖1,籤名驗證模塊104根據消息(即邊)及其籤名辮子和公鑰， 判斷該籤名辮子是否為該消息(即邊)的有效籤名。圖5圖解了籤名驗證模塊104的結構。參考圖5,該驗證模塊包括消息 辮子對生成單元501、中間辮子生成單元503、第一中間辮子生成子單元505、 第二中間辮子生成子單元507、第三中間辮子生成子單元509以及籤名驗證 單元511。在本發明的驗證模塊中，消息辮子對生成單元501將本模塊中輸入的欲 驗證籤名的消息(即邊的兩個頂點)進行哈希運算得到消息辮子對。具體來 說，在根據本發明的優選實施方式中，消息辮子對生成單元401將籤名(/, 乂， i 》和所述公鑰(戶，g)作為輸入，先計算兩個辮子6屍H(/)和6廣H(/)。然後，中間辮子生成單元503根據消息辮子對生成單元501所計算出來 的辮子對，生成籤名驗證所需要的中間辮子。在根據本發明的實施方式中，中 間辮子生成單元503根據消息辮子對生成單元501所計算出來的辮子對6產H(/) 和6廣H(/),計算三個中間辮子C屍Z)》/1、 C2=2i^.、 C產PC"中間辮子生成單元503可分為以下三個子單元第一中間辮子生成子單 元505、第二中間辮子生成子單元507和第三中間辮子生成子單元509。第一中間辮子生成子單元505將本模塊中消息辮子對生成單元503所生 成的第一辮子與第二辮子的逆辮子進行乘積運算，得到第一中間辮子。在根 據本發明的優選實施方式中，第一中間辮子生成子單元505計算中間辮子 C產6,力/作為第一中間辮子。
第二中間辮子生成子單元507將密鑰生成模塊101的辮子獲取單元205 所獲取的第三辮子和本模塊中輸入的籤名辮子進行乘積運算，得到第二中間 辮子。在根據本發明的優選實施方式中，第二中間辮子生成子單元507根據 辮子獲取單元205獲取的第三辮子g與輸入的籤名辮子計算C2=2&*為 第二中間辮子。第三中間辮子生成子單元509將密鑰生成模塊101的辮子選擇單元203 所選擇的第二辮子和所述第 一 中間辮子進行乘積運算，得到第三中間辮子。 在根據本發明的優選實施方式中，第三中間辮子生成子單元509根據辮子選 擇單元203獲取的第二辮子P與第 一中間辮子戶計算C屍屍d作為第三中間辮子。然後，籤名驗證單元511判斷本模塊所輸入的籤名辮子是否和所述第一 中間辮子共軛，以及所述第二中間辮子是否與所述第三中間辮子共軛。若這兩個共軛關係均成立，則籤名有效，輸出1;否則，籤名無效，輸出0。在根 據本發明的實施方式中，籤名驗證單元511判斷籤名辮子和第 一中間辮子 Q是否共軛、第二中間辮子C2是否與第三中間辮子G共軛，用公式表示為 i^ d和C2~C3。如果&. d和C2 C3共軛關係同時成立，則該籤名驗 證單元511判斷該籤名正確，並輸出1;否則，該籤名驗證單元511判斷為該 籤名錯誤，並輸出0。例如，驗證籤名(1, 2, i 12)的計算步驟為 先計算兩個頂點l和2的哈希辮子，如上，假設假設6計算三個中間辮子C2^0/ i2氣^「1(1。3 、、0^—' ^"「、^710^12 °^10_ 3—、5) cr丄o^1 <r3 <r4 cr3—1 cr2 (J丄根據本發明的優選實施方式，提供基於辮群的傳遞數字籤名方法。圖6 圖解了根據本發明的基於辮群的傳遞數字籤名方法的流程圖。 在圖6所示的步驟101中，選擇該傳遞數字籤名系統的系統參數。具體 來說，首先選擇"為系統安全參數，以構造辮群A，所有工作辮子均來自於辮群A，規定工作辮子的(自然)長度(即所包含的生成子的個數)的規模 為0("2)。其次，將每個待籤名的消息對應為一條無向邊，將其兩個頂點編號 (例如，取為自然數)以便以無向邊的兩個頂點的編號組成的二元組表示該 無向邊。在這種情況下，消息空間可以看作是可能的無向邊的集合，因此，在具有m個頂點的消息空間中含有w ) /2個條無向邊。而每條邊的籤 名都是一個辮子，故籤名空間也可以看作是^。然後，選4和哈希函數/Z: iV—& 作為單向Hash函數，用來把頂點編號映射為隨機辮子，這裡7V表示自然數 集合。然後，在步驟102，根據所選擇的系統參數生成用戶的籤名私鑰和相應 的驗證籤名的公鑰。具體過程如下將系統安全參數"作為輸入，從辮群S"中隨機選擇兩個自然長度規模為 <9("2)的辮子，分別記為第一辮子『和第二辮子戶。將第一辮子ff作為共軛 子，根據該共軛子獲取與第二辮子屍共軛的第三辮子Q，這裡可以通過^ = 『^P『計算得到。然後，得到籤名私鑰sk=『和相應的驗證籤名的公鑰pk =(戶，0。接下來，在步驟103，根據共軛操作和所述私鑰對欲籤名的消息(即邊) 進行計算，生成籤名辮子，並且將欲籤名的消息與所獲得的籤名辮子組合成 完整的籤名。具體來說，該步驟103包括以下子步驟1 )對欲籤名的消息的兩個頂點進行哈希運算得到消息辮子對。在本發明 的優選實施方式中，欲籤名的消息為邊(z',力，其兩個頂點為z'和,通過哈希 運算得到消息辮子對，其表示為(6屍H(/)， 6廣H(/));2) 將消息辮子對的第一辮子乘以消息辮子對的第二辮子的逆辮子，得到中間辮子。在本發明的優選實施方式中，中間辮子可以計算為6,V';3) 將選擇的第一辮子『(即籤名私鑰)作為共軛子，獲取與中間辮子共 輒的籤名辮子。在本發明的優選實施方式中，中間辮子為Z^,因此，籤名辮 子為W『『、力/『；以及4) 將所述消息與所述籤名辮子組合起來得到完整的籤名), &)。在 本發明的優選實施方式中，將所述消息(/,力與所述籤名辮子i^.組合起來得到 完整的籤名(/, , A.)。 接下來，在步驟104，根據共享頂點信息的兩個消息的所述籤名和所述 公鑰，合成第三個消息的籤名。在本發明的優選實施方式中，共享頂點信息的兩個消息表示為邊(/，力和(/'， Q,它們共享頂點y，這兩個信息的所述籤名為(/， y， 和(_/, A:， 和所述公鑰為(屍，2),則合成第三個消息(/，A)的籤名為(/， t凡J,其中凡fi ^&，即對應兩個籤名辮子相乘。接下來，在步驟105,其它用戶得到上述籤名(無論是原始生成的還是 合成的)後，可以通過以下方法進^^瞼i正i )將籤名(/，y， &.)和所述公鑰(屍，Q)作為輸入，先計算兩個辮子6產H(/)和6廣H(/);2)再計算三個中間辮子C產6,力/1、 C2=^^.、 C產屍d;3 )判斷籤名辮子和中間辮子d是否共軛、中間辮子C2是否和中間辮 子C3共軛，用公式表示為&.-G和C2-C3;以及4)如果7^. d和C2 C3共軛關係同時成立，則該籤名正確，並輸出1; 否則，該籤名錯誤，並輸出0。因此，本發明通過將普通傳遞籤名方案中的籤名替換成基於辮群的籤名， 使得根據本發明的籤名方案能抵抗已知的量子分析，因而更加安全。上述實施方式中的全部或部分模塊可以由硬體來實現，也可以通過相應 電腦程式指令控制相應的硬體實現。所述電腦程式指令可以存儲在由計 算機系統讀取的任何數據存儲設備上。計算機可讀記錄介質的示例包括只讀 存儲器(ROM)、隨機存取存儲器(RAM)、 CD-ROM、磁帶、軟盤、光數 據存儲裝置和載波(諸如通過網際網路的數據發送)。計算機可讀記錄介質還可 以分布在聯網的計算機系統中，以便以分布的方式存儲並執行計算機可讀代 碼。儘管上述是參照示例性實施方式描述了本發明，但本領域技術人員將理 解，在不背離由所附權利要求書限定的本發明宗旨和範圍的前提下，可以對 本發明進行各種形式和細節上的修改。優選實施方式應該僅認為是說明性的， 而不是限制性的。因此，本發明的詳細描述不限定本發明的範圍，本發明的 範圍應該由所附權利要求限定，並且本發明的範圍內的所有區別技術特徵應 理解為包含在本發明中。
權利要求
1. 一種基於辮群的傳遞數字籤名系統，包括密鑰生成模塊，用於根據系統安全性要求選擇系統參數，根據系統參數確定辮群，並根據所選擇的系統參數和所述辮群生成籤名私鑰和相應的驗證籤名的公鑰，其中，所述系統參數包括辮群的辮指數n、工作辮子的長度規模、由欲籤名的消息的二元組所構成的消息空間以及用來為消息空間中的消息而在所述辮群中選擇籤名辮子的哈希函數；籤名辮子生成模塊，用於根據共軛操作和所述密鑰生成模塊生成的私鑰，將該哈希函數應用到消息空間中欲籤名的表示成二元組的消息來在所述辮群中選擇相應籤名辮子，並將欲籤名的消息與其籤名辮子組合成該消息的完整的籤名；以及籤名合成模塊，用於根據所述籤名辮子生成模塊所生成的至少兩個消息的籤名和公鑰，合成第三消息的籤名辮子。
2. 如權利要求1所述的基於辮群的傳遞數字籤名系統，還包括籤名驗證 模塊，用於根據接收到的消息及其籤名和公鑰，判斷該籤名是否為該消息的 有效籤名。
3. 如權利要求2所述的基於辮群的傳遞數字籤名系統，其中，所述密鑰 生成模塊包括系統參數選擇單元，用於根據系統安全性要求選擇合適的系統參數；辮子選擇單元，用於從根據系統參數選擇單元所選擇的系統參數所確定 的辮群中隨機選擇第 一辮子和第二辮子；辮子獲取單元，用於將辮子選擇單元選擇的第一辮子作為共軛子，根據 該共軛子獲取與第二辮子共軛的第三辮子；以及密鑰生成單元，用於將辮子選擇單元選擇的第二辮子和辮子獲取單元中 獲取的第三辮子作為公鑰，將辮子選擇單元選擇的第 一辮子作為私鑰。
4. 如權利要求3所述的基於辮群的傳遞數字籤名系統，其中，所述籤名 辮子生成模塊包括消息辮子對生成單元，用於通過哈希函數從欲籤名的消息的二元組計算 出第四辮子與第五辮子；中間辮子生成單元，用於將消息辮子對生成單元生成的第四辮子與第五 辮子的逆辮子進行乘積運算，得到中間辮子；以及籤名辮子生成單元，用於將辮子選擇單元中選擇的第 一辮子作為共軛子, 獲取與該中間辮子生成單元生成的該中間辮子共軛的籤名辮子。
5. 如權利要求2所述的基於辮群的傳遞數字籤名系統，其中，所述籤名 合成模塊包括籤名驗證單元，用於調用所述籤名驗證模塊來判斷待合成的至少兩個籤 名是否有效，並且若待合成的該至少兩個籤名中任何一個無效，則拒絕合成, 並輸出無效標誌；以及籤名合成單元，用於把待合成的該至少兩個有效籤名相乘，得到並輸出 合成後的籤名辮子。
6. 如權利要求3所述的基於辮群的傳遞數字籤名系統，其中，所述籤名 驗證模塊包括消息辮子對生成單元，用於通過哈希函數從欲籤名的消息的二元組計算 出第四辮子與第五辮子；中間辮子生成單元，用於生成籤名驗證所需要的中間辮子，該中間辮子 生成單元包括第一中間辮子生成子單元，用於將本模塊中消息辮子對生成單元生 成的第四辮子與第五辮子的逆辮子進行乘積運算，得到第 一中間辮子，第二中間辮子生成子單元，用於密鑰生成模塊的辮子獲取單元中獲 取的第三辮子和要驗證的籤名辮子進行乘積運算，得到第二中間辮子，和第三中間辮子生成子單元，用於將密鑰生成模塊的辮子選擇單元中 選^f奪的第二辮子和所述第 一中間辮子進行乘積運算，得到第三中間辮子；以 及籤名驗證單元，用於判斷要驗證的籤名辮子是否和所述第一中間辮子共 輒，以及所述第二中間辮子是否與所述第三中間辮子共軛，若這兩個共軛關 系均成立，則判斷為該籤名有效，否則，判斷為該籤名無效。
7. 如權利要求1至6之一所述的基於辮群的傳遞數字籤名系統，其中， 所述工作辮子的長度規模被規定為(9("2)。
8. 如權利要求1至6之一所述的基於辮群的傳遞數字籤名系統，其中， 所述哈希函數是將所述消息空間映射到所述籤名空間的單向Hash函數。
9. 一種基於辮群的傳遞數字籤名方法，該方法包括步驟1 )根據系統安全性要求選擇系統參數，根據系統參數確定辮群，並根據 所選擇的系統參數和所述辮群生成籤名私鑰和相應的驗證籤名的公鑰，其中， 所述系統參數包括辮群的辮指數"、工作辮子的長度規模、由欲籤名的消息 的二元組所構成的消息空間以及用來為消息空間中的消息而在所述辮群中選擇籤名辮子的哈希函數；2) 根據共軛操作和所生成的私鑰，將該哈希函數應用到消息空間中欲籤 名的表示成二元組的消息來在所述辮群中選擇相應籤名辮子，並將欲籤名的 消息與其籤名辮子組合成該消息的完整的籤名；以及3) 根據至少兩個消息及其所生成的籤名和公鑰，合成第三消息的籤名辮子。
10. 如權利要求9所述的基於辮群的傳遞數字籤名方法，還包括步驟4): 根據欲籤名的消息的籤名和公鑰，驗證該籤名的有效性。
11. 如權利要求IO所述的基於辮群的傳遞數字籤名方法，其中，步驟l) 包括從系統參數所確定的辮群中隨機選擇第 一辮子和第二辮子，將所述第一 辮子作為共軛子，根據所述共軛子獲取與所述第二辮子共軛的第三辮子；以 及將所述第二辮子和第三辮子作為公鑰，將所述第一辮子作為私鑰。
12. 如權利要求11所述的基於辮子群的傳遞數字籤名方法，其中，步驟2) 包括通過哈希函數從欲籤名的消息的二元組計算出第四辮子與第五辮子； 將該第四辮子乘以該第五辮子的逆辮子，得到中間辮子； 將所述第二辮子與所述中間辮子進行乘積運算，得到籤名辮子；以及將所述欲籤名的消息和所述籤名辮子的組合作為所述欲籤名的消息的完 整的籤名。
13. 如權利要求IO所述的基於辮子群的傳遞數字籤名方法，其中，步驟3) 包括根據該至少兩個消息及其相應籤名和公鑰，判斷該相應籤名是否為相應消息的有效籤名；以及在該至少兩個消息的籤名有效時合成該第三消息的籤名辮子。
14. 如權利要求11所述的基於辮子群的數字籤名方法，其中，步驟4)包括通過哈希函數從欲籤名的消息的二元組計算出第四辮子與第五辮子； 將該第四個辮子與該第五個辮子的逆辮子進行乘積運算，得到第 一 中間辮子；將所述第三辮子與要驗證的籤名辮子進行乘積運算，獲得第二中間辮子; 將所述第二辮子與所述第一中間辮子進行乘積運算，獲得第三中間辮子; 判斷欲驗證籤名中的籤名辮子與所述第 一 中間辮子是否共軛，以及判斷 所述第二中間辮子和所述第三中間辮子是否共軛；以及如果要驗證的籤名辮子與所述第一中間辮子共軛，且所述第二中間辮子 和所述第三中間辮子共軛，則判定所述籤名有效。
15. 如權利要求9至14之一所述的基於辮群的傳遞數字籤名方法，其中， 所述工作辮子的長度規模被規定為0(w2)。
16. 如權利要求9至14之一所述的基於辮群的傳遞數字籤名方法，其中， 所述哈希函數是將所述消息空間映射到所述籤名空間的單向Hash函數。
17. —種計算機產品，其上實施有基於辮群的傳遞數字籤名方法的程序, 該方法包括步驟根據系統安全性要求選擇系統參數，根據系統參數確定辮群，並根據所 選擇的系統參數和所述辮群生成籤名私鑰和相應的驗證籤名的公鑰，其中， 所述系統參數包括辮群的辮指數"、工作辮子的長度規模、由欲籤名的消息 的二元組所構成的消息空間以及用來為消息空間中的消息而在所述辮群中選 擇籤名辮子的哈希函數；根據共輒操作和所生成的私鑰，將該哈希函數應用到消息空間中欲籤名 的表示成二元組的消息來在所述辮群中選擇相應籤名辮子，並將欲籤名的消 息與其籤名辮子組合成該消息的完整的籤名；以及根據至少兩個消息及其所生成的籤名和公鑰，合成第三消息的籤名辮子。
全文摘要
提供基於辮群的傳遞數字籤名系統和方法。該傳遞數字籤名系統包括密鑰生成模塊，用於根據系統安全性要求選擇系統參數來生成籤名私鑰和相應的驗證籤名的公鑰；籤名辮子生成模塊，用於根據共軛操作和所述密鑰生成模塊生成的私鑰，將該哈希函數應用到消息空間中欲籤名的表示成二元組的消息來在所述辮群中選擇相應籤名辮子，並將欲籤名的消息與其籤名辮子組合成該消息的完整的籤名；以及籤名合成模塊，用於根據所述籤名辮子生成模塊所生成的至少兩個消息的籤名和公鑰，合成第三消息的籤名辮子。本發明用基於辮群的籤名方案代替了傳統傳遞籤名中的普通籤名，所產生的籤名能抵抗已知的量子分析，因而更加安全。
文檔編號H04L29/06GK101399668SQ20071015320
公開日2009年4月1日 申請日期2007年9月29日 優先權日2007年9月29日
發明者王勵成, 黃曉芳 申請人:索尼(中國)有限公司