橢圓曲線密碼算法在VPN安全握手中的應用

白永祥

（1．西北大學 信息科學與技術學院，陜西 西安 710127；2．渭南職業技術學院 陜西 渭南 714000）

為防止網絡上未授權的用戶讀取信息，在VPN中，對通過公共網絡傳遞的數據必須實施加密，因此，加密技術是VPN中的一項關鍵技術。通常VPN采用安全套接層協議（Secure Sockets Layer，SSL）來實現數據的保密性、完整性及認證服務。在SSL會話中，使用證書來驗證通信雙方的身份，協商加密算法及密鑰生成等，通常采用基于RSA的非對稱加密算法交換密鑰，保證密鑰的安全性。由于RSA加密算法進行加密的VPN系統存在不足，我們提出將橢圓曲線加密算法（Elliptic Curve Cryptosystem，ECC）應用于SSL安全握手中。同RSA等常用加密算法相比較，ECC在相同的安全強度下具有密鑰長度短，運算量較小，復雜度低等特點，所以在實際應用中可以顯著提高運算效率[1]。

1 基于SSL協議的VPN

安全套接層SSL位于TCP和應用層之間，它主要適用于Point-to-Point之間的信息傳輸，常采用Client/Server結構模式 (簡稱C/S)，具有保護傳輸數據以及識別通信機器的功能。SSL主要采用非對稱加密體制和X.509數字證書技術,在Internet基礎上提供用戶和服務器身份的合法性認證、鏈路上的數據完整性和數據機密性等安全性保證。SSL并不是一個單獨的協議，它由兩部分組成，上層協議包括SSL握手協議、SSL密碼算法選擇協議和SSL警報協議，下層協議為SSL記錄協議。SSL握手協議（SSL Handshake Protocol）主要維護客戶和服務器之間的會話狀態，為通信雙方建立安全的傳輸信道，它建立在SSL記錄協議之上，是SSL協議中最復雜的部分。在執行握手協議的過程中實現對服務器的身份認證，或者對通信實體雙方身份進行鑒別，協商確定加密和鑒別算法以及協商密鑰。加密算法可以選擇DES、3-DES、IDEA、RC4等，鑒別算法可使用MD5、SHA-1、SHA-2等，密鑰交換常采用RSA公鑰算法來完成，當然還有其他一些輔助算法，如壓縮算法等。當這些順利完成后，才可以實現服務器和客戶機之間邏輯意義上的“安全握手”，再下來應用程序才能開始交換數據，具體過程如圖1所示。

圖1 客戶/服務器結構模式Fig.1 Client/Server structure mode

目前，SSL VPN接入技術有3種：Web代理、端口轉發和隧道技術。作為一種遠程接入技術，SSL VPN必須解決終端安全問題，并且真正的提供全網接入能力，客戶端（Client）將數據SSL封裝后發送到服務器，服務器端(Server)將來自客戶端的數據進行正確解碼后轉發到SSL協議的應用層，要求使用非對稱加密算法協商密鑰，傳統的基于RSA加密算法的SSL服務器CPU大量時間耗費在處理SSL加解密上，只有少量時間處理應用程序邏輯。本文基于橢圓曲線密碼體制的優勢將ECC加密算法應用到握手協議的加解密過程中。SSL握手協議有多種操作模式，圖2包括了所有工作模式下所涉及的消息[2]。

表1 SSL協議結構Tab.1 The SSL protocol srtucture

2 橢圓曲線密碼體制

圖2 SSL握手協議Fig.2 SSL handshake protocol

2.1 橢圓曲線加密體制原理

1985年，Miller和Koblitz各自獨立的提出了橢圓曲線公鑰密碼[3]，它是基于有限域上的橢圓曲線構成加密體制，其安全性基于有限域上橢圓曲線離散對數問題 （Elliptic Curve Discrete Logarithm Problem,ECDLP）的難解性。ECDLP難解性是指：對于曲線上給定的離散點P和Q，難以找到整數I，使得I×P=Q。設P為公鑰，Q為私鑰，其安全性就表現為知道P無法推導Q。對于有限群上的x和y，若存在正整數n，使得y=xn，求解n=logxy的問題稱為有限群上離散對數問題（Discrete Logarithm Problem,DLP）。而對橢圓曲線上離散點P和Q，求解I，使得I×P=Q稱為橢圓曲線離散對數問題，ECDLP的難解性優于DLP。

