高效的兩方ECDSA門限方案

顏 萌， 馬昌社

(華南師范大學(xué)計(jì)算機(jī)學(xué)院, 廣州 510631)

在公鑰密碼技術(shù)領(lǐng)域中，密鑰對于密碼算法來說至關(guān)重要，私鑰的安全決定著系統(tǒng)以及敏感信息的安全，一旦公鑰系統(tǒng)中的私鑰被泄露或者丟失，不僅會造成系統(tǒng)出現(xiàn)單點(diǎn)故障，而且在惡意攻擊者獲得用戶私鑰之后就可以輕松地獲取并篡改敏感信息。由此，SHAMIR[1]提出門限方案，又名秘密共享方案，該方案利用密碼技術(shù)將需要保護(hù)的明文信息進(jìn)行分割并安全地由不同的參與者存儲。隨后，DESMEDT和FRANKEL[2]正式提出門限簽名的概念。隨著云計(jì)算以及區(qū)塊鏈技術(shù)的高速發(fā)展，系統(tǒng)終端更容易遭受惡意攻擊。為了防止權(quán)力過度集中，提升計(jì)算系統(tǒng)抵抗安全風(fēng)險(xiǎn)的能力，學(xué)者們針對不同的應(yīng)用場景提出了不同的門限簽名方案[3-5]。

1992年，JOHNSON等[6]為了響應(yīng)NIST對數(shù)字簽名標(biāo)準(zhǔn)的要求而提出了橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm，ECDSA)。隨后，ECDSA算法作為數(shù)字簽名算法的一種，被廣泛用于移動電子商務(wù)領(lǐng)域。由于網(wǎng)上交易為現(xiàn)在的主流消費(fèi)方式，基于ECDSA算法設(shè)計(jì)出高效率的門限方案勢在必行。

現(xiàn)階段，圍繞ECDSA算法的門限化簽名工作出現(xiàn)了大量研究。1996年，GENNRAO等[7]提出(t,q)門限ECDSA簽名方案，該方案的門限值t≤q/2，且簽名的計(jì)算和通信開銷高。2001年，MACKENZIE和REITER[8]提出了第1個兩方ECDSA門限簽名方案，該方案在密鑰生成過程中利用乘法秘密分享以及Paillier加法同態(tài)加密技術(shù)來解決ECDSA門限化工作中的難點(diǎn)，使得2個簽名參與方能協(xié)同生成有效簽名。GENNARO等[5]為了解決比特幣錢包安全的問題，設(shè)計(jì)了基于門限加法同態(tài)加密技術(shù)的(t,q)門限方案，并在惡意模型下給出了安全證明。隨后，BONEH等[9]優(yōu)化了文獻(xiàn)[5]的方案，提出了le-vel-1全同態(tài)加密的門限簽名方案。但是，這些方案都采用了計(jì)算開銷和通信開銷都非常高的分布式同態(tài)加密密鑰生成技術(shù)，在實(shí)際應(yīng)用中受限。

LINDELL[10]提出的兩方方案由于不需要執(zhí)行分布式Paillier密鑰算法，減少了部分的計(jì)算開銷，與以前普通的DSA簽名的門限方案相比，效率有一定的提升。相反，DOERNER等[11]沒有采取同態(tài)加密方案而引入了不經(jīng)意傳輸技術(shù)，提出了滿足安全差異性需求的(2,n)門限ECDSA簽名方案。雖然文獻(xiàn)[11]的方案未利用同態(tài)加密技術(shù)，提高了協(xié)同簽名的計(jì)算性能，但是該方案引入了不經(jīng)意傳輸技術(shù)[12-13]，與文獻(xiàn)[10]的方案相比，增加了近千倍的通信開銷。近些年，國內(nèi)學(xué)者在ECDSA門限化的研究上也取得了一些進(jìn)展，如：王婧等[14]利用了Beaver三元組，提出了一種安全高效的兩方協(xié)同ECDSA簽名方案。

為了進(jìn)一步提升兩方ECDSA門限方案[10]的效率，本文提出了一個高效的兩方ECDSA門限方案。該方案主要有以下優(yōu)勢：(1)在每一次對消息M進(jìn)行簽名時，簽名雙方在保證不泄露自己簽名私鑰份額的前提下共同生成有效簽名；(2)不依賴待簽名消息完成簽名預(yù)處理，減少了簽名過程中所產(chǎn)生的計(jì)算量，提升了簽名效率。

