一个改进的离散对数问题攻击算法

2007年4月

文章编号:1001-9081(2007)04-0843-03

计算机应用

ComputerApplications

Vo.l27No.4Apr.2007

一个改进的离散对数问题攻击算法

张海波,王小非,夏学知,黄友澎

(1.哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001;

2.武汉数字工程研究所,湖北武汉430074)

(zhanghb412@yahoo.com.cn)

摘 要:小步)大步攻击算法是一个求解离散对数问题通用且高效的算法,但较大的存贮开销是它的一个明显不足。提出的改进算法使得存贮开销减少一半,并取消了求逆元操作,通过引入抗冲突的哈希函数,省略了表排序过程,并使查表时间降到常数级。性能分析表明,改进算法的时间和空间耗费明显降低,性能优于原算法。另外,还探讨了如何通过降低问题的规模来进一步缩短攻击算法的计算过程,并给出了一个简单易行的对离散对数进行奇偶筛选的方法。

关键词:离散对数问题;小步)大步攻击算法;成功停机;平方乘算法中图分类号:TP309 文献标识码:A

1,2

1,2

2

1,2

Animprovedattackalgorithmfordiscretelogarithmproblem

ZHANGHa-ibo,WANGXiao-fei,XIAXue-zhi,HUANGYou-peng

1,2

1,2

2

1,2

(1.SchoolofComputerScienceandTechnology,HarbinEngineeringUniversity,HarbinHeilongjiang150001,China;

2.WuhanDigitalEngineeringInstitute,WuhanHubei430074,China)Abstract:Baby-step-giant-stepattackalgorithmisuniversallysuitabletosolvealldiscretelogarithmproblems,butitsrelativelylargerstoragecostisanobviousdefect.Animprovedattackalgorithmwhichcancutdownhalfofspacespendingand

canceltheinversing-computationonmultiplicativegroupwaspresented.Byusinghashfunction,thisnewalgorithmabolisheslis-tsortingprocessanddropsthetimecomplexityoflist-searchingintoO(1).Theperformanceanalysisshowsthatthenewalgorithmobviouslyreducesthetimeandspaceuse.Furthermore,howtoplaydowntheinputsizetoshortencomputationjourneyofattackalgorithmswasdiscussedandaneasywaytoparitysievefordiscretelogarithmwasgiven.

Keywords:DiscreteLogarithmProblem(DLP);baby-step-giant-stepattackalgorithm;successfullytermination;square-multiplicationalgorithm

很多密码技术的安全性都建立在离散对数问题的困难性

上,如Diffie-Hellman密钥协议[1],ElGamal密码及其签名方案,以及它们的变种等。Diffie-Hellman问题[2],模合数n乘群Z*n中的离散对数问题,以及n的因子分解问题,在密码学上存在一定的关联,它们的困难性存在着内在的等价性[1]。针对离散对数问题有许多攻击方法,目前已知的有穷举攻击,Pohlig-Hellman攻击[3],指数积分攻击[3],Pollard概率攻击[3],小步)大步攻击[2,4],袋鼠攻击[5]和生日攻击[6]等。这些攻击方法往往在某些特定场合尤其有效,如当p-1为形如2的幂次方[6],p-1的因数都较小[3]或p的位数较短时。小步)大步攻击算法则适合于包括椭圆曲线[2,3]在内的所有离散对数问题,是本文进行研究并加以改进的对象。

对于小步)大步攻击算法,在忽略对数因子的情况下,其时间复杂度为O(n),已接近于离散对数问题的任何通用算法的复杂性下界[6],但仍留有值得优化的余地。另一方面,空间复杂度较大一直是小步)大步算法的不足之处。

关。

证明

设A和C是阶为n的乘法群G的两个不同生成

元,且设BIG。若x=logAB,y=logCB,z=logAC,则有Ax=

y

B=C=(Az)C。从而有x=zymodn,logCB=logAB(logAC)-1

题称为离散对数问题(DiscreteLogarithmProblem,DLP)。

