一種基于AES 和ECC 的混合密碼技術的研究

尤紫云，劉曉東

（1.武漢郵電科學研究院，湖北武漢 430070；2.武漢虹旭信息技術有限責任公司，湖北 武漢 430070）

由于網絡的廣泛應用，信息安全[1]已成為保障網絡環境的關鍵因素。在網絡上有效地安全傳輸數據信息，保證信息的真實性、完整性和不可抵賴性是數據加密技術[2]的重中之重。

在對稱加密算法中，如AES 算法，具有速度快、加密強度高、便于實現的優點，但是依然存在局限性，此算法的密鑰分配與管理[3]比較困難。而非對稱加密算法的密鑰分發與管理簡單并且有更高的加密強度，但是運算速度較慢。因此，將對稱加密算法和非對稱加密算法相結合，彌補各自算法的局限。因此文中提出基于AES 算法和ECC 算法的混合加密方案[4]，采用AES 算法對明文加密，而ECC 算法加密管理密鑰實現數字簽名。該方案能有效地提高信息傳輸的安全性和效率，使網絡傳輸變得更加安全可靠。

1 AES算法

1.1 AES算法結構描述

AES(Advanced Encryption Standard)可稱為高級數據加密標準，屬于對稱加密算法[5]，它也是一種基于分組迭代的加密算法。AES 算法的密鑰長度可獨立指定為128 bits，192 bits 或256 bits，在AES 數據加密標準中規范了明文分組長度為128 bits。

在AES 算法中數據塊要經過多次數據變換，每一次變換產生一個中間結果，這個中間結果為狀態。此狀態可以用二維字節數組來表示，也就是一個狀態矩陣，該矩陣的行數為4，列數Nb=分組長度/32。種子密鑰也可以類似地用一個狀態矩陣表示，同樣以字節為元素，行數為4，列數Nk=密鑰長度/32。Nb和Nk共同決定了算法的迭代輪數Nr，由于在AES 算法中分組長度固定128 bits，因此迭代的輪數可以由密鑰長度推得。

AES 算法的輪函數采用的是SP（替代、置換）結構，每一輪由3 個層組成，每個層都是可逆并均勻變換的。1）非線性層：并行使用最優的S 盒，起到混淆作用，防止攻擊者分析出密鑰；2）線性混合層：通過行移變換和列混淆變換，以保證經過多輪變換之后能達到高度擴散，以防止統計分析的攻擊；3）密鑰加層：通過進行輪密鑰加變換，將圈密鑰異或到中間狀態上，從而實現密鑰的加密控制作用。

1.2 AES算法輪變換

AES 加密算法中的輪變換[6]由4 個部分組成，分別是字節代換(ByteSub)、行移變換(ShiftRow)、列混淆變換(MixColumn)、輪密鑰加(AddRoundKey)。

每一輪都依次進行字節代換（S 盒變換）、行移變換、列混淆變換和輪密鑰加。值得注意的是，加密算法的最后一輪沒有列混淆變換。其中輪變換總體框架如圖1 所示。

圖1 AES輪變換框架圖

1）字節代換

字節代換是將每個字節進行S 盒轉換，達到非線性變換。它通過S 盒獨立地對狀態的每個字節進行變換，使字節高度混淆，步驟如下：1）將字節作為GF(28)上的元素映射到自己的逆元，實現有限域上的乘法逆；2）將每個字節作GF(2)上的仿射變換[7]，即：y=Ax-1+B如式（1）所示，其中A是一個GF(2)上8×8的可逆矩陣，B是GF(2)上一個8 位列向量。

2）行移變換

行移變換是一種線性變換，它與列混淆變換結合使加密數據達到充分的混淆，它將狀態矩陣中的各行循環移位若干位，移位量根據行數不同而改變。第0 行不需要移動，第1、2、3 行分別循環左移C1、C2、C3個字節。逆行移位變換是行移位變換的逆變換，它對狀態的每一行進行循環右移。表1 為左移量與分組大小Nb的關系。

表1 左移量與分組大小Nb的關系

