郭士增

（哈爾濱工業(yè)大學，黑龍江 哈爾濱 150001）

0 引 言

基于橢圓曲線密碼體制的多方認證密鑰協(xié)商協(xié)議即為多用戶之間協(xié)商并加入身份驗證這一機制的密鑰協(xié)商協(xié)議，當今可將區(qū)塊鏈存儲技術思想應用于基于橢圓曲線的多方密鑰協(xié)商協(xié)議方案。首先針對基于區(qū)塊鏈存儲的多方認證密鑰協(xié)商協(xié)議進行協(xié)議有效性和可靠性的分析，其次對協(xié)議有效性提升提出了優(yōu)化的點乘算法，并在協(xié)議可靠性驗證上針對密鑰體制安全性仿真分析了Pollard-rho攻擊算法，估算了破解時間。

1 多方密鑰協(xié)商協(xié)議有效性與可靠性衡量

衡量多方認證密鑰協(xié)商協(xié)議的有效性指標為通信輪數(shù)、計算次數(shù)和計算量。計算量這一指標在某些有效性要求高的場景下會用通信時延來代替。文中采用計算量的衡量方法。

通信輪數(shù)：2輪。第一輪為用戶Ui與用戶{Ui-2,Ui-1,Ui+1,Ui+2}進行通信，向用戶{Ui-2,Ui-1}處發(fā)送消息，從用戶{Ui+1,Ui+2}處接收消息。第二輪為與服務器進行通信，發(fā)送消息(mi′,Sigi(H(mi′)))，接收消息(mi′′,Sigi(H(mi′′)))。該協(xié)議通信輪數(shù)為2，屬于較少輪數(shù)的協(xié)議，滿足場景要求。

計算次數(shù)：單個普通用戶（排除驗證節(jié)點）的計算次數(shù)為4，分別為協(xié)議第一輪中計算Zi的1次點乘計算、第二輪中計算αi中的2次點乘計算和1次安全單向函數(shù)的計算。

計算量：計算量指標是指根據(jù)相關文獻結(jié)論，對基本運算計算復雜度的估計。設求逆元運算的復雜度為I，乘法運算復雜度為M，平方運算復雜度為S，設密鑰長度為l，可得出3次點乘計算量約為4lI+8lM+7lS，而安全單向函數(shù)在仿真中使用平方取中法，計算量僅有1次平方運算。因此，可以認為計算量為4lI+8lM+7lS。

多方認證密鑰協(xié)商協(xié)議的可靠性要求大多采用已知密鑰安全性、完美前向保密性、密鑰不可控制性、抵抗密鑰泄露攻擊、密鑰共享可知性、會話密鑰托管（SessionKey Escrow，SKE）、密鑰值偏移攻擊（Key Off-set Attack，KOA）、抵抗中間人攻擊（Man-in-the-middle Attack Resilience，MITM） 和防重放攻擊等標準衡量。

已知密鑰安全性：攻擊者通過已知的過去的密鑰無法得到新會話密鑰。因為在本協(xié)議中每個用戶都會在第一輪產(chǎn)生隨機數(shù)作為短暫的私鑰，因此每次最終產(chǎn)生的密鑰是唯一的。由于該私鑰在一次會話結(jié)束后立即被舍棄，攻擊者通過已知的過去的密鑰無法得到新會話密鑰。

完美前向保密性：一個用戶或多個用戶長期使用的私鑰被泄露，對于該私鑰泄漏前生成的會話密鑰不產(chǎn)生影響。由于本協(xié)議除數(shù)字簽名外不會使用長期私鑰，每次生成密鑰的過程中都會使用新的隨機數(shù)作為私鑰，因此不會導致之前的會話密鑰泄露。因此，本協(xié)議滿足完美前向保密性。

密鑰不可控制性：參與群組通信的不同用戶都不能對協(xié)商的會話密鑰預先控制為特定值。本協(xié)議雖然有驗證節(jié)點和服務器這種與普通用戶權(quán)限不同的節(jié)點參與密鑰協(xié)商，但各方都不能對協(xié)商最終產(chǎn)生的會話密鑰預先控制。最終密鑰包含每個用戶節(jié)點產(chǎn)生的短私鑰信息，具有隨機性，不可預先生成。

