彭 韜 陳文慶

（1.廣東茂名幼兒師范專科學(xué)校 高州 525200）（2.湛江師范學(xué)院教務(wù)處 湛江 524048）

1 引言

基于離散對數(shù)的橢圓曲線密碼體制（Elliptic Curve Cryptosystem，ECC）是 由 Koblitz［1］和 Victor Miller在1985年分別獨(dú)立提出的。由于ECC是基于橢圓曲線上的離散對數(shù)難解問題，相同長度的密鑰比其他密碼體制具有更高的安全性，近年來已經(jīng)成為密碼學(xué)領(lǐng)域研究的熱點(diǎn)之一［1］。在許多基于橢圓曲線的密碼方案中，標(biāo)量乘法是影響橢圓曲線密碼體制中最基本、最耗時(shí)的運(yùn)算，其執(zhí)行效率直接影響整個(gè)密碼體制的性能。目前，許多學(xué)者研究出用多種方法來加快點(diǎn)乘速度：1）通過對m的展開形式的優(yōu)化來提高運(yùn)算效率，代表算法有NAF表示、τ-adic表示、雙基表示等［1～3，9～13］；2）引入預(yù)計(jì)算的窗口算法和梳子算法等［1］；3）根據(jù)橢圓曲線的特點(diǎn)使用不同的坐標(biāo)表示，例如仿射坐標(biāo)、射影坐標(biāo)和Inverted Edwards坐標(biāo)［5］等。

本文主要討論整數(shù)的雙基表示以及基于樹型方法計(jì)算雙基鏈方法。

2 雙基數(shù)系統(tǒng)

Dimitrov和Cooklev在文獻(xiàn)［1～3］中首次提出了雙基數(shù)系統(tǒng)（DBNS）的概念，并在隨后將其應(yīng)用到了橢圓曲線密碼學(xué)［7，14～15］。在DBNS 中，每一個(gè)整數(shù)n被表示為2-整數(shù)的和或差的形式，即

顯而易見在DBNS中，整數(shù)n的表達(dá)式并不唯一。例如，10準(zhǔn)確的有5種不同的雙基方法，100準(zhǔn)確的有402種，而1000準(zhǔn)確的有1295579種不同的表示方法，159就已經(jīng)有49305013890836539593285＞1022種不同的雙基數(shù)表示形式了［1～2］。貪婪算法是找到一個(gè)項(xiàng)數(shù)盡可能少的雙基表達(dá)式的有效算法。

例1 令n=81232利用貪婪算法可以求出n的DBNS表示：

841232=2738+2136-2232+21

Dimitrov等給出了貪婪算法求出n的DBNS表達(dá)式項(xiàng)數(shù)的上界，對于任意整數(shù)，貪婪算法都可以項(xiàng)內(nèi)求出其DBNS展開式［2～3］。

然而，n的DBNS表達(dá)式是非常稀疏，并不適合用來計(jì)算標(biāo)量乘法，因?yàn)闊o序的指數(shù)使得必須計(jì)算Q/2或者Q/3，而這樣的操作是非常耗時(shí)。為了避免上述情況的發(fā)生，雙基表達(dá)式的指數(shù)序列必須滿足同時(shí)遞減，即a1≥a2≥ … ≥al且b1≥b2≥ … ≥bl。滿足這一性質(zhì)的雙基展開式叫做雙基鏈（DBC）［7～8］。只要在普通貪婪算法的每輪迭代中將目標(biāo)值對應(yīng)的上輪近似值的指數(shù)作為本輪該目標(biāo)值搜索的指數(shù)上界，就得到了一個(gè)用來求解雙基鏈的貪婪算法［2～3，7～9］。

例2 將上例中的n展開為雙基鏈形式如下：

841232=2738+1424

1424=2136-34，

34=33+7，

7=32-2，

2=31-1。

即841232=2738+2136-33-32+31-1。一般而言，一個(gè)整數(shù)的雙基鏈長度要大于其對應(yīng)的DBNS表達(dá)式。

3 樹型算法

