橢圓曲線加密算法于1985年提出，由于自身優(yōu)點(diǎn)，它一出現(xiàn)便受到關(guān)注，現(xiàn)在密碼學(xué)界普遍認(rèn)為它將替代RSA加密算法成為通用的公鑰加密算法。那么我們今天就來看看橢圓曲線加密算法是如何通過C語(yǔ)言來設(shè)計(jì)實(shí)現(xiàn)的。

一、橢圓曲線加密算法的C語(yǔ)言設(shè)計(jì)

1、橢圓曲線加密系統(tǒng)的基本結(jié)構(gòu)

橢圓曲線的加解密流程如圖1所示：

橢圓曲線進(jìn)行加密通信的過程如下：首先選定一個(gè)適合加密的橢圓曲線Ep(a，b)，并取橢圓曲線上的一點(diǎn)作為基點(diǎn)G。選擇一個(gè)私有密鑰k，并生成公開密鑰K=kG。加密時(shí)，將明文編碼到Ep(a，b)上的一點(diǎn)M，并產(chǎn)生一個(gè)隨機(jī)整數(shù)r(r<n)。

計(jì)算點(diǎn)C1=M+rK，C2=rGo將C1、C2存入密文。解密時(shí)，從密文中讀出CI、C2，計(jì)算C1-kC2，根據(jù)C1-kC2=M+rK-k( rG)=M+rK-r( kG)=M，解得的結(jié)果就是點(diǎn)M，即明文。

2、高精度整數(shù)的表示

加密算法幾乎都是建立在高精度大整數(shù)的運(yùn)算上， 而一般的程序語(yǔ)言都不提供大整數(shù)的結(jié)構(gòu)，因此要表示上百位的高精度整數(shù)需另辟蹊徑。

本文使用了LibTomMath庫(kù)的高精度整數(shù)結(jié)構(gòu)。LibTomMath是一個(gè)計(jì)算高精度整數(shù)的庫(kù)的開源軟件，由加拿大人湯姆St.丹尼斯編寫，用標(biāo)準(zhǔn)C語(yǔ)言寫了幾乎所有標(biāo)準(zhǔn)的密碼算法模塊，并且在幾乎所有的操作系統(tǒng)下都可執(zhí)行。

LibTomMath庫(kù)對(duì)高精度大整數(shù)的表示是該庫(kù)最大的一個(gè)特點(diǎn)。在LibTomMath庫(kù)中的高精度大整數(shù)表示如下：在32位機(jī)上unsigned long為32bit，用mp_digit表示這個(gè)類型：typedef unsigned_long mp_digit；實(shí)際使用了32位的28位，少用4位，因此用16進(jìn)制表示一個(gè)mp_digit為0XXXXXXX，其中X為16進(jìn)制數(shù)字，將這個(gè)32位bit串稱為一個(gè)mp_digit單元，若干個(gè)mp_digit單元構(gòu)成一個(gè)大整數(shù)，結(jié)構(gòu)定義一個(gè)大整數(shù)mpint如下：

typeclef struct {

inl used，alloc，sign；

mp_digit *dp;

) mp_int；

其中：dp是存放大整數(shù)的地址，將大整數(shù)（二進(jìn)比特串）分段（mp_digit單元）存放在從該地址起的內(nèi)存里，缺省時(shí)分配dp為MP_PREC=64個(gè)mp_digit單元，即alloc =64；used為實(shí)際使用的mp_digit單元；sign=0表示非負(fù)數(shù)，為1表示負(fù)數(shù)。對(duì)于分配了alloc個(gè)mp_digit的大整數(shù)mpjnL，因?yàn)閷?shí)際可以使用的比特?cái)?shù)是28*alloc，因此可以表示的整數(shù)范圍是[-228*alloc，228*alloc]。對(duì)于64位機(jī)情況類似。

3、橢圓曲線的參數(shù)選取

在基于橢圓曲線的加密和解密實(shí)現(xiàn)方案中，首先要給出橢圓曲線域的參數(shù)來確定一條橢圓曲線。

在SECI及IEEE P1363ECC工作草案中，所定義的二進(jìn)制域上橢圓曲線用到六個(gè)參量T=(p，a，b，G，n，h)o p，a，b用來確定一條橢圓曲線，G為基點(diǎn)，n為點(diǎn)G的階，h是橢圓曲線上所有點(diǎn)的個(gè)數(shù)m與n相除的整數(shù)部分，這幾個(gè)參量取值的選擇直接影響加密的安全性。參量值一般要求滿足以下幾個(gè)條件：

a）p當(dāng)然越大越安全，但越大，計(jì)算速度會(huì)變慢，200位左右可以滿足一般安全要求；

b）p≠nxh；

c）pt≠l (mod n)，l≤t<20；

d）a3+27b2≠O (mod p)；

e）n為素?cái)?shù)；

f）h≤4。

