前向安全的橢圓曲線數字簽名方案

張 平，栗亞敏

河南科技大學 數學與統計學院，河南 洛陽471000

1 引言

在互聯網高速發展的今天，越來越多的密碼系統被應用于安全性較差的場合，密鑰保護勢在必行。在公鑰密碼體制中，密鑰泄露會給用戶帶來極大的損失。為了減小密鑰泄露的可能，早期的辦法包括：秘密分享系統、門限密碼系統和前攝密碼系統。但是這些系統的開銷很大，因此有很大的局限性。密鑰泄露是無法避免的，但是前向安全技術可以減少密鑰泄露帶來的損失。這個技術的核心就是系統時間劃分方法，它的具體思想是將簽名系統的有效期劃分為若干個時間段，私鑰隨著時間段的變化而變化，公鑰保持不變，即使某一時間段的私鑰泄露，也不會影響到以前各時間段簽名方案的安全性。

橢圓曲線密碼體制是基于橢圓曲線的一種公鑰體制，橢圓曲線理論是包含代數幾何、代數數論和解析數論這三門學科的綜合性學科。由于早期的基于有限乘法群的密碼體系不安全，研究人員提出了能否用其他有限群來代替有限乘法群的問題。鑒于此，Koblitz[1]和Miller[2]提出了橢圓曲線密碼體制（ECC），該體制是目前安全性最高的公鑰加密算法。1997 年，Anderson[3]在CCCS’97 上首次提出了前向安全的思想，但是只給出了簡單的概念性描述，并沒有給出具體的使用方案。隨后，Bellare 和Miner[4]在Crypto’99 上給出了前向安全的詳細定義，并且構造出首個有效的具有前向安全的簽名體制。2003年，Hu[5]等人提出了第一個基于雙線性配對的前向安全簽名方案。2004年，徐丹等人[6]提出了一種基于離散對數問題的強健的密鑰演化簽名體制。2006 年，符茂勝等人[7]利用關聯因子構造了一種基于ECC的前向安全數字簽名方案。2013年，徐光寶等人[8]在Guillou-Quisquater 簽名體制和Rabin 密碼體制的基礎上提出了一個強前向安全的數字簽名方案。2015年，陳輝焱等人[9]提出了一種基于橢圓曲線的前向安全簽名；同年，甄平等人[10]利用Chebyshev 公鑰算法，提出一種基于身份的前向安全數字簽名算法。2016 年，周克元[11]設計了一種具有消息恢復功能的橢圓曲線數字簽名方案，該方案不僅能抗偽造簽名攻擊，還具有前向安全性；同年，李亞榮等人[12]提出一個前向安全代理簽名方案，該方案滿足前向安全代理簽名的所有安全性要求；李順波等人[13]借助單向散列鏈技術構造了一種基于ElGamal 體制的數字簽名方案。2017 年，李靳元等人[14]針對基于橢圓曲線的前向安全數字簽名方案所存在的安全性漏洞問題，給出偽造簽名的方法，并對方案進行了改進。隨后，一些前向安全的特殊數字簽名方案[15-19]被相繼提出。

現有的前向安全的簽名方案大多數都是建立在大素數因子分解和有限域離散對數問題上的。目前安全性，最高的公鑰加密算法是橢圓曲線密碼體制（ECC）。相對于RSA 密碼體制和DSA 密碼體制來說，橢圓曲線具有以下優勢：（1）有限域上的橢圓曲線資源豐富；（2）求解橢圓曲線上離散對數問題（ECDLP）比有限域上離散對數問題更加困難；（3）在相同的安全強度下，橢圓曲線密鑰長度更小，更加節省計算資源和存儲空間。但是已有的橢圓曲線簽名方案大部分沒有前向安全性。本文將橢圓曲線密碼體制的優勢與前向安全的概念相結合，在ECDSA方案的基礎上，引入系統時間劃分方法來減少密鑰泄露帶來的損失，從而構造出一種基于橢圓曲線的前向安全的簽名方案，然后在隨機預言模型基于ECDLP 問題的困難性證明該方案的前向安全性，并將該方案與同樣具有前向安全性的周克元方案進行效率比較。