1 預(yù)備知識

1.1 ECDSA算法標(biāo)準(zhǔn)

ECDSA算法是DSA算法的變體，利用了橢圓曲線加密算法(Elliptic Curve Cryptography,ECC)對DSA算法進(jìn)行模擬。與普通的離散對數(shù)問題和大整數(shù)分解問題相比，因?yàn)闄E圓曲線密碼是目前唯一無法用亞指數(shù)算法破解的公鑰密碼，所以橢圓曲線密碼的單位比特強(qiáng)度高于其他公鑰密碼體制。1999年，ECDSA算法成為ANSI標(biāo)準(zhǔn)，是目前應(yīng)用最廣泛的簽名算法之一。以下給出對ECDSA算法的形式化定義。

定義1[6](ECDSA)設(shè)H(·)為哈希雜湊函數(shù)，待簽名消息為M，所采用的橢圓曲線參數(shù)D=(E,G,P,p,q,h)，對應(yīng)的密鑰對為(x,Q)，其中，Q=x·P為公鑰，x為私鑰。

簽名步驟：

(1)選擇一個隨機(jī)數(shù)k←Zq;

(2)計(jì)算R←k·P，并令R=(rx,ry);

(3)計(jì)算r=rxmodq，若r=0，則重新從第(1)步開始執(zhí)行;

(4)計(jì)算待簽名消息M的哈希值H(M);

(5)計(jì)算簽名s=k-1(H(M)+xr)modq，若s=0，則重新從第(1)步開始執(zhí)行;

(6)輸出對消息M的簽名(r,s)。

驗(yàn)證步驟：驗(yàn)證方在接收到消息M和簽名(r,s)之后，進(jìn)行如下運(yùn)算：

(1)計(jì)算sP+H(M)Q=(x1,y1);

(2)當(dāng)且僅當(dāng)x1modq==r時，驗(yàn)證成功。

1.2 Paillier同態(tài)加密方案

Paillier同態(tài)加密方案PC=(PK,PE,PD)是基于復(fù)合剩余類的困難問題來保證加密方案的安全性的概率公鑰加密算法[15]。該方案的描述如下：

(1)密鑰生成算法PK：任選2個長度相同且滿足gcd(pq,(p-1)(q-1))=1的大素?cái)?shù)p和q，然后計(jì)算N=pq，令λ(N)=lcm(p-1,q-1)為N的卡邁可爾函數(shù)，并且任意選擇整數(shù)g令L(x)=(x-1)∕N，計(jì)算生成Paillier加密方案的公鑰ppk=(N,g)，私鑰psk=(λ(N),μ)。

(2)加密算法PE：選擇隨機(jī)數(shù)r然后計(jì)算密文C=E(m,r)=gmrNmodN2，其中mN為待加密信息。

(3)解密算法PD：針對密文C，對其進(jìn)行解密得到明文m=L(CλmodN2)×μmodN。

Paillier加密方案滿足加法同態(tài)加密性質(zhì)。對于任意2個明文a,bN，其對應(yīng)的密文分別為ea=PE(ppk,a)=gar1NmodN2和eb=PE(ppk,b)=gbr2NmodN2，其中隨機(jī)數(shù)r1,r2*n。定義則ea?eb為a+b的密文。定義

1.3 門限簽名算法

1991年，DESMEDT和FRANKEL[16]提出了第一個真正的門限加密以及簽名方案。一個(t,n)門限簽名方案中有n個成員參與分布式簽名，至少需要t+1(t+1≤n)個成員共同參與來生成簽名，如成員人數(shù)少于或者等于門限數(shù)量t則無法生成有效簽名。該方案通過將私鑰信息分割并由多個用戶分散保存，提高了系統(tǒng)的魯棒性及安全性。1個(t,n)門限方案可以分為如下3個子協(xié)議：

(1)分布式密鑰生成協(xié)議Thresh-KeyGen。該協(xié)議通過輸入安全參數(shù)1λ，每個參與簽名的成員Pi會獲得公鑰Pk以及對應(yīng)的私鑰份額ski，則sk1,sk2,…,skn是關(guān)于私鑰sk的(t,n)門限秘密共享。