抵抗密鑰泄露攻擊：假設用戶A的私鑰長期泄露，那么攻擊者能夠假扮用戶A欺騙其他用戶，但不能扮演其他用戶去欺騙A。由于本協(xié)議在用戶與用戶之間和服務器之間都采用了數(shù)字簽名技術，而且每次通信均由驗證網(wǎng)絡進行身份驗證，因此防止了攻擊者已知Si情況下的密鑰泄露攻擊。

密鑰共享可知性：協(xié)議在全體用戶知曉下才能進行，任一或多個參與者不知曉的情況下，都不能進行密鑰協(xié)商協(xié)議。根據(jù)協(xié)議本身網(wǎng)絡結(jié)構(gòu)與過程可知，每個用戶與相鄰的4個用戶進行通信，而聯(lián)盟鏈場景下成員間相互信任并知曉成員數(shù)量和某些身份信息，因此在計算中如果跳過某成員，那么它相鄰的成員在通信時會察覺出某用戶不知曉的情況，此時該協(xié)議停止。

會話密鑰托管SKE：通過監(jiān)聽協(xié)議參與者在協(xié)議運行過程中的通信過程，根據(jù)已有消息以及通信過程獲得的消息，可以恢復該次協(xié)議運行產(chǎn)生的會話密鑰。根據(jù)本文提出的協(xié)議，服務器可通過累加得到最終密鑰。但是，由于第三方中心每次通信時都需經(jīng)過驗證網(wǎng)絡驗證，因此一旦第三方可信中心利用最終密鑰作惡時，驗證網(wǎng)絡可知曉其行為異常，且記錄在系統(tǒng)賬本中，可終止服務器與用戶間的通信，防止其繼續(xù)做惡。

密鑰值偏移攻擊KOA：該攻擊是指攻擊者攔截并篡改通信參與者之間交互的信息，使通信參與者最終計算出的密鑰值是錯誤的。如果協(xié)議可以避免這種情況的發(fā)生，則稱該協(xié)議能夠抵抗密鑰值偏移攻擊。因為在本協(xié)議的通信過程中，每次信息都會包含散列值與數(shù)字簽名，因此一旦篡改密鑰或信息都會改變散列值進而改變簽名，隨后驗證網(wǎng)絡察覺異常并被信息接收者知曉。本協(xié)議滿足該指標。

抵抗中間人攻擊MITM：中間人攻擊是指攻擊者與通信的參與方分別建立獨立的聯(lián)系，并交換所收到的數(shù)據(jù)，使通信的參與者認為他們正在通過一個私密的連接與對方直接對話，但事實上整個會話都被攻擊者完全控制。由于用戶間通信需要進行數(shù)字簽名及身份驗證，如在第一輪中用戶與相鄰用戶進行通信的過程中使用了數(shù)字簽名，在中間人不知道用戶數(shù)字簽名的私鑰的前提下，中間人無法偽造用戶的數(shù)字簽名，因此不能進行中間人攻擊。若中間人在用戶通信開始前已經(jīng)控制了雙方通信過程，即同時偽造兩個身份與雙方通信，此時中間人使用自己的私鑰并發(fā)給用戶對應對方的偽造公鑰。由于用戶事先在服務器（或可信第三方機構(gòu)）注冊密鑰對中的公鑰，因此在基于PKI體系認證中其他用戶會根據(jù)服務器發(fā)送的證書得知該用戶可信合法的公鑰，從而知曉中間人的簽名與用戶簽名不同而終止協(xié)議。而在身份認證中，其他用戶預先知曉用戶的合法公鑰，中間人的攻擊同樣不會奏效。

防重放攻擊：重放攻擊是指攻擊者把截取到的以前消息再次發(fā)送給接收者，以此使接收者認為其正在通信。由于每次通信中消息都加入了時間戳，因此使用之前的消息進行攻擊會與用戶解密出的消息時間戳不同，從而使用戶發(fā)覺被攻擊而終止協(xié)議。

根據(jù)上述分析，公網(wǎng)-專網(wǎng)聯(lián)盟場景下對于多方密鑰協(xié)商協(xié)議可靠性滿足密鑰共享可知性；對于每次生成消息的數(shù)字簽名和散列值可防止任意一個成員否認或纂改，滿足完美前向保密性；監(jiān)聽者只監(jiān)聽用戶之間的消息，那么監(jiān)聽者只能得到第一輪中的消息而無法得出最終生成的會話密鑰，滿足密鑰不可控制性；因為第一輪消息的保密性是基于橢圓曲線上的離散對數(shù)問題（Elliptic Curves Discrete Logarithms Problem，ECDLP）問題難解，即抵抗中間人攻擊，協(xié)議滿足抵抗密鑰泄露攻擊要求指標。綜上所述，給出的方案滿足該場景下的可靠性要求。

