基于橢圓曲線的代理數字簽名方案

摘要：對白國強等人提出的基于橢圓曲線的代理數字簽名方案，以及武玉華等人對此方案的改進進行了分析，指出該方案不能有效控制代理人對代理權限的濫用，并對其進行了改進。改進的方案在保證原簽名方案安全性的基礎上，從時間上對代理人的代理權限進行了有效控制。驗證人收到代理人的代理簽名信息，通過檢查代理人的代理權是否在有效時期內，判斷代理人的代理權是否合法。

關鍵詞：橢圓曲線；代理簽名；數字簽名；離散對數問題；橢圓曲線離散對數

中圖分類號：TP309文獻標識碼：A文章編號：1009-3044(2008)29-0449-02

Proxy Digital Signature Scheme Based on Elliptic Curves

YUAN Zuo-lin， JI Peng

(Coll. of Info. Sci. and Eng.， Nanjing Univ. of Tech.，Nanjing，210009，China)

Abstract: A scheme was carefully analyzed which was based on two papers. One was proposed by Guoqiang Bai etc based on “Proxy Digital Signature Based on Elliptic Curves” and the other improved was proposed by Yuhua Wu etc. In the scheme， the problem was found that delegation power misuse was not controlled effectively. And an improved scheme was proposed which solved the problem on the time control. When a verifier receives the message of proxy digital signature， he judges the legitimacy of the proxy through checking the time limit first.

Key words: elliptic curve; proxy signature; digital signature; discrete logarithmic problems; elliptic curve discrete logarithm

1 引言

代理簽名[1]是指原始簽名人，由于各種原因不能行使簽名權力時，將簽名的權力委托給他人，使他能夠代替原始簽名人行使簽名的權力。對任何消息，代理簽名人代表原始簽名人生成的簽名，任何知道原始簽名人公鑰的驗證人，都可以驗證該消息簽名的有效性。

橢圓曲線密碼體制[2]是一種基于橢圓曲線離散對數問題的公鑰密碼體制。它的安全性基于橢圓曲線離散對數問題求解的困難性上。與離散對數問題相比較，在有限域相同的情況下，它可以達到更大的安全性。

目前，已有多種與橢圓曲線有關的代理簽名方案[3-7]被提出，文獻[4]提出的方案雖然具有橢圓曲線密碼體制的優勢，但是該代理簽名方案并不能阻止原始簽名人冒充代理簽名人，存在一定的安全隱患；文獻[5]針對這個安全隱患進行了改進，通過在代理簽名中加入代理人的私鑰來解決這一問題。但這兩個方案都不能控制代理人對代理權限的濫用。本文針對這一問題，在原方案的基礎上，給出了一個改進的代理簽名方案，可以有效地對代理人的代理權限在時效上進行控制。

2 文獻[4-5]的方案

2.1 初始化過程

假定 E 是定義在有限域 F上的一條橢圓曲線，P ∈E 是 E 中一個階為 n 的點，將 E，n 和 P 公開。假定 A 為原始簽名人，A 的私鑰為 kA，公鑰為 PA，私鑰 kA 保密，公鑰 PA 公開。公鑰 PA 和私鑰 kA 之間有關系 PA = kAP。

2.2 委托過程

A 選取隨機數 k0，并計算 k0P。記 Q0 = k0P = (x0，y0)，其中x0，y0∈F。然后計算：r0≡x0 mod n 和

σ ≡ ( kA + r0 k0 ) mod n (1)

( σ，Q0 )即為 A 將其簽名權委托給 B 的委托信息。A 將σ秘密地發送給 B，Q0 可以公開地發送給 B。代理簽名人 B 收到委托信息( σ，Q0 )后，驗證以下等式是否成立：

σ P = PA + r0 Q0 (2)

如果等式(2)不成立，則代理簽名人 B 必須拒絕接受委托信息( σ，Q0 )。如果等式(2)成立，則說明( σ，Q0 ) 確實來自于原始簽名人 A；

2.3 代理簽名的產生過程

對任何消息 m (0 < m < n)，B 首先選取隨機數 k，0 < k < n，然后計算 kP，記 kP = ( x，y )，其中x，y ∈F。接著 B 計算: 1) r ≡ x mod n；2) s ≡ k-1 ( m + rσ ) mod n. 則( m，r，s，Q0 ) 一起構成了代理簽名人 B 對消息 m 的代理簽名。

2.4 代理簽名的驗證過程