由于橢圓曲線加密算法具有密鑰長度短，占用存貯空間少、靈活性好等特點，所以在運算速度和存貯空間方面有很大的優勢，與同長度密鑰算法相比較安全性高，是一種能適現代通信技術及信息安全技術發展的先進加密體制。由于服務器端的CPU處理能力和存儲空間都有限，所以橢圓曲線加密算法相對于以往基于RSA加密算法的握手過程具有絕對的優勢，目前已成為非對稱密鑰加密體制中的研究熱點。

2.2 ECC加密和解密算法原理

非對稱加密方案可用來提供機密性，但加密過程比較復雜，運算量大，不適應于對大量數據的加密解密，一般應用在少量數據的加密上，如信用卡號碼、密鑰加解密。大批量的數據文件加解密使用運算速度更快的對稱密鑰算法來完成。下面給出了加密和解密方案[1]：

加密過程，當用戶Alice發送信息M給用戶Bob時，用戶Alice執行下列步驟：

1)找出 Bob的公鑰 QB；

2)將信息M表示成橢圓曲線E(Fq)上的一點m，且m∈Fq；

3)在區間[1,n-1]內隨機選取一個整數k；

4)計算點(x1，y1)=kP；

5)計算點(x2，y2)=kQB，如是 x2=0，則返回到第 3)步；

6)計算 c=m×x2；

7)將加密數據(x1，y1，c）傳送給 Bob。

解密過程，當Bob解密從Alice收到的密文 (x1,y1,c)時，Bob執行下列步驟：

1)Bob 使用私鑰 dB，計算點(x2,y2)=dB(x1,y1)，得出 x2∈Fq；

在上述過程中，QB=dP是公開的，如果除Alice、Bob外的第三者能解答橢圓曲線上的離散對數問題，就能從dP中求出d，從而解密信息m。

3 ECC優勢及其在SSL安全均衡中的應用

1)ECC優勢:在相同安全性下，橢圓曲線加密算法的密鑰短，所以計算量小、占用存儲空間小、處理速度快，與RSA相比橢圓曲線的密鑰長度和系統參數要小得多，比如：160位ECC與1 024位RSA具有相同的安全強度，210位ECC安全強度等同于2 048位RSA，很明顯ECC它所占用存儲空間要小得多，相應的橢圓曲線加密算法的帶寬要也非常低。此外，由于橢圓曲線具有豐富的群結構和多選擇性，可以通過改變參數設置獲得不同的曲線，所以，橢圓曲線加密算法的靈活性要高于RSA加密算法。

2)對ECC加密算法的優化:橢圓曲線有理點加法運算構成一個群，設P是橢圓曲線上的一個點，將P自身相加k倍在運算，稱為倍點運算。在橢圓曲線公鑰生成和加密解密算法中需要大量的倍點運算，因此，對倍點運算的優化意義重大，倍點運算如下：

計算倍點最常用的方法是二進制法，具體步驟如下：

①令Q=P；

②For i=l-1 to 1 step-1

Q=2Q

if ni=1 then Q=Q+P

③輸出Q。

具體的倍點運算優化算法如下[4]：

①將k表示成二進制數形式，k=(knkn-1…k1k0)2；

②去掉 k=(knkn-1…k1k0)2的最高位 kn，得(ki-1…k1k0)2；

③P1=P,P2=2P,i=1；

若 i≤2h-1，則作 P2i+1=P2i-1+P2；

④Q=O；

⑤若i≥0轉⑥，否則轉⑧；

⑥若ki=0，則Q=2Q，i=i-1否則轉⑦；

⑦Q=2i-l-1Q+P(ki…kl),i=l-1 轉⑤；

⑧輸出Q。

采用常規方法，需進行n次點加運算；在以上算法中，平均只須3/2[log2n]次運算，最多需要2[log2n]次運算。