本文選用大素?cái)?shù)域上的橢圓曲線E(p)：y2=x3+ax+b作為我們的加密曲線。

（1）參數(shù)a、b的選取

采用構(gòu)造法產(chǎn)生橢圓曲線CM(Complex Multiplication)法，即先確定有限域Fp和其上的橢圓fHj線的階，然后再構(gòu)造滿足要求的橢圓曲線，即求出橢圓曲線方程E(p)：y2=
x3+ax+b中的a，b。

（2）基點(diǎn)的確定

首先在橢圓曲線上隨機(jī)選擇一個(gè)有效點(diǎn)，然后根據(jù)選擇的點(diǎn)得到階是n的有效基點(diǎn)。這里有效基點(diǎn)的階最好是曲線階的點(diǎn)，至少是曲線階的最大素因子，這樣可以保證一定的安全。

（3）私鑰的確定

隨機(jī)選取1到P-1之間的素?cái)?shù)作為私鑰d。

（4）公鑰的確定

由d乘我們所確定的基點(diǎn)得到公鑰K，即K=dG。

4、橢圓曲線的點(diǎn)加和標(biāo)量乘

對(duì)于一般的橢圓曲線方程yz+alxy+a3y =X3+a2xz+a,x+a6，設(shè)點(diǎn)P(xi，yl)，Q(X2，yz)的和R(X3，y3)的坐標(biāo)為x3=k2+kal+a2+xl+x2；y3=k(XI-X4) -y1-alx4-a3，其中當(dāng)P≠Q(mào)時(shí)（點(diǎn)加運(yùn)算）k=（y1-y2）／（x1-x2）；

當(dāng)P=Q時(shí)（倍點(diǎn)運(yùn)算）k= (3x2+2a2x+a4-aly)/(2y+a1x+a3)；對(duì)于橢圓曲線方程y2-X3+aX+b，上述的公式變?yōu)閄3=θ2_X1_X2; y3=θ(X1-X3) -y1，其中當(dāng)P≠Q(mào)時(shí)（點(diǎn)加運(yùn)算）θ=（y1-y2）／（x1-x2）；

當(dāng)P=Q時(shí)（倍點(diǎn)運(yùn)算）θ=（3x12一a）／2y1。

橢圓曲線中最基本最重要的運(yùn)算之一就是標(biāo)量乘法(ScalarM ultiplication)，即求點(diǎn)P的k倍。

在加密體制的實(shí)現(xiàn)中，它的運(yùn)算速度直接影響到整體速度。目前計(jì)算標(biāo)量乘的算法主要有二元展開法、帶符號(hào)的二元法、k進(jìn)制方法、帶符號(hào)的k進(jìn)制方法、滑動(dòng)窗口法、Frobenius自同態(tài)法等。本文采用基本的二元展開法。表示如下：

設(shè)m的二進(jìn)制表示為m=(mn-1mn-2…m1mo)，其中mn-1=1，Q=P，從左到右依次計(jì)算。

for(1=n-2 t0 0)

{

Q=2Q;

if(mi =1) Q=Q+P；

}

則Q=mP.

Return Q；

5、明文的嵌入和恢復(fù)

明文信息如何嵌入到橢圓曲線上也是橢圓曲線加密算法的關(guān)鍵之一。橢圓曲線一個(gè)點(diǎn)由x坐標(biāo)和y坐標(biāo)組成，因而一個(gè)點(diǎn)就是由兩個(gè)數(shù)組成的數(shù)對(duì)，并且這兩個(gè)數(shù)都要在橢圓曲線的有限域上。本文采用如下方法進(jìn)行明文編碼：

取一段明文作為橢圓曲線上點(diǎn)的X坐標(biāo)，然后按照橢圓曲線方程yZ=X3+aX+b (modp)計(jì)算Y坐標(biāo)的值，取明文的長(zhǎng)度由有限域決定。若有限域長(zhǎng)為192bit串，則取明文比特長(zhǎng)應(yīng)在1-191bit之間。由于本
系統(tǒng)高精度整數(shù)結(jié)構(gòu)上處理的特點(diǎn)，需在取得的明文塊后加結(jié)束標(biāo)志字符char(255)，所以當(dāng)有限域比特長(zhǎng)為192位時(shí)，所取的最大明文塊為22字符長(zhǎng)。

由于本系統(tǒng)上的運(yùn)算都是基于比特位的，且采用高精度整數(shù)結(jié)構(gòu)，明文比特串和高精度整數(shù)之間需要一個(gè)轉(zhuǎn)換過程。

（1）加密明文比特串的轉(zhuǎn)換

mp_digit只用28比特，一個(gè)單元最多可存放三個(gè)半字節(jié)。

實(shí)現(xiàn)將明文文件的二進(jìn)制比特串轉(zhuǎn)換成mp_int數(shù)a的函數(shù)，主要循環(huán)部分說明如下：

//chlong為要存人的字符數(shù)組長(zhǎng)