(2)分布式簽名協(xié)議Thresh-Sig。此協(xié)議將待簽名的信息M作為公共輸入，同時將參與簽名成員的私鑰份額ski作為私有輸入，σi為每個簽名成員對信息M的簽名。該協(xié)議結(jié)束后，將所有的簽名份額σi合并后輸出簽名σ{Sig(sk,m)}。

(3)中心化驗(yàn)證算法Ver。輸入待簽名消息M、公鑰Pk和簽名σ，以檢查σ是否正確。若驗(yàn)證算法Ver輸出1，則簽名驗(yàn)證成功。

1.4 安全模型和定義

1.4.1 敵手模型 根據(jù)GENNARO等[7]對敵手模型進(jìn)行的描述可知，假定惡意敵手在(t,n)門限方案簽名階段至少可以攻擊n個成員P1,P2,…,Pn中的t個成員，然后根據(jù)攻擊能力的大小將敵手分為以下3種類型：

(1)竊聽敵手：能夠獲取被攻擊成員所存儲的信息以及接收其通信信道的廣播信息。

(2)中止敵手：不但擁有竊聽敵手的能力，而且可以促使被攻擊成員在每輪簽名開始時停止發(fā)送消息。

(3)惡意敵手：不但擁有竊聽敵手的能力，而且可以促使被攻擊成員修改協(xié)議。

1.4.2 安全定義 本文定義的門限簽名方案的安全性僅考慮不可偽造性，其定義如下：

定義2((t,n)門限簽名方案的不可偽造性)令ε=(Thresh-KeyGen,Thresh-Sig,Ver)為(t,n)門限簽名方案，稱其是不可偽造的，如果敵手可以自適應(yīng)地選擇k次待簽名信息M1,M2,…,Mk進(jìn)行門限簽名查詢之后，能夠在新的待簽名信息M′(M′{M1,M2,…,Mk})上偽造有效的門限簽名的概率是可忽略的。

2 高效的兩方ECDSA門限方案

本文提出的高效的兩方ECDSA數(shù)字簽名方案共包括3個部分，分別為密鑰生成算法TPKG、兩方簽名算法TPsign和簽名驗(yàn)證。

2.1 密鑰生成算法TPKG

在密鑰生成階段，由兩方共同生成數(shù)字簽名算法中用于驗(yàn)證簽名的公鑰和各方的部分簽名私鑰片，同時用戶1調(diào)用同態(tài)加密方案，將其私鑰的密文發(fā)送給用戶2。如圖1所示，令U1、U2分別表示為用戶1、用戶2，兩方分別執(zhí)行以下步驟：

圖1 密鑰生成算法TPKG

Step 1. 首先，用戶U1選擇隨機(jī)數(shù)x1←Zq作為子私鑰，并且計(jì)算子公鑰片P1=x1·P，其中P是ECDSA橢圓曲線的基點(diǎn)； 然后，用戶U1調(diào)用1.3節(jié)Paillier同態(tài)加密方案PC=(PK,PE,PD)，該同態(tài)加密方案的公鑰、私鑰分別為ppk、psk，將其所擁有的子私鑰利用Paillier同態(tài)加密方案進(jìn)行加密，其表示為ex1=PE(ppk,x1)。

Step 2. 用戶U1將子公鑰片P1和子私鑰同態(tài)加密密文ex1發(fā)送給用戶U2。

Step 3.U2同樣隨機(jī)選擇x2←Zq作為子私鑰，并計(jì)算子公鑰片P2=x2·P。

Step 4. 用戶U2將子公鑰片P2發(fā)送給用戶U1。

Step 5. 用戶U1在收到用戶U2發(fā)送的公鑰份額P2后，計(jì)算公鑰Pk=P2+P1，并存儲參數(shù){Pk,P2,ppk,psk}。

Step 6. 用戶U2在收到用戶U1發(fā)送的公鑰份額P1后，計(jì)算公鑰Pk=P1+P2，并存儲參數(shù){Pk,P1,ppk,ex1}。

2.2 兩方簽名算法TPsign