定义1 设(G,#)是乘法群,对于一个n阶元素AIG和元素BI,存在唯一的整数a,0[

a[

n-1,满足:

Aa=B,称a为A与B相关的离散对数,记为logAB。

密码学领域内的离散对数问题是困难的[2~4],即计算上不可行。这是许多密码技术的安全性之所在。下面的命题进一步阐明了离散对数问题保持安全性的一个性质。

命题1

离散对数问题的困难性与其生成元的选取无

modn。这表明任何计算以为A底的对数的算法,也可以用于计算以G的其他生成元C为底的对数。

对于群论,密码学上应用最广泛的有两类,一类是有限域Fq上的乘群F*q。如模素数p的乘群Z*,有限域F2m上的乘群pF2m,以及n为合数的乘群Z*另一类是定义在有限域上的椭n。圆曲线的点群。适用于乘群上的离散对数算法,只要稍作修改均可直接应用到基于椭圆曲线的离散对数问题,故本文侧重

*

1 离散对数问题

在密码学系统中,一般将求解数论中某个数的对数的问

收稿日期:2006-09-30;修订日期:2007-01-05

作者简介:张海波(1972-),男,湖北人,博士研究生,主要研究方向:密码学、信息安全; 王小非(1957-),男,湖北人,研究员,博士生导师,主要研究方向:网络、信息安全、并行计算; 夏学知(1966-),男,湖北人,研究员,博士,主要研究方向:网络与信息栅格、并行计算; 黄友澎(1963-),男,福建人,博士研究生,主要研究方向:数据融合、信息安全.

844

于讨论乘群上的离散对数。

计算机应用2007年

离散对数的求解虽是困难的,但其逆运算即指数运算,可以应用平方乘的方法有效地计算。若将指数用有符号的二进制数表示,使之具有较小的海明权重[7],则可以进一步减少其中乘法的次数,从而提高运算速度。

3 改进算法

先给出改进后的算法描述,其中参数与算法1完全相同。算法2 改进的小步)大步攻击算法Improved-Baby-Step-Giant-Step(n,A,B)

1)系统初始化

(1.1)sz1,uzB,L1zNul;l

(1.2)mz7nô,m转换成具有较小海明权重[7]的表示形式;

mm

(1.3)运用多精度平方乘[1]算法计算A,tzA;2)forjz1tom(2.1)szs@t;

(2.2)L1(h(s))z(j,s),其中h()是抗冲突的哈希函数3)foriz1tom

(3.1)uzu#A;

(3.2)若L1(h(u))=(j,y)XNULL,logABz(mj-i)modn,结束。

2 小步)大步攻击算法及分析

小步)大步(Baby-Step-Giant-Step)攻击算法有时也称为Shanks算法[4],具体实现如下面的算法1所示。其中参数n,A,B的意义与定义1中的定义相同。

算法1 小步)大步攻击算法[2]

Baby-Step-Giant-Step(n,A,B)1)mz7nô2)forjz0tom-1

mj

(2.1)计算A

mj

3)对m个有序对(j,A)关于第二个坐标排序,得到一个列表

L1

4)foriz0tom-1

(4.1)计算BA-i

-i5)对m个有序对(iBA)关于第二个坐标排序,得到一个列表

L2

6)找到(j,y)IL1和(i,y)IL2(即找到两个具有相同第二坐标的有序对)

7)logABz(mj+i)modn

命题3 算法2成功停机的充要条件是BI。

证明

mj