雙基鏈表達(dá)式的長度和形式，直接影響到標(biāo)量乘的效率，由 Dimitrov提出貪婪算法［2～3，7～9］得求雙基鏈并不是最優(yōu)方法，同時(shí)該算法求得的雙基表達(dá)并不一定適合標(biāo)量乘。基于樹型方法［4］計(jì)算雙基鏈方法能較好地滿足標(biāo)量乘，具體算法如下：

2）f(n)-1和f(n)+1分別為樹的左結(jié)點(diǎn)和右結(jié)點(diǎn)。

3）比較各葉結(jié)點(diǎn)的值的大小，保留B（B為樹每層保留最小葉結(jié)點(diǎn)參數(shù)值）個(gè)最小值葉結(jié)點(diǎn)，去掉其它葉結(jié)點(diǎn)。

4）直到有一個(gè)葉結(jié)點(diǎn)的值為1，否則對B個(gè)最小值葉結(jié)點(diǎn)轉(zhuǎn)步聚2）。

5）從值為1的葉結(jié)點(diǎn)反向搜索到根即得到n的雙基鏈。

如n=841232，B=2為例，其結(jié)果如圖1所示。

從值為1的葉結(jié)點(diǎn)開始，沿著虛線得到：

841232＝24（25（2231（23（24+1）+1）-1）+1）

即得雙基鏈如下：

841232=21831+21431-21131+29+24

如n=841232，若設(shè)B＝4，則該算法可得到如下雙基鏈：

841232=2738+2633-2532-24

圖1 B為2時(shí)生成雙基鏈的二叉樹

4 樹型方法的Delphi實(shí)現(xiàn)

4.1 二叉樹結(jié)點(diǎn)結(jié)構(gòu)

樹結(jié)點(diǎn)的結(jié)構(gòu)具體定義如下：

type

recordnode=record

data：integer； //整數(shù) n

leftnode：pointer； //右結(jié)點(diǎn)

rightnode：pointer； //左結(jié)點(diǎn)

Bexp：byte； //存2次方值

Texp：byte； //存3次方值

End；

4.2 計(jì)算2或3次方過程

入口參數(shù)：數(shù)值data；次方數(shù)temp

出口參數(shù)：i為次方值。

procedure computeTexp（var data：integer；var i，temp：byte）； //計(jì)算n的次方

begin

i：=0；

while（data mod temp=0）and（data＜＞1）do

begin

data：=data div temp；

i：=i+1；

end；

end；

4.3 對于任整數(shù)n構(gòu)建二叉樹過程

入口參數(shù)：pt為指向樹結(jié)點(diǎn)的指針。

出口參數(shù)：二叉樹。

procedure CreateTree（var pt：TPRecnode）；

var

temp，i：byte；

pl，pr：TPRecnode；

s：ShortString；

begin

if pt.data＜＞1 then

begin

temp：=2；

computeTexp（pt.data，i，temp）；//調(diào)用計(jì)算2的次方

pt.Bexp：=i；//2的次方數(shù)

temp：=3；

computeTexp（pt.data，i，temp）；//調(diào)用計(jì)算3的次方

pt.Texp：=i； //3的次方數(shù)

s：=IntToStr（pt.data）；

showmessage（s）；

GetMem（pl，SizeOf（TPRecnode））；

pt.leftnode：=pl；

pl.data：=pt.data-1；

pl.leftnode：=nil；

pl.rightnode：=nil；

pl.Bexp：=0；

pl.Texp：=0；

pt：=pl；

CreateTree（pt）； //創(chuàng)建左子樹

GetMem（pr，SizeOf（TPRecnode））；

pt.leftnode：=pr；

pr.data：=pt.data-1；

pr.leftnode：=nil；

pr.rightnode：=nil；

pr.Bexp：=0；

pr.Texp：=0；

pt：=pr；

CreateTree（pt）； //創(chuàng)建右子樹

end

else

pt：=nil；

end；

5 結(jié)語

本文主要研究雙基數(shù)據(jù)系統(tǒng)（DBNS）基本理論和求解任意整數(shù)雙基數(shù)表示的樹型方法，最后在Delphi環(huán)境下實(shí)現(xiàn)了基于樹型方法計(jì)算雙基鏈。