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

圣文順 王玉祥 孫艷文

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

0 引 言

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

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

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

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

1 基于橢圓曲線的SET協(xié)議改進

1.1 基于一補數(shù)減法形式的改進算法

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

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

(1)

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

(2)

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

算法1一補數(shù)形式計算標量乘的算法

輸入：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

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

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

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

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

算法2將二進制表示的整數(shù)轉(zhuǎn)換成部分使用一補數(shù)減法

輸入：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循環(huán)；

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

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

(3)

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

算法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

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

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

k=(1000010111001010111011011110111)2

(4)

轉(zhuǎn)換后的表示為：

(5)

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

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

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

算法4二進制表示轉(zhuǎn)換成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

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

算法5二進制表示轉(zhuǎn)換成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表示過程中的一些基本轉(zhuǎn)換對比

由表2中的數(shù)據(jù)可得，相對于NAF的一些無效轉(zhuǎn)換來說，PCS在減少計算量、提高算法效率方面有著明顯的優(yōu)勢。

1.3 改進算法與MD5融合策略

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

圖1 融合策略流程

2 實 驗

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 不同k值的二進制表示轉(zhuǎn)換成NAF形式和PCS表示的轉(zhuǎn)換次數(shù)比較圖

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

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

2.3 融合算法性能評估

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

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

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

3 結(jié) 語

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