杜珍珍，陸正福，周　同，楊春堯，3

（1.云南大學 數(shù)學與統(tǒng)計學院，云南 昆明 650091；2.銅陵職業(yè)技術(shù)學院，安徽 銅陵 244000；3.衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都610041）

公鑰加密算法LUC的并行實現(xiàn)方法

杜珍珍1，2，陸正福1，周同1，2，楊春堯1，3

（1.云南大學 數(shù)學與統(tǒng)計學院，云南 昆明 650091；2.銅陵職業(yè)技術(shù)學院，安徽 銅陵 244000；3.衛(wèi)士通信息產(chǎn)業(yè)股份有限公司，四川 成都610041）

LUC是基于數(shù)論的公鑰密碼體制，相比RSA公鑰密碼體制，具有能夠抵抗共模攻擊的優(yōu)點。但LUC算法因?qū)崿F(xiàn)難度大，運算時間長而難以用于實際加密。而影響其運算速度的主要因素是密鑰長度和模冪算法。本文參考相關(guān)文獻工作，得到將密鑰進行分段計算的公式，而后利用LUC序列的性質(zhì)將密鑰進行分段計算，并在多核系統(tǒng)下實現(xiàn)了LUC并行算法，從而提高了LUC算法的執(zhí)行效率。

Lucas序列；密碼體制；密碼算法

以Lucas序列［1，2］為基礎(chǔ)構(gòu)造的公鑰密碼體制——LUC密碼體制，是一種可以替代RSA的密碼體制，同時LUC算法同RSA算法一樣建立在大整數(shù)分解（BIF）的數(shù)學難題上，并也是以推廣歐拉定理為基礎(chǔ)的。在選定的消息直接做數(shù)字簽名時，RSA密碼體制可能遇到適應(yīng)性攻擊，LUC密碼體制由于不具有乘法的封閉性，可以抵御這種適應(yīng)性攻擊，因此LUC安全性高于RSA［3］。但是LUC一般的實現(xiàn)方法耗時太多，對其快速算法的研究具有重要意義。

本文對LUC密碼體制進行研究，設(shè)計并行算法，并對其復(fù)雜度進行分析，實驗證明該算法的實現(xiàn)效率高于原有算法［4，5］。

1　基礎(chǔ)知識

設(shè)P是一個正整數(shù)，Lucas序列具有下列二階線性關(guān)系：Ts=PTs-1-QTs-2，s≥2，從而其特征方程為x2-Px+Q=0，其根為表示D的平方根），其中D是方程的判別式，D=P2-4Q。如果選P，使D≠0，則Lucas數(shù)列可定義為：

這里僅給出本文中所用到的幾個重要性質(zhì)：

性質(zhì) 1［1］設(shè)a，b是任意正整數(shù)，則有

性質(zhì)2［1］設(shè)n是任意正整數(shù)，則有

性質(zhì)3［1］設(shè)n是任意正整數(shù)，則有

性質(zhì)4［5］設(shè)m，n是任意正整數(shù)且m＞n，則有Um+n=UmVn-QnUm-n。

性質(zhì)5［5］設(shè)m，n是任意正整數(shù)且m＞n，則有Vm+n=VmVn-QnVm-n。

性質(zhì) 6［1］設(shè) m，n是任意正整數(shù)，則有2Vm+n=VmVn+DUmUn（其中D=P2-4Q）。

性質(zhì)7［2］設(shè)m，n是任意正整數(shù)，則有2Um+n=UmVn+UnVm。

2　LUC密碼體制

①取兩個不同的大素數(shù) f，w（保密）；

③隨機選取整數(shù)e，滿足（gcd）（e，?）

N=1；

④計算d，滿足de=1（mod?）（N），同時刪除f，w（其中N，e為公鑰，d為私鑰）；

加密：由線性關(guān)系Ts=PTs-1-QTs-2，設(shè)其特征方程的根為α，β，則有

3　LUC密碼算法

3.1計算Vk（P，Q 的遞歸算法

