基于復合離散對數的高效有向數字簽名
2007-01-01 00:00:00陳振黃夢橋馬昌社
計算機應用研究 2007年6期
摘 要：現有的有向數字簽名方案均采用了增加簽名方和驗證方的指數運算來實現接收者直接驗證簽名。提出了一個基于復合離散對數的有向數字簽名方案，其運算量、簽名的長度等效于離散對數的數字簽名。相對于現有的有向數字簽名方案，該方案在計算量和通信成本等方面有顯著提高。
關鍵詞：有向數字簽名； 復合離散對數； 有向驗證性； 不可否認性
中圖分類號：TP309文獻標志碼：A
文章編號：1001-3695(2007)06-0136-03
0 引言
數字簽名作為一種密碼原創為保障消息的認證性和完整性提供了一種強大的工具。普通的數字簽名均具有一個通用的屬性，也就是其簽名可以被任何人驗證。但是在有些場合，數字簽名的簽名者和接收者為了保護自己的隱私和利益，不想具有公開驗證的功能，于是在交換協議［1］、數字簽名的基礎上添加了一些限制屬性，以避免潛在的對數字簽名的濫用。不可抵賴數字簽名［2］就是這樣一種數字簽名，其簽名只能在簽名者的幫助下才能得到驗證，以保護簽名者的利益。Chaum在文獻[3]中提出了一種指定驗證人數字簽名，以彌補不可抵賴數字簽名的缺陷(也就是避免當簽名者離線時也能驗證簽名的有效性)。在Aurocrypt’92上，文獻[4]提出了有向數字簽名(Directed Signature)的概念并設計了相應的方案。其后，C.H.Lim和P.J.Lee［5］設計了另外一個有向數字簽名方案，并提出了一些應用。假設用戶Alice想向用戶Bob發送消息，那么有向數字簽名就是滿足如下性質的一個數字簽名：
（1）有向性。只有接收者Bob才能驗證發送者A的簽名，而其他人如果沒有得到Alice或Bob的幫助，則對簽名的信息將一無所知。
（2）可公開驗證性。如果發生糾紛，接收者Bob可以向一個可信第三方(Trusted Party for short， TP)證明簽名的有效性。
在許多的應用場合，簽名消息具有個人或者商業敏感性，如稅單、健康檢查表等。在這些場合下，有向數字簽名是最理想的數字簽名之一。
本文提出了一個基于復合離散對數的高效有向數字簽名方案。該數字簽名方案具有一般的數字簽名方案的效率，簽名時只需要進行一次指數運算，而文獻[4， 5]中的方案則需要三次指數運算；驗證時該方案只需要進行兩次指數運算，而文獻[4， 5]中的方案仍需要三次指數運算。此外本文方案的簽名長度比文獻[4， 5]中的方案都要短，因此無論是計算量，還是通信開銷，該方案都優于文獻[4， 5]中提出的方案。
1 復合離散對數
2 有向數字簽名方案
2.1 形式化定義
定義1 形式化地說，一個有向簽名方案(DS=KeyGen，DSign，DVerify，PVerify)涉及兩個參與方，即Alice和Bob，且由以下四個算法組成：
（1）KeyGen。這是用戶密鑰產生協議，運行這個協議之后，Alice 能夠獲得他的簽名私鑰SKA及對應用來驗證她的簽名的公鑰PKA；Bob獲得了他的解密密鑰SKB和相應的加密密鑰PKB。
（2）Sign。類似傳統的簽名算法，輸入〈SKA，PKB，m〉，輸出Alice對消息m 的簽名s。
（3）DVerify。類似傳統的簽名驗證算法，輸入〈PKA，SKB，m;s〉，如果s 是有效的簽名，則輸出1，否則輸出0。
（4）PVerify。這是Bob和任何一個可信第三方之間的一個零知識的協議，它能保證Bob可以向任何一個可信第三方證明Alice的簽名的有效性。
2.2 高效有向數字簽名方案
KeyGen 為了建立本文的系統，需要一個可信的權威機構(Trusted Authority for short， TA)來產生并發布公共參數，TA按以下步驟進行：
（1）(TA-1)選擇一個安全的RSA模N= pq，這里的p和q是隨機大素數，具有相同的比特長度，并且p-1和q-1非光滑；
3 安全性分析
3.1 安全模型
本文從三個方面來考慮有向簽名方案DS=(KeyGen，DSign，DVerify)的安全性，即不可否認性、有向驗證性和可公開驗證性。假設PPT 表示概率多項式時間。這里首先給出不可否認性的安全模型。
簽名的不可否認性指的是除了Alice誰也不能生成有效的簽名s來構造有效的密文，即Alice的簽名是不可偽造的。其形式化定義是通過隨機預言機模型下［8］的Game 1 來描述的，這是挑戰者C與一攻擊者F之間一個游戲。
3.2 安全性分析
（1）不可否認性。有向簽名方案DS的不可否認性由下面的定理來描述。
定理1 在隨機預言機模型下，有向簽名方案DS在自適應的選擇消息攻擊下，是存在性不可偽造的，即UFDSCMA是安全的。具體地說：如果存在一個攻擊者以優勢至少為證明： 與文獻[7]中的證明類似，這里只給出一個證明概要。詳細的證明，讀者可以參見文獻[7]。關于偽造Alice的簽名問題，不誠實的Bob處于最有利的位置來干這件事情，因為只有他知道唯一的私鑰xB來驗證Alice的簽名的有效性，即不誠實的Bob是能力最強的攻擊者。為此本文就考慮隨機預言機模型下的Game 1 模型：攻擊者掌握了簽名接收者Bob的私鑰xB后，以自適應的方式可選擇消息和接收者的私鑰對簽名預言機和驗證預言機進行查詢。實際上，即使在攻擊的過程中知道了Bob的私鑰，偽造一個本文方案的簽名等價于偽造文獻[7]中方案的簽名，而該文中的方案已經被證明其安全性等價于整數分解。因此，本文的方案能抵抗自適應的選擇消息攻擊。
（2）有向驗證性。只有接收者才能驗證簽名的有效性，如果攻擊者想在沒有得到Bob的幫助下， 驗證一個有向簽名的有效性， 他首先應計算Alice與Bob 之間的DeffieHellman密鑰PAB=gxA×xBmod N。如果不知道xA或xB，這是不可行的，即使知道y，從其中解出PAB也是不可行，因為p、q以及g的階對任何人是保密的。
（3）可公開驗證性。也就是說Alice不能抵賴她對消息的簽名。簽名的接收者Bob可以向任何一個可信第三方證明他收到的確實是發送者Alice對消息的簽名。顯然通過上面方案中的零知識證明方式Bob可以向任何一個可信第三方證明Alice的數字簽名的有效性；同時該證明是零知識方式的，所以沒有泄漏Bob的關于其私鑰的任何信息。
4 效率分析與比較
在本文的方案中，產生一個有向數字簽名需要一次模指數運算、一次Hash函數運算；而文獻[5]中的方案是兩次模指數運算加一次Hash函數運算。驗證一個有向數字簽名，本文方案需要兩次模指數運算、一次模逆運算、一次Hash函數運算；而文獻[5]中的方案，需要四次模指數運算、一次Hash函數運算。此外，相對于文獻[5]中協議而言，本文協議中向TP證明簽名的有效性同樣高效。就通信開銷而言，本文方案僅需要(2|H|+|S|)bits。具體比較如表1所示。
5 結束語
本文提出了一個基于復合離散對數的高效實用的有向數字簽名方案。該方案的安全性是基于整數環上的離散對數問題，其簽名和驗證分別需要一次和兩次模指數運算，這和普通的數字簽名具有一樣的效率，此外，通信開銷很小，只有(2|H|+|S|)bits。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