任何一個驗證人 C 收到代理簽名( m，r，s，Q0 ) 后，利用原始簽名人 A 的公鑰PA，進行下列計算：1) c ≡ s-1mod n；2) u1 ≡ mc mod n，u2 ≡ rc mod n；3) 計算u1 P + u2 ( PA + r0 Q0 )，設 u1 P + u2 ( PA + r0 Q0 ) = ( x′， y′)；4) 計算 r′ ≡ x′ mod n。如果 r′ = r，則代理簽名( m，r，s，Q0) 得到驗證。

文獻[5]對文獻[4]方案的改進主要在于代理簽名的產生過程，在此過程中增加了代理簽名人的私鑰，以加強方案的安全性。說明如下：

設B有自己的私鑰 kB，公鑰 PB = kBP。對任何消息 m ( 0 < m < n )，B 首先選取隨機數 k，0 < k < n，然后計算 kP，記 kP = ( x，y )，其中x，y ∈F。接著B 計算：1) r ≡ x mod n；2) σ′ = σ + kB；3) s ≡ k-1( m + rσ′ ) mod n. 則( m，r，s，Q0) 一起構成了代理簽名人 B 對消息 m 的代理簽名。

在代理簽名的驗證過程中，通過計算 u1 P + u2 ( PA + r0 Q0 + PB) = ( x′， y′)；r′ = x′ mod n 是否等于 r 來判斷代理簽名的合法性，證明如下：

u1 P + u2 ( PA + r0 Q0 + PB) = mcP + rc( kAP + r0k0P + kBP) = c ( m + r (kA + r0k0 + kB )) P = s-1( m + rσ′ ) P = kP = ( x ， y )。

3 改進后的方案

3.1 初始化過程同2.1

3.2 委托過程

A 選取隨機數 k0，計算 k0 P。記 Q0 = k0 P = ( x0，y0)，其中x0，y0 ∈F。然后 A 計算：

r0 ≡ x0 mod n (3)

σ ≡ ( kA + r0 k0) mod n (4)

st ≡ k0-1( T + r0 kA) mod n (5)

其中，T 為代理權限的時限。 A 將 σ 秘密地發送給 B，Q0 和 St 可以公開地發送給 B。( T，σ，Q0，st )為 A 對 B 的委托信息。代理簽名人 B 收到委托信息( T，σ，Q0，st )后，需驗證兩個部分：

1) 時間 T 的簽名是否有效。

計算①c ≡ st-1mod n；②u1 ≡ Tc mod n，u2 ≡ r0c mod n；③計算u1 P + u2 PA，設u1 P + u2 PA = ( x′， y′)；④計算r′ = x′ mod n。如果 r′ = r，則 A 對時間 T 的簽名有效。

2) 以下等式是否成立：

σ P = PA + r0 Q0 (6)

如果1)、2)兩項都得到驗證，則說明( T，σ，Q0，st )確實來自于原始簽名人A；只要有一項不成立，則代理簽名人B 拒絕接受委托信息( T，σ，Q0，st )。

3.3 代理簽名的產生過程

設B有自己的私鑰kB，公鑰PB=kB P。對任何消息 m (0 < m < n)，B 首先選取隨機數k，0 < k < n，然后計算 kP，記 kP = ( x，y)，其中x，y ∈F。接著 B 計算：1) r ≡ x mod n；2) σ′ = σ+ kB；3) s ≡ k-1( m + rσ′) mod n. 則( T，m，r，s，Q0，st )一起構成了代理簽名人B對消息m的代理簽名。

3.4 代理簽名的驗證過程

任何一個驗證人 C 收到代理簽名(T，m，r，s，Q0，st)后，需要驗證兩個部分：

1) 首先需要驗證B的代理權是否在有效期內，計算①c ≡ st-1mod n；②u1 ≡ Tc mod n，u2 ≡ rc mod n；③計算 u1 P + u2 PA，設 u1 P + u2 PA = ( x′， y′)；④計算x′ mod n。如果 x′ mod n = r，則說明 B 的代理權限還在有效期內，繼續驗證代理簽名；否則說明B的代理權已經失效，拒絕簽名消息。

2) 代理簽名的驗證。C 利用原始簽名人 A 的公鑰 PA和代理簽名人的公鑰 PB，進行下列計算：①c ≡ s-1 mod n；②u1 ≡ mc mod n， u2 ≡ rc mod n； ③計算 u1 P + u2 ( PA + r0 Q0 + PB )，設 u1 P + u2 ( PA + r0 Q0 +PB ) = ( x′， y′ )；④計算 r′ = x′ mod n。如果 r′ = r，則代理簽名( T，m，r，s，Q0，st ) 得到驗證。

