基于橢圓曲線加密算法的SET協議改進研究

圣文順 王玉祥 孫艷文

1(南京工業大學浦江學院 江蘇 南京 211200) 2(南京信息工程大學計算機與軟件學院 江蘇 南京 210044)

0 引 言

電子商務統指在網絡上從事的交易行為，可以用來買賣商品、信息和服務等[1]。由于全程通過互聯網絡操作，不受地理位置、時間等外界因素的影響，交易方式靈活，耗費的財力和人力少且交易過程簡潔，所以備受人們的喜愛[2]。電子商務作為網絡信息社會中一種新興的商務模式，一直在改變著人們的衣食住行。

電子商務的核心問題是如何保證其安全性，由于所有交易環節都在網絡上進行，交易雙方對彼此的身份知之甚少，這使得交易過程存在一定的安全隱患[3-5]。為了更好地發展電子商務，研究人員著力于研發更為安全、高效的加密技術。

1996年2月，國際組織的兩大信用卡發行商MasterCard和VISA共同商議并最終敲定安全電子交易協議，即SET協議[6]。此后，全球各大金融機構都紛紛自發地研發能夠應用于SET協議的軟件和相關技術。當前，SET協議已經成為全球電子交易領域的規范和標準。SET協議最適合應用于商家與消費者交易模式，可以實現三方認證，因此獲得了該行業中的Microsoft、惠普、IBM和美國網景[7-9]等大型公司的支持，并通過了IETF標準的認可，成為商家與消費者模式的權威標準。MasterCard和VISA兩大信用卡國際組織于1997年12月共同成立了能夠在全球范圍內管理與促進安全電子交易SET協議推廣應用的安全電子交易有限公司。該公司被授予了一些最高等級的權利，諸如可以認定根認證機構，建立一個具有分層結構的認證系統等。

安全電子交易協議也具有一定的缺陷，例如操作過程不夠簡單、耗費財力過高且難以普及等，待進一步改進和提高。本文從電子商務SET協議的基本原理[10]出發，對電子支付安全體系中涉及的算法和技術都做了詳細的介紹；著重分析研究橢圓曲線加密算法的基礎理論框架[11]；基于橢圓曲線技術對SET協議進行改進，并融合了MD5哈希生成算法[12]提高數據加密的安全性；通過大量仿真實驗進行算法性能對比，驗證改進后算法的優越性。

1 基于橢圓曲線的SET協議改進

1.1 基于一補數減法形式的改進算法

為了提高橢圓曲線上標量點乘kP的計算效率[13-15]，提出了用二進制的補碼來進行運算的改進辦法，首先將整數k轉換成二進制，然后用二進制位權的補數形式來表示整數k，具體實現算法如下：

1) 一補數減法形式方法。若正整數k的二進制表示為(ki-1,…,k1,k0)2，則將其轉換為一補數減法[16-17]形式：

(1)

(100000000)2-(00010100)2-1=

(2)

通過上述計算結果我們可以得出，若k的二進制表示對應的漢明權[18]相比其一補數減法形式較大時，則對其進行轉換是非常必要的。因為在標量乘計算中，k越大計算量就越大。

算法1一補數形式計算標量乘的算法

輸入：k=(kl-1,…,k1,k0)2,P∈E(Fq)。

輸出：Q=kP。

Step2If 0≤i≤l-1

Ifki=1

Q←Q+P；

Else

Q←Q-P；

Step3返回Q；

End

從上述例子可以看出，轉換前后運算次數相差兩次，很明顯經轉換后計算次數減少了近一半。將算法1稱為一補數減法形式，簡稱CS形式。將NAF方法[19]與CS方法基于二進制長度的變化進行比較，比較結果如表1所示。

表1 不同二進制長度下NAF與CS方法運算時間對比 ms

可以看出，CS方法很明顯比改進前的NAF算法要高效、快速。

2) 部分使用一補數減法形式方法。二進制表示轉換成一補數減法形式具有簡單、快速的優點，但是在減少二進制表示的漢明權效果上并不是對所有的標量都有效。因此，在CS方法的基礎上需做進一步改進，通過特定的算法來判斷是否需要進行轉換以及對哪一部分進行轉換，稱該方法為部分使用一補數減法，簡稱PCS方法，如算法2所示。

算法2將二進制表示的整數轉換成部分使用一補數減法

輸入：k=(kl-1,…,k1,k0)2。

輸出：k的PCS形式k′。

Step1i=0；

Step2Ifi≤l-3

Ifki=ki+1=1

j=i+2；

Ifj≥0

Ifkj=0

Ifj≤l-3且kj+1=kj+2=1

j=j+3；

Else跳出j≥0循環；

Elsej=j+1；

Else Ifl=((j-1)-i+1)>2

If 0≤n≤j-i

kn+i=mn；

i=j；

Elsei=j+2；

Elsei=i+1；

Step3返回k的PCS形式k′；

End

對于是否進行轉換，評判標準為：如果有兩個連續的“1”則進行標記以便進一步判斷。即轉換部分所需要滿足的條件為：

(3)

式中：i≥2，j≥0，k≥2。式(3)的含義為：如果在掃描過程中遇到兩個連續的“1”則先將其進行標記，若掃描到“0”，則繼續掃描“0”后面是否有兩個“1”，若符合則往下掃描，否則在“0”前終止，所得結果為前面的標記部分TP(i,j,k)；接下來計算TP(i,j,k)的長度，如果大于2，則進行轉換，小于2則不轉換。

算法3PCS形式計算標量乘的算法