2 預備知識

2.1 橢圓曲線離散對數問題

橢圓曲線離散對數問題是橢圓曲線密碼體制的核心。橢圓曲線離散對數問題就是對于橢圓曲線E(GF(q))上任意兩點G 和Q，有Q=dG，在已知G 和Q 的前提下求出小于q 的正整數d。己知d 和G 計算Q 比較容易，但是己知Q 和G 計算d 則很困難，這便是橢圓曲線加密體制的核心。

橢圓曲線密碼體制的安全性基于橢圓曲線離散對數問題，也就是求解ECDLP 算法的時間復雜度。和一般的有限乘法群上的離散對數問題所不同的是，有限域上的橢圓曲線離散對數問題的求解難度更大，求解過程更復雜，在多項式時間內無法被所有的已知算法求解。在一般的離散對數問題中，有限域上的代數運算包括域加法和域乘法兩種運算，這使得一般的離散對數問題可以在亞指數時間內被求解。然而，在橢圓曲線離散對數中的代數運算只包含橢圓曲線上的點加這一種基本運算。這導致的結果是除了一些非常特殊的橢圓曲線外，在亞指數時間內所有的離散對數求解算法都無法求解橢圓曲線離散對數問題。

2.2 前向安全體制

前向安全體制中的密鑰更新過程如圖1所示，在前向安全的密碼系統中，假設密鑰演化體制中存在一個可信的第三方TD（Trusted Dealer），它擁有一些特殊的密鑰，這些特殊的密鑰用來更新簽名體制中的密鑰。這里假設整個體制的時間被劃分為N 個時間段。用戶的公鑰自始至終都保持不變，但是用戶的私鑰要在每個時間段的開始進行一次更新。在整個密鑰更新過程中，F表示單向的密鑰更新函數，第j-1 個時間段的私鑰SKj-1通過計算函數F 可以得到第j 個階段的私鑰SKj，要保證由SKj計算SKj-1是困難的。由于在某個特定的時間段j 內，用戶在進行簽名時用到的只是該時間段的私鑰SKj，所以該時間段的密鑰泄漏，只會損失系統當前的安全性和以后的安全性，卻不會危害到系統之前的安全性。

圖1 前向安全的密鑰更新過程

密鑰演化體制KE=(Gen,Upd,Sign,Vrfy) 由以下四部分組成[20]。

Gen（密鑰生成算法）：(PK,SK0,S)←Gen(1λ,…)該算法是概率多項式時間的算法。輸入的是安全參數λ和其他系統參數，輸出為公鑰PK 、初始私鑰SK0。其中S 代表陷門，當系統中存在可信的第三方TD時，將陷門S 給TD，如果系統中不存在可信的第三方TD，則丟棄陷門S。

Upd（私鑰更新算法）：SKj←Upd(j,SKj-1)該算法是確定多項式時間的算法。輸入的是前一時間段的私鑰SKj-1，輸出為該時間段的私鑰SKj。當系統中存在可信的第三方TD時，則該過程與第三方TD共同完成。

Sign（簽名生成算法）：(j,s)←Sign(j,SKj,m)該算法是概率多項式時間的算法。輸入的是該時間段的私鑰SKj和消息m，輸出為該時間段消息m 的簽名(j,s)。

Vrfy（簽名驗證算法）：{ }0,1 ←Vrfy(PK,M,(j,s))該算法是確定多項式時間的算法。輸入的是公鑰PK 、消息m 和消息m 所對應的簽名(j,s)，輸出為0 或1，其中0 表示拒絕接受簽名，1 表示同意接受簽名。當Vrfy(PK,M,(j,s))=1 時，簽名(j,s)是消息m 在j 時間段的有效簽名。

3 ECDSA簽名方案

3.1 參數選擇