設(shè)P，Q是兩個正整數(shù)，且P2-4Q是一個非完全平方數(shù)，利用性質(zhì)2和性質(zhì)3設(shè)計遞歸算法。當輸入的數(shù)為偶數(shù)時執(zhí)行性質(zhì)2式，當輸入的數(shù)為奇數(shù)時，執(zhí)行性質(zhì)3式，具體算法如下：算法名稱:計算Vk（P，Q）的遞歸算法

此算法由于采用遞歸方法，它的時間復(fù)雜度為O （log2k），但當k較大時，實現(xiàn)效率較低。

3.2計算Vk（P，Q）的快速遞推算法

設(shè)P是正整數(shù)，且P2-4Q是一個非完全平方數(shù)，對于?k≥1，由性質(zhì)2、性質(zhì)3及文獻［4］設(shè)計實現(xiàn)Vk（ P，Q）的快速算法。

算法名稱:計算V（P，Q） 的快速遞推算法［2］

算法偽碼描述如下:

此算法的實現(xiàn)復(fù)雜度為O （log2k），實現(xiàn)效率相對較高。

3.3輸出Uk-Vk的快速遞推算法

在算法3.2的基礎(chǔ)上，實現(xiàn)輸出Uk-Vk的算法。在文獻［5］中，設(shè)k＞0，把k用二進制表示，令

Kj-1=kj-1+2Kj=Kj+kj-1+Kj。

由性質(zhì)4和性質(zhì)5有下列關(guān)系：

具體算法如下：

算法名稱:計算Uk-Vk的快速遞推算法［5］

輸出:（Uk，Vk）

算法描述如下:

此算法是遞推算法，它的實現(xiàn)復(fù)雜度為O （log2k），實現(xiàn)效率接近于算法3.2。

3.4輸出Uk-Vk的并行算法

此算法是在算法3.3的基礎(chǔ)，把k的2進制表示按20:21:22:…:2t的比例劃分為t+1段，分多個進程分別計算［7］，然后多次使用性質(zhì)6和性質(zhì)7計算出Vk和Uk，這里

該算法適用于多核系統(tǒng)，將密鑰分割成多個部分，每部分又有高位段和低位段，首先需要對每部分的高位段密鑰進行低位補零，然后將該部分密鑰分別交由兩個進程執(zhí)行。其余部分的進程任務(wù)依此類推，具體算法如下：

算法名稱:輸出Uk-Vk的并行算法

輸入:k

輸出:Uk，Vk

算法偽碼描述:

此種實現(xiàn)方法的算法復(fù)雜度是O （log2k），但由于使用多個處理器系統(tǒng)并行計算，實現(xiàn)速度快于前面的兩個算法［4，5］。

為了使算法3.4更容易理解，下面用一個圖形來進行說明。圖中的（1），（2），（3），（4）表示文中

如圖1，進程1、進程2、進程3和進程4分別計算出U（1）和V（1）、U（2）和V（2）、U（3）和V（3）及U（4）和V（4），利用性質(zhì)6和性質(zhì)7進行下面的計算：

圖1　給四個進程分配任務(wù)

將U（1）和V（1）與U（2）和V（2）及U（3）和V（3）與U（4）和V（4）可以分別合并出U（（1）+（2））和V（（1）+（2））及U（（3）+（4））和V（（3）+（4）），最后再由U（（1）+ （2））和V（（1）+（2））與U（（3）+（4））和V（（3）+（4））合并出U（（1）+（2）+（3）+（4））和V（（1）+（2）+（3）+（4））。

4　實驗分析

接下來測試本文中的相關(guān)算法運行時間。實驗在Windows環(huán)境下進行，并行算法采用MPI機制來實現(xiàn)，編譯器為VC++6.0，實驗中采用的機器配置為：Intel Pentuim D雙核處理器（1.9 GHz），內(nèi)存1 GB。取隨機數(shù)m（即加密體制中的明文編碼）的長度為一定值，隨機素數(shù) p，q都為密鑰k （k=m+n）長度的一半，對于不同的密鑰長度，計算Vk的快速算法［4］、計算Uk-Vk的快速算法［5］、計算Uk-Vk的并行算法運行時間（此算法在文獻［5］的基礎(chǔ)上設(shè)計的），在mpich2環(huán)境下執(zhí)行之后，得到了串行和并行算法的部分計算時間如表1所示。