輸入：k=(kl-1,…,k1,k0)2,P∈E(Fq)。

輸出：Q=kP。

Step1計算k的PCS形式k′；

Step2If 0≤i≤length(k′)-1

Q←2Q；

Ifki=1

Q←Q+P；

Else

Q←Q-P；

Step3返回Q；

End

下面舉例說明該算法的有效性。

對于一整數1122334455，其二進制形式k為：

k=(1000010111001010111011011110111)2

(4)

轉換后的表示為：

(5)

這說明用PCS形式進行轉換后，計算次數明顯小于二進制的情況，由此得出，改進后的PCS算法在減少計算量方面有著突出的優勢。

1.2 算法改進前后比較與分析

將整數k轉換成NAF的過程需要進行大量運算，始終保持k值的二進制表示不變，對PCS方法與NAF方法進行對比分析。算法4就是將二進制轉換成NAF表示的算法。

算法4二進制表示轉換成NAF表示的算法

輸入：k=(kl-1,…,k1,k0)2。

輸出：k的NAF表示k′。

Step1i=0,C0=0,kl=kl+1=0；

Step2If 0≤i≤l

{

Ci+1=[(ki+ki+1+Ci)/2]；

}

Step3返回k的NAF表示k′；

End

將以上轉換應用于標量乘算法中就得到了對應的標量乘算法，如算法5所示。

算法5二進制表示轉換成NAF表示的標量乘算法

輸入：k=(kl-1,…,k1,k0)2,P∈E(Fq)。

輸出：Q=kP。

Step1計算k的NAF表示k′；

Step2Q←∞；

Step3If 0≤i≤length(k′)-1

Q←2Q；

Ifki=1

Q←Q+P；

Else

Q←Q-P；

Step4返回Q；

End

表2 NAF表示過程中的一些基本轉換對比

由表2中的數據可得，相對于NAF的一些無效轉換來說，PCS在減少計算量、提高算法效率方面有著明顯的優勢。

1.3 改進算法與MD5融合策略

將改進后的算法與MD5哈希算法進行融合，在改進后的算法中添加對信息H運用MD5算法進行128位密碼的生成策略，在提高算法效率的同時確保數據的安全性。具體步驟如下：1) 信息H在進行ECC加密的同時進行MD5加密，得到128位密碼；2) 在發送信息過程中，發送128位密碼和信息H；3) 解密時通過ECC得到信息H，并對信息H進行MD5哈希生成算法融合；4) 對比解密得到的128位密碼和接收到的密碼是否一致，判斷是否接受為信息H。對應流程如圖1所示。

圖1 融合策略流程

2 實 驗

2.1 RSA和橢圓曲線加密算法對比

橢圓曲線加密技術具有高效、快速、低耗等優點[20]。對于相同的安全需求來說，橢圓曲線相比RSA[21]的計算量和消耗的時間都要少，如表3所示。

表3 相同安全強度時RSA與ECC密鑰長度比較

根據表3中的數據，在MATLAB中做數據擬合得到曲線如圖2所示。

圖2 RSA和ECC密鑰長度的比較

可以看出，在相同的安全強度下，RSA所需要的密鑰量遠高于橢圓曲線所需要的密鑰量。

2.2 改進前NAF與改進后PCS對比

1) 運算時間的對比。根據NAF方法和CS方法在只有二進制長度作變量情況下運算耗時的差別，本文在MATLAB中做仿真曲線實驗，結果如圖3所示。

圖3 NAF方法和CS方法的運算時間比較

可以看出，CS形式的優勢在于它比NAF形式更省時。在算法1中，運算量只來源于位減法，而不像NAF形式需要大量的取模和除運算。因此所提出的改進算法更簡單、快速。

2) 漢明權的對比。根據表2對10個不同k值在三種表示形式下的漢明權進行對比，在MATLAB中做仿真曲線實驗，結果如圖4所示。

可以看出，在減少漢明權方面，PCS形式和NAF表示的效果相同。這表明PCS形式在減少標量乘計算的運算量方面與NAF表示具有相同的效果。

3) 轉換次數的對比。對10個不同正整數的二進制表示分別用PCS形式和NAF形式進行轉換，得到轉換次數的對比數據，在MATLAB中做仿真曲線，結果如圖5所示。

圖5 不同k值的二進制表示轉換成NAF形式和PCS表示的轉換次數比較圖

圖5說明了針對不同二進制表示的k值，將其變換成NAF要比PCS的變換次數多，即NAF表示在進行轉換時比PCS形式耗時更多。

盡管一般情況下采用NAF形式能夠取得較好的效果，但同時會伴有一些無效的二進制轉換導致大量的時間浪費。提出的PCS形式很好地解決了這一問題，只要進行轉換必定會帶來漢明權的減少，明顯地提高了轉換處理效率，從而將標量乘的處理時間大幅縮短。

2.3 融合算法性能評估

通過對樣本文件進行加密解密操作，包括文件序號、文件存儲大小、文件存儲時間、文件內存信息和文件大小，具體信息如表4所示。

表4 文件加密時間、存儲文件和文件大小

可以看出，加密以及存儲大小都在合理范圍內，可以有效節省內存空間以及加速加密過程，從而提高效率，驗證了本文算法的優越性。

3 結 語

安全在電子商務中不容忽視。本文基于橢圓曲線加密算法對SET協議做出改進，在提高算法效率的同時融合MD5哈希生成算法進一步提高加密的安全性，并通過仿真實驗多次對比加密時間和轉換次數，驗證了改進算法的性能及其優越性。