2 橢圓曲線加密攻擊Pollard-rho算法

在公網(wǎng)-聯(lián)盟鏈情形下的多方認證密鑰協(xié)商協(xié)議的一般場景，每個用戶的私鑰的破解是攻擊算法的目標[1]。根據(jù)橢圓曲線基本原理，從程序?qū)崿F(xiàn)角度，將n次點加運算累加引入數(shù)據(jù)乘2的運算，降低了運算次數(shù)。而對于ECDLP問題，尚未發(fā)現(xiàn)有效的亞指數(shù)級計算復雜度的一般攻擊方法，且ECDLP的攻擊算法大多只針對特定橢圓曲線有效[1]。因此，研究針對階數(shù)為合數(shù)與素數(shù)的橢圓曲線進行攻擊的一種Pollard-rho算法，對于存在較小階n橢圓曲線的ECDLP問題進行求解，分析基于橢圓曲線加密的密鑰協(xié)商協(xié)議可靠性。假設ECDLP問題中橢圓曲線參數(shù)如下：素數(shù)p，橢圓曲線E，橢圓曲線參數(shù)a、b，基點P，階為n，橢圓曲線上另一點Q，其中Q=kP，k為常數(shù)。對于ECDLP求解問題，已知P、Q，求解k。

2.1 點乘優(yōu)化算法

假設Q=kP，階數(shù)n。求解的問題為：已知P、Q，求解k。

點乘運算和點加運算是橢圓曲線密碼體制的基本運算，一般把點乘運算分為多倍點運算和2倍點運算。兩種優(yōu)化算法都是基于2倍點運算和點加運算的點乘算法。最基礎的點加運算和2倍點運算可按式（1）和式（2）進行計算。

對于基本運算計算復雜度的估計，可推出表1。

表1 基本運算的復雜度

兩種點乘的優(yōu)化算法分別為二進制展開法和加減法，這里給出加減法算法。

本算法原理是3k和k對應比特不同時說明低位有進位從而計算k。利用這一過程直接進行點加操作，從而求出kP。其中，Q-P的運算是通過Q+(-P)實現(xiàn)的。假設P(x,y)，定義-P(x,-y)。

第一步，將倍數(shù)k和3k轉(zhuǎn)換為二進制數(shù)，k為krkr-1…k1k0，3k為hrhr-1…h(huán)1h0，其中3k的最高位為1，同時創(chuàng)建Q[1][2]數(shù)組存儲Q點坐標；

第二步，置Q為點P，i為r-1（i為循環(huán)變量）；

第三步，Q=2Q，將坐標存入數(shù)組對應位置；

第四步，（1）若hi=1且ki=0，則Q=Q+P；

（2）若hi=0且ki=1，則Q=Q-P；

（3）將坐標存入數(shù)組對應位置；

（4）i-1；

第五步，判斷i是否小于1，若是，輸出Q坐標；否則返回第三步。

圖1為加減法算法流程圖。

圖1 加減法算法流程

計算多倍點乘運算，設k的比特數(shù)為l，k的碼重為W。二進制展開法需要l-1次2倍點運算和W-1次點加運算；加減法需要l次2倍點運算和l/3次點加運算。設求逆元運算的復雜度為I，乘法運算復雜度為M，平方運算復雜度為S，

由于k具有隨機性，一般有W≈l/2，可得到二進制轉(zhuǎn)換法計算復雜度為1.5lI+3lM+2.5lS，加減法算法計算復雜度1.33lI+2.67lM+2.33lS。加減法比二進制轉(zhuǎn)換法計算復雜度低，因此加減法在時間復雜度要優(yōu)于二進制轉(zhuǎn)換法[2]。

2.2 Pollard-rho算法