for (j=O;j<chlong/7;j++)//以7個(gè)字符為單元循環(huán)，

把7個(gè)字符放人mp_int的兩個(gè)單元中

{

j+=-7；//每次跳7個(gè)字符

*++templ=(mp_digit) (ch [i-l]＆255);//Aemp

跳過前一個(gè)單元，存人后一單元

*temp<<=(mp_digit)CHAR_BIT;

//存人高8位并向左移8位，以便放人下一個(gè)字符

*temp 1=(mp_digit)(ch[i-2]&255);

//存入字符

*temp <<= (mp_digit)CHAR_BIT;

//左移8位

*temp I-(mp_digit)(ch[i-3]&255);

//存人字符

*temp<<-(mp_digit)4;//向左移4位，以便放入下一個(gè)字符的高4位

*temp-1.(mp_digit)((ch[i-4]&255)>> 4)；

//存放被切分的字符的高4位，temp跳回前一個(gè)單元

//存人第一單元

*temp f- (mp_digit) (ch[i-4] &)7);

//存放被切分的字符的低4位，yy= (mp._digit) 15

*Lemp<<．(mp_digit)CHAR_BIT;//向左移8位，以便放人下一個(gè)字符

*temp I-(mp_digit) (ch[i-5]＆255);11存入字符

*temp<<：(mp_digit)CHAR_BIT;//左移8位

*temp J=(mp_digit)(ch[j-6]&255)：//存人字符

*temp<<=(mp_digit)CHAR_BIT;//左移8位

*temp++|=(mp_digit)(ch[i-7]＆255)；//存放被切分的字符的低4位．temp跳到后一個(gè)單元

temp++；//再向后跳一單元，這樣和下次的++temp實(shí)現(xiàn)每次循環(huán)跳兩個(gè)單元

}

明文恢復(fù)時(shí)，采用和上面相反的過程將mp_int數(shù)轉(zhuǎn)換成明文的二迸制比特串。

（2）密文的存儲(chǔ)結(jié)構(gòu)

在文件加密存儲(chǔ)中，需解決密文存入磁盤后如何讀入和區(qū)分每次加密的密文段的問題。本文是如下處理的：

存儲(chǔ)時(shí)先存*mp->dp的最高8位，再依次往下存后面3個(gè)8位。依據(jù)*mp->dp的特點(diǎn)，最高8位為0000xxxx，因此，可將255作為一個(gè)密文段的結(jié)束標(biāo)志，把前一密文段和后一密文段區(qū)分開。這樣在密文文件中，密文的存取結(jié)構(gòu)為：

用變量i記數(shù)，利用fgetc每次讀取一個(gè)字符，當(dāng)?shù)趇個(gè)字符是255，且i%4=0時(shí)截止。這時(shí)所讀的這段字符即為一次存儲(chǔ)的密文段。讀出密文段后，用相應(yīng)的方法把密文段比特串轉(zhuǎn)換成mp_int型數(shù)。

二、橢圓曲線加密算法的C語(yǔ)言實(shí)現(xiàn)

文件加密、解密處理都是根據(jù)有限域大小分段進(jìn)行的。加密時(shí)無論明文文件的表現(xiàn)形式和內(nèi)容如何，都將其組成成分看作是二進(jìn)制數(shù)字文件。

文件加密時(shí)，每次取一段二進(jìn)制明文，并在末尾附加一個(gè)明文結(jié)束標(biāo)志字符char(255)，以避免二進(jìn)制的明文讀入mpjnt數(shù)后出現(xiàn)高位比特位是0，導(dǎo)致出錯(cuò)。取得明文后，產(chǎn)生一個(gè)隨機(jī)整數(shù)r(r<有限域p），計(jì)算點(diǎn)C1=M+rK、C2=rG，將點(diǎn)C1、C2坐標(biāo)依次存入密文文件。

文件解密時(shí)，按前述方法讀入密文。根據(jù)C1-dC2=M+rK-k (rG)=M+rK-r(kG)=M計(jì)算C1-dC2（d為私鑰），得到明文點(diǎn)坐標(biāo)mx，myo其中兩點(diǎn)減的計(jì)算為P-Q=P+(-Q)，其中-Q=(X，-Y)，-Y=P-Y；計(jì)算C1-dC2完畢后按前面所述取解密文的方法取出解密字符，去掉最末的一個(gè)char(255)符，存入解密文中，完成解密。

為驗(yàn)證系統(tǒng)的文件加密、解密功能，我們對(duì)文本文件、BMP、WORD、EXCEL等文件進(jìn)行了加密和解密測(cè)試。驗(yàn)證結(jié)果表明，所給定的明文文件經(jīng)系統(tǒng)加密后，再對(duì)密文解密所得的解密文與原明文相比完全一致，沒有一個(gè)比特的偏差，很好的實(shí)現(xiàn)了橢圓曲線加密算法的功能。

admin

收藏 海報(bào)分享