一種在LUC基礎(chǔ)上改進(jìn)的密碼體制及其安全性分析

杜珍珍，周 同，陸正福

（1.銅陵職業(yè)技術(shù)學(xué)院，安徽 銅陵 244000；2.云南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南 昆明 650091）

引言

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

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

一、預(yù)備知識(shí)

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

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

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

它有下面的兩個(gè)重要性質(zhì)：

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

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

LUC密碼體制的基本思想：

①取兩個(gè)不同的大素?cái)?shù)f,w（保密）

③隨機(jī)選取整數(shù)e，滿足

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

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

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

LUC密碼體制的證明：

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

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

（二）H-LUC密碼體制的相關(guān)知識(shí)

1.H-LUC序列簡(jiǎn)介

定義 設(shè)P,k為正整數(shù)(P＞k)，構(gòu)造序列

則有

性質(zhì)3 設(shè)a，b為任意正整數(shù)，則有

性質(zhì)4 設(shè)a，b為任意正整數(shù)，則有

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

2.H-LUC密碼體制

取兩個(gè)奇素?cái)?shù)f和w（保密）。計(jì)算N=fw（公開），（保密）。隨機(jī)選取e（公開），滿足計(jì)算d，滿足 （保密）。

構(gòu)造LUC公鑰體制表示如下：

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

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

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

二、安全性分析

關(guān)于H-LUC密碼體制的安全性分析：

（一）H-LUC序列和離散對(duì)數(shù)問題的計(jì)算關(guān)系

定理1 對(duì)于任意的（x為整數(shù)），可以找到一個(gè)正整數(shù)來構(gòu)造H- LUC 序列，在多項(xiàng)式時(shí)間內(nèi)，有

證明：因?yàn)椋顁-k=g，設(shè)是由r,k產(chǎn)生的序列，則

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

證明：設(shè)Mt(r,k)是由r,k產(chǎn)生的序列，

則z-k=(r-k)x，由，令r-k=g，則由定 理1，y=gx. 因此，對(duì)于任意給定的，在多項(xiàng)式時(shí)間內(nèi)，我們?cè)谟騁F(p)或GF(p2)中能找到依賴于r和k的兩個(gè)元素g和y，使得y=gx。

定理3 如果一個(gè)算法AL在GF(p)上能夠用來解決H-LUC 問題，那么在多項(xiàng)式時(shí)間內(nèi)，算法AL在域GF(p)或GF(p2)上也能用來解決離散對(duì)數(shù)問題。

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

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

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

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

因?yàn)槿鬴,w已知，則便可算出.

解密密鑰d關(guān)于e滿足：

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

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

三、實(shí)驗(yàn)分析

（一）文章在Java 平臺(tái)上，取隨機(jī)數(shù)r的長(zhǎng)度為2000 比特位，隨機(jī)素?cái)?shù)f，w都為1500 比特位，密鑰k為3000比特位，分別測(cè)試LUC算法、H-LUC算法（Java庫里的求模冪算法）、RSA算法（Java庫里的求模冪算法）的運(yùn)行時(shí)間.在此，文章通過實(shí)驗(yàn)來演示LUC密碼算法與H-LUC密碼算法和RSA密碼算法的實(shí)現(xiàn)時(shí)間（見圖1）。

測(cè)試平臺(tái)：CPU Intel—T6600（主頻2.2GHZ，雙核），內(nèi)存2G，操作系統(tǒng)Windows-XP。

圖1：算法運(yùn)行時(shí)間比較

結(jié)束語

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