簽名生成階段包括2個步驟：離線預(yù)處理過程和在線簽名過程(圖2、圖3)。離線預(yù)處理過程不依賴待簽名消息，在正式簽名之前就可以生成所必需的數(shù)據(jù)，從而提高簽名效率。正式簽名時，一旦接收到待簽名消息M，簽名者可以高效地生成對消息M的簽名。兩方簽名算法TPsign的詳細(xì)過程如算法1和算法2。

圖2 簽名離線預(yù)處理步驟圖

圖3 在線簽名步驟圖

算法1離線階段的預(yù)處理算法

Step 1. 用戶U1生成隨機(jī)數(shù)k1←Zq，并計(jì)算R1=k1·P;

Step 2. 用戶U1將R1發(fā)送給用戶U2;

Step 3. 用戶U2選擇隨機(jī)數(shù)k1←Zq，b←Zq和ρ←Zq2;

Step 4. 用戶U2計(jì)算R2=k2·P;

Step 6. 用戶U2利用在密鑰生成階段從用戶U1獲得的同態(tài)加密公鑰來計(jì)算eb=PE(ppk,b+ρq)，此處為了讓傳遞的信息更加安全，用戶U2將ρ·q與b一起進(jìn)行同態(tài)加密;

Step 8. 用戶U2利用從用戶U1獲得的R1計(jì)算(x,y)=k2·R1;

Step 9. 計(jì)算r=xmodq;

Step 11. 用戶U1利用從用戶U2獲得的R2計(jì)算(x,y)=k1·R2;

Step 12. 計(jì)算r=xmodq;

Step 15. 用戶U2存儲參數(shù){x2,Pk,ppk,ex1,k2,r,b}。

算法2 在線簽名算法

Step 1. 用戶U2收到待簽名消息M后，計(jì)算待簽名消息M的哈希值h=H(M);

Step 3. 用戶U2將ps發(fā)送給用戶U1;

Step 5. 用戶U1輸出簽名σ=(r,s)。

2.3 簽名驗(yàn)證

本方案的簽名驗(yàn)證過程詳細(xì)表述如下：

Step 1. 用戶U1利用簽名驗(yàn)證算法對得到的簽名σ=(r,s)進(jìn)行驗(yàn)證：通過計(jì)算sP+H(M)Pk=(x,y)來驗(yàn)證是否滿足xmodq==r。若驗(yàn)證失敗，則終止協(xié)議。

Step 2. 用戶U2收到簽名σ=(r,s)后，采用與用戶U1相同的計(jì)算方式來驗(yàn)證簽名。如果2個通信方的驗(yàn)證都通過，則表明此次兩方ECDSA簽名有效，正常退出，否則終止操作。

3 方案分析

3.1 正確性分析

根據(jù)分布式密鑰生成算法，可得簽名驗(yàn)證公鑰：

Pk=P1+P2=x1·P+x2·G=(x1+x2)·P。

根據(jù)兩方協(xié)同簽名算法，可得

R=R1·k2=R2·k1=k1·k2·P。

此外,sk=x1+x2，k=k1·k2,可得

Pk=sk·P，R=k·P=(x,y)，r=xmodq，

由此可知，本文提出的兩方ECDSA簽名方案的輸出簽名(r,s)和驗(yàn)證公鑰Pk與ECDSA簽名方案的輸出簽名(r,s)和驗(yàn)證公鑰Q一致。所以，本文方案滿足設(shè)計(jì)目標(biāo)要求的正確性。

3.2 安全性分析

引理1[7]若簽名方案是不可偽造的，并且它的門限簽名方案是可模擬的，則該門限簽名方案也是不可偽造的。

下面給出可模擬的概念。

定義3一個(t,n)門限簽名方案需要滿足以下條件才可以說是可模擬的：

(1)門限簽名方案的密鑰生成協(xié)議Thresh-KeyGen是可模擬的。保證在輸入公鑰Pk和被破壞的t-1個成員的私鑰份額sk1,sk2,…,skt-1的條件下，存在一個能夠模擬其他人在Thresh-KeyGen協(xié)議輸出公鑰Pk的交互視圖的模擬器。