在對明文m加密之前，首先要將明文m映射到橢圓曲線有限域Fq上的一個點，這就需要判別數是否為模P下的平方剩余。現有的平方剩余判定算法只簡單地根據平方剩余定義來判別，如果涉及大數的平方運算和取模運算，算法效率就會非常低，所以如何提高平方剩余判定方法的效率非常關鍵。

如果明文m映射到點Pm(x,y)上，即滿足：256≤x≤256(m+1)，Pm(x,y)∈Fq。 這個問題可以轉換為：

給定一個x，判定A=x3+ax+b是否是模p下的平方剩余。即判定A/p是否為1，即如下情況所示。

4 基于ECC的SSL安全均衡握手協議

Alice向Bob在傳輸數據前，就必須知道Bob的公鑰，如何保證Bob的公鑰不被人假冒或修改，這里就需要對Bob進行身份認證，通常使用數據證書實現這一目標。所謂數據證書就是網絡通信中的“身份證”，一般由一個權威機構認證機構頒發（CA），客戶證書就是一份關于用戶公鑰的文件，采用數據簽名技術來保證文件的真實性。在設計適合于VPN系統的安全協議時，首先要解決這個問題[5]。這里選用一種簡化了的X.509標準的證書形式，用戶Bob的證書可能如下：

在基于ECC密碼算法體制下，首先要為Alice、Bob生成公鑰和私鑰，然后才能進行加密、解密和簽名，整個這個過程非常復雜，此處不再詳述，有興趣的讀者可以閱讀相關資料。這里簡單描述一下形成過程。

1)認證中心選擇定義在有限域上的橢圓曲線E[GF(q)]

E上的點構成循環群P∈E[GF(q)]，CA選取一條橢圓曲線，G稱為基點，且=k，k≥160位，這樣選擇的橢圓曲線能保證其上的離散對數難解性[5]。

2)CA隨機選擇一個數KCA∈{1,2,…,l-1}，作為其私鑰，(KCA,l-1)=1，計算公鑰PUCA，并公開公鑰，以便對服務器端和客戶端的證書進行簽名。

3)客戶隨機選擇一個數Cd∈{1,2,…,l-1}，作為其私鑰，(Cd,1）=1，計算PUC作為其公鑰，并提交給CA為其頒發證書：

這里SIGNC是CA的簽名。用戶聯網時，為其生成私鑰和公鑰，同時根據用戶提交的有效信息生成證書：

4)客戶接收到服務器端證書后，首先要驗證證書的合法性，并利用證書中的信息IDC,PUC,TimerC生成：

然后驗證：

如果不成立，立即停止繼續執行，否則，則簽名有效，證書合法，并計算kP,k,PUVN和Q=(SVN+k)PUVN=(X,Y)

X和Y分別是點Q的坐標。保存{k,kP,kpVN}和X。這里一定要注意k在每次進行身份認證的時候都必須重新隨機產生。

5 結論

在橢圓曲線加密算法中采用160 bits的密鑰可與1024bits密鑰的RSA算法的安全性相當，且隨著模數的增大，它們之間安全性的差距猛烈增大[6]。本文首次把橢圓曲線加密算法技術運用到了SSL VPN的安全握手技術中，并使用了倍點加速優化技術，與傳統的加密和解密過程相比較，使SSL服務器的工作效率得到大大提高。

[1]王學理，裴定一.橢圓與超橢圓曲線公鑰密碼的理論與實現[M].北京：科學出版社，2006.

[2]Cryptography and network security principles and practice,fifth edition[M].北京：電子工業出版社.2011.

[3]祝躍飛，張亞娟.橢圓曲線公鑰密碼導引[M].北京：科學出版社，2006.

[4]Jose H.Silverman.The arithmetic of elliptic curves[M].Springer-Verlag.1992.

[5]李麗，劉福軍.基于ECC加密算法的SSL VPN安全握手技術研究[J].遼寧工業大學學報,2008(8):228-231.LI li,LIU Fu-jun.The research of SSL VPN security handshake technology based on ECC[J].Journal of LiaoNing University of Technology,2008(8):228-231.

[6]吳世忠，祝世雄等.應用密碼學協議、算法與C源程序[M].北京：機械工業出版社,2010.