假設Q=kP，階數(shù)n。求解的問題為：已知P、Q，求解k。Pollard-rho算法的思想是將循環(huán)群分為不同子群，循環(huán)群的行走路線像一條ρ行的線，因此有很大概率當不同子群（以不同步長）進行行走時會走入同一個環(huán)。不同步長行走的點重合時，可以根據(jù)參數(shù)求解k，如式（3）所示。文獻[3]給出了Pollard-rho算法過程。

由Pollard-rho算法的流程和算法思想可以發(fā)現(xiàn)：該算法的核心思想是在每次迭代中按照不同步長行走i步和2i步的點進行比較，二者相等時只要按照待定系數(shù)法即可求得k。算法第一步中選取子群的初始位置可以有多個，根據(jù)算法思想，初始位置變化后會對求解迭代次數(shù)有影響。從這個特征可以看出，Pollard-rho算法是一個隨機型算法，無法給出其運算上界，只能給出其期望運算次數(shù)。綜上所述，雖然Pollard-rho算法是ECDLP問題求解的有效算法，但是在計算資源無限的情況下仍然不能保證求出正確的解，而由于計算資源有限，求解ECDLP問題依舊被認為是困難的，由此保證了橢圓曲線加密體制的安全性[3]。

3 點乘優(yōu)化算法和Pollard-rho算法仿真

協(xié)議攻擊者根據(jù)監(jiān)聽消息破解用戶私鑰，從而求出最終密鑰。通過求解該曲線上的ECDLP問題來完成目的，在k和n較小情況下模擬Pollard-rho算法的迭代求出迭代次數(shù)，并對曲線進行分析，根據(jù)復雜度估算Pollard-rho算法對于實際情況下的橢圓曲線的ECDLP問題破解時間。

數(shù)據(jù)導入處理和破解時間計算的平臺為matlab，算法運行的平臺為Visual Stdio 2010。

3.1 點乘優(yōu)化算法仿真

對應的求逆元運算程序根據(jù)擴展歐幾里得算法編寫。這一方法分為求最大公因數(shù)和求模逆元兩部分。該算法求模逆元的運算次數(shù)與輾轉(zhuǎn)相除的次數(shù)m成正比，即時間復雜度為O(m)。由對應求模逆元程序運算次數(shù)為5m+5，計算量對比中運算次數(shù)取5m。在橢圓曲線密碼體制計算中的數(shù)字乘法運算需加3次取模運算，平方運算需加2次取模運算。假定數(shù)字的乘法與取模運算計算次數(shù)為1，平方運算計算次數(shù)為3，乘法運算計算次數(shù)為4。以計算次數(shù)作為計算量單位，表2給出了部分仿真參數(shù)的具體數(shù)值，其中m為輾轉(zhuǎn)相除次數(shù)。在橢圓曲線上點的坐標運算中，m隨橢圓曲線參數(shù)中的p增大而增大，也受坐標差值而制約，因此處于波動狀態(tài)，但有上界和下界。計算中，m取10。圖2給出了密鑰長度對點乘優(yōu)化算法計算量的影響圖。

表2 部分仿真參數(shù)和變量

圖2 不同密鑰長度下兩種算法性能比較

從圖2看出，在不同密鑰長度下，加減法的性能明顯優(yōu)于二進制轉(zhuǎn)換法，同時加減法的計算次數(shù)與二進制轉(zhuǎn)換法的計算次數(shù)成正比。但是，兩種算法的計算量均比計算k次點加運算的計算量小很多。兩種算法計算次數(shù)成正比的原因是，求逆元運算計算次數(shù)遠大于乘法運算和平方運算。因此，兩種算法的計算次數(shù)主要由二者求模逆元次數(shù)決定。

3.2 Pollard-rho算法仿真

3.2.1 階數(shù)和密鑰長短對Pollard-rho算法的影響

Pollard-rho算法是一個概率性算法，研究階數(shù)和密鑰大小對Pollard-rho算法求解ECDLP問題時迭代次數(shù)的影響。先在階數(shù)n∈[20～211]、n取素數(shù)的前提下，對一定初始位置下Pollard-rho算法進行仿真對迭代次數(shù)進行統(tǒng)計。表3給出了部分仿真參數(shù)的具體數(shù)值。

表3 部分仿真參數(shù)和變量