3）列混淆變換

列混淆變換為對狀態矩陣中列的線性變換。將狀態矩陣每列的4 個字節表示為GF(28)上多項式，再將該多項式與固定的多項式c(x)進行模x4+1 乘法，其中要求c(x)模x4+1 可逆。定義如下：

令b(x)=c(x)?a(x)mod(x4+1)，列混淆變換過程如圖2 所示。

圖2 列混淆變化示意圖

4）輪密鑰加

輪密鑰加運算就是每輪的狀態與對應的128 bits輪密鑰進行逐比特異或。

2 AES算法的S盒優化

在AES 算法中實現數據的非線性置換[8]S 盒起到重要的作用，S 盒的設計有嚴格的數學計算，整個密碼算法的安全性直接依賴于S 盒的安全性。

AES 算法S 盒的循環迭代周期比較短，遍歷性有待提高，它的擴散性和表達式的復雜度并不能保證AES 算法在代數計算攻擊中的安全性。現針對于上述S 盒性能的不足，將S 盒算法進行優化。

1）在有限域中對輸入的字節元素求逆元。若兩個元素相乘滿足a(x)?b(x)modm(x)=1，就稱b(x) 是a(x)的逆元，其中m(x)=x8+1 不變；

即取了一組新的仿射變換對(155，62)；

3）運用新的仿射變換對，將字節作GF(2)上的仿射變換[9]；

4）做乘法逆運算。

運用了新的仿射變換對使S 盒的循環迭代周期為256，GF(28)中所有元素只屬于一個迭代循環。并將乘法逆運算和仿射變換的順序交換，使得表達式長度增加到255 項，增加了代數計算復雜度，從而提高了算法的安全性。該文對原S 盒與提出的新S 盒的各項性能進行了比較，結果如表2 所示。

表2 兩種S盒的對比分析指標

3 ECC算法

KOBLITZ 和MILLER 在1985年提出ECC(Elliptic Curve Crypto-system)，稱為橢圓曲線密碼體制。與其他的公鑰密碼[10]如RSA[11]相比，在相同密鑰長度下，橢圓曲線密碼安全性更高，同時橢圓曲線密碼更節約存儲空間和算力。這主要得益于在橢圓曲線上離散對數問題[12]比有限域上的離散對數問題更難解。像一般的非對稱加密算法原理那樣，橢圓曲線密碼也是基于“從a推導出b很難，從b推導出a容易”這樣的模式實現了非對稱加密。

3.1 有限域GF(p)上的橢圓曲線

橢圓曲線通常是指Weierstrass 方程所確定的曲線，它是由方程y2+axy+by=x3+cx2+dy+e的全體解再加上一個無窮遠點O構成的集合。

在有限域GF(p)上，可以將上述曲線方程轉化為y3≡x3+ax+b(modp)，常記為Ep(a,b)，簡記為E。其中a,b,x和y均在有限域GF(p)上取值，p是素數，且滿足4a3+27b2(modp)≠0。該橢圓曲線只有有限個點數n，表示為橢圓曲線的階[13]，其中n越大安全性越高。

3.2 橢圓曲線點的運算

當4a3+27b2(modp)≠0 時，稱Ep(a,b)是一條非奇異橢圓曲線[14]。對于非奇異橢圓曲線上點得集合Ep(a,b)定義的加法規則構成一個群稱為Abel 群[15]。規則如下：

1）單位元。O為加法的單位元，對于橢圓曲線上的任何一點P，有P+O=O+P=P。

2）逆元。對于橢圓曲線上的一點P=(x,y)，它的逆元為-P=(x,-y)，注意到P+(-P)=P-P=O。

3）點加。設P和Q是橢圓曲線上x坐標不同的兩點，P+Q的定義如下：過點P和Q作直線l，直線l與橢圓曲線相交于唯一的點R，然后過R點作y軸的平行線l′，l′與橢圓曲線相交的另一點S就是P+Q，如圖3 所示。

圖3 橢圓曲線上點的加法的幾何解釋

