前向安全的環簽名研究

摘要：基于模合數平方根和因子分解問題的難解性，首次提出一個具有前向安全性的環簽名方案，即使攻擊者非法獲取了用戶當前簽名密鑰，也無法偽造之前的簽名。

關鍵詞：數字簽名； 環簽名； 前向安全； 模合數平方根； 因子分解

中圖分類號：TP393．08文獻標志碼：A

文章編號：1001－3695(2008)01－0249－02

數字簽名是一種廣泛應用于計算機和網絡通信的安全技術。在數字簽名中，密鑰的安全是至關重要的，一旦密鑰泄漏，密鑰泄露之前簽名的消息也將不可信，因此無法確定簽名的合法性。對于密鑰的保護，最具有代表性的方法是采用密鑰分布式共享[1]。但是該方法需要更多的系統資源，且攻擊者可能采用同樣的攻擊方法獲取所有分布式密鑰。為了將密鑰泄漏所帶來的損失減小到最小程度，Anderson[2]于1997年首次在數字簽名的研究中提出了前向安全的思想。隨后，Bellare和Miner[3]給出了前向安全數字簽名的正式定義。前向安全的基本思想是在簽名算法中加入密鑰更新算法，將用戶密鑰的生存時間劃分為若干時期，階段性地對簽名密鑰進行更新，但公鑰保持不變。在每個時期開始時產生新的簽名密鑰，并安全刪除上一時期的密鑰，使得攻擊者即使非法獲取了某用戶當前的簽名密鑰，也無法偽造前階段的環簽名，從而提高了系統的安全性。

環簽名的概念是R.Rivest等人[4]于2001年首次明確提出的，它是一種新的匿名簽名技術，因簽名中參數根據一定規則首尾相接組成環狀而得名。環簽名可以視為簡化的沒有群主管的群簽名。與群簽名不同的是，群簽名中群主管可以揭露簽名者的真實身份，而環簽名中任何人均無法揭示簽名成員的身份，從而保證了簽名者的無條件匿名性。在環簽名中，簽名人只要知道某個用戶的公鑰，不需要其同意或者合作就可以將其加入到環中對消息進行簽名，其惟一假設是所有用戶都擁有支持某種標準簽名方案的公鑰。由于環簽名的這些性質及其應用背景，很多學者均對環簽名進行了研究[5~12]。

本文首次在環簽名中引入前向安全的思想，在模合數平方根和因子分解的難解性基礎上提出了一個前向安全的環簽名方案，使得攻擊者即使獲得某用戶當前的簽名密鑰，也不能得到該用戶之前的密鑰，從而不能偽造之前的環簽名。

1相關知識

1．1模合數平方根問題

定義1給定合數N和模N的二次剩余a，求解a模N的平方根。

如果N的因子已知，利用中國剩余定理可以很容易地求解。但當N的因子分解是困難性問題時，求解a模N的平方根也是一個困難性問題。

1．2因子分解問題

定義2給定一個正整數N，找到其素因子分解，即將N寫成N=pe11pe22…pekk。其中：pi是兩兩不同的素數；ei是正整數。

1．3環簽名

假設每個用戶均擁有一對支持某種標準簽名方案的公鑰及私鑰。一個環簽名方案是包括以下算法的數字簽名方案：

a)簽名算法。一個概率算法，給定消息m，n個環成員的公鑰及一個成員（真正的簽名人）的私鑰，輸出關于消息m的環簽名σ。

b)驗證算法。一個確定性算法，輸入消息m和簽名σ（包含所有成員的公鑰），輸出0或1。

一個環簽名方案必須滿足以下安全性質：

a）無條件匿名性。攻擊者即使非法獲取了所有可能簽名者的私鑰，他能確定出真正簽名者的概率不超過1/n。其中n為環成員（可能的簽名者）的個數。

b）不可偽造性。外部攻擊者在不知道任何成員的私鑰的情況下，即使能從一個產生環簽名的隨機預言模型中得到任何不同于m的消息簽名，也不能以不可忽略的概率成功地偽造關于消息m的有效環簽名（該環不包括攻擊者）。

2前向安全的環簽名方案 

本文在Abe等人[10]環簽名思想的基礎上提出一個前向安全的環簽名方案。該方案由以下四部分組成。

1)密鑰生成

3．4．2環簽名的前向安全性

由方案的不可偽造性可知，對某一具體時段，攻擊者在不知道任何環成員私鑰時無法偽造有效的環簽名，而簽名密鑰的前向安全性又保證攻擊者即使非法獲取了某用戶當前時段的簽名密鑰，也無法計算出前一時段的密鑰，因此無法偽造前一時段的環簽名，保證了環簽名的前向安全性。

4結束語

前向安全的數字簽名能將簽名密鑰泄露所帶來的損失減小到最小程度。本文基于模合數平方根和因子分解問題的難解性，首次提出一個具有前向安全性的環簽名方案，使得攻擊者即使獲得某用戶當前的簽名密鑰，也不能得到該用戶以前時刻的密鑰，從而不能偽造以前的環簽名。

參考文獻：

[1]王尚平，王育民，王曉峰，等. 基于零知識證明的前向安全數字簽名方案[J]. 通信學報， 2003，24(9):42－47.

[2]ANDERSON R. Invited lecture [EB/OL]. (1999).http://cite￣seer.nj.nec.com.

[3]BELLARE M， MINER S. A forward secure digital signature scheme[C]//Proc ofLecture Notes in Computer Science 1666. Berlin: Springer Verlag， 1999:431－448.

[4]RIVEST R， SHAMIR A， TAUMAN Y. How to leak a secret [C]//Proc ofLecture Notes in Computer Science 2248. Berlin: Springer Verlag， 2001:552－565.

[5]ZHANG Fang guo， KIM K. ID based blind signature and ring signature from pairing [C]//Proc ofLecture Notes in Computer Science 2501. Berlin: Springer Verlag， 2002:533－547.

[6]LIN C Y， WU T C. An identity based signature scheme from bilinear pairing [EB/OL].(2003). http://eprint.iacr.org. 

[7]AWASTHI A K， LAL S. ID based ring signature and proxy ring signature scheme from bilinear pairings[EB/OL].(2004).http ://eprint.iacr.org.

[8]HERRANZ J， SAEZ G. New identity based ring signature [C]//Proc ofLecture Notes in Computer Science 3269. Berlin: Springer Verlag， 2004:27－39. 

[9]BRESSON E， STERN J， SZYDLO M. Threshold ring signatures and applications to Ad hoc groups (extended abstract) [C]//Proc ofLecture Notes in Computer Science 2442. Berlin: Springer Verlag， 2002:465－480. 

[10]ABE M， OHKUBO M， SUZUKI K.1 out of n signatures from a varie￣ty of keys [C]//Proc ofLecture Notes in Computer Science 2501. Berlin: Springer Verlag， 2002:415－432. 

[11]LIU J K， WEI V K， WONG D S. Linkable spontaneous anonymous group signatures for Ad hoc groups [C]//Proc ofLecture Notes in Computer Science 3108. Berlin: Springer Verlag， 2005:325－335.

[12]TSANG P P， WEI V K， CHAN T K， et al. Separable linkable threshold ring signatures [C]//Proc ofLecture Notes in Computer Science 3384. Berlin: Springer Verlag， 2004:384－398.

[13]ALFRED J M，OORSCHOT P C van，SCOTT A V.應用密碼學手冊[M].胡磊，王鵬，等譯. 北京:電子工業出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”