圖3為階數(shù)n對算法迭代次數(shù)的影響曲線圖。隨著階數(shù)n的增加，迭代次數(shù)總體呈折線式上升，其中該算法迭代次數(shù)與算法計算次數(shù)、時間復雜度成正比。這一結(jié)論驗證了階數(shù)n越大，求解ECDLP問題計算量越大，從側(cè)面驗證了橢圓曲線密碼體制的安全性和協(xié)議可以抵抗監(jiān)聽者的被動攻擊。

圖3 階數(shù)n對Pollard-rho算法迭代次數(shù)影響

密鑰大小是隨機生成的，小于橢圓曲線階數(shù)的正整數(shù)。密鑰不同，對Pollard-rho算法的迭代次數(shù)有著影響。在3個不同階數(shù)的情況下，測試破解不同密鑰需要的迭代次數(shù)。密鑰大小取[2n-1]，n為階數(shù)。表4給出了部分仿真參數(shù)的具體數(shù)值，圖4給出了不同階數(shù)的情況下不同密鑰與需要的迭代次數(shù)關系圖。

表4 部分仿真參數(shù)和變量

圖4 密鑰大小與Pollard-rho算法迭代次數(shù)關系

由圖4的曲線可以得出以下結(jié)論：

（1）不同階數(shù)的橢圓曲線密鑰大小對Pollardrho算法迭代次數(shù)影響具有一定的相似性。3條曲線形狀有很大的相似性，說明Pollard-rho算法具有一定的穩(wěn)定性，無論對于階數(shù)大小如何，所有大小的密鑰破解情況具有相似性。

（2）對于一條既定橢圓曲線上的密鑰，迭代次數(shù)隨密鑰大小遞增有以下規(guī)律：k=2時取最大值，隨后多次遞增和遞減，最后k接近階數(shù)n時呈線性遞減。

（3）得到曲線形狀相似，驗證了Pollard-rho屬于概率性算法，一條曲線上破解密鑰的平均迭代次數(shù)應與計算復雜度成正比。

根據(jù)結(jié)論兩協(xié)議可以采取不安全密鑰舍棄原則：產(chǎn)生的密鑰過小或過大都不足夠安全。密鑰較小時，攻擊者采用此算法迭代次數(shù)非常大，已知橢圓曲線參數(shù)的情況下，攻擊者會先存儲密鑰較小時kp的坐標，若協(xié)議用戶采用這種密鑰，會直接被攻擊者根據(jù)表內(nèi)查找kp坐標，此時密鑰安全性很低；密鑰較大接近于階數(shù)時，采用該算法迭代次數(shù)較低，密鑰也不具有安全性。因此，協(xié)議用戶在隨機生成密鑰后，若密鑰符合上述兩種情況，應當舍棄此密鑰，選取適當大小的密鑰，提高協(xié)議的可靠性。

3.2.2 密鑰長度對破解時間的影響

隨著密鑰長度的增加，破解時間增加，對不同密鑰長度下進行破解仿真。假設算法可實現(xiàn)求解，根據(jù)給出的算法復雜度，可估算破解時間。表5給出了部分仿真參數(shù)的具體數(shù)值。

表5 主要參數(shù)和變量

階數(shù)n為合數(shù)，圖5給出了密鑰長度增加對破解時間的影響圖。隨著密鑰長度增加，破解時間在對數(shù)坐標軸下呈線性增長趨勢，即密鑰長度增長時，破解難度增加，破解時間呈指數(shù)級上升。從圖5可以看出，密鑰長度為106 bit時，Pollard-rho算法的破解時間在104年量級；密鑰長度為160 bit時，破解時間1012年量級。160 bit長度的密鑰是安全的，對橢圓密碼體制威脅很小。

圖5 密鑰長度對Pollard-rho算法破解時間影響

4 結(jié) 語

通過對求解一般橢圓曲線上的ECDLP問題的Pollard-rho算法仿真，研究不同階數(shù)和不同密鑰對算法求解該問題的計算量影響，得出了隨階數(shù)增大，Pollard-rho算法計算量增大和不同階數(shù)的橢圓曲線密鑰大小對Pollard-rho算法迭代次數(shù)影響具有一定相似性的結(jié)論，并提出了一個針對協(xié)議的不安全密鑰舍棄的原則。

根據(jù)Pollard-rho算法復雜度，估算出不同密鑰長度下的破解時間，驗證了橢圓曲線密碼體制的安全性，證明了協(xié)議的可靠性，給出了協(xié)議應采用160 bit長度密鑰的依據(jù)。