新方案在原方案的基礎上增加了對時間 T 限制的數字簽名， 可以有效的防止代理簽名人 B 代理權限的濫用；同時，新方案也兼顧了原方案的安全性；對時間限制 T 數字簽名的安全性也由橢圓曲線離散對數求解問題的困難性所保證。

4 方案的安全性

方案的安全性一般要求基本的不可偽造性，代理簽名的不可偽造性，代理簽名的區分性，不可抵賴性，身份證實性，密碼依賴性，可注銷性等。在文獻[4-5]中對此進行了分析，歸結為以下幾點：

1) 代理簽名人 B 不能從委托信息中獲取原始簽名人的私鑰；

在方案中，A給B的委托信息是( σ，Q0 )，其中，Q0 = k0P，σ ≡ ( kA + r0 k0 ) mod n，A的私鑰可通過σ ≡ ( kA + r0 k0 ) mod n 計算，參數σ和r0已知，只要知道k0就可計算出A的私鑰，但B從Q0 = k0P中計算出k0時不可能的，這是一個典型的橢圓曲線離散對數問題。

2) 代理簽名的偽造者E（包括原始簽名人A）都不能冒充 B 而產生消息 m 的代理簽名，從而欺騙驗證人 C；

在B對消息m的代理簽名過程中，包含了B的私鑰：σ′ = σ + kB ，s ≡ k-1( m + rσ′ ) mod n，在不知道B的私鑰的情況下，任何人都不能冒充B。

攻擊者E想偽造B的簽名，設它的私鑰kE，公鑰PE。E通過以下步驟生成代理簽名：

①選擇隨機數k'，計算k' = x' mod n；

②r' = x' mod n；

③σ1′ = σ + kE；

④s' = k'-1(m' + r' σ1′ )mod n。

則(m'， r'， s'， Q0)一起構成了E代替B對消息m的冒充代理簽名。

驗證人C收到代理簽名后，利用A和B的公鑰kA，kB進行驗證，計算：

①1c ≡ s'-1mod n；

②u1' ≡ m'c' mod n，u2' ≡ r'c' mod n；

③計算u1' P + u2' ( PA + r0 Q0 +PB)，設 u1' P + u2 '( PA + r0 Q0+PB ) = ( x′， y′)；

④計算 r′ ≡ x′ mod n；

驗證過程u1' P + u2'( PA + r0 Q0+PB ) = m'c'P + r'c'( kAP + r0 k0P + kBP ) = c'(m' + r'( kA + r0 k0 + kB ))P ≠ s'-1( m' + r'σ′1 )P ≠ k'P ≠ (x'，y')。因此，驗證人和接收人都會識別出偽造的代理簽名。

3) 代理簽名人B不能濫用他的代理權限；

在3.4代理簽名的驗證過程，首先要驗證的是簽名的實效性，這是A對時效T的簽名，如果不能獲得A的私鑰kA，那么B不能偽造A對T的簽名；在B行使它的代理簽名的過程時，也就不能用過期的權限來欺騙驗證人C。

5 結束語

本文針對文獻[4-5]中提出的代理簽名方案的不足，在沒有增加大量計算量的情況下，對其進行了改進；在保留了原代理簽名方案安全性的基礎上，增加了對代理人代理權限的控制，進一步提高了方案的安全性。

參考文獻：

[1] Mambo M，Usuda K，Okamoto E.Proxy signature:Delegation to sign messages[J].IEICE Transactions on Fundatamentals，1996，E792A(9):1338-1354.

[2] 徐秋亮，李大興.橢圓曲線密碼體制.計算機研究與發展[J]，1999，36(11):1281-1288.

[3] Sun HM，Chen BJ.Time2stamped Proxy Signatures with Traceable

Receivers[C].Proceedings of the 9 th National Conference on Information Security，1999:247-253.

[4] 白國強，黃諄，陳弘毅，等.基于橢圓曲線的代理數字簽名[J].電子學報，2003，31(11):1659-1663.

[5] 武玉華，李艷俊，楊剛，等.一種改進的基于橢圓曲線的代理簽名方案[J].計算機應用研究，2007(2):132-137.

[6] 祁明，韓亮.限制性代理簽名方案[J].計算機工程，2001，27(2):41-42.

[7] 吳鴻華，溫鳳桐.具有限制性的代理簽名方案[J].濟南大學學報，2007，21(4):353-355.