GF(q)是有限域，E:y2=x3+ax+b(mod q)（a,b ∈GF(q)，且4a3+27b2≠0）是該有限域上的橢圓曲線，G是橢圓曲線上的一個基點，ord(G)=n，n 是一個大素數，是余因子，d 是簽名私鑰，Q=dG 是簽名公鑰，是美國NIST和NSA 設計的一種安全Hash 算法，輸入信息長度一般小于264bit。D={ }q,a,b,G,n,h ，Q、H 公開，d 保密。

3.2 簽名生成

簽名者A利用公私鑰對消息m 簽名：

（2）計算kG=(x1,y1) ，r=x1mod n ；若r=0 ，跳至步驟（1）。

（3）計算e=H(m)。

（4）計算s= k-1(e+dr)mod n ；若s= 0 ，則跳至步驟（1）。

（5）簽名結果為(r,s)。

3.3 簽名驗證

（2）計算e=H(m)。

（3）計算w=s-1mod n。

（4）計算u1=ew mod n 和u2=rw mod n。

（5）計算X=u1G+u2Q=( x2,y2)。

（6）若X=0，拒絕該簽名。

（7）計算v=x2mod n，若v=r ，則接受該簽名，否則拒絕該簽名。

3.4 安全性分析

該方案不具有前向安全性，即一旦私鑰d 泄露，之前所有的簽名都會被破壞，從而導致整個密碼體制崩潰。為減少密鑰泄露帶來的損失，需要設計出一個新的密碼體制，使得某一時間段私鑰的泄露不影響以前各時間段簽名體制所提供的安全保障。

4 改進的橢圓曲線簽名方案

針對原簽名方案存在的安全問題，進行改進，引用徐丹等人[6]密鑰更新方法，將系統的有效時間分為若干個時間段，在每個時間內進行密鑰演化，提出了一個新的橢圓曲線簽名方案。假設在系統中存在可信第三方TD，其持有一些用來更新密鑰的秘密。

4.1 參數選擇

GF(q)是有限域，E:y2=x3+ax+b(mod q)（a,b ∈GF(q)，且4a3+27b2≠0）是該有限域上的橢圓曲線，G是橢圓曲線上的一個基點，ord(G)=n，n 是一個大素數，是余因子，是美國NIST和NSA設計的一種安全Hash算法，輸入信息長度一般小于264bit。假設在系統中存在可信第三方TD，其持有一些用來更新密鑰的秘密。假設系統的有效時間被分為N 段。

4.2 密鑰生成

（1）隨機選擇z 次多項式f(x)=a0+a1x+a2x2+…+azxzmod n。

（2）初始私鑰SK0=f(0)=a0，公鑰為PK=(a0G,a1G,…,azG)。

（3）隨機選擇xi∈[1,n-1]，1 ≤i ≤z，將f(xi)分配給TD。

4.3 密鑰演化

該部分引用徐丹等人[6]密鑰更新方法。簽名者和TD 用分布式的方法共同計算SKj=f(j)(j ≥0) 。在密鑰更新過程中需要TD 的參與，假設有z 個TD，每個TDi有一個共享份額f(xi)(1 ≤i ≤z)，xi互不相同，且遠大于時間段數N ，簽名者擁有時間段j-1 的私鑰f(j-1)。假設簽名者和TD 之間有保密信道。不妨假設簽名者是TD0，則由Langrange 插值公式可知：

（1）每個TDl(1 ≤l ≤z)，隨機選z 元變量(al,z,…,al,1)，構建一個z 次多項式，通過保 密 信 道 將hl(xi) 發 送 給TDi(1 ≤i ≤z) ，設F(x)=

（2）每個TDl(1 ≤l ≤z)，計算自己的共享份額F(xl)=

（3）每個TDl(1 ≤l ≤z)，通過保密信道發送F(xl)給簽名者TD0。

（4）簽名者TD0根據F(x0),F(x1),…, F(xz) 通過Langrange插值公式計算F(x)的常數項系數，則計算出其在第j 時間段的私鑰

4.4 簽名生成

4.4.1 第一種簽名生成方案

簽名者A利用公私鑰對消息m 簽名：

（2）計算kG=(x1,y1)，r=x1mod n ；若r=0，跳至步驟（1）。

