摘要：小步—大步攻击算法是一个求解离散对数问题通用且高效的算法,但较大的存贮开销是它的一个明显不足。提出的改进算法使得存贮开销减少一半,并取消了求逆元操作,通过引入抗冲突的哈希函数,省略了表排序过程,并使查表时间降到常数级。性能分析表明,改进算法的时间和空间耗费明显降低,性能优于原算法。另外,还探讨了如何通过降低问题的规模来进一步缩短攻击算法的计算过程,并给出了一个简单易行的对离散对数进行奇偶筛选的方法。
关键词：离散对数问题;小步—大步攻击算法;成功停机;平方乘算法
中图分类号：TP309文献标识码：A
文章编号：1001-9081(2007)04-0843-03
很多密码技术的安全性都建立在离散对数问题的困难性上,如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]，但仍留有值得优化的余地。另一方面，空间复杂度较大一直是小步—大步算法的不足之处。
1离散对数问题
离散对数的求解虽是困难的，但其逆运算即指数运算，可以应用平方乘的方法有效地计算。若将指数用有符号的二进制数表示，使之具有较小的海明权重[7]，则可以进一步减少其中乘法的次数，从而提高运算速度。
2小步—大步攻击算法及分析
小步—大步(Baby—Step—Giant—Step)攻击算法有时也称为Shanks算法[4]，具体实现如下面的算法1所示。其中参数n，α，β的意义与定义1中的定义相同。
3改进算法
先给出改进后的算法描述,其中参数与算法1完全相同。
4改进算法的性能分析
同样以群乘法为基本运算单位，分析改进算法的时间和空间复杂性。
与算法1一样，在第1)步，要先预计算αm并缓存。虽时间复杂度仍为O(logm)，但在(1.2)步中将指数m采取具有较小海明权重[7]的表示方式，可以显著减少其中乘法的次数，从而可以平均提高大致11%的运算速度[2]。由于平方运算最快可以比两个不同整数的乘法运算快两倍[1]，所以这项措施的好处是非常明显的；同时在(1.3)步中采用多精度平方乘算法[1]，可进一步提高运算速度。
5两算法的对比
由上面的分析，可归纳出两个算法的主要不同之处在于：
1)存贮表的数目。算法1需要两个表，而算法2则只需1个,从而存贮器开销不同。
2)表元素的比较时机。算法1是两组数据(两张表)都计算完成后再进行比较，而算法2则是只需在第一张表完成的基础上即可开展比较工作。
5)表排序与查表时间。算法1需对两张表都排序，且查表时间与表的规模直接相关（为O(m)）。而算法2由于引入抗冲突的哈希函数，无须排序操作，且查表时间也降为O(1)。
6进一步的改进措施
改进后的小步—大步攻击算法较原算法而言进行了算法实现上的多项优化，但这仅是针对算法本身的优化，两种算法所面对的问题规模仍然是相同的。可以尝试通过降低问题的规模来进一步缩短攻击算法的计算过程。这一点对于比特位较长的素数p意义更加明显。
7结语
本文将改进后的小步—大步攻击算法与原算法的性能进行了对比分析，表明上述改进措施均是正确而行之有效的。如何减少存贮开销，尽量避免或减少求逆元运算，如何有效应用多精度算法，以及通过变换指数表现形式来加速幂运算速度等，都值得在日益广泛应用的密码系统和签名方案的实现过程中加以充分考虑和探讨。
努力提高攻击算法的运算效率只是一个方面的工作，延伸到如何降低算法的输入规模将是一件非常有意义的工作。本文仅讨论了离散对数的奇偶筛选问题，如何预测或确定离散对数中的其他多个特定比特位的数值值得进一步的深入研究。
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
推荐访问： 对数 离散 算法 改进 攻击