(2)門限簽名方案的分布式簽名協(xié)議Thresh-Sig是可模擬的。在輸入公鑰Pk，待簽名消息M以及對它的數(shù)字簽名σ，還有t-1個成員的私鑰份額sk1,sk2,…,skt-1的條件下，存在一個能夠模擬其他人在Thresh-Sig協(xié)議中輸出數(shù)字簽名σ的交互視圖的模擬器。

定理1如果ECDSA是EUF-CMA安全的，則本文的兩方ECDSA簽名方案是不可偽造的。

證明根據(jù)引理1，只需要證明兩方ECDSA門限簽名方案是可模擬的。由于本方案只存在2個用戶U1和U2，所以，僅考慮用戶U1被攻擊和用戶U2被攻擊2種情況，并分別展示如何模擬密鑰生成和簽名生成協(xié)議。

情形1:用戶U1被攻擊。假設(shè)敵手1攻擊并控制了用戶U1，再構(gòu)造模擬器im1來模擬用戶U2，通過提取用戶U1的輸入，生成一個敵手不可區(qū)分的交互視圖。

(2)模擬簽名生成。

③若第1條會話信息被解析為驗(yàn)證R1=k1·P，則模擬器im1令否則模擬器im1隨機(jī)地選取R2;

情形2:用戶U2被攻擊。假設(shè)敵手2攻擊并控制了用戶U2，現(xiàn)在構(gòu)造模擬器im2來模擬用戶U1，通過提取用戶U2的輸入，生成一個敵手不可區(qū)分的交互視圖。

(1)模擬密鑰生成。與用戶U1被攻擊的情況相同，假設(shè)敵手2破壞了用戶U2，那么由于模擬器知道用戶U2的私鑰份額x2和系統(tǒng)的公鑰Pk，則模擬器可以通過計(jì)算P1=Pk-x2·P來模擬用戶U1在密鑰生成算法TPKG中輸出公鑰Pk的視圖。所以，密鑰生成算法TPKG是可模擬的。

(2)模擬簽名生成。

綜上所述，根據(jù)引理1，無論是用戶U1還是用戶U2被攻擊，都可以構(gòu)造相應(yīng)的模擬器來模擬其協(xié)議的整個運(yùn)行過程，即可證明ECDSA門限簽名方案具有不可偽造性。證畢。

3.3 效率分析

在現(xiàn)有的兩方ECDSA方案中，LINDELL提出的方案[10]比DOERNER提出的方案[11](下文分別簡稱為LINDELL方案、DOERNER方案)的效率更高，究其原因?yàn)椋篋OERNER方案采用OT(Oblivious Transfer)技術(shù)來替代Paillier同態(tài)加密技術(shù)，在實(shí)際應(yīng)用中，一次k比特的OT運(yùn)算需要O(k)次公鑰密碼操作，與同態(tài)加密技術(shù)相比，其計(jì)算量更大。由于本文提出的方案與LINDELL方案[10]相類似，所以接下來將與LINDELL方案進(jìn)行效率對比。

本文提出的方案暫為一個基礎(chǔ)的兩方ECDSA門限方案，其安全性只達(dá)到被動安全級別，但同樣可以利用LINDELL方案中所采取的理想函數(shù)實(shí)現(xiàn)主動安全。在進(jìn)行效率分析時，忽略零知識證明，在半誠實(shí)模型下與本文方案進(jìn)行比較，并列舉出2個方案的指數(shù)運(yùn)算次數(shù)。

表1 2種方案的計(jì)算效率

4 結(jié)論

現(xiàn)有的兩方ECDSA簽名方案不是存在計(jì)算開銷過大的問題就是交互輪數(shù)過多，導(dǎo)致在實(shí)際應(yīng)用中的效率并不高。為了提高協(xié)同簽名效率，本文提出了一種高效的兩方ECDSA門限簽名方案，主要是將兩方簽名算法拆分為離線預(yù)計(jì)算算法和在線簽名算法，并且證明了其不可偽造性。與文獻(xiàn)[10]的兩方ECDSA方案相比，本文提出的方案計(jì)算效率高，其離線預(yù)計(jì)算階段完成了大部分的計(jì)算量，從而在線簽名階段僅僅需要簡單的操作。本文方案雖然只具有被動安全，但是在通用可組合安全框架下可以實(shí)現(xiàn)主動安全。