（3）計算e=H(m,r)。

（4）計算sj=k-1(e+SKj?r) mod n；若sj=0，則跳至步驟（1）。

（5）簽名結果為(j,(e,sj) )。

4.4.2 第二種簽名生成方案

由于第一種簽名生成方案中存在模逆運算，效率勢必會很低，對此作出改進。

簽名者A利用公私鑰對消息m 簽名：

（2）計算kG=( x1,y1)，r=x1mod n ；若r=0，跳至步驟（1）。

（3）計算e=H(m,r)。

（4）計算sj=k+e ?SKjmod n ；若sj=0 ，則跳至步驟（1）。

（5）簽名結果為(j,(e,sj) )。

4.5 簽名驗證

驗證者B 驗證(j,(e,sj) )是否是A 對消息m 的簽名（僅對第二種簽名生成方案進行簽名驗證）：

（1）檢驗e,sj∈[1,n-1] 是否成立，若不成立，返回拒絕簽名。

（3）計算r'=x2mod n。

（4）驗證e=H(m,r')是否成立，若成立，則接受該簽名，否則拒絕該簽名。

4.6 正確性分析

5 安全性分析

（1）與ECDSA方案相比，改進方案可以抵抗隨機數攻擊。很多人都提到不同消息使用同一簽名方案進行簽名時，使用相同的隨機數（這種概率非常?。┦遣恍械腫21]，原因是：如果使用ECDSA方案對不同消息進行簽名時使用了相同的隨機數，就可以用一個二階的線性方程組解k=(s'-s)-1(e'-e)mod n ，進而解出私鑰d=r-1(sk-e)mod n。

如果運用改進方案分別在不同的時間段i、j，對兩個不同消息使用相同的隨機數進行簽名，就會得到方程組，由于不同時間段的私鑰是不同的，因此無法通過方程組求得兩個私鑰f(i)和f(j)。所以，改進方案可以抵抗隨機數攻擊。

（2）密鑰演化算法具有前向安全性。根據徐丹等人[6]密鑰更新方法可知，該方法即使是在z 個私鑰泄露的情況下，依然是選擇消息攻擊下存在性不可偽造的。敵手無法通過第j 時段的私鑰SKj求得第j-1 時段的私鑰SKj-1。

（3）簽名算法具有前向安全性。當敵手獲得第j 時段的私鑰時，他無法通過第j 時段的私鑰去偽造第j-1時段的簽名。由sj-1=k+e ?SKj-1mod n 可知，如果敵手要偽造第j-1 時段的簽名(j-1,(e,sj-1))，需要知道SKj-1。而由密鑰演化算法的前向安全性可知，敵手無法通過第j 時段的私鑰SKj求得第j-1 時段的私鑰SKj-1，從而保證了簽名算法的前向安全性。

通過以上分析可知，本文解決了敵手在得到某時間段的簽名私鑰后，在不知道之前時間段私鑰的情況下能夠偽造任意時間段簽名的問題。

（4）在隨機預言模型下，若存在敵手A 以不可忽略的優勢ε 攻破改進方案，那么存在算法B 至少以優勢ε'=ε/N-negl(n)的優勢解決ECDLP 問題，這里N 是時間段總數。

證明 假設攻擊者A以優勢ε 攻破改進方案。算法B的輸入為G，G ∈E。B模擬A的挑戰者如下。

準備階段：B 設定時間段總數為N ，并猜測A 偽造時間段J(0 ≤J ≤N)的簽名。B 在有限域GF(q)上選擇橢圓曲線E ，并在E 上選擇一基點G ，ord(G)=n。B選擇哈希函數H ，z 次多項式。B 將公鑰PK=(a0G,a1G,…,azG)發送給A。

查詢階段：哈希查詢：模擬哈希查詢，B包含哈希查詢列表LH和簽名列表LS。所有列表初始為空。當A對m 進行哈希查詢時，B 首先檢查m 是否已出現在列表LS中，若沒有，B進行下面的簽名生成過程：

（3）消息m 的簽名是σ=(j,(e,sj))。