1)必要性。算法2成功停机,表明第(3.2)步有A=y=i(mj-i)BA,则B=A,因1[i,j[m,有mj-i\\0,又A是生成元,故BI。

2)充分性。BI,0[

logAB[n-1,m=7nô,故

0[logAB[n-1[m2-1。令1[j[m且logAB=mj-i,则易知i满足:1[i[m。也即当i,j满足1[i,j[m时,logAB可写成logAB=mj-i。A是生成元,有B=A(mj-i),即mjA=BAi,故算法2第(3.2)步必会成功,从而算法2会成功停机。

从命题3的证明过程可知,改进后的算法2是一个能返回正确结果的有效算法。

下面以群乘法为基本运算单位来分析该算法的时间和空间复杂性。

m

在第2)步,为了(2.1)步计算的快速,要先预计算A并缓存,平方乘算法是比较通用且非常有效的方法,比单纯的连乘算法提速显著,采用平方乘算法也需要O(logm);另外,第(2.1)步需执行m次,时间开销是O(m)。

在第3)步,若用快速排序算法,也得O(mlogm)。同样,第5)步的时间复杂度也为O(mlogm)。在这两步中,分别需O(m)的空间复杂度。

在第4)步,为了(4.1)步的快速计算,需先计算A-1并缓存,采用扩展的Euclidean算法,时间复杂度为O(logA)UO(logm);另外,第(4.1)步需执行m次,时间开销是O(m)。

4 改进算法的性能分析

同样以群乘法为基本运算单位,分析改进算法的时间和空间复杂性。

与算法1一样,在第1)步,要先预计算Am并缓存。虽时间复杂度仍为O(logm),但在(1.2)步中将指数m采取具有

[7]

较小海明权重的表示方式,可以显著减少其中乘法的次数,从而可以平均提高大致11%的运算速度[2]。由于平方运算最快可以比两个不同整数的乘法运算快两倍[1],所以这项措施的好处是非常明显的;同时在(1.3)步中采用多精度平方乘算法[1],可进一步提高运算速度。

在第(2.2)步,无须排序操作,只需通过抗冲突的哈希函数快速建立索引表,且仅需一张表L1,省略了第二张表L2,也即存贮空间减少了一半。

在第(3.2)步,哈希函数的引入使得查表时间降为O(1)。

随着计算能力的不断提升,目前要求素数p的取值一般都在1024bit或更长,故一次快速哈希函数的时间相对于一次两个1024bit大整数相乘的时间来说微不足道,可以近似不计。同时p的取值要求(1024bit或更长)也表明改进算法的时间和空间优势是比较显著的。

由于列表L1和L2已经排好序,第6)步的查找时间为O(m)。

综上所述,算法1的总的时间复杂度为O(mlogm),空间复杂度为O(m)。若忽略对数因子,时间和空间复杂度均为O(m)=O(n)。

进一步研究算法1可发现,小步)大步攻击算法能否正确地返回所求解的离散对数,关键在于第6步能否成功。通过下面的命题作进一步的阐述。

命题2 小步)大步攻击算法成功停机的充要条件是BI。

证明

mj

1)必要性。算法1成功停机,表明第6)步有A=y=BA-i,则B=A(mj+i),A是生成元,故BI。2)充分性。BI,可令B=Ax,则x=logAB,因AIG的阶为n,且m=7nô,有0[

logAB[n-1,故可令i=logAB

modm,从而可令logAB=mj+i,又logAB[n-1[m2-1=m(m-1)+m-1,故有0[i,j[m-1。由logAB=mj+i,A

mj是生成元,有B=A(mj+i),即A=BA-i,故第6)步必会成功,从

5 两算法的对比

由上面的分析,可归纳出两个算法的主要不同之处在于:

1)存贮表的数目。算法1需要两个表,而算法2则只需1个,从而存贮器开销不同。

2)表元素的比较时机。算法1是两组数据(两张表)都

而算法会成功停机。

第4期张海波等:一个改进的离散对数问题攻击算法 845

计算完成后再进行比较,而算法2则是只需在第一张表完成

的基础上即可开展比较工作。

3)求解成功时的条件和结果的计算公式。算法1求解成

mj

功时有A=y=BA-i,0[i,j[m-1,结果为logAB=(mj+i)modn。而算法2求解成功时则是Amj=y=BAi,1[i,j[m,结果为logAB=(mj-i)modn。

4)是否需要求解逆元。算法1需要求解逆元,而算法2则无需求解任何逆元。

5)表排序与查表时间。算法1需对两张表都排序,且查表时间与表的规模直接相关(为O(m))。而算法2由于引入抗冲突的哈希函数,无须排序操作,且查表时间也降为O(1)。

表1列出了改进算法与原算法的性能区别。

表1 改进算法与原算法的性能对比

比较项目

原算法

改进算法采用具有较小海明

m

预计算A

一个较易快速实现的措施就是对将要计算的logAB先进行奇偶筛选,这样可以将问题的规模降低约一半。该措施的有效性和奇偶筛选的实现方法由下面的命题4给出。其中n,A,B

*

的意义同定义1,且定义在模p的乘群Zp上。

n/2

命题4 若B=1modp,则logAB是偶数,否则是奇数。

证明 设x=logABmodn,则B=Axmodp。有(An/2)2=An=1modp,则An/2=?1modp。因A的阶为n,有An/2X1modp,故An/2=-1modp。从而Bn/2=Ax#n/2=(-1)xmodp。也即Bn/2=1modp时logAB是偶数,否则是奇数。

7 结语

本文将改进后的小步)大步攻击算法与原算法的性能进行了对比分析,表明上述改进措施均是正确而行之有效的。如何减少存贮开销,尽量避免或减少求逆元运算,如何有效应用多精度算法,以及通过变换指数表现形式来加速幂运算速度等,都值得在日益广泛应用的密码系统和签名方案的实现过程中加以充分考虑和探讨。

努力提高攻击算法的运算效率只是一个方面的工作,延伸到如何降低算法的输入规模将是一件非常有意义的工作。本文仅讨论了离散对数的奇偶筛选问题,如何预测或确定离散对数中的其他多个特定比特位的数值值得进一步的深入研究。参考文献:

[1] ALFREDJM,PAULCVO,SCOTTAV.Handbookofappliedcryp-tography[M].胡磊,王鹏,译.北京:电子工业出版社,2005.99-101,459-468,527-532.

[2] DOUGLASRS.Cryptographytheoryandpractice.Secondedition

[M].冯登国,译.北京:电子工业出版社,2003.193-227.[3]

JOHANNESB,DAMIANW.Discretelogarithms:recentprogress[A].InternationalConferenceonCodingTheory,CryptographyandRelatedAreas[C].Berlin:Springer-Verlag,2000.42-56.[4] ANDREWO.Discretelogarithms:thepastandthefuture[J].De-signs,Codes,andCryptography,2000,19(2/3):129-145.[5] CHRISS.Thediscretelogproblem[D].PhD.Thesis,Universityof

Toronto,2002.7-9.

[6] WADET,LAWRENCECW.Introductiontocryptographywithcod-ingtheory[M].邹红霞,许鹏文,李勇奇,译.北京:人民邮电出版社,2004.121-122,127-134.

[7] MUIRJA,STINSONDR.OnThelowhammingweightdiscretelog-arithmproblemfornonadjacentrepresentations[J].AAECC,2006,16(6):461-472.

采用平方乘算法

权重指数的多精度

平方乘算法,运算速度提高约11%

预计算A缓存

-1

采用扩展的Euclidean

算法,O(logA)UO(logm)*

m-1需存A和Am次群乘法

无

m

只需存A相同

表1元素计算时间表2元素计算时间表排序查表时间

需存贮的元素数目

m次群乘法两个表,每个表各O(mlogm)O(m)2m

平均(m+1)/2次群乘法**无O(1)m

注:*m=7nô,n为元素AIG的阶。**当查找成功时所需的平均计算时间=1m+1=次群乘法。

2m

E

m

i#

i=1

6 进一步的改进措施

改进后的小步)大步攻击算法较原算法而言进行了算法

实现上的多项优化,但这仅是针对算法本身的优化,两种算法所面对的问题规模仍然是相同的。可以尝试通过降低问题的规模来进一步缩短攻击算法的计算过程。这一点对于比特位较长的素数p意义更加明显。(上接第842页)

图2是语音信号隐藏秘密信息前后的波形图,图3是语音信号隐藏秘密信息前后的频谱图。从主观听觉测试结果表明,本文所提算法获得的携密语音仅仅比原始明文略多一点噪声,并不影响整体听觉效果。在长度为4.109s(样点总数约为9.1@104)的语音数据中嵌入了29bit的信息。从图中可以看出秘密信息嵌入后没有引起语音信号质量大的变化。

大量仿真试验结果表明,算法对GSM中的RPE2LTP编码有很强的鲁棒性。算法简单易行并且是基于盲检测的,具有很大的实用性。本文提出的基于语音的信息隐藏方法可以广泛运用于移动通信网条件下信息安全传输、数字水印等领域。参考文献:

[1] 陈力,谢玉琼.一种基于分形维数的自适应语音信息隐藏算法

[J].武汉大学学报,2003,49(3):313-317.

[2] 郑见灵,谭月辉,焦桂芝,等.音频文件中信息隐藏技术研究及其

实现[J].河北工业科技,2006,23(2):76-79.

[3] WUZJ,YANGW,YANGYX.ABS-basedspeechinformationhid-ingapproach[J].ElectronicsLetters,2003,39(22):1617-1619.[4] 吴志军,钮心忻,杨义先,等.语音隐藏的研究及实现[J].通信学

报,2002,23(8):99-104.

5 结语

本文基于一般语音编码对相邻段语音能量比改变不大这

一特性,提出了一种能够在GSM移动通信网络中使用的信息隐藏算法能量比调整(ABSEnergyRatioAdjust)算法。算法采用了ABS技术,在隐藏算法中根据输入明文语音实时的调整相邻段能量比,使得隐藏效果和解码效果都达到最佳值。