表1　本文中的兩種算法在不同密鑰長度下的執(zhí)行時間

根據(jù)表1繪制得到圖2，從圖2中可以看到在密鑰長度較短的時候，串行算法要略優(yōu)于并行算法，這是由于并行的兩個進程間通信需要消耗一定時間，但是隨著密鑰長度的增加，并行算法要優(yōu)于串行算法，尤其是在重負載（密鑰長度大于1 000 b）的情況下表現(xiàn)得更明顯。根據(jù)實驗結(jié)果，計算Vk的并行算法理論加速比約為1.33，實際加速比為1.22。

從實驗結(jié)果來看，對于本文提出的并行LUC算法，并不是使用的進程越多，執(zhí)行的速度就會更快。因為當進程開啟較多的時候，系統(tǒng)對進程的調(diào)度、進程間的通信、進程間的等待所消耗的時間是不可忽略的，從圖2中看到，在1萬比特以下的密鑰長度，4個進程的執(zhí)行時間會比2個進程的執(zhí)行時間要短，但當密鑰長度超過1萬比特時，采用2個進程的執(zhí)行效果要比4個進程理想得多。

圖2　本文中的兩種算法在不同密鑰長度下的執(zhí)行時間

5　結(jié)語

LUC公鑰密碼體制是一種可以替代RSA的一種新體制，但其實現(xiàn)效率相對較低，此問題不解決就難以實際應(yīng)用，因此，對其快速算法的研究備受密碼學界的高度重視。因此，本文在分析研究前人設(shè)計的LUC密碼算法的基礎(chǔ)上，設(shè)計LUC密碼快速實現(xiàn)算法，通過理論分析與實驗表明，本算法能夠提高LUC的運算效率［5］。

［1］ Smith P.LUC Public-Key encryption［J］.Dr.Dobb's Journal，1993，18（1）：44-49.

［2］ 孫琦，張起帆，彭國華.Dickson多項式ge（x，1）公鑰密碼體制的新算法［J］.四川大學學報（自然科學版），2002，39（1）：18-23.

［3］ 羅相根，薛延平，劉益民.RSA公鑰密碼系統(tǒng)算法結(jié)構(gòu)及其安全性［J］.信息安全與通信保密，2006（8）：119-120，124.

［4］Castagnos G.An efficient probabilistic public-key cryp-tosystem over quadratic fields quotients［J］.Finite Fields and TheirApplications，2006，13（3）：563-576

［5］ Joye M，Jean-Jacques Q.Efficient computation of full Lucas se-quences［J］.Electronics Letters，March，1996，32（6）：537-538

［6］ Knuth D E.The art of Computer Programming［M］. Semi-Numerical Algorithms，Addision-Wesley，Reading，MA，1981.

［7］ 梁帥.RSA密碼系統(tǒng)中的并行算法研究［D］.呼和浩特：內(nèi)蒙古大學，2008.

A parallel realization for LUC algorithm of public key cryptosystems

DU Zhen-zhen1，2，LU Zheng-fu1，ZHOU Tong1，2，YANG Chun-yao1，3

（1.School of Mathematics and Statistics，Yunnan University，Yunnan Kunming 650091，China；2.Tongling Polytechnic，Tongling Anhui，244000，China；3.Chengdu Westone Information Security Industry Co.，Ltd，Chengdu Sichuan 610041，China）

The LUC algorithm based on the number theory is one of the public key encryption，which resists common modulus attack comparing with the RSA public cyptosystem.But it is difficult for practical encryption and decryption as LUC is a long time of computing task.The main factor that affects the calculation speed of LUC encryption is key length and mode power algorithm.Reviewed with related

in this paper，we deduced the expression which computed by key division segmentation，then applying the mathematical properties of LUC sequences，and the LUC algorithm is computed by key division segmentation，which is executed parallelly by implemented on multi-core platform，consequently，the computation efficiency of LUC algorithm is improved.

Lucas sequence；Cryptography；Cryptographic algorithm

TP393

A

1004-4329（2016）02-070-04

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）02-070-04

2016-01-05

杜珍珍（1984－），女，碩士，講師，研究方向：信息安全、網(wǎng)絡(luò)計算研究。