（4）分別更新列表LH和LS。

接下來，如果A 詢問H(m,b)，B 檢查b=r 是否成立，如果成立返回e ；否則B 選擇隨機數l ∈，返回lG，并將元組(m,b,lG,l)插入到列表LH中。

密鑰泄露查詢：A 提交breakin(j+)(1 ≤j+＜N)。若j+≤J ，B報告失敗并中止；若j+＞J ，B執行密鑰更新算法生成SKj+，即SKj+←Update(…Update(SK0))。B 將SKj+返回給A。

簽名查詢：A 提交(j,m)(0 ≤j ≤j+) 。B 任意選擇k ∈[1 ,n-1] ，計算。然后，將簽名( j,(e,sj) )返回給A。

偽造階段：如果B 在查詢階段沒有中止退出，則A將以至少為ε 的優勢輸出時間段索引j*，消息M*和有效偽造(j*,(e*,sj*))，其中0 ≤j*＜j+。若j*≠J ，則B 報告失敗并中止；否則有，那么，從而求得ECDLP問題。

在上述模擬過程中，若B 猜中A 偽造簽名的時間段，則在密鑰泄露查詢時有j+＞J ，即B能產生私鑰SKj+而不中止退出，B 猜測正確的概率為1/N ，故B 成功求解ECDLP 問題的概率至少為ε'=ε/N-negl(n)，這里N是時間段總數。

6 效率分析

從算法運算量角度分析，設模乘運算的數據規模是n，1 次倍點運算復雜度是，1 次模逆運算復雜度是（相當于9次倍點運算），1次模乘運算復雜度是。由于改進方案引入了密鑰演化思想，和ECDSA方案相比，總體運算效率勢必會降低，但是在簽名階段和驗證階段的效率還是很快的。在簽名階段和驗證階段上，將改進方案的運算量與ECDSA 方案的運算量以及同樣具有前向安全的周克元方案[11]的運算量進行對比，結果如表1所示。

表1 ECDSA、周克元方案和本文改進方案運算量比較

由表1 可知，在簽名階段和驗證階段，ECDSA 方案的總運算量是N1=O[( 4 lb n+21) n2] ，周克元方案的總運算量是N2=O[( 6 lb n+13 )n2] ，改進方案的總運算量是N3=O[( 2 lb n+2) n2] 。三種復雜度圖形表示如圖2所示。

圖2 三種方案的簽名復雜度比較

本文改進方案在密鑰生成上雖然無法和其他兩種方案相比，但是它的簽名生成和簽名驗證效率要比其他兩種方案高得多。影響復雜度的主要運算是模乘運算和模逆運算，改進方案在簽名生成和驗證時比ECDSA方案少了2次模逆運算，所以在簽名生成和驗證階段改進方案比ECDSA方案的效率高。改進方案和周克元方案同樣具有前向安全性，但是與周克元方案相比，改進方案在簽名生成和驗證階段少了2 次倍點運算、4 次模乘運算和1次模逆運算，所以改進方案的簽名效率提高了很多。因此，與其他兩種方案相比，改進方案不僅保證了前向安全性，還大大地提高了簽名效率。然而，由于改進方案加入了密鑰演化過程，總體效率勢必會降低，因此，該方案適用于對安全性要求較高，對總體效率要求低的應用場合。

7 結束語

本文首先對ECDSA 方案進行分析，發現該方案沒有前向安全性，存在密鑰泄露的安全隱患。針對這個安全隱患，引用徐丹等人[6]的密鑰更新方法提出改進方案，并對改進方案進行安全性分析。由分析可知，改進方案可以抗隨機數攻擊，另外，根據證明可知，在隨機預言模型下基于橢圓曲線離散對數問題困難的假設，改進方案滿足前向安全性。最后，針對簽名過程，運用MATLAB編程將該方案與ECDSA方案以及同樣具有前向安全性的周克元方案進行效率比較，發現本文改進方案比其他兩種方案的簽名效率高。因此，改進方案不僅保證了安全性，簽名效率也得到了顯著提高。