一種在LUC基礎上改進的密碼體制及其安全性分析

杜珍珍，周 同，陸正福

（1.銅陵職業技術學院，安徽 銅陵 244000；2.云南大學 數學與統計學院，云南 昆明 650091）

引言

LUC密碼體制[1]是一種可以替代RSA的公鑰密碼體制，特別是其不存在乘法的封閉性，在用于身份驗證時可以抵抗適應性攻擊，所以此時它的安全性高于RSA。為了能使LUC 密碼體制在實際中有很好的應用，許多學者對LUC密碼體制進行研究[2]，設計快速算法，并利用其設計秘密共享方案及數字簽名方案[3，4，5]。

本文通過引入盲因子，結合LUC與RSA密碼體制，構造新的密碼體制，使其計算量低于LUC 密碼體制，接近于RSA 密碼體制，又擁有LUC 密碼體制可以抵御乘法攻擊的特性。

一、預備知識

（一）Lucas序列及LUC密碼體制[1，2]

Lucas 序列可定義為：選兩個非負整數P和Q，構成二次式x2-Px+Q=0，其根為，其中D是方程的判別式，即D=P2-4Q，如果選P和Q，使，則Lucas序列可定義為:

對于Lucas 序列，公鑰密碼體制主要研究Vn(P,Q)，在此只研究Vn(P,1)

它有下面的兩個重要性質：

性質1 設a，b為任意正整數，則有Va b(P,1)=Va(Vb(P,1) ,1)

性質2 設a，b為任意正整數，則有Vb(V a(P,1) ,1)=V a(Vb(P,1) ,1)

LUC密碼體制的基本思想：

①取兩個不同的大素數f,w（保密）

③隨機選取整數e，滿足

④計算d，滿足，同時刪除f和w（其中N,e為公鑰，d為私鑰）。

加密算法：C=Ve(P,1) modN

解密算法：P=Vd(C,1) modN

LUC密碼體制的證明：

加密：由二次式x2-Px+ 1=0，設其特征方程的根為則有Lucas 序列性質得

解密:由二次式x2-Ve(P,1)x+1=0，設其特征方程的根為，則有方程根與系數的關系

（二）H-LUC密碼體制的相關知識

1.H-LUC序列簡介

定義 設P,k為正整數(P＞k)，構造序列

則有

性質3 設a，b為任意正整數，則有

性質4 設a，b為任意正整數，則有

證明性質3左邊=(P-k)ab+k，右邊=((P-k)b+k-k)a+k=(P-k)ba+k=(P-k)ab+k，即證等式成立.證明性質4由性質3得

2.H-LUC密碼體制

取兩個奇素數f和w（保密）。計算N=fw（公開），（保密）。隨機選取e（公開），滿足計算d，滿足 （保密）。

構造LUC公鑰體制表示如下：

公鑰：N，e;私鑰：d（陷門信息f，w）;P為小于N的一個正整數;

加密算法：C=M e(P,k)modN

解密算法：P=M d(C,k)modN

二、安全性分析

關于H-LUC密碼體制的安全性分析：

（一）H-LUC序列和離散對數問題的計算關系

定理1 對于任意的（x為整數），可以找到一個正整數來構造H- LUC 序列，在多項式時間內，有

證明：因為，令r-k=g，設是由r,k產生的序列，則

定理2 對于任意的和由r,k產生的序列，對于正整數x，有在域GF(p)或GF(p2)中可以找到兩個元素g和y，使在多項式時間內，z=Mx(r,k)=y+k和y=gx成立.

證明：設Mt(r,k)是由r,k產生的序列，

則z-k=(r-k)x，由，令r-k=g，則由定 理1，y=gx. 因此，對于任意給定的，在多項式時間內，我們在域GF(p)或GF(p2)中能找到依賴于r和k的兩個元素g和y，使得y=gx。

定理3 如果一個算法AL在GF(p)上能夠用來解決H-LUC 問題，那么在多項式時間內，算法AL在域GF(p)或GF(p2)上也能用來解決離散對數問題。

證明：對于任意給定的且對某些未知的正整數x，有y=gx，我們想在多項式時間內通過算法AL計算出x。對任意給定的g和y，通過定理1，在多項式時間內，可以找到兩個正整數，構造序列Mt(r,k)，使得成立.由于AL 能用來解決H-LUC 問題，則可以用算法AL 去計算x，使Mx(r,k)=y+k=gx+k成立，因而滿足y=gx。

定理4 如果算法AL′在域GF(p)或GF(p2)中能用來解決離散對數問題，則對于任意給定的，AL′能用來計算正整數x，使得在多項式時間內，成立。

從定理3 和定理4 可知，如果算法AL能解決GF(p)上的H-LUC 問題，則在多項式時間內算法AL也能解決GF(p)上的離散對數問題;另一方面，如果算法AL′能解決GF(p)或GF(p2)上的離散對數問題，則在多項式時間內，算法AL′也能解決H-LUC 問題。因此，我們得到的結論是，H-LUC 函數的計算安全問題在多項式時間內等價于一般的離散對數問題。

（二）若N=fw被因子分解，則H-LUC 并沒有被攻破。

因為若f,w已知，則便可算出.

解密密鑰d關于e滿足：

故d也不難求得，但由于在設計密碼體制時，P是公開的，k是保密的，所以此時明文并不能被恢復。因此H-LUC 的安全性不僅依賴于因子分解的困難性，還依賴于盲因子k。

（三）LUC 公鑰體制的抗攻擊性高于RSA，是因為采用Lucas 數列來取代RSA 中冪的產生，不存在乘法的封閉性，即對于MdLd=(ML)d，如果知道M、M dmodN、L和LdmodN，則在不知道d的情況下，ML和(ML)dmodN也能被計算出來.而LUC 不具有乘法的封閉性，故在用于身份驗證時可以抵抗此種攻擊.該方案中所使用的H-LUC 數列，也不存在乘法的封閉性，所以其在用于身份驗證時安全性也高于RSA，且計算量低于LUC。

三、實驗分析

（一）文章在Java 平臺上，取隨機數r的長度為2000 比特位，隨機素數f，w都為1500 比特位，密鑰k為3000比特位，分別測試LUC算法、H-LUC算法（Java庫里的求模冪算法）、RSA算法（Java庫里的求模冪算法）的運行時間.在此，文章通過實驗來演示LUC密碼算法與H-LUC密碼算法和RSA密碼算法的實現時間（見圖1）。

測試平臺：CPU Intel—T6600（主頻2.2GHZ，雙核），內存2G，操作系統Windows-XP。

圖1：算法運行時間比較

結束語

密鑰管理是計算機網絡中研究的一個熱點問題，許多學者對其進行研究，主要從兩個方面入手，一是減小計算量，二是增加安全性。LUC是一種可以替代RSA的密碼體制，相比RSA公鑰密碼體制，具有能夠抵抗共模攻擊的優點，但其實現效率相對較低，文章結合RSA 與LUC 密碼體制的特點構造HLUC序列，并給出其安全性證明。通過理論分析與實驗表明，文章由H-LUC序列構造的密碼算法運算效率高于LUC密碼算法，略微低于RSA算法。