4）倍點。為計算點Q的兩倍，在Q點作一條切線并找到與橢圓曲線的另一個交點T，則Q+Q=2Q=-T。

4 AES和ECC混合密碼算法

4.1 ECC算法密鑰的生成

1）由橢圓曲線參數p,a,b來確定一條橢圓曲線，記為Ep(a,b)；

2）在Ep(a,b)上選取基點G(x,y)，且滿足nG=0，其中n為G的階(n為一個大素數)；

3）選取一個整數Ks∈[1,n-1]，通過計算Kp=Ks G，可以得到密鑰對(Ks,Kp)，其中Ks、Kp分別是私鑰和公鑰。

4.2 加密過程

明文使用AES 加密算法對其進行加密。AES 密鑰加密采用ECC 加密算法對其加密生成密鑰密文。其過程如下：

1）發送者選取一個隨機整數r(r

2）將密鑰明文用編碼函數嵌入橢圓曲線Ep(a,b)上一點M=(mx,my)；

3）計算C1=rG，C2=M+rKp；

4）向接收者發送(C1,C2)。

4.3 解密過程

AES 密鑰的解密過程如下；

1）接收者收到(C1,C2)；

2）計算C2-KsC1=M+rKp-KsrG=M+rKsG-KsrG=M，可以得到點M；

3）再對M進行解碼，得到AES 密鑰。再結合AES 解密算法得到相應的明文。

4.4 數字簽名的生成和驗證

1）數字簽名的生成

假設發送者向接收者發送消息M并進行簽名，發送者需執行以下步驟：

①任取一個整數k∈[1,n-1]；

②根據kG=(x1,y1)，計算r=x1modn，若r=0，則回到步驟①；

③根據t=k-1modn，計算t的值；

④用Hash 函數SHA-1 計算Hash 值e=SHA(M)；

⑤計算s=k-1(e+Ksr)modn，若s=0，則回到步驟①；

⑥發送消息M和它的簽名(r,s)。

2）數字簽名的驗證

接收者接收到消息M和簽名(r,s)后，接收者需執行以下步驟進行驗證：

①驗證r和s，需滿足r、s∈[1,n-1]；

②計算e=SHA(M)；

③計算w=s-1modn；

④計算u1=ewmodn和u2=rwmodn；

⑤計算U=u1G+u2Kp=(x2,y2)；

⑥若U=0，則拒絕簽名；若U≠0，計算v=x2modn；

⑦若v=r，則接收簽名；若v≠r，則拒絕簽名。

4.5 混合算法流程圖

發送方：

①明文消息通過AES 加密算法的輪變換等進行加密，從而得到密文；

②再通過利用ECC 加密算法對AES 的密鑰進行加密，從而得到AES 的密鑰塊；

③用發送者私鑰在明文中提取消息摘要生成簽名塊；

④最后將密文、AES密鑰和簽名塊傳送給接收方。

數據加密具體流程圖如圖4 所示。

圖4 數據加密流程

接收方：

①首先將AES 的密鑰塊通過ECC 解密算法進行解密，可以得到AES 密鑰；

②然后將密文通過AES 密鑰進行解密，從而得到明文消息，再進行SHA-1 算法[16]獲得其信息摘要；

③用發送者公鑰解密簽名塊生成摘要結果；

④比較兩個摘要結果，若相等，則簽名成功。

數據解密具體流程圖如圖5 所示。

圖5 數據解密流程

5 結束語

由于互聯網越來越被大眾接受和使用，人們對信息安全保護的需求越來越迫切，該文提出一種基于AES 和ECC 的混合密碼技術，具備了兩種算法的優點：儲存空間小、運算速度快、密鑰管理方便等。從而可以高效地實現了互聯網中的信息加密、數字簽名和身份認證，解決了密碼體制中速度和安全性不能兼顧的問題。同時重新設計了AES 算法中的S盒，改進的S 盒的循環迭代周期擴大到256，提高了遍歷性，表達式長度增加到255 項，增加了代數計算復雜度，從而提高了算法的安全性。