彭 韬 陈文庆

（1.广东茂名幼儿师范专科学校 高州 525200）（2.湛江师范学院教务处 湛江 524048）

1 引言

基于离散对数的椭圆曲线密码体制（Elliptic Curve Cryptosystem，ECC）是 由 Koblitz［1］和 Victor Miller在1985年分别独立提出的。由于ECC是基于椭圆曲线上的离散对数难解问题，相同长度的密钥比其他密码体制具有更高的安全性，近年来已经成为密码学领域研究的热点之一［1］。在许多基于椭圆曲线的密码方案中，标量乘法是影响椭圆曲线密码体制中最基本、最耗时的运算，其执行效率直接影响整个密码体制的性能。目前，许多学者研究出用多种方法来加快点乘速度：1）通过对m的展开形式的优化来提高运算效率，代表算法有NAF表示、τ-adic表示、双基表示等［1～3，9～13］；2）引入预计算的窗口算法和梳子算法等［1］；3）根据椭圆曲线的特点使用不同的坐标表示，例如仿射坐标、射影坐标和Inverted Edwards坐标［5］等。

本文主要讨论整数的双基表示以及基于树型方法计算双基链方法。

2 双基数系统

Dimitrov和Cooklev在文献［1～3］中首次提出了双基数系统（DBNS）的概念，并在随后将其应用到了椭圆曲线密码学［7，14～15］。在DBNS 中，每一个整数n被表示为2-整数的和或差的形式，即

显而易见在DBNS中，整数n的表达式并不唯一。例如，10准确的有5种不同的双基方法，100准确的有402种，而1000准确的有1295579种不同的表示方法，159就已经有49305013890836539593285＞1022种不同的双基数表示形式了［1～2］。贪婪算法是找到一个项数尽可能少的双基表达式的有效算法。

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

841232=2738+2136-2232+21

Dimitrov等给出了贪婪算法求出n的DBNS表达式项数的上界，对于任意整数，贪婪算法都可以项内求出其DBNS展开式［2～3］。

然而，n的DBNS表达式是非常稀疏，并不适合用来计算标量乘法，因为无序的指数使得必须计算Q/2或者Q/3，而这样的操作是非常耗时。为了避免上述情况的发生，双基表达式的指数序列必须满足同时递减，即a1≥a2≥ … ≥al且b1≥b2≥ … ≥bl。满足这一性质的双基展开式叫做双基链（DBC）［7～8］。只要在普通贪婪算法的每轮迭代中将目标值对应的上轮近似值的指数作为本轮该目标值搜索的指数上界，就得到了一个用来求解双基链的贪婪算法［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。一般而言，一个整数的双基链长度要大于其对应的DBNS表达式。

3 树型算法

双基链表达式的长度和形式，直接影响到标量乘的效率，由 Dimitrov提出贪婪算法［2～3，7～9］得求双基链并不是最优方法，同时该算法求得的双基表达并不一定适合标量乘。基于树型方法［4］计算双基链方法能较好地满足标量乘，具体算法如下：

2）f(n)-1和f(n)+1分别为树的左结点和右结点。

3）比较各叶结点的值的大小，保留B（B为树每层保留最小叶结点参数值）个最小值叶结点，去掉其它叶结点。

4）直到有一个叶结点的值为1，否则对B个最小值叶结点转步聚2）。

5）从值为1的叶结点反向搜索到根即得到n的双基链。

如n=841232，B=2为例，其结果如图1所示。

从值为1的叶结点开始，沿着虚线得到：

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

即得双基链如下：

841232=21831+21431-21131+29+24

如n=841232，若设B＝4，则该算法可得到如下双基链：

841232=2738+2633-2532-24

图1 B为2时生成双基链的二叉树

4 树型方法的Delphi实现

4.1 二叉树结点结构

树结点的结构具体定义如下：

type

recordnode=record

data：integer； //整数 n

leftnode：pointer； //右结点

rightnode：pointer； //左结点

Bexp：byte； //存2次方值

Texp：byte； //存3次方值

End；

4.2 计算2或3次方过程

入口参数：数值data；次方数temp

出口参数：i为次方值。

procedure computeTexp（var data：integer；var i，temp：byte）； //计算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 对于任整数n构建二叉树过程

入口参数：pt为指向树结点的指针。

出口参数：二叉树。

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）；//调用计算2的次方

pt.Bexp：=i；//2的次方数

temp：=3；

computeTexp（pt.data，i，temp）；//调用计算3的次方

pt.Texp：=i； //3的次方数

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）； //创建左子树

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）； //创建右子树

end

else

pt：=nil；

end；

5 结语

本文主要研究双基数据系统（DBNS）基本理论和求解任意整数双基数表示的树型方法，最后在Delphi环境下实现了基于